Convex OptimizationOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

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 f:Rn→Rf: \mathbb{R}^n \to \mathbb{R} is convex if, for every two points x,yx, y in its domain and every λ∈[0,1]\lambda \in [0, 1]:

f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)

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: ff is convex if and only if its Hessian is positive semi-definite (PSD) everywhere:

∇2f(x)⪰0∀x\nabla^2 f(x) \succeq 0 \quad \forall x

Examples

FunctionConvex?Why
f(x)=x2f(x) = x^2✅ Yesf′′(x)=2>0f''(x) = 2 > 0
f(x)=∥x∥f(x) = \|x\|✅ Yestriangle inequality; f′′f'' undefined at 0 but subgradient exists
f(x)=log⁡(1+ex)f(x) = \log(1 + e^x)✅ Yessoftplus; f′′=σ(x)(1−σ(x))>0f'' = \sigma(x)(1-\sigma(x)) > 0
f(x)=−x2f(x) = -x^2❌ Nof′′(x)=−2<0f''(x) = -2 < 0 (concave)
f(x)=sin⁡(x)f(x) = \sin(x)❌ Noalternates between concave and convex regions
f(x)=x3f(x) = x^3❌ Nof′′(x)=6xf''(x) = 6x changes sign at x=0x=0
Python
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 (x,y)(x, y) and check whether f ⁣(x+y2)≤f(x)+f(y)2f\!\left(\frac{x+y}{2}\right) \leq \frac{f(x)+f(y)}{2} 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

-224.5-0.5E[f(X)] = 1.799f(E[X]) = 0.004E[X] = -0.06
E[f(X)] − f(E[X])1.7956
Jensenholds
midpoint gap1.7956
½·f″(m)·d²1.7956
midpoint scan (1000 pairs)0 violations

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: 00 violations for x2x^2, ∣x∣|x| and softplus; 501501 for x3x^3; 502502 for sin⁡x\sin x; 10001000 for −x2-x^2.

The two "sometimes" cases both land near 500500, and that is not luck. Write the endpoints as m±dm \pm d (midpoint and half-width) and expand:

12(f(m+d)+f(m−d))−f(m)  =  12f′′(m) d2+O(d4)\tfrac{1}{2}\big(f(m+d) + f(m-d)\big) - f(m) \;=\; \tfrac{1}{2}f''(m)\,d^2 + O(d^4)

The chord clears the curve exactly when the curvature at the midpoint is positive. For these two functions there is no O(d4)O(d^4) slop to argue about — the identities are exact:

x3:    gap=3md2sin⁡:    gap=−sin⁡(m) (1−cos⁡d)x^3:\;\; \text{gap} = 3md^2 \qquad\qquad \sin:\;\; \text{gap} = -\sin(m)\,(1 - \cos d)

Both are negative precisely when f′′(m)<0f''(m) < 0, 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 ≈500/1000\approx 500/1000.

Two things worth doing with it:

  1. Straddle the inflection of x3x^3. Put x1=−2x_1 = -2 and x2=2x_2 = 2: the midpoint sits at 00, the gap is exactly 00, 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.
  2. Pick ∣x∣|x| and watch the Hessian story break. Its f′′f'' is 00 everywhere the derivative exists, yet it is convex — all of its curvature is concentrated at the single kink where f′′f'' is undefined. Move the midpoint onto x=0x = 0 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 ℓ1\ell_1 regularization needs subgradients.

Jensen's inequality

If ff is convex and XX is a random variable, then:

f ⁣(E[X])≤E[f(X)]f\!\left(\mathbb{E}[X]\right) \leq \mathbb{E}[f(X)]

"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 1−λ1-\lambda on x1x_1 and λ\lambda on x2x_2: then E[X]=(1−λ)x1+λx2\mathbb{E}[X] = (1-\lambda)x_1 + \lambda x_2 is the point on the axis, E[f(X)]\mathbb{E}[f(X)] is the height of the chord above it, and f(E[X])f(\mathbb{E}[X]) 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 pp be the true distribution and qq the model distribution. The gap between cross-entropy and entropy is an expectation of a log-ratio, and Jensen (applied to the convex −log⁡-\log, with expectations under pp) pins its sign:

H(p,q)−H(p)=Ep ⁣[−log⁡q(x)p(x)]  ≥  −log⁡Ep ⁣[q(x)p(x)]=−log⁡∑xq(x)=−log⁡1=0H(p, q) - H(p) = \mathbb{E}_p\!\left[-\log \frac{q(x)}{p(x)}\right] \;\geq\; -\log \mathbb{E}_p\!\left[\frac{q(x)}{p(x)}\right] = -\log \sum_x q(x) = -\log 1 = 0

So H(p,q)≥H(p)H(p, q) \geq H(p), with equality only when q=pq = p — the cross-entropy loss can never beat the entropy of the truth, and the gap is exactly the KL divergence DKL(p∥q)D_{\mathrm{KL}}(p\|q).

Worked example: log-sum-exp

The partition function in exponential families requires computing log⁡∑kezk\log \sum_k e^{z_k}. Jensen gives a lower bound: for any distribution qq over kk,

log⁡∑kezk=log⁡∑kqkezkqk≥∑kqk(zk−log⁡qk)=Eq[zk]+H(q)\log \sum_k e^{z_k} = \log \sum_k q_k \frac{e^{z_k}}{q_k} \geq \sum_k q_k \left(z_k - \log q_k\right) = \mathbb{E}_q[z_k] + H(q)

This is the ELBO (Evidence Lower BOund) that underlies variational inference.

Jensen numerical check

For f(x)=exf(x) = e^x and X∼N(0,1)X \sim \mathcal{N}(0, 1): E[eX]=e1/2≈1.649\mathbb{E}[e^X] = e^{1/2} \approx 1.649 (the moment-generating function), while eE[X]=e0=1e^{\mathbb{E}[X]} = e^0 = 1. Jensen is tight — 1.649≥11.649 \geq 1.

Convex sets and feasible regions

A set C\mathcal{C} is convex if for any x,y∈Cx, y \in \mathcal{C} and λ∈[0,1]\lambda \in [0,1], the point λx+(1−λ)y\lambda x + (1-\lambda)y is also in C\mathcal{C}.

Relevant examples in ML:

  • Half-spaces {x:a⊤x≤b}\{x : a^\top x \leq b\} — the building block of linear constraints
  • Balls {x:∥x∥≤r}\{x : \|x\| \leq r\} — the ℓ2\ell_2 regularization feasible set
  • Probability simplex {p≥0:∑ipi=1}\{p \geq 0 : \sum_i p_i = 1\} — valid distributions
  • Intersections of convex sets are always convex, so Ridge (ℓ2\ell_2) and Lasso (ℓ1\ell_1) 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 ff is convex, any local minimum is a global minimum.

Proof sketch. Suppose x∗x^* is a local minimum but not the global minimum, so there exists yy with f(y)<f(x∗)f(y) < f(x^*). By convexity, for any λ∈(0,1)\lambda \in (0, 1):

f(λy+(1−λ)x∗)≤λf(y)+(1−λ)f(x∗)<f(x∗)f(\lambda y + (1-\lambda)x^*) \leq \lambda f(y) + (1-\lambda)f(x^*) < f(x^*)

For small enough λ\lambda, λy+(1−λ)x∗\lambda y + (1-\lambda)x^* is arbitrarily close to x∗x^*, which contradicts x∗x^* being a local minimum. □\square

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:

ℓ(w)=−ylog⁡σ(w⊤x)−(1−y)log⁡(1−σ(w⊤x))\ell(w) = -y \log \sigma(w^\top x) - (1-y) \log(1 - \sigma(w^\top x))

where σ(z)=1/(1+e−z)\sigma(z) = 1/(1+e^{-z}). The Hessian of the full training loss is:

H=∑i=1nσ(w⊤xi)(1−σ(w⊤xi)) xixi⊤H = \sum_{i=1}^n \sigma(w^\top x_i)(1 - \sigma(w^\top x_i))\, x_i x_i^\top

Each term σ(1−σ)>0\sigma(1-\sigma) > 0 is a positive scalar and xixi⊤x_i x_i^\top is PSD, so H⪰0H \succeq 0 for all ww. Logistic regression is convex — gradient descent finds the global optimum.

Python
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 HH hidden units has H!H! permutations — the loss has H!H! 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 f(x;W1,W2)=W2σ(W1x)f(x; W_1, W_2) = W_2 \sigma(W_1 x). Even for linear activation (σ=id\sigma = \text{id}), the loss involves the product W2W1W_2 W_1, which is non-convex in the joint parameter space (the set {(A,B):AB=C}\{(A, B) : AB = C\} 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:

PropertyDefinitionConvergence rate
Convexf(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda)f(y)O(1/k)O(1/k) (GD)
μ\mu-strongly convexf(y)≥f(x)+∇f(x)⊤(y−x)+μ2∥y−x∥2f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y-x\|^2O(ρk)O(\rho^k) linear
LL-smooth∥∇f(x)−∇f(y)∥≤L∥x−y∥\|\nabla f(x) - \nabla f(y)\| \leq L\|x-y\|needed for step-size bounds
Quasi-convexsublevel sets {x:f(x)≤c}\{x : f(x) \leq c\} are convexbisection works

Strong convexity (μ\mu-SC) is the strongest: it means the function curves up at least as fast as μ2∥x∥2\frac{\mu}{2}\|x\|^2. Ridge regression with λ>0\lambda > 0 is λ\lambda-strongly convex, which is why it enjoys linear convergence.

LL-smoothness bounds how fast the gradient can change. The canonical GD step size is η=1/L\eta = 1/L.

Together, μ\mu-SC + LL-smooth gives the condition number κ=L/μ\kappa = L/\mu; convergence requires O(κlog⁡(1/ϵ))O(\kappa \log(1/\epsilon)) 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

  1. Assuming convexity implies fast convergence. Convexity guarantees global minima but not speed. A badly conditioned convex problem (κ≫1\kappa \gg 1) can be extremely slow for vanilla GD.
  2. Confusing convexity of loss with convexity of predictions. The logistic loss is convex in ww, but the predicted probabilities σ(w⊤x)\sigma(w^\top x) are not linear in ww. Composing a convex function with a non-convex one can break convexity.
  3. Checking convexity only on the loss, not the domain. Constrained problems require convexity of both the objective and the feasible set.
  4. 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 (f(E[X])≤E[f(X)]f(\mathbb{E}[X]) \leq \mathbb{E}[f(X)]) 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 = σ(1−σ)xx⊤⪰0\sigma(1-\sigma) x x^\top \succeq 0); neural net losses are not.
  • Strong convexity (μ\mu-SC) + LL-smoothness together give linear (exponential) convergence.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelated
Convex OptimizationCalculus for MLNeural NetworksMultivariable OptimizationGradient Descent VariantsConstrained Optimization …