th <- seq(0, 2 * pi, length.out = 300)
disc <- cbind(cos(th) - 2.2, sin(th))
# closed polygon: two lower corners, an apex, and a notch
arrow <- rbind(
c(1.2, -1), c(2.2, 0.9), c(3.2, -1),
c(2.2, -0.2), c(1.2, -1)
)
draw_plane(
curves = list(
disc, arrow,
chord_ok = rbind(c(-2.9, -0.6), c(-1.6, 0.6)),
chord_bad = rbind(c(1.2, -1), c(3.2, -1))
),
curve_color = c(
amds_colors[1], amds_colors[2],
amds_gray, amds_colors[3]
),
curve_line_type = c("solid", "solid", "solid", "dashed"),
notes = list(
convex = c(-2.2, -1.5),
`not convex` = c(2.2, -1.5)
),
xlab = "x1", ylab = "x2"
)15 Convexity
Optimization has one dividing line, and it is not between easy and hard problems. It is between problems where finding a local minimum is enough and problems where it is not.
That line is convexity. On one side, any downhill algorithm that stops has found the best answer there is, and you can prove it. On the other, stopping tells you nothing about whether somewhere else is better. Almost every guarantee in optimization is really a statement about which side you are on.
15.1 The shape of an optimization problem
An optimization problem has three parts:
\[ \min_{\mathbf{x} \in C} f(\mathbf{x}) \]
the objective \(f\) to be made small, the variable \(\mathbf{x}\) you may choose, and the feasible set \(C\) of allowed choices. The problem is convex when \(f\) is a convex function and \(C\) is a convex set — and then everything works.
Maximizing is the same problem: \(\max f = -\min(-f)\), and the negative of a convex function is concave. Everything here applies to concave maximization unchanged, with the inequalities flipped.
15.2 Convex sets
A set \(C\) is convex if the straight line between any two of its points stays inside it:
\[ \mathbf{x}, \mathbf{y} \in C \;\Longrightarrow\; \lambda\mathbf{x} + (1-\lambda)\mathbf{y} \in C \quad\text{for all } \lambda \in [0,1] \tag{15.1}\]
As \(\lambda\) runs from 0 to 1, \(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}\) traces the segment from \(\mathbf{y}\) to \(\mathbf{x}\). So the condition is: no dents, no holes, no separate pieces.
Convex sets you will meet:
| Set | Convex? |
|---|---|
| a line, a plane, all of \(\mathbb{R}^n\) | yes |
| a halfspace \(\{\mathbf{x} : \mathbf{a}^\top\mathbf{x} \leq b\}\) | yes |
| a ball \(\{\mathbf{x} : \|\mathbf{x}\| \leq r\}\) | yes |
| the unit balls of Figure 4.5 | yes, for every norm |
| an intersection of convex sets | yes, always |
| a union of convex sets | usually no |
| \(\{\mathbf{x} : \|\mathbf{x}\| = r\}\) — the sphere itself | no |
The intersection rule is the useful one: a feasible set defined by many simultaneous linear constraints is an intersection of halfspaces, so it is automatically convex. That covers linear programming, and it is why constrained problems are often better behaved than they look (Section 17.2).
15.3 Convex functions
A function is convex if the chord between any two points on its graph lies on or above the graph:
\[ f\bigl(\lambda\mathbf{x} + (1-\lambda)\mathbf{y}\bigr) \;\leq\; \lambda f(\mathbf{x}) + (1-\lambda)f(\mathbf{y}) \tag{15.2}\]
The left side is the function at a point between \(\mathbf{x}\) and \(\mathbf{y}\); the right side is the chord’s height there. Convex means the function never bulges above its own chords.
xg <- seq(-0.4, 2.4, length.out = 200)
draw_plane(
curves = list(
`x^2` = cbind(xg, xg^2),
chord = rbind(c(0, 0), c(2, 4))
),
curve_color = c(amds_colors[1], amds_colors[2]),
points = rbind(c(1, 1), c(1, 2)),
notes = list(
`f(1) = 1` = c(1.02, 0.45),
`chord = 2` = c(1.05, 2.5)
),
xlab = "x", ylab = "f(x)"
)One violation anywhere is enough to disqualify a function.
xw <- seq(-1.9, 1.9, length.out = 300)
well <- function(x) x^4 - 3 * x^2
draw_plane(
curves = list(
`x^4 - 3x^2` = cbind(xw, well(xw)),
chord = rbind(c(-1.5, well(-1.5)), c(1.5, well(1.5)))
),
curve_color = c(amds_colors[1], amds_colors[2]),
points = rbind(c(0, 0), c(0, well(1.5))),
xlab = "x", ylab = "f(x)"
)c(
f_at_mid = well(0),
chord_at_mid = (well(-1.5) + well(1.5)) / 2
) f_at_mid chord_at_mid
0.0000 -1.6875 The function is \(0\) where the chord is \(-1.69\). Convexity fails.
15.4 Tests for convexity
Equation 15.2 is the definition but a poor test — you cannot check every pair of points. Three practical tests instead.
Second-order test. For a twice-differentiable function:
| Dimension | Convex iff |
|---|---|
| one variable | \(f''(x) \geq 0\) everywhere |
| many variables | \(\nabla^2 f(\mathbf{x})\) is positive semi-definite everywhere |
This is the payoff from Section 8.9 and Section 12.8: curvature non-negative in every direction, at every point. Note everywhere — \(x^4 - 3x^2\) has \(f'' = 12x^2 - 6\), which is positive for large \(|x|\) but negative near the origin, and that local failure is fatal.
First-order test. For a differentiable function, convex iff every tangent lies below the graph:
\[ f(\mathbf{y}) \;\geq\; f(\mathbf{x}) + \nabla f(\mathbf{x})^\top(\mathbf{y}-\mathbf{x}) \tag{15.3}\]
The right side is the linear approximation from Equation 11.4. So convexity says the linear approximation is always an underestimate — which is exactly what makes it a usable bound rather than merely a local one.
[,1] [,2] [,3] [,4] [,5] [,6] [,7]
x -3 -2 -1 0 1 2 3
gap 16 9 4 1 0 1 4Never negative, touching zero only at the point of tangency.
Recognition. Often the fastest test is knowing the standard convex functions:
| Convex | Concave | Neither |
|---|---|---|
| \(x^2\), \(x^{2k}\) | \(\log x\) | \(x^3\) |
| \(e^{ax}\) | \(\sqrt{x}\) | \(\sin x\) |
| \(\lvert x\rvert\), any norm | \(-x^2\) | \(x^4 - 3x^2\) |
| \(\max(0, x)\) | ||
| \(-\log x\) |
15.5 Operations that preserve convexity
You rarely check a real objective from the definition. You build it from convex pieces using operations known to preserve convexity.
\[ \begin{aligned} &f, g \text{ convex},\; a, b \geq 0 &&\Rightarrow\quad af + bg \text{ convex} \\ &f, g \text{ convex} &&\Rightarrow\quad \max(f, g) \text{ convex} \\ &f \text{ convex} &&\Rightarrow\quad f(\mathbf{A}\mathbf{x} + \mathbf{b}) \text{ convex} \\ &f \text{ convex, } g \text{ convex non-decreasing} &&\Rightarrow\quad g(f(\mathbf{x})) \text{ convex} \end{aligned} \]
Two things to notice. The weights must be non-negative — subtracting a convex function can destroy convexity. And it is the maximum that is preserved, not the minimum: the pointwise max of convex functions is convex, while the min generally is not.
This is enough to certify most of the loss functions in machine learning:
| Objective | Why convex |
|---|---|
| \(\|\mathbf{y}-\mathbf{X}\boldsymbol{\beta}\|^2\) | squared norm composed with an affine map |
| ridge, \(+\lambda\|\boldsymbol{\beta}\|^2\) | sum of two convex terms, \(\lambda \geq 0\) |
| Lasso, \(+\lambda\|\boldsymbol{\beta}\|_1\) | same; the \(L_1\) norm is convex |
| hinge loss \(\max(0, 1-y\hat{y})\) | max of two affine functions |
| logistic loss | second derivative is positive everywhere |
NoteIn machine learning
Every one of these is convex in the parameters, which is why linear and logistic regression, ridge, Lasso and SVMs have a unique optimum you can certify. Note the Lasso’s \(L_1\) term is convex but not differentiable at zero — convexity does not require smoothness, and that corner is exactly what produces sparse solutions (Figure 4.5).
15.6 Why convexity matters
Three consequences, and the first is the one everything rests on.
1. Every local minimum is a global minimum. If \(\mathbf{x}^*\) is a local minimum of a convex \(f\), no point anywhere is better. So an algorithm that gets stuck has succeeded, and there is nothing to be gained by restarting elsewhere.
The reason is Equation 15.3. At a local minimum \(\nabla f(\mathbf{x}^*) = \mathbf{0}\), so the bound reads
\[ f(\mathbf{y}) \geq f(\mathbf{x}^*) + \mathbf{0}^\top(\mathbf{y}-\mathbf{x}^*) = f(\mathbf{x}^*) \]
for every \(\mathbf{y}\). A one-line proof of a global statement, from a local condition.
2. \(\nabla f = \mathbf{0}\) is sufficient, not just necessary. In general a vanishing gradient could be a minimum, a maximum, or a saddle (Section 12.9). For convex \(f\) there are no maxima to find and no saddles to be trapped by — a critical point is a minimum, always.
3. You get a certificate. The gradient bound gives a computable guarantee on how far from optimal you are, so you can stop with a proof rather than a hope.
The set of minimizers is itself convex, so if the optimum is not unique the solutions form a connected flat region — never two isolated answers with a barrier between them.
15.7 Strong convexity and smoothness
Convexity says curvature is non-negative. Two refinements bound it from each side, and together they determine how fast algorithms converge.
\(f\) is \(m\)-strongly convex if it curves at least as much as a quadratic:
\[ \nabla^2 f \succeq m\mathbf{I}, \qquad m > 0 \]
meaning every eigenvalue of the Hessian is at least \(m\). Equivalently, \(f(\mathbf{x}) - \frac{m}{2}\|\mathbf{x}\|^2\) is still convex. This rules out flat directions, which is what guarantees a unique minimum.
\(f\) is \(L\)-smooth if the curvature is bounded above:
\[ \nabla^2 f \preceq L\mathbf{I} \]
so the gradient cannot change faster than rate \(L\). This is what lets you take a step of a definite size without overshooting.
Between them:
\[ \kappa = \frac{L}{m} \]
the condition number of the problem — the same quantity as Section 6.10, now describing a landscape rather than a matrix.
L m kappa
20 2 10 This is the Hessian of Figure 12.2. \(\kappa = 10\) is the elongation of those level sets: \(m\) is the curvature along the valley floor, \(L\) across it. A circular bowl has \(\kappa = 1\) and is the easiest possible case; as \(\kappa\) grows the valley narrows and gradient descent slows in direct proportion (Section 16.4).
15.8 Non-convexity in deep learning
Neural network losses are emphatically not convex. Composing linear maps with non-linearities destroys it, and the symmetries alone guarantee many distinct minima — permuting hidden units gives an identical function with different parameters.
Compare Figure 12.1, where every path downhill reaches the same point. Here the outcome depends on the starting point, and no algorithm can promise the best basin without searching them all.
And yet deep learning works. Three observations reconcile this:
Most critical points are saddles, not bad minima. In high dimensions a critical point is a minimum only if all \(n\) Hessian eigenvalues are positive, which becomes vanishingly unlikely as \(n\) grows (Section 12.9). The obstacle is flat regions, not traps — and momentum exists largely to cross them (Section 16.6).
The minima that exist are often comparably good. Empirically, the many minima of a large network tend to reach similar loss. You are not choosing between a great solution and a terrible one so much as among many adequate ones.
Convex theory still guides practice. Learning rate bounds, momentum, and convergence analysis are all derived in the convex setting and then applied by analogy. They come with no guarantee off-piste, which is precisely why deep learning is so much more empirical than convex optimization.
WarningWatch out
“Non-convex” is not a synonym for “hopeless”, and “convex” is not a synonym for “easy”. A convex problem in ten million variables can be far harder to solve in practice than a small non-convex one.
Convexity buys you a guarantee about what a solution means, not speed. Conflating the two leads people to abandon convex formulations that would have worked fine.
15.9 Summary
| Concept | Statement |
|---|---|
| Convex set | the segment between any two points stays inside |
| Convex function | chords lie above the graph |
| Second-order test | \(f'' \geq 0\); Hessian positive semi-definite |
| First-order test | tangents lie below the graph |
| Preserved by | non-negative sums, max, affine composition |
| Key consequence | every local minimum is global |
| Strong convexity | \(\nabla^2 f \succeq m\mathbf{I}\), unique minimum |
| Smoothness | \(\nabla^2 f \preceq L\mathbf{I}\), safe step sizes |
| Condition number | \(\kappa = L/m\) |
15.10 Exercises
1. Is \(f(x) = x^3\) convex on \(\mathbb{R}\)? On \([0, \infty)\)?
TipSolution
\(f'' = 6x\), which is negative for \(x < 0\). So not convex on \(\mathbb{R}\) — it is concave on the left half and convex on the right.
On \([0,\infty)\) we have \(f'' \geq 0\) throughout, so it is convex there.
[,1] [,2] [,3] [,4] [,5]
x -2 -1 0 1 2
second_deriv -12 -6 0 6 12Convexity is a property of a function on a domain, exactly as injectivity was in Section 3.6.
2. Show that \(f(x) = |x|\) is convex despite not being differentiable at 0.
TipSolution
Use the definition directly. By the triangle inequality (Section 4.7),
\[ |\lambda x + (1-\lambda)y| \leq \lambda|x| + (1-\lambda)|y| \]
which is Equation 15.2 exactly.
lhs rhs
1.5 2.7 The second-order test needs differentiability; the definition does not. Every norm is convex for this reason, and the non-differentiable corners are what make \(L_1\) regularization produce exact zeros.
3. Is the intersection of two convex sets convex? What about the union?
TipSolution
Intersection: always convex. If \(\mathbf{x}, \mathbf{y}\) are in both sets, the segment between them stays inside each one, so it stays inside both.
Union: usually not. Two disjoint discs are each convex, but a segment joining one to the other passes through the gap.
This asymmetry is why constraints compose so well: adding a convex constraint intersects the feasible set, and convexity survives. Adding alternatives — “either this or that” — takes a union and destroys it, which is why problems with discrete choices are categorically harder.
4. Confirm that the least squares loss is convex by computing its Hessian.
TipSolution
From Section 13.7, the Hessian is \(2\mathbf{X}^\top\mathbf{X}\), positive semi-definite for any \(\mathbf{X}\) since \(\mathbf{v}^\top\mathbf{X}^\top\mathbf{X}\mathbf{v} = \|\mathbf{X}\mathbf{v}\|^2 \geq 0\).
Both eigenvalues positive, so positive definite here — strongly convex, with a unique minimum. With collinear columns the smaller eigenvalue would approach zero: still convex, but no longer strongly so, and the minimum stops being unique. That is Section 6.11 in the language of this chapter, and ridge works by adding \(\lambda\mathbf{I}\) to restore strong convexity.
5. For \(f(x,y) = 10x^2 + y^2\), find \(m\), \(L\) and \(\kappa\). What would make the problem easier?
TipSolution
The Hessian is \(\begin{bmatrix}20 & 0\\0 & 2\end{bmatrix}\), constant, so \(L = 20\), \(m = 2\), \(\kappa = 10\).
c(L = 20, m = 2, kappa = 10) L m kappa
20 2 10 Rescaling the variables would help: substituting \(u = \sqrt{10}\,x\) turns the objective into \(u^2 + y^2\), a circular bowl with \(\kappa = 1\).
That is exactly what feature standardization does to a regression problem, and why it speeds up gradient descent so reliably. The problem was never intrinsically hard — it was badly parameterized.
6. Is \(\max(x^2,\; 2-x)\) convex? Is \(\min\bigl(x^2,\; (x-3)^2\bigr)\)?
TipSolution
The max is convex: \(x^2\) is convex, \(2-x\) is affine and therefore convex, and the pointwise max of convex functions is convex.
The min is not, and the two parabolas show why.
f_at_0 f_at_3 chord_at_1.5 f_at_1.5
0.00 0.00 0.00 2.25 Both parabolas have a minimum of zero, at \(0\) and at \(3\). The chord between those two points sits at height \(0\) the whole way, but the function rises to \(2.25\) in the middle where the two wells meet. The graph bulges above its chord, so convexity fails.
The general principle: a max keeps you above every constituent and preserves the bowl shape, while a min follows whichever piece is lower and can carve a ridge between two wells.
A tempting counterexample that is not one. \(\min(x^2,\; 2x-1)\) looks like it should fail too, and it does not. Since \(x^2 - (2x-1) = (x-1)^2 \geq 0\), the parabola is never below the line, so the min is just \(2x-1\) everywhere — affine, hence convex. Two convex functions have a non-convex min only where they actually cross, which is why a counterexample needs two wells in different places.