15-09 — Convexity

Phase: Numerical Methods for ML | Subject: 15-09 Prerequisites: 15-01-floating-point-arithmetic.md, 15-04-backpropagation-implementation.md, 15-05-numerical-linear-algebra-ml.md, 04-03-derivatives.md, 04-08-optimization.md Next subject: 15-10-gradient-descent.md

Learning Objectives

By the end of this subject, you will be able to:

1. Define convex sets and convex functions and test for convexity using first- and second-order conditions
2. State and apply Jensen's inequality and explain its significance in ML (e.g., EM algorithm, variational inference)
3. Prove that any local minimum of a convex function is a global minimum
4. Identify common convex and non-convex loss functions used in ML
5. Explain why non-convex deep learning optimization often works despite the lack of global guarantees

Core Content

Convex Sets

A set $C \subseteq \mathbb{R}^n$ is convex if for any $\mathbf{x}, \mathbf{y} \in C$ and any $\theta \in [0, 1]$:

$$\theta \mathbf{x} + (1 - \theta)\mathbf{y} \in C$$

Geometrically: the line segment between any two points in $C$ lies entirely in $C$.

Examples of convex sets: - $\mathbb{R}^n$, any affine subspace - Halfspaces: ${\mathbf{x} : \mathbf{a}^T \mathbf{x} \leq b}$ - Norm balls: ${\mathbf{x} : |\mathbf{x}|_p \leq r}$ for $p \geq 1$ - Polyhedra: ${\mathbf{x} : A\mathbf{x} \leq \mathbf{b}, C\mathbf{x} = \mathbf{d}}$ - Positive semidefinite cone: ${X \in \mathbb{S}^n : X \succeq 0}$

Operations preserving convexity: Intersection of convex sets is convex. Affine images and pre-images preserve convexity. Cartesian product of convex sets is convex.

⚠️ CRITICAL — The feasible set of a convex optimization problem must be a convex set. This means constraints must define convex regions: $g_i(\mathbf{x}) \leq 0$ where each $g_i$ is a convex function (i.e., sublevel sets of convex functions), and $h_j(\mathbf{x}) = 0$ where each $h_j$ is affine (equality constraints must be linear).

Convex Functions

A function $f : \mathbb{R}^n \to \mathbb{R}$ is convex if its domain is convex and for all $\mathbf{x}, \mathbf{y} \in \operatorname{dom}(f)$ and $\theta \in [0, 1]$:

$$f(\theta \mathbf{x} + (1 - \theta)\mathbf{y}) \leq \theta f(\mathbf{x}) + (1 - \theta) f(\mathbf{y})$$

Geometrically: the function lies below the chord connecting any two points. A function is strictly convex if the inequality is strict for $\mathbf{x} \neq \mathbf{y}$ and $\theta \in (0, 1)$. A function $f$ is concave if $-f$ is convex.

First-order condition (for differentiable $f$):

$$f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y} - \mathbf{x}) \quad \forall \mathbf{x}, \mathbf{y}$$

The first-order Taylor approximation is a global under-estimator of a convex function. This is the most practically useful characterization.

Second-order condition (for twice-differentiable $f$):

$$\nabla^2 f(\mathbf{x}) \succeq 0 \quad \forall \mathbf{x}$$

The Hessian is positive semidefinite everywhere. For strict convexity, $\nabla^2 f(\mathbf{x}) \succ 0$ is sufficient but not necessary (e.g., $f(x) = x^4$ is strictly convex but $\nabla^2 f(0) = 0$).

Jensen's Inequality

For a convex function $f$ and random variable $X$:

$$f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$$

This is the probabilistic generalization of the convexity definition. For concave $f$, the inequality reverses.

In ML, Jensen's inequality is the engine behind:

1. EM Algorithm: The E-step constructs a lower bound on the log-likelihood using Jensen's inequality: $$\log p(\mathbf{x}; \theta) = \log \sum_z p(\mathbf{x}, z; \theta) = \log \mathbb{E}{q(z)}\left[\frac{p(\mathbf{x}, z; \theta)}{q(z)}\right] \geq \mathbb{E}{q(z)}\left[\log \frac{p(\mathbf{x}, z; \theta)}{q(z)}\right]$$ where the inequality follows from concavity of $\log$.

2. Variational Inference: The ELBO (Evidence Lower BOund) is derived via Jensen's inequality: $$\log p(\mathbf{x}) = \log \int p(\mathbf{x}, \mathbf{z}) d\mathbf{z} \geq \mathbb{E}_{q(\mathbf{z})}[\log p(\mathbf{x}, \mathbf{z}) - \log q(\mathbf{z})]$$

3. Information Theory: The non-negativity of KL divergence follows from Jensen's: $$D_{\text{KL}}(p | q) = \mathbb{E}_p\left[-\log \frac{q}{p}\right] \geq -\log \mathbb{E}_p\left[\frac{q}{p}\right] = -\log 1 = 0$$

Why Convexity Matters for Optimization

Theorem: For a convex function, any local minimum is a global minimum.

Proof sketch: Suppose $\mathbf{x}^$ is a local minimum but not global. Then $\exists \mathbf{y}$ with $f(\mathbf{y}) < f(\mathbf{x}^)$. By convexity, for small $\theta > 0$: $f(\theta \mathbf{y} + (1-\theta)\mathbf{x}^) \leq \theta f(\mathbf{y}) + (1-\theta)f(\mathbf{x}^) < f(\mathbf{x}^)$. As $\theta \to 0$, the convex combination approaches $\mathbf{x}^$, contradicting local optimality. $\square$

Theorem: For a strictly convex function, the global minimum (if it exists) is unique.

This is why convex optimization is "easy" — we never get stuck in bad local minima. Gradient descent, Newton's method, or any reasonable algorithm that descends will find the global optimum.

Convexity in ML Loss Functions

Convex losses (nice to optimize):

Non-convex losses (the reality of deep learning):

⚠️ CRITICAL — Deep neural network loss landscapes are non-convex, yet SGD works remarkably well. This is an active research area. Key insights: (a) In overparameterized networks, most local minima are near-global in quality; (b) SGD noise helps escape bad saddle points; (c) The loss landscape has many "flat" minima that generalize well vs "sharp" minima that don't.

Convexity-Preserving Operations

To verify whether a complex function is convex, build it from known convex functions using these operations:

1. Nonnegative weighted sum: If $f_i$ are convex and $w_i \geq 0$, then $\sum w_i f_i$ is convex
2. Affine composition: If $f$ is convex, $f(A\mathbf{x} + \mathbf{b})$ is convex
3. Pointwise maximum: If $f_i$ are convex, $\max_i f_i(\mathbf{x})$ is convex (used in hinge loss, max-pooling)
4. Composition with scalar convex nondecreasing function: If $g$ is convex and nondecreasing and $h$ is convex, then $g \circ h$ is convex
5. Perspective: $t f(\mathbf{x}/t)$ is convex in $(\mathbf{x}, t)$ for $t > 0$ if $f$ is convex

Example: Prove the logistic loss $\ell(\mathbf{w}) = \log(1 + e^{-y \mathbf{w}^T \mathbf{x}})$ is convex in $\mathbf{w}$.

• $z \mapsto e^z$ is convex ✓
• $z \mapsto -y \mathbf{w}^T \mathbf{x}$ is affine in $\mathbf{w}$ ✓
• Composition: $e^{-y \mathbf{w}^T \mathbf{x}}$ is convex (convex nondecreasing $e^z$ composed with affine)
• $z \mapsto 1+z$ is affine (convex) ✓
• $z \mapsto \log(z)$ is concave and nondecreasing... This needs care.

Better approach: The Hessian $\nabla^2 \ell(\mathbf{w}) = \frac{e^{-y \mathbf{w}^T \mathbf{x}}}{(1 + e^{-y \mathbf{w}^T \mathbf{x}})^2} \mathbf{x}\mathbf{x}^T \succeq 0$ since $\mathbf{x}\mathbf{x}^T \succeq 0$ and the scalar coefficient is nonnegative. QED by second-order condition.

Strong Convexity

A function $f$ is $\mu$-strongly convex if $f(\mathbf{x}) - \frac{\mu}{2}|\mathbf{x}|^2$ is convex. Equivalently:

$$f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y} - \mathbf{x}) + \frac{\mu}{2}|\mathbf{y} - \mathbf{x}|^2$$

Or: $\nabla^2 f(\mathbf{x}) \succeq \mu I$ for all $\mathbf{x}$ (the Hessian eigenvalues are all $\geq \mu$).

Strong convexity guarantees: - Unique global minimum - Linear convergence rate for gradient descent: $f(\mathbf{x}_k) - f^ \leq (1 - \mu/L)^k (f(\mathbf{x}_0) - f^)$ where $L$ is the Lipschitz constant of $\nabla f$ - The condition number $\kappa = L/\mu$ governs convergence speed

L2 regularization $\frac{\lambda}{2}|\mathbf{w}|^2$ makes any convex loss $\lambda$-strongly convex — this is why weight decay accelerates convergence.

Key Terms

• Concave function
• Convex function
• Convex set
• ELBO (Evidence Lower Bound)
• Epigraph
• Jensen's inequality
• Lipschitz gradient
• Positive semidefinite (PSD)
• Saddle point
• Strong convexity

Worked Examples

Example 1: Verifying Convexity via Hessian

Determine whether $f(x, y) = x^2 + 3y^2 + 2xy$ is convex. If so, is it strictly convex?

Solution: Gradient: $\nabla f = (2x + 2y, \; 6y + 2x)^T$.

Hessian: $\nabla^2 f = \begin{pmatrix} 2 & 2 \ 2 & 6 \end{pmatrix}$.

Check if PSD: eigenvalues of $H$ satisfy $\det(H - \lambda I) = 0$: $(2-\lambda)(6-\lambda) - 4 = \lambda^2 - 8\lambda + 8 = 0$. $\lambda = 4 \pm \sqrt{8} = 4 \pm 2\sqrt{2}$. $\lambda_1 = 4 + 2\sqrt{2} \approx 6.828 > 0$, $\lambda_2 = 4 - 2\sqrt{2} \approx 1.172 > 0$.

Both eigenvalues are strictly positive → $H \succ 0$ everywhere → $f$ is strictly convex. The unique global minimum is at $\nabla f = \mathbf{0}$:

$2x + 2y = 0$, $6y + 2x = 0$. From first: $y = -x$. Substitute: $6(-x) + 2x = -4x = 0 \implies x = 0, y = 0$.

$f(0, 0) = 0$ is the unique global minimum.

Example 2: Jensen's Inequality Bounding

For $X \sim \text{Uniform}(0, 1)$, use Jensen's inequality to bound $\mathbb{E}[-\ln X]$. Compare with the exact value.

Solution: $f(x) = -\ln x$ is convex on $(0, \infty)$ (check: $f''(x) = 1/x^2 > 0$).

By Jensen: $-\ln(\mathbb{E}[X]) \leq \mathbb{E}[-\ln X]$.

$\mathbb{E}[X] = 1/2$, so $-\ln(1/2) = \ln 2 \approx 0.6931$ is a lower bound.

Exact computation: $\mathbb{E}[-\ln X] = \int_0^1 (-\ln x) \cdot 1 \, dx = [-(x\ln x - x)]_0^1$.

At $x=0$: $\lim_{x \to 0^+} (x\ln x - x) = 0$ (using L'Hôpital). At $x=1$: $-(1 \cdot 0 - 1) = 1$.

So $\mathbb{E}[-\ln X] = 1$.

Jensen's bound: $\ln 2 \approx 0.693 \leq 1 = \mathbb{E}[-\ln X]$. The gap $1 - \ln 2 \approx 0.307$ is the "Jensen gap" — large because $-\ln x$ is highly curved on $[0, 1]$.

Example 3: Strong Convexity and Convergence Rate

Consider $f(x) = \frac{1}{2}x^2$ ($\mu=1$ strongly convex with $L=1$, so $\kappa=1$) vs $f(x) = \frac{1}{200}x^2$ ($\mu=1/100$, $L=1/100$, $\kappa=1$). Both have $\kappa=1$. Now consider $f(x) = \frac{1}{2}x^2 + \frac{99}{2}(x-1)^2$. Compute $\mu$, $L$, $\kappa$, and interpret.

Solution: $f(x) = \frac{1}{2}x^2 + \frac{99}{2}(x^2 - 2x + 1) = (\frac{1}{2} + \frac{99}{2})x^2 - 99x + \frac{99}{2} = 50x^2 - 99x + \frac{99}{2}$.

$f'(x) = 100x - 99$, $f''(x) = 100$.

So $f''(x) = 100$ everywhere → $L = 100$, $\mu = 100$, $\kappa = L/\mu = 1$.

For gradient descent with step size $\alpha = 1/L = 1/100$: $x_{k+1} = x_k - \frac{1}{100}(100x_k - 99) = x_k - x_k + 0.99 = 0.99$.

It converges in one step! This is the ideal $\kappa=1$ case — gradient descent converges instantly.

Now consider $g(x) = \frac{1}{2}(x^2 + 100(y-1)^2)$. Hessian: $\nabla^2 g = \begin{pmatrix} 1 & 0 \ 0 & 100 \end{pmatrix}$. $L = 100$, $\mu = 1$, $\kappa = 100$.

The convergence rate is $1 - 1/100 = 0.99$ per iteration. To reduce error by factor $10^{-3}$: need $k$ such that $0.99^k \leq 0.001$, so $k \approx \ln(1000)/\ln(1/0.99) \approx 688$ iterations.

This illustrates the fundamental role of condition number: even for a simple quadratic, poor conditioning ($\kappa \gg 1$) makes gradient descent slow.

Quiz

Q1: What does the concept of First-order condition primarily refer to in this subject?

A) A computational error related to First-order condition B) The definition and application of First-order condition C) A historical anecdote about First-order condition D) A visual representation of First-order condition

Correct: B)

• If you chose A: This is incorrect. First-order condition is defined as: the definition and application of first-order condition. The other options describe different aspects that are not the primary focus.
• If you chose B: First-order condition is defined as: the definition and application of first-order condition. The other options describe different aspects that are not the primary focus. Correct!
• If you chose C: This is incorrect. First-order condition is defined as: the definition and application of first-order condition. The other options describe different aspects that are not the primary focus.
• If you chose D: This is incorrect. First-order condition is defined as: the definition and application of first-order condition. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) The inverse operation of the formula in question B) An unrelated formula from a different topic C) C \subseteq \mathbb{R}^n D) A simplified version of C \subseteq \mathbb{R}^n...

Correct: C)

• If you chose A: This is incorrect. The formula C \subseteq \mathbb{R}^n is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: This is incorrect. The formula C \subseteq \mathbb{R}^n is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: The formula C \subseteq \mathbb{R}^n is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose D: This is incorrect. The formula C \subseteq \mathbb{R}^n is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Second-order condition?

A) It is primarily a historical notation system B) It is used only in advanced research contexts C) It is used to second-order condition in mathematical analysis D) It replaces all other methods in this domain

Correct: C)

• If you chose A: This is incorrect. Second-order condition serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: This is incorrect. Second-order condition serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose C: Second-order condition serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose D: This is incorrect. Second-order condition serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Concave function is TRUE?

A) Concave function is mentioned only as a historical footnote B) Concave function is not related to this subject C) Concave function is a fundamental concept covered in this subject D) Concave function is an advanced topic beyond this subject's scope

Correct: C)

• If you chose A: This is incorrect. Concave function is a fundamental concept covered in this subject. This subject covers Concave function as part of its core content.
• If you chose B: This is incorrect. Concave function is a fundamental concept covered in this subject. This subject covers Concave function as part of its core content.
• If you chose C: Concave function is a fundamental concept covered in this subject. This subject covers Concave function as part of its core content. Correct!
• If you chose D: This is incorrect. Concave function is a fundamental concept covered in this subject. This subject covers Concave function as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) A different result from a common mistake C) An unrelated numerical value D) Jensen's Inequality Bounding

Correct: D)

• If you chose A: This is incorrect. The worked examples show that the result is Jensen's Inequality Bounding. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is Jensen's Inequality Bounding. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is Jensen's Inequality Bounding. The other options represent common errors.
• If you chose D: The worked examples show that the result is Jensen's Inequality Bounding. The other options represent common errors. Correct!

Q6: How are Concave function and Convex function related?

A) Concave function and Convex function are completely unrelated topics B) Concave function and Convex function are closely related concepts C) Concave function is the inverse of Convex function D) Concave function is a special case of Convex function

Correct: B)

• If you chose A: This is incorrect. Both Concave function and Convex function are covered in this subject as interconnected topics.
• If you chose B: Both Concave function and Convex function are covered in this subject as interconnected topics. Correct!
• If you chose C: This is incorrect. Both Concave function and Convex function are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Concave function and Convex function are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Convex set?

A) Convex set has no common misconceptions B) The main error with Convex set is using it when it is not needed C) A common mistake is confusing Convex set with a similar concept D) Convex set is always computed the same way in all contexts

Correct: C)

• If you chose A: This is incorrect. Students often confuse Convex set with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Convex set with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: Students often confuse Convex set with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose D: This is incorrect. Students often confuse Convex set with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply ELBO (Evidence Lower Bound)?

A) ELBO (Evidence Lower Bound) is not practically useful B) Use ELBO (Evidence Lower Bound) only in pure mathematics contexts C) Avoid ELBO (Evidence Lower Bound) unless explicitly instructed D) Apply ELBO (Evidence Lower Bound) to solve problems in this subject's domain

Correct: D)

• If you chose A: This is incorrect. ELBO (Evidence Lower Bound) is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: This is incorrect. ELBO (Evidence Lower Bound) is a practical tool used throughout this subject to solve relevant problems.
• If you chose C: This is incorrect. ELBO (Evidence Lower Bound) is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: ELBO (Evidence Lower Bound) is a practical tool used throughout this subject to solve relevant problems. Correct!

Practice Problems

1. Prove that the sum of convex functions is convex. Does the product of convex functions need to be convex?
   

   Click for answer

   Let $f_1, f_2$ be convex. For any $\mathbf{x}, \mathbf{y}$ and $\theta \in [0,1]$: $(f_1+f_2)(\theta \mathbf{x} + (1-\theta)\mathbf{y}) = f_1(\theta \mathbf{x} + (1-\theta)\mathbf{y}) + f_2(\theta \mathbf{x} + (1-\theta)\mathbf{y})$ $\leq [\theta f_1(\mathbf{x}) + (1-\theta)f_1(\mathbf{y})] + [\theta f_2(\mathbf{x}) + (1-\theta)f_2(\mathbf{y})]$ $= \theta(f_1+f_2)(\mathbf{x}) + (1-\theta)(f_1+f_2)(\mathbf{y})$. ✓ Product is NOT generally convex. Counterexample: $f_1(x) = x^2$, $f_2(x) = (x-1)^2$, both convex. But $f_1(x)f_2(x) = x^2(x-1)^2$ has second derivative $2(6x^2 - 6x + 1)$ which is negative for $x \in ((3-\sqrt{3})/6, (3+\sqrt{3})/6) \approx (0.21, 0.79)$.

2. Use the second-order condition to prove that the softmax function composed with cross-entropy (log-softmax) is convex in the logits.
   

   Click for answer

   Let $\mathbf{z} \in \mathbb{R}^K$ be logits, $y \in \{1,\ldots,K\}$ be the true class. Loss: $\ell(\mathbf{z}) = -\log\left(\frac{e^{z_y}}{\sum_j e^{z_j}}\right) = -z_y + \log\sum_j e^{z_j}$. Gradient: $\frac{\partial \ell}{\partial z_i} = -\delta_{iy} + \frac{e^{z_i}}{\sum_j e^{z_j}} = \hat{p}_i - \delta_{iy}$ where $\hat{p} = \operatorname{softmax}(\mathbf{z})$. Hessian: $\frac{\partial^2 \ell}{\partial z_i \partial z_j} = \hat{p}_i \delta_{ij} - \hat{p}_i \hat{p}_j$, i.e., $\nabla^2 \ell = \operatorname{diag}(\hat{\mathbf{p}}) - \hat{\mathbf{p}}\hat{\mathbf{p}}^T$. For any $\mathbf{v}$: $\mathbf{v}^T \nabla^2 \ell \mathbf{v} = \sum_i \hat{p}_i v_i^2 - (\sum_i \hat{p}_i v_i)^2 = \operatorname{Var}_{\hat{\mathbf{p}}}(\mathbf{v}) \geq 0$. This is the variance of $\mathbf{v}$ under the discrete distribution $\hat{\mathbf{p}}$, which is always nonnegative. So $\nabla^2 \ell \succeq 0$ — the loss is convex in $\mathbf{z}$.

3. The function $f(x) = \max(x, 0)$ (ReLU) is convex. Show this using Jensen's inequality directly (not the second-order test).
   

   Click for answer

   Need to show: $\max(\theta x + (1-\theta)y, 0) \leq \theta \max(x, 0) + (1-\theta)\max(y, 0)$. Case 1: $\theta x + (1-\theta)y \leq 0$ → LHS $= 0 \leq$ RHS (RHS is nonnegative). ✓ Case 2: $\theta x + (1-\theta)y > 0$ → LHS $= \theta x + (1-\theta)y \leq \theta \max(x, 0) + (1-\theta)\max(y, 0)$ since $x \leq \max(x, 0)$ and $y \leq \max(y, 0)$. ✓ Thus ReLU is convex. ReLU is also nondecreasing — this combination makes it a valid activation for convexity-preserving composition.

4. For a $\mu$-strongly convex function $f$, prove that gradient descent with step size $\alpha = 1/L$ (where $L$ is the Lipschitz constant of $\nabla f$) satisfies $|\mathbf{x}_{k+1} - \mathbf{x}^|^2 \leq (1 - \mu/L)|\mathbf{x}_k - \mathbf{x}^|^2$.
   

   Click for answer

   Gradient descent: $\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)$. With $\alpha = 1/L$: $\|\mathbf{x}_{k+1} - \mathbf{x}^*\|^2 = \|\mathbf{x}_k - \mathbf{x}^* - \frac{1}{L}\nabla f(\mathbf{x}_k)\|^2$ $= \|\mathbf{x}_k - \mathbf{x}^*\|^2 - \frac{2}{L}\nabla f(\mathbf{x}_k)^T(\mathbf{x}_k - \mathbf{x}^*) + \frac{1}{L^2}\|\nabla f(\mathbf{x}_k)\|^2$. By $\mu$-strong convexity: $\nabla f(\mathbf{x}_k)^T(\mathbf{x}_k - \mathbf{x}^*) \geq f(\mathbf{x}_k) - f(\mathbf{x}^*) + \frac{\mu}{2}\|\mathbf{x}_k - \mathbf{x}^*\|^2$. By $L$-smoothness (co-coercivity): $\|\nabla f(\mathbf{x}_k)\|^2 \leq 2L(f(\mathbf{x}_k) - f(\mathbf{x}^*))$. Substituting: $\|\mathbf{x}_{k+1} - \mathbf{x}^*\|^2 \leq \|\mathbf{x}_k - \mathbf{x}^*\|^2 - \frac{2}{L}(f(\mathbf{x}_k) - f^* + \frac{\mu}{2}\|\mathbf{x}_k - \mathbf{x}^*\|^2) + \frac{2}{L}(f(\mathbf{x}_k) - f^*)$ $= (1 - \frac{\mu}{L})\|\mathbf{x}_k - \mathbf{x}^*\|^2$. ✓ This linear convergence is the hallmark of strongly convex optimization.

5. Prove that $\mathbb{E}[X^2] \geq (\mathbb{E}[X])^2$ (variance is nonnegative) using Jensen's inequality.
   

   Click for answer

   $f(x) = x^2$ is convex ($f''(x) = 2 > 0$). By Jensen: $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$, i.e., $(\mathbb{E}[X])^2 \leq \mathbb{E}[X^2]$. Rearranging: $\operatorname{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2 \geq 0$. Jensen's inequality directly proves the non-negativity of variance. The same argument shows $\mathbb{E}[|X|] \geq |\mathbb{E}[X]|$ (since $|\cdot|$ is convex) and $\mathbb{E}[1/X] \geq 1/\mathbb{E}[X]$ for positive $X$ (since $1/x$ is convex for $x > 0$).

Summary

Key takeaways:

• A set $C$ is convex if line segments between any two points in $C$ stay in $C$; convex functions satisfy $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$
• First-order condition: $\nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x})$ is a global under-estimator; second-order: $\nabla^2 f(\mathbf{x}) \succeq 0$ everywhere
• Jensen's inequality $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$ powers the EM algorithm, variational inference, and information-theoretic bounds
• For convex optimization: every local minimum is global; strictly convex functions have unique minima; strong convexity gives linear convergence rates
• Convex ML losses (MSE, cross-entropy, hinge) are well-behaved; neural network losses are non-convex but overparameterization and SGD noise help find good solutions
• Strong convexity parameter $\mu$ and Lipschitz constant $L$ determine convergence speed; condition number $\kappa = L/\mu$ is the key figure of merit
• Convexity is preserved by nonnegative weighted sums, affine composition, and pointwise maximization — use these to verify complex loss functions

Pitfalls

• Confusing convex sets with convex functions: A set being convex does not imply a function defined on it is convex, and vice versa. The set ${x : f(x) \leq c}$ (sublevel set) is convex if $f$ is convex, but the converse is false — quasiconvex functions have convex sublevel sets but are not necessarily convex. Always check the function definition, not just the domain geometry.
• Checking only the second-order condition for non-differentiable functions: The Hessian test $\nabla^2 f \succeq 0$ only applies to twice-differentiable functions. For non-differentiable functions (e.g., ReLU, hinge loss, $\ell_1$ norm), use the definition $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$ directly, or check convexity-preserving composition rules. Many ML loss functions are non-differentiable but still convex.
• Reversing Jensen's inequality for concave functions: Jensen's states $f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]$ for convex $f$, but the inequality reverses for concave $f$: $f(\mathbb{E}[X]) \geq \mathbb{E}[f(X)]$. A common mistake in derivations (e.g., EM algorithm, variational inference, KL divergence) is forgetting which direction the inequality goes. Always pause to identify whether the function is convex or concave before applying Jensen's.
• Assuming a neural network loss is convex because the per-layer operations are "simple": MSE is convex in linear model weights, but the composition $f(\mathbf{x}; W_1, W_2) = W_2 \sigma(W_1 \mathbf{x})$ is non-convex in $(W_1, W_2)$ jointly — composition breaks convexity. Even ReLU (a convex activation) in a multi-layer network produces a non-convex loss landscape. Convexity is not preserved through nonlinear compositions.
• Confusing strong convexity with strict convexity: Strict convexity ($f(y) > f(x) + \nabla f(x)^T(y-x)$ for $x \neq y$) guarantees at most one minimum but does NOT guarantee a convergence rate for gradient descent. Strong convexity ($\nabla^2 f \succeq \mu I$, $\mu > 0$) gives both uniqueness AND linear convergence $O((1-\mu/L)^k)$. Weight decay makes objectives strongly convex; without it, even a strictly convex function can converge arbitrarily slowly.

Next Steps

Next up: 15-10-gradient-descent.md — gradient descent variants (batch, stochastic, mini-batch), convergence analysis, learning rate schedules, and modern optimizers (momentum, Adam).