Convex Optimisation Basics: Why Some Problems Are Easy

Optimisation is the engine of learning. Some optimisation problems are treacherous — full of local minima and saddle points. Others are benign: any downhill path leads to the best answer. The dividing line is convexity. Linear regression, logistic regression, SVMs and lasso are convex; deep neural networks are not. Understanding convexity tells you when you can trust your optimiser's answer.

Convex sets#

A set $C$ is convex if the line segment between any two of its points lies entirely inside it:

Examples: balls, half-spaces $\{\mathbf{x} : \mathbf{a}^\top\mathbf{x} \le b\}$, polyhedra, the set of positive semi-definite matrices. The intersection of convex sets is convex — so constraint sets built from linear inequalities are convex. A crescent or a donut is not convex.

Convex functions#

A function $f$ is convex if its domain is convex and

Geometrically: the chord between any two points on the graph lies above the graph. It is strictly convex if the inequality is strict for $\mathbf{x} \ne \mathbf{y}$ and $\theta \in (0,1)$.

Practical tests#

1. First-order condition (differentiable $f$): the tangent plane is a global under-estimator:

1. Second-order condition (twice differentiable): the Hessian is positive semi-definite everywhere, $\nabla^2 f(\mathbf{x}) \succeq 0$. In 1-D: $f''(x) \ge 0$.

Building blocks#

• Linear and affine functions (both convex and concave).
• Norms $\|\mathbf{x}\|_p$ for $p \ge 1$.
• $e^{x}$, $x^2$, $-\ln x$, $\ln(1 + e^x)$ (softplus), $\max(0, 1 - x)$ (hinge).
• Log-sum-exp $\ln\sum_i e^{x_i}$.

Operations that preserve convexity#

• Non-negative weighted sums: $\sum_i w_i f_i$ with $w_i \ge 0$.
• Composition with an affine map: $f(\mathbf{A}\mathbf{x} + \mathbf{b})$.
• Pointwise maximum: $\max_i f_i(\mathbf{x})$.

With these rules you can verify convexity of most ML objectives without computing a Hessian.

The fundamental theorem#

Proof sketch. Suppose $\mathbf{x}$ is a local minimum but some $\mathbf{y}$ has $f(\mathbf{y}) < f(\mathbf{x})$. Points on the segment near $\mathbf{x}$, $\mathbf{z} = \theta\mathbf{y} + (1-\theta)\mathbf{x}$ with small $\theta > 0$, satisfy $f(\mathbf{z}) \le \theta f(\mathbf{y}) + (1-\theta)f(\mathbf{x}) < f(\mathbf{x})$ — contradicting local minimality. $\blacksquare$

Which ML problems are convex?#

Strong convexity and smoothness#

Two constants govern how fast gradient methods converge:

• $\mu$-strongly convex: $\nabla^2 f \succeq \mu\mathbf{I}$ — the function curves up at least as fast as a quadratic.
• $L$-smooth: $\nabla^2 f \preceq L\mathbf{I}$ — gradients do not change too abruptly.

Their ratio $\kappa = L/\mu$ is the condition number. Gradient descent with step $1/L$ on a strongly convex, smooth function converges linearly: the error shrinks by a factor of roughly $(1 - 1/\kappa)$ per step. Large $\kappa$ means slow convergence — a key motivation for feature standardisation, which improves conditioning.

import numpy as np

def gd(H, x0, lr, steps=200):
    x = x0.copy()
    for _ in range(steps):
        x -= lr * (H @ x)                  # gradient of 0.5 x^T H x
    return np.linalg.norm(x)

x0 = np.array([1.0, 1.0])
for kappa in [2, 20, 200]:
    H = np.diag([1.0, float(kappa)])       # mu = 1, L = kappa
    print(f"kappa={kappa:>3}: distance to optimum after 200 steps = {gd(H, x0, 1 / kappa):.2e}")

Convex solvers in practice#

For convex problems we have excellent tools: scikit-learn solvers (liblinear, L-BFGS, SAGA), and modelling languages like CVXPY that let you write a problem in mathematical form and hand it to a specialised solver.

import cvxpy as cp
import numpy as np

rng = np.random.default_rng(0)
X, y = rng.normal(size=(50, 10)), rng.normal(size=50)
w = cp.Variable(10)
problem = cp.Problem(cp.Minimize(cp.sum_squares(X @ w - y) + 0.5 * cp.norm1(w)))
problem.solve()
print(np.round(w.value, 3))   # lasso solution with some exact zeros