Convexity, smoothness and the condition number

Before this lesson: lesson 01 (gradient descent and the narrow valley); the Hessian and Taylor's theorem (calculus 03); eigenvalues of symmetric matrices and the Rayleigh quotient (linear algebra 06); positive semidefinite matrices and the order $A \preceq B$ (linear algebra 07). Time: about 75 minutes, plus the notebook.

---

Why this matters #

Most convergence rates in this track depend on three numbers: the largest curvature $L$, the smallest curvature $\mu$, and their ratio $\kappa = L/\mu$. For each digit of accuracy, gradient descent needs a number of steps proportional to $\kappa$ (lesson 03); momentum needs a number proportional to $\sqrt\kappa$ (lesson 04). Convexity turns "the gradient is zero" into "this is the global minimum", which is why linear models are easy to train and to analyse. A neural-network loss is not convex, but near a minimum the Hessian still plays the role of $L$ and $\mu$: its largest eigenvalue limits the learning rate, and preconditioners (feature scaling, Adam, Shampoo, Muon) try to make the effective $\kappa$ smaller. Discretized differential equations have a huge $\kappa$, one reason why physics-informed losses are hard to train.

1. Predict first #

2. The picture #

Convex: chords above, tangents below #

A function of one variable is convex when the segment between any two points of its graph (a chord) lies on or above the graph. For a differentiable function this is the same as: every tangent line lies on or below the graph. For a twice-differentiable function it is the same as $f'' \ge 0$ everywhere: the slope never decreases.

Interactive figure: loading…

Two parabolas around the graph #

Suppose $\mu \le f''(x) \le L$ for all $x$, with $\mu > 0$. Pick any point $x$. Taylor's theorem puts the whole graph between two parabolas that touch it at $x$:

The first line is an upper parabola with curvature $L$, the second a lower parabola with curvature $\mu$. The upper parabola ("$f$ curves up at most as fast as $L$") is $L$-smoothness. The lower one ("$f$ curves up at least as fast as $\mu$") is $\mu$-strong convexity. The important word is every: the two parabolas must hold around every point $x$, not only at the minimum.

Interactive figure: loading…

Two dimensions: the condition number is the shape of the valley #

Take the quadratic $f(x) = \tfrac12(x_1^2 + 100\,x_2^2) = \tfrac12 x^\top A x$ with $A = \operatorname{diag}(1, 100)$. Its curvature is 1 along $x_1$ and 100 along $x_2$, so $\mu = 1$, $L = 100$ and $\kappa = 100$. The level sets are ellipses with axis ratio $\sqrt{\kappa} = 10$: a long, narrow valley. As in lesson 01, gradient descent must use steps small enough for the steep direction ($\eta < 2/L$), and then it crawls along the flat one. For a general quadratic, $L$ and $\mu$ are the largest and smallest eigenvalues of $A$, and the valley points along the eigenvectors.

Interactive figure: loading…

3. Definitions and main results #

Convex sets and convex functions #

A set $C \subseteq \R^d$ is convex if, for all $x, y \in C$ and $\theta \in [0, 1]$, the point $\theta x + (1 - \theta) y$ is in $C$: the segment between two points of $C$ stays in $C$. Examples: balls, half-spaces $\{x : a^\top x \le b\}$, the positive semidefinite matrices, the probability simplex. The intersection of convex sets is convex.

A function $f$ is convex if its domain is convex and, for all $x, y$ in it and $\theta \in [0, 1]$,

The right side is the chord. $f$ is strictly convex if the inequality is strict for $x \ne y$ and $\theta \in (0, 1)$.

Theorem 1 (local = global). If $f$ is convex, every local minimum is a global minimum, and the set of minimizers is convex.

Proof.

1. Let $x$ be a local minimum: there is $r > 0$ with $f(x) \le f(z)$ whenever $\|z - x\| \le r$. Suppose some $y$ has $f(y) < f(x)$.
2. For $\theta \in (0, 1]$ let $z_\theta = (1 - \theta) x + \theta y$. Convexity gives $f(z_\theta) \le (1 - \theta) f(x) + \theta f(y) < f(x)$.
3. For $\theta \le r/\|y - x\|$, the point $z_\theta$ is inside the ball around $x$ and has a smaller value than $x$. This contradicts step 1, so no such $y$ exists.
4. If $x$ and $y$ are both minimizers with value $f^\star$, then $f(\theta x + (1 - \theta) y) \le \theta f^\star + (1 - \theta) f^\star = f^\star$: the whole segment consists of minimizers. $\blacksquare$

The first-order condition: tangents lie below #

Theorem 2 (first-order condition). Let $f$ be differentiable on an open convex set $D$. Then $f$ is convex if and only if

for all $x, y \in D$. The right side is the tangent plane at $x$ (in 1D, the tangent line).

Proof.

1. (⇒) Fix $x, y$ and $t \in (0, 1]$. Convexity with $\theta = 1 - t$ gives $f(x + t(y - x)) \le (1 - t) f(x) + t f(y)$.
2. Subtract $f(x)$ and divide by $t$: $\dfrac{f(x + t(y - x)) - f(x)}{t} \le f(y) - f(x)$.
3. Let $t \to 0^+$. The left side tends to the directional derivative $\nabla f(x)^\top (y - x)$.
4. (⇐) Take $\theta \in [0, 1]$ and $z = \theta x + (1 - \theta) y$. Use the inequality at the point $z$ twice: $f(x) \ge f(z) + \nabla f(z)^\top (x - z)$ and $f(y) \ge f(z) + \nabla f(z)^\top (y - z)$.
5. Multiply the first by $\theta$, the second by $1 - \theta$, and add. The gradient terms cancel, because $\theta(x - z) + (1 - \theta)(y - z) = \theta x + (1 - \theta) y - z = 0$. What is left is $\theta f(x) + (1 - \theta) f(y) \ge f(z)$. $\blacksquare$

Consequence. If $f$ is convex and differentiable and $\nabla f(x^\star) = 0$, then $f(y) \ge f(x^\star) + 0$ for every $y$: a stationary point is a global minimizer. For a convex loss, "gradient descent converged" means "we found the best parameters".

The second-order condition: curvature is never negative #

Theorem 3 (second-order condition). Let $f$ be twice continuously differentiable on an open convex set $D$. Then $f$ is convex if and only if the Hessian is positive semidefinite, $\nabla^2 f(x) \succeq 0$, at every $x \in D$.

Why. Taylor's theorem with integral remainder gives

If the Hessian is PSD, the integral is $\ge 0$, and Theorem 2 gives convexity. Conversely, on a line $g(t) = f(x + tv)$ the function $g$ is convex, so its slope $g'$ cannot decrease, and $g''(0) = v^\top \nabla^2 f(x)\, v \ge 0$ for every direction $v$.

In 2D, a PSD Hessian means the surface is a bowl or a trough at every point, never a saddle. The figure shows the three shapes of a quadratic $x^\top S x$.

Interactive figure: loading…

Two tests you will use again:

• Least squares $f(w) = \frac{1}{2n}\|Xw - y\|^2$. The Hessian is $\frac1n X^\top X$, and $v^\top X^\top X v = \|Xv\|^2 \ge 0$. Convex.
• Logistic loss with labels $y_i \in \{-1, +1\}$: $\ell(w) = \frac1n \sum_i \log(1 + e^{-m_i})$ with margins $m_i = y_i\, x_i^\top w$. With the sigmoid $\sigma(m) = 1/(1 + e^{-m})$,

The weights $\sigma(1 - \sigma)$ lie in $(0, \tfrac14]$, so $\nabla^2\ell \succeq 0$ (convex) and $\nabla^2\ell \preceq \frac{1}{4n}X^\top X$. The weights go to 0 as the margins grow, so no $\mu > 0$ works everywhere. Adding $\tfrac{\lambda}{2}\|w\|^2$ adds $\lambda I$ to the Hessian.

Where convexity fails: neural networks #

The smallest example is a "network" with one weight per layer, $f(u, v) = \tfrac12(uv - 1)^2$. Both $(1, 1)$ and $(-1, -1)$ are minimizers ($f = 0$), but their midpoint $(0, 0)$ has $f = \tfrac12$. The set of minimizers, the hyperbola $uv = 1$, is not convex, so by Theorem 1 the function is not convex. The Hessian agrees: $\nabla^2 f(0, 0) = \begin{pmatrix} 0 & -1 \\ -1 & 0 \end{pmatrix}$ has eigenvalues $\pm 1$.

The same happens in every network with two or more hidden units. Swapping two hidden units (their rows in the first layer, their columns in the next) does not change the function. So a minimizer $\theta_A$ with two different hidden units has a copy $\theta_B$ with the same loss. If the loss were convex, the midpoint would also be a minimizer. But at the midpoint the two units are equal, and the loss is in general higher. Sign flips (for tanh) and rescaling $(aW_1, W_2/a)$ with $a > 0$ (for ReLU) give the same conclusion.

Interactive figure: loading…

Operations that preserve convexity #

You rarely check a Hessian by hand. You build the function from convex pieces (Boyd and Vandenberghe §3.2):

• nonnegative weighted sums $\sum_i c_i f_i$ with $c_i \ge 0$ (a data term plus a regularizer);
• composition with an affine map, $f(Ax + b)$ (any convex loss of a linear model);
• pointwise maximum $\max_i f_i(x)$, or supremum over any family (hinge loss $\max(0, 1 - y\,w^\top x)$);
• $h(g(x))$ with $h$ convex and nondecreasing and $g$ convex (for example $e^{g(x)}$);
• partial minimization $\inf_{z \in C} f(x, z)$, with $f$ jointly convex and $C$ convex.

CVXPY's disciplined convex programming (DCP) rules apply these rules automatically. Products of convex functions and compositions like $W_2\,\phi(W_1 x)$ are not on the list.

Smoothness, strong convexity and the condition number #

Definition ($L$-smooth). $f$ is differentiable and its gradient is $L$-Lipschitz: $\|\nabla f(x) - \nabla f(y)\| \le L\,\|x - y\|$ for all $x, y$. For twice-differentiable $f$ this is the same as $-L I \preceq \nabla^2 f(x) \preceq L I$ for all $x$.

Definition ($\mu$-strongly convex, $\mu > 0$). $f - \tfrac{\mu}{2}\|x\|^2$ is convex. For differentiable $f$ this is the same as $f(y) \ge f(x) + \nabla f(x)^\top (y - x) + \tfrac{\mu}{2}\|y - x\|^2$ for all $x, y$. For twice-differentiable $f$: $\nabla^2 f(x) \succeq \mu I$ for all $x$.

With both, $\mu I \preceq \nabla^2 f(x) \preceq L I$ for all $x$. The condition number is $\kappa = L/\mu \ge 1$.

• Quadratic $f(x) = \tfrac12 x^\top A x - b^\top x$ with $A$ symmetric positive definite: the Hessian is $A$ everywhere, so $L = \lambda_{\max}(A)$ and $\mu = \lambda_{\min}(A)$ (Rayleigh quotient, linear algebra 06).
• Ridge regression $f(w) = \frac{1}{2n}\|Xw - y\|^2 + \tfrac{\lambda}{2}\|w\|^2$ with $X \in \R^{n \times d}$: $\nabla^2 f = \frac1n X^\top X + \lambda I$. With the singular values $s_1 \ge \dots \ge s_d$ of $X$ (set $s_j = 0$ for $j > n$ when $n < d$), $L = s_1^2/n + \lambda$ and $\mu = s_d^2/n + \lambda$. A larger $\lambda$ lowers $\kappa$. With $\lambda = 0$ and $\operatorname{rank} X < d$, $\mu = 0$: convex, but not strongly convex.

Strictly convex is not strongly convex

$x^4$ and $e^x$ are strictly convex, but not strongly convex. For $x^4$, $f''(0) = 0$; for $e^x$, $f''(x) = e^x \to 0$ as $x \to -\infty$. No $\mu > 0$ fits under the curve everywhere. Strong convexity is what gives the linear convergence rates of lesson 03; strict convexity only gives a unique minimizer (when one exists: $e^x$ has none).

The descent lemma #

Theorem 4 (descent lemma). If $f$ is $L$-smooth, then for all $x, y$:

No convexity is needed. This is the upper parabola of section 2, in any dimension.

Proof. Write $z_t = x + t(y - x)$ for the points of the segment from $x$ to $y$.

1. By the fundamental theorem of calculus along the segment, $f(y) - f(x) = \int_0^1 \nabla f(z_t)^\top (y - x)\, dt$.
2. Subtract $\nabla f(x)^\top (y - x) = \int_0^1 \nabla f(x)^\top(y - x)\,dt$. The integrand becomes $\big(\nabla f(z_t) - \nabla f(x)\big)^\top (y - x)$.
3. By Cauchy–Schwarz, the integrand is at most $\|\nabla f(z_t) - \nabla f(x)\|\,\|y - x\|$. By the Lipschitz bound, $\|\nabla f(z_t) - \nabla f(x)\| \le L\|z_t - x\| = Lt\,\|y - x\|$. So the integrand is at most $L t\,\|y - x\|^2$.
4. $\int_0^1 L t\, dt = L/2$. $\blacksquare$

Corollary (one gradient step). Put $y = x - \eta\nabla f(x)$ into the lemma:

The decrease is guaranteed for $0 < \eta < 2/L$, and it is largest at $\eta = 1/L$, where $f(x - \nabla f(x)/L) \le f(x) - \|\nabla f(x)\|^2/(2L)$. So the step $1/L$ minimizes the upper parabola. This answers the question "how small is small enough?" left open in lesson 01.

The PL inequality #

On the quadratic of section 2 ($x^\star = 0$, $f^\star = 0$): $\|\nabla f(x)\|^2 = x_1^2 + 100^2 x_2^2$ and $2\mu\,(f(x) - f^\star) = x_1^2 + 100\, x_2^2$. Each term on the left is at least the matching term on the right, because $\lambda_i^2 \ge \mu\lambda_i$ for every eigenvalue. So the gradient is large whenever the gap $f - f^\star$ is large. This is what makes gradient descent converge fast.

Theorem 5 (Polyak–Łojasiewicz, PL). If $f$ is differentiable and $\mu$-strongly convex with minimum value $f^\star$, then

Proof.

1. Strong convexity at $x$: $f(y) \ge f(x) + \nabla f(x)^\top (y - x) + \tfrac{\mu}{2}\|y - x\|^2$ for all $y$.
2. Take the minimum over $y$ of both sides. The left side becomes $f^\star$.
3. The right side is a convex quadratic in $y$. Its gradient $\nabla f(x) + \mu(y - x)$ is zero at $y = x - \nabla f(x)/\mu$, and its value there is $f(x) - \|\nabla f(x)\|^2/(2\mu)$.
4. So $f^\star \ge f(x) - \|\nabla f(x)\|^2/(2\mu)$. Rearrange. $\blacksquare$

The same argument on the descent lemma gives the upper twin, $\|\nabla f(x)\|^2 \le 2L\,(f(x) - f^\star)$, for any $L$-smooth $f$ with a minimum. Together they explain the stopping rule of lesson 01: a small gradient means a small gap, $f(x) - f^\star \le \|\nabla f(x)\|^2/(2\mu)$.

Lesson 03 combines PL with the corollary of the descent lemma: with $\eta = 1/L$, each step gives $f(x_{k+1}) - f^\star \le (1 - \mu/L)(f(x_k) - f^\star)$, a linear rate whose speed depends only on $\kappa$.

PL without convexity

PL is weaker than strong convexity. Two examples:

• $f(x) = x^2 + 3\sin^2 x$ has $f''(\pi/2) = 2 + 6\cos\pi = -4 < 0$, so it is not convex. But its only stationary point is $x = 0$, and it satisfies PL: Karimi, Nutini and Schmidt (2016) show that $\mu = 1/32$ works; numerically the best constant is about $0.175$.
• Least squares with a singular $X^\top X$ has many minimizers (not strongly convex), but satisfies PL with $\mu$ equal to the smallest nonzero eigenvalue of $\frac1n X^\top X$.

Since the linear rate of lesson 03 uses only the descent lemma and PL, it also holds for these functions. Liu, Zhu and Belkin (2022) show that very wide neural networks satisfy a PL-type condition in a ball around their initialization, which helps explain why gradient descent can drive their training loss to zero.

Feature scaling is diagonal preconditioning #

With centered, uncorrelated features of standard deviations $s_j$, the least-squares Hessian is $\frac1n X^\top X \approx \operatorname{diag}(s_1^2, \dots, s_d^2)$, so $\kappa \approx s_{\max}^2/s_{\min}^2$. Standardizing ($x_j \to x_j/s_j$) gives a Hessian of about $I$ and $\kappa \approx 1$.

In weight space this is a change of variables $w = Dv$ with $D = \operatorname{diag}(1/s_j)$:

1. The new loss $g(v) = f(Dv)$ has gradient $\nabla g(v) = D\,\nabla f(Dv)$ and Hessian $\nabla^2 g = D\, \nabla^2 f\, D$ (chain rule).
2. A gradient step on $v$ is $v^+ = v - \eta D\nabla f(w)$. Multiply by $D$ to map it back: $w^+ = w - \eta D^2 \nabla f(w)$.
3. So gradient descent on the standardized problem is gradient descent on the original problem with one step size per coordinate, $\eta/s_j^2$: a diagonal preconditioner.

A diagonal preconditioner cannot remove correlations. Two standardized features with correlation $\rho$ give the Hessian $\begin{pmatrix} 1 & \rho \\ \rho & 1\end{pmatrix}$ with eigenvalues $1 \pm \rho$, so $\kappa = (1 + |\rho|)/(1 - |\rho|)$. That needs a full-matrix preconditioner (whitening, or Newton's method in lesson 10).

Why $\kappa$ controls first-order methods. On a quadratic, gradient descent multiplies the error along eigenvector $i$ by $1 - \eta\lambda_i$ per step (lesson 01). The steep direction needs $\eta < 2/L$. Then the flat direction keeps a factor $1 - \eta\mu > 1 - 2/\kappa$, so about $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ steps or more are needed to reduce its error by a factor $\varepsilon$ (lesson 03; momentum needs about $\sqrt{\kappa}$, lesson 04).

Answers to section 1. (1) $x^4$ is convex and even strictly convex. But $f''(x) = 12x^2$ is unbounded, so no $L$ works on all of $\R$, and $f''(0) = 0$, so no $\mu > 0$ works. The rates of lesson 03 do not apply: fixed-step gradient descent, $x^+ = x(1 - 4\eta x^2)$, even diverges from every start with $|x_0| > 1/\sqrt{2\eta}$. (2) The variances are $1$ and $10^6$, so $\kappa \approx 10^6$ before and $\kappa \approx 1$ after. The step estimate $\tfrac{\kappa}{2}\ln(1/\varepsilon)$ drops by a factor of about $10^6$.

4. Worked example #

Least squares with $n = 4$ samples and two centered, uncorrelated features with standard deviations 1 and 10:

and the loss is $f(w) = \frac{1}{2n}\|Xw - y\|^2$.

So $w^\star = (1, 0.1)$ and $f^\star = 0$.

Step 1: the constants. The two columns are orthogonal: $(1, -1, 1, -1)\cdot(10, 10, -10, -10) = 0$. So $\frac1n X^\top X = \operatorname{diag}(4/4,\ 400/4) = \operatorname{diag}(1, 100)$. $f$ is strongly convex with $\mu = 1$, $L = 100$, $\kappa = 100$.

Step 2: ridge. Adding $\tfrac{1}{2}\|w\|^2$ ($\lambda = 1$) gives the Hessian $\operatorname{diag}(2, 101)$ and $\kappa = 50.5$: better conditioned, but the minimizer moves to $(0.5,\ 0.099)$, because ridge changes the problem.

Step 3: standardizing. Divide column 2 by its standard deviation 10. The Hessian becomes $I$, so $\kappa = 1$, and the minimizer in the new coordinates is $v^\star = (1, 1)$ (since $10 \cdot 0.1 = 1$).

Step 4: the descent lemma at $w_0 = 0$. $f(w_0) = \frac18\|y\|^2 = \frac18 \cdot 8 = 1$. The gradient is $\nabla f(w) = \frac1n X^\top(Xw - y) = \operatorname{diag}(1, 100)\,(w - w^\star)$, so $\nabla f(w_0) = (-1, -10)$ and $\|\nabla f(w_0)\|^2 = 101$. One step with $\eta = 1/L = 0.01$: $w_1 = (0, 0) - 0.01\,(-1, -10) = (0.01,\ 0.1)$. Then

So $f(w_1) = 0.49005 \le 0.495$: the bound of the corollary holds, and it is almost tight.

Step 5: PL at $w_0$. $\|\nabla f\|^2 = 101 \ge 2\mu\,(f - f^\star) = 2$, and $101 \le 2L\,(f - f^\star) = 200$. ✓

Step 6: what the step did. The steep coordinate $w_2$ reached its optimum $0.1$ in one step. The flat coordinate $w_1$ moved only 1% of the way, from 0 to 0.01. Its error shrinks by $1 - \mu/L = 0.99$ per step, so a reduction by $10^6$ takes $\ln(10^6)/(-\ln 0.99) \approx 1{,}375$ steps. After standardizing, the gradient at $v = 0$ is $(-1, -1)$, and one step with $\eta = 1/L = 1$ lands exactly on $v^\star = (1, 1)$.

5. In code #

NumPy checks the worked example.

import numpy as np

# Worked example: two centered, uncorrelated features with standard deviations 1 and 10
X = np.array([[1, 10], [-1, 10], [1, -10], [-1, -10]], dtype=float)
w_star = np.array([1.0, 0.1])
y = X @ w_star                               # so f* = f(w*) = 0
n = len(y)
H = X.T @ X / n                              # Hessian of f(w) = ||Xw - y||^2 / (2n)
mu, L = np.linalg.eigvalsh(H)                # eigenvalues in ascending order
print(mu, L, L / mu)                         # 1.0 100.0 100.0

ridge = np.linalg.eigvalsh(H + 1.0 * np.eye(2))       # ridge with lambda = 1
print(ridge, ridge[1] / ridge[0])                      # [  2. 101.] 50.5

Xs = X / X.std(axis=0)                                 # standardized features
print(np.linalg.eigvalsh(Xs.T @ Xs / n))               # [1. 1.]  -> kappa = 1

f = lambda w: np.sum((X @ w - y) ** 2) / (2 * n)
grad = lambda w: X.T @ (X @ w - y) / n
w0 = np.zeros(2)
g0 = grad(w0)
w1 = w0 - g0 / L                                       # one step with step 1/L
print(f(w0), g0, g0 @ g0)                              # 1.0 [ -1. -10.] 101.0
print(w1, f(w1), f(w0) - g0 @ g0 / (2 * L))            # [0.01 0.1 ] 0.49005 0.495
print(2 * mu * f(w0) <= g0 @ g0 <= 2 * L * f(w0))      # True (PL and its upper twin)

The two parabolas and PL on a convex function that is not quadratic, $f(x) = \tfrac12 x^\top A x - b^\top x + \sum_i \log\cosh x_i$. Its Hessian is $A + \operatorname{diag}(1/\cosh^2 x_i)$ and $0 < 1/\cosh^2 \le 1$, so $\mu = \lambda_{\min}(A)$ and $L = \lambda_{\max}(A) + 1$. We test both bounds at 10,000 random pairs of points:

import numpy as np
from scipy.optimize import minimize

rng = np.random.default_rng(0)
M = rng.standard_normal((3, 3))
A = M @ M.T + 0.5 * np.eye(3)                 # symmetric positive definite
b = rng.standard_normal(3)
f = lambda x: 0.5 * x @ A @ x - b @ x + np.sum(np.log(np.cosh(x)))
grad = lambda x: A @ x - b + np.tanh(x)
ev = np.linalg.eigvalsh(A)
mu, L = ev[0], ev[-1] + 1.0

upper = lower = True
for _ in range(10_000):
    x, z = 3 * rng.standard_normal((2, 3))
    tangent = f(x) + grad(x) @ (z - x)
    upper &= f(z) <= tangent + L / 2 * (z - x) @ (z - x) + 1e-9
    lower &= f(z) >= tangent + mu / 2 * (z - x) @ (z - x) - 1e-9
fstar = minimize(f, np.zeros(3), jac=grad, method="BFGS", options={"gtol": 1e-12}).fun
pl = all(grad(x) @ grad(x) >= 2 * mu * (f(x) - fstar) - 1e-9
         for x in 3 * rng.standard_normal((10_000, 3)))
print(upper, lower, pl)                       # True True True

6. Where it shows up #

• Linear models. Least squares, ridge, logistic regression, the lasso and the hinge-loss SVM are convex: a stationary point is the answer, and $\kappa$ is the condition number of the (regularized) feature covariance. For example, scikit-learn's documentation says that its sag and saga solvers converge fast only when the features have about the same scale.
• Deep networks. Not convex (permutation symmetry), but near a minimum the Hessian plays the role of $L$ and $\mu$. Its largest eigenvalue, the sharpness, limits the stable learning rate to about $2/\lambda_{\max}$ (lessons 03 and 11). Adam's per-coordinate scaling is a diagonal preconditioner (lesson 06); Shampoo and Muon use matrix preconditioners (lesson 12). Normalization layers such as BatchNorm apply the idea of feature scaling inside the network: they standardize the inputs of a layer.
• ML for science. The 1D Laplacian on $N$ grid points has $\kappa \approx 4(N + 1)^2/\pi^2$, which grows like $h^{-2}$ for grid spacing $h$ (about 48, 4,134 and 406,095 for $N$ = 10, 100, 1,000). A least-squares loss on the residual of the discretized equation, $\tfrac12\|Tu - g\|^2$, has Hessian $T^\top T$, so its condition number is the square of that. Rathore et al. (ICML 2024) trace the difficulty of training physics-informed neural networks to this ill-conditioning. Nondimensionalizing and normalizing each input field of a surrogate model (temperature in K, pressure in Pa) is the same diagonal preconditioning as feature scaling.

7. Common mistakes #

• Checking the Hessian at one point. $\nabla^2 f(x^\star) \succeq 0$ at a minimizer holds for many nonconvex functions. Convexity needs $\nabla^2 f \succeq 0$ on the whole (convex) domain.
• Strict = strong. $x^4$ and $e^x$ are strictly convex, but $f''$ gets arbitrarily close to 0, so they are not strongly convex.
• "Logistic regression is strongly convex." Only with an L2 term. Without it, $\mu = 0$ on $\R^d$, and on linearly separable data there is no minimizer at all (the loss keeps decreasing as $\|w\| \to \infty$).
• Reading $\kappa$ off $X$. The Hessian is $\frac1n X^\top X$, and $\kappa(X^\top X) = \kappa(X)^2$, where $\kappa(X) = s_1/s_d$ is the ratio of singular values.
• "Standardization makes $\kappa = 1$." Only for uncorrelated features. Correlated features keep $\kappa = (1 + |\rho|)/(1 - |\rho|)$ or worse.
• Ridge "fixes" conditioning for free. A larger $\lambda$ lowers $\kappa$, but it also changes the minimizer. Feature scaling does not change the fitted function of an unregularized linear model.
• Notation. Bubeck writes $\alpha$ (strong convexity) and $\beta$ (smoothness); Boyd and Vandenberghe write $m$ and $M$. This track uses $\mu$ and $L$.

8. Check yourself #

1. For $|x|$, $\max(0, x)^2$ and $e^x$ on $\R$: convex? $L$-smooth? strongly convex?
   Answer

   $|x|$: convex; not differentiable at 0, so not $L$-smooth; not strongly convex. $\max(0, x)^2$: convex; $L$-smooth with $L = 2$ (its derivative $2\max(0, x)$ is 2-Lipschitz); not strongly convex (flat for $x < 0$). $e^x$: strictly convex; not $L$-smooth ($f'' = e^x$ is unbounded); not strongly convex ($f'' \to 0$ as $x \to -\infty$).
2. A quadratic has Hessian eigenvalues $0.1$, $1$ and $50$. Give $L$, $\mu$, $\kappa$. What is $\kappa$ after adding $\tfrac{0.9}{2}\|x\|^2$?
   Answer

   $L = 50$, $\mu = 0.1$, $\kappa = 500$. The new term adds $0.9I$: eigenvalues $1$, $1.9$, $50.9$, so $\kappa = 50.9$.
3. Why does the PL inequality imply that every stationary point is a global minimizer?
   Answer

   At a point with $\nabla f(x) = 0$, PL gives $0 \ge 2\mu\,(f(x) - f^\star)$, so $f(x) \le f^\star$. Since always $f(x) \ge f^\star$, we get $f(x) = f^\star$.
4. Two standardized features have correlation $0.8$. What is $\kappa$ of $\frac1n X^\top X$? Does more rescaling of single features help?
   Answer

   The eigenvalues are $1.8$ and $0.2$, so $\kappa = 9$. No: a diagonal rescaling cannot remove a correlation. Whitening (a full-matrix preconditioner) can.
5. Show that $f(w) = \|Xw - y\|^2 + \lambda\|w\|_1$ with $\lambda \ge 0$ is convex without computing a Hessian.
   Answer

   $\|\cdot\|^2$ is convex, and composition with the affine map $w \mapsto Xw - y$ keeps convexity. $\|\cdot\|_1$ is a norm, hence convex (triangle inequality and homogeneity). A nonnegative weighted sum of convex functions is convex.
6. $f$ is $L$-smooth with $L = 4$. Which step guarantees the largest decrease from the descent lemma, and what is that guaranteed decrease if $\|\nabla f(x)\| = 2$?
   Answer

   $\eta = 1/L = 0.25$. The guaranteed decrease is $\|\nabla f(x)\|^2/(2L) = 4/8 = 0.5$.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Define a convex function.

   Show answer

2. State the first-order condition for convexity.

   Show answer

3. Why is a stationary point of a convex differentiable function a global minimizer?

   Show answer

4. What is the second-order test for convexity?

   Show answer

5. Why is the loss of a neural network with two hidden units not convex?

   Show answer

6. Define $L$-smooth and $\mu$-strongly convex for a $C^2$ function.

   Show answer

7. State the descent lemma.

   Show answer

8. What does one step with $\eta = 1/L$ guarantee for an $L$-smooth $f$?

   Show answer

9. State the PL inequality.

   Show answer

10. Two uncorrelated features have standard deviations 1 and 10. What is $\kappa$ of the least-squares Hessian, and after standardizing?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Is the training loss of a neural network convex?" — No. Permuting hidden units gives distinct minimizers whose midpoint is in general worse. Smallest example: $\tfrac12(uv - 1)^2$, with minimizers $(1, 1)$ and $(-1, -1)$ and value $\tfrac12$ at the midpoint.
• "What is the condition number, and why care?" — $\kappa = L/\mu$, the ratio of the largest to the smallest curvature. Gradient descent needs $O(\kappa\log(1/\varepsilon))$ steps.
• "Why standardize features before gradient descent?" — It is a diagonal preconditioner that lowers $\kappa$ (to about 1 for uncorrelated features). For an unregularized linear model it does not change the fitted function, only the speed.
• "Strictly vs strongly convex?" — $x^4$ is strictly but not strongly convex. Strong convexity gives $f(x) - f^\star \ge \tfrac{\mu}{2}\|x - x^\star\|^2$ and linear rates.
• "Why is logistic regression convex?" — Its Hessian is $\frac1n\sum_i \sigma_i(1 - \sigma_i)x_i x_i^\top \succeq 0$.

10. Practice #

The notebook for this lesson runs in Colab. It has four exercises, each with a check cell and a folded solution:

1. Test convexity on a grid with the second-order condition: logistic loss (convex) against a small two-unit network loss (not convex).
2. Compute $L$, $\mu$ and $\kappa$ of ridge regression on the diabetes data, with raw and with standardized features.
3. Verify the descent lemma numerically at many random points.
4. Verify the PL inequality for a strongly convex quadratic and find the best constant.

11. Watch and read #

Convexity 101 [Optimization Bootcamp]Steve Brunton · 15 min

Convex sets and functions with pictures, and why convex problems are easy.

2.3 Convex FunctionsConstantine Caramanis · 17 min

The definition, the chord picture and examples of convex functions.

3.2 Smooth and Strongly Convex FunctionsConstantine Caramanis · 29 min

The two parabolas of section 2: the definitions of L-smooth and μ-strongly convex.

Lecture 3 | Convex Optimization I (Stanford)Stanford · Stephen Boyd, EE364A · 77 min

Convex functions, the first- and second-order conditions and the operations that preserve convexity.

• Boyd and Vandenberghe, Convex Optimization, free PDF: §2.1–2.3 (convex sets), §3.1.3–3.1.4 (first- and second-order conditions), §3.2 (operations that preserve convexity), §9.1.2 (strong convexity, written with $m$ and $M$).
• Garrigos and Gower, Handbook of Convergence Theorems for (Stochastic) Gradient Methods, §2: the first-order condition, strong convexity, the descent lemma and PL, with proofs.
• Karimi, Nutini and Schmidt, Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak–Łojasiewicz Condition (2016): PL and its relation to other conditions.
• CVXPY, Disciplined Convex Programming: the composition rules in practice.
• Rathore, Lei, Frangella, Lu and Udell, Challenges in Training PINNs: A Loss Landscape Perspective (ICML 2024): ill-conditioning in physics-informed losses.