Nearly all supervised machine learning tasks, from linear regression and logistic modeling to support vector machines and graphical energy models, are ultimately cast as numerical optimization problems. When the objective loss function is convex, the treacherous landscape of local traps, saddle points, and deceptive plateaus dissolves. In high-dimensional convex geometry, every local minimum is a global minimum, and the behavior of first-order algorithms is governed by precise mathematical convergence rates.
1. Convex Sets, Functions, and Epigraphs
A subset $mathcal{C} subseteq mathbb{R}^d$ is convex if for all points $x, y in mathcal{C}$ and any convex combination parameter $theta in [0, 1]$:
$$theta x + (1 – theta) y in mathcal{C}$$
A function $f: mathcal{C} to mathbb{R}$ is convex if its epigraph $text{epi}(f) = {(x, t) in mathcal{C} times mathbb{R} : f(x) le t}$ is a convex set. Analytically, this requires Jensen’s inequality to hold for all $x, y in mathcal{C}$ and $theta in [0, 1]$:
$$f(theta x + (1 – theta) y) le theta f(x) + (1 – theta) f(y)$$
For continuously differentiable functions, convexity is equivalent to the first-order condition—the first-order Taylor expansion always under-approximates the function globally:
$$f(y) ge f(x) + nabla f(x)^T (y – x) quad forall x, y in mathcal{C}$$
2. Smoothness and Strong Convexity
To establish quantifiable convergence rates for iterative algorithms, optimization theory classifies functions by two fundamental curvature bounds:
- $L$-Lipschitz Smoothness (Curvature Upper Bound): The gradient does not change arbitrarily fast. For all $x, y$:
$$|nabla f(x) – nabla f(y)| le L |x – y| iff f(y) le f(x) + nabla f(x)^T (y – x) + frac{L}{2} |y – x|^2$$
This guarantees that the function can everywhere be upper-bounded by a quadratic bowl with curvature $L$.
- $mu$-Strong Convexity (Curvature Lower Bound): The function grows at least as fast as a quadratic bowl with modulus $mu > 0$:
$$f(y) ge f(x) + nabla f(x)^T (y – x) + frac{mu}{2} |y – x|^2$$
Strong convexity guarantees a unique global minimum $w^*$ and guarantees that gradients cannot vanish away from the optimum: $|nabla f(x)|^2 ge 2mu (f(x) – f(w^*))$.
3. Gradient Descent Convergence Theorems
Standard Gradient Descent updates parameters along the negative gradient direction with step size (learning rate) $eta$:
$$w_{t+1} = w_t – eta nabla f(w_t)$$
Theoretical analysis establishes two distinct convergence regimes depending on curvature assumptions:
- Convex and $L$-Smooth Functions ($eta = 1/L$): The objective value error decays sublinearly at rate $mathcal{O}(1/T)$:
$$f(w_T) – f(w^*) le frac{L |w_0 – w^*|^2}{2T}$$
- $mu$-Strongly Convex and $L$-Smooth Functions ($eta = 2/(L + mu)$): The parameter distance decays exponentially (linearly in log-space) as a geometric progression:
$$|w_T – w^*|^2 le left( frac{kappa – 1}{kappa + 1} right)^{2T} |w_0 – w^*|^2, quad text{where} quad kappa = frac{L}{mu}$$
4. The Condition Number $kappa$ and Ill-Conditioned Geometry
The ratio $kappa = frac{L}{mu} = frac{lambda_{max}(nabla^2 f)}{lambda_{min}(nabla^2 f)}$ is the Condition Number of the Hessian matrix. Geometrically:
- When $kappa approx 1$, level sets are spherical, gradients point directly toward the minimum, and convergence is instantaneous.
- When $kappa gg 1$, level sets form elongated ellipsoidal ravines. Gradients point almost perpendicularly to the optimal direction, forcing standard gradient descent to oscillate wildly across ravine walls while making agonizingly slow progress along the valley floor.
5. Subgradient Calculus for Non-Smooth Objectives
Many critical objectives—such as the $L_1$ norm in Lasso or the Hinge loss $max(0, 1 – y w^T x)$ in Support Vector Machines—are non-differentiable at sharp points. Optimization generalizes through the Subdifferential $partial f(x)$:
$$partial f(x) = {g in mathbb{R}^d : f(y) ge f(x) + g^T (y – x) quad forall y}$$
For the absolute value function $f(x) = |x|$, at $x = 0$, the subdifferential is the entire closed interval $[-1, +1]$. By selecting any valid subgradient vector $g_t in partial f(w_t)$, subgradient descent guarantees convergence to within an $epsilon$-neighborhood at sublinear rate $mathcal{O}(1/sqrt{T})$, establishing the mathematical foundation for non-smooth machine learning.
