Convex Optimization
Convexity is the single property that transforms an optimization problem from "hard in general" to "solvable reliably." Most classic ML loss functions are convex by design — gradient descent on them always finds the global minimum.
What is convexity?
A function is convex if, for every two points in its domain and every :
Geometric meaning: any chord connecting two points on the graph lies above (or on) the curve. The function "curves upward."
For twice-differentiable functions there is an equivalent condition: is convex if and only if its Hessian is positive semi-definite (PSD) everywhere:
Examples
| Function | Convex? | Why |
|---|---|---|
| ✅ Yes | ||
| ✅ Yes | triangle inequality; undefined at 0 but subgradient exists | |
| ✅ Yes | softplus; | |
| ❌ No | (concave) | |
| ❌ No | alternates between concave and convex regions | |
| ❌ No | changes sign at |
import numpy as np
x = np.linspace(-2, 2, 400)
# Verify softplus convexity: second derivative = sigmoid * (1-sigmoid) > 0
softplus_dd = lambda x: (1/(1+np.exp(-x))) * (1 - 1/(1+np.exp(-x)))
print("softplus f'' range:", softplus_dd(x).min().round(4), "to", softplus_dd(x).max().round(4))
# All positive → convex
The chord test
The definition says the chord between any two points must lie above the curve. To test convexity numerically, pick 1000 random pairs and check whether holds for all of them. The notebook exercise automates exactly this.
The chord test, run on every row of that table
One chord, three definitions
Drag the two endpoints and the weight λ. The point on the chord is E[f(X)] for the two-point distribution that puts 1−λ on x₁ and λ on x₂; the point below it on the curve is f(E[X]). Convexity, Jensen's inequality and 'the chord lies above the graph' are three descriptions of the same vertical gap. The rose band marks where f″ < 0.
That scan is running for real (1000 seeded random pairs, the exact test the callout describes) and it separates the table cleanly: violations for , and softplus; for ; for ; for .
The two "sometimes" cases both land near , and that is not luck. Write the endpoints as (midpoint and half-width) and expand:
The chord clears the curve exactly when the curvature at the midpoint is positive. For these two functions there is no slop to argue about — the identities are exact:
Both are negative precisely when , so a random pair fails the test exactly when its midpoint lands in the rose band, which covers half of each of these symmetric domains. Hence .
Two things worth doing with it:
- Straddle the inflection of . Put and : the midpoint sits at , the gap is exactly , and the chord touches. Nudge either endpoint and the sign of the gap follows the sign of the midpoint, not the sign of the endpoints. Convexity is a local-curvature property being tested globally.
- Pick and watch the Hessian story break. Its is everywhere the derivative exists, yet it is convex — all of its curvature is concentrated at the single kink where is undefined. Move the midpoint onto and the readout says so rather than printing a zero it cannot justify. This is why the PSD-Hessian criterion is stated for twice-differentiable functions, and why regularization needs subgradients.
Jensen's inequality
If is convex and is a random variable, then:
"The function of the mean is less than or equal to the mean of the function."
This is the same picture again, not a new one. Put probability on and on : then is the point on the axis, is the height of the chord above it, and is the height of the curve. The λ slider above is moving a probability weight, and the vertical bar it drags along is the Jensen gap. The chord definition is Jensen restricted to two-point distributions; the general case follows by taking limits of those.
Application: cross-entropy ≥ entropy
Let be the true distribution and the model distribution. The gap between cross-entropy and entropy is an expectation of a log-ratio, and Jensen (applied to the convex , with expectations under ) pins its sign:
So , with equality only when — the cross-entropy loss can never beat the entropy of the truth, and the gap is exactly the KL divergence .
Worked example: log-sum-exp
The partition function in exponential families requires computing . Jensen gives a lower bound: for any distribution over ,
This is the ELBO (Evidence Lower BOund) that underlies variational inference.
Jensen numerical check
For and : (the moment-generating function), while . Jensen is tight — .
Convex sets and feasible regions
A set is convex if for any and , the point is also in .
Relevant examples in ML:
- Half-spaces — the building block of linear constraints
- Balls — the regularization feasible set
- Probability simplex — valid distributions
- Intersections of convex sets are always convex, so Ridge () and Lasso () constraint balls are convex
This matters because optimization over a convex domain with a convex objective gives the strongest guarantees.
Key theorem: local minimum = global minimum
Theorem. If is convex, any local minimum is a global minimum.
Proof sketch. Suppose is a local minimum but not the global minimum, so there exists with . By convexity, for any :
For small enough , is arbitrarily close to , which contradicts being a local minimum.
Consequence: Gradient descent on a convex loss is guaranteed to find the global minimum (given appropriate step sizes). There are no bad local minima to get stuck in.
Logistic regression is convex
The logistic regression loss for a single example is:
where . The Hessian of the full training loss is:
Each term is a positive scalar and is PSD, so for all . Logistic regression is convex — gradient descent finds the global optimum.
from sklearn.linear_model import LogisticRegression
import numpy as np
rng = np.random.default_rng(42)
X = rng.standard_normal((200, 2))
y = (X[:, 0] + X[:, 1] > 0).astype(int)
# Regardless of initialization, GD finds the same optimum
lr1 = LogisticRegression(solver='lbfgs', random_state=0).fit(X, y)
lr2 = LogisticRegression(solver='saga', random_state=99).fit(X, y)
print("Weights (lbfgs):", lr1.coef_.round(3))
print("Weights (saga) :", lr2.coef_.round(3))
# Different solvers → same answer (global minimum)
Practical guarantee
Because logistic regression is convex, you never need to worry about random initialization, learning rate schedules, or getting stuck in bad local minima. Any reasonable optimizer converges to the same global solution.
Non-convex functions in deep learning
Neural network losses are not convex. Two concrete reasons:
1. Permutation symmetry. Swap the two hidden units in a two-neuron network: the loss is identical. A network with hidden units has permutations — the loss has equivalent global minima. The loss landscape is not bowl-shaped; it has many symmetric valleys.
2. Product structure. The output of a two-layer net is . Even for linear activation (), the loss involves the product , which is non-convex in the joint parameter space (the set is not convex).
Why deep learning still works
Despite non-convexity:
- Overparameterization: modern networks have far more parameters than training examples. This creates a connected manifold of global minima, making it easier for GD to find one.
- Implicit bias: SGD has a built-in preference for "flat" minima (low curvature), which tend to generalize better than sharp ones.
- Empirical observation: in high dimensions, most critical points are saddle points, not local minima. Gradient descent tends to escape them.
Non-convexity does not mean chaos
Deep networks are non-convex, but their landscapes are not random noise. Structured non-convexity (with benign saddle points and few poor local minima) is why training large networks works reliably in practice.
Convexity-adjacent tools
When strict convexity cannot be guaranteed, weaker properties still give useful convergence results:
| Property | Definition | Convergence rate |
|---|---|---|
| Convex | (GD) | |
| -strongly convex | linear | |
| -smooth | needed for step-size bounds | |
| Quasi-convex | sublevel sets are convex | bisection works |
Strong convexity (-SC) is the strongest: it means the function curves up at least as fast as . Ridge regression with is -strongly convex, which is why it enjoys linear convergence.
-smoothness bounds how fast the gradient can change. The canonical GD step size is .
Together, -SC + -smooth gives the condition number ; convergence requires iterations.
Exercise
Which of the following functions is convex?
Need a hint?
A function is convex if the line segment between any two points on its graph lies above or on the graph.
Exercise
For a convex function, what does finding a point where the gradient equals zero guarantee?
Need a hint?
Consider what it means for a convex function to have a local minimum.
Exercise
For a convex loss with Lipschitz gradient (L-smooth), what step size η = 1/L guarantees about gradient descent convergence?
Need a hint?
Think about what the Lipschitz condition says about how fast the gradient can change.
Common mistakes
- Assuming convexity implies fast convergence. Convexity guarantees global minima but not speed. A badly conditioned convex problem () can be extremely slow for vanilla GD.
- Confusing convexity of loss with convexity of predictions. The logistic loss is convex in , but the predicted probabilities are not linear in . Composing a convex function with a non-convex one can break convexity.
- Checking convexity only on the loss, not the domain. Constrained problems require convexity of both the objective and the feasible set.
- Dismissing non-convex losses as unsolvable. Non-convexity does not mean intractable. It means you lose the global minimum guarantee, but practical methods often work extremely well.
Key takeaways
- A function is convex when any chord lies above the curve; equivalently when the Hessian is PSD everywhere.
- Jensen's inequality () underlies the KL divergence bound and the ELBO.
- For convex functions, every local minimum is a global minimum — gradient descent is provably correct.
- Logistic regression is convex (Hessian = ); neural net losses are not.
- Strong convexity (-SC) + -smoothness together give linear (exponential) convergence.
Related concepts
- Multivariable Optimization: gradients and Hessians
- Gradient Descent Variants: algorithms that exploit convexity
- Constrained Optimization & KKT: optimizing with constraints