Optimization Function Classes

Convex Optimization Basics

Convex sets, convex functions, gradient descent convergence, strong convexity, and duality: the optimization foundation that every learning-theoretic result silently depends on.

CoreTier 1Stable~60 min

Prerequisites

Differentiation in Rn Matrix Operations and Properties

Quiz (12)Pulse Check

Why This Matters

Optimizer Race

Surface:

Race:

LR:0.050

Every learning algorithm solves an optimization problem. When you minimize empirical risk, train a neural network, or fit a kernel SVM, you are running an optimization algorithm on a loss landscape. Convex optimization is the case where this landscape has no local minima traps. every local minimum is global.

This is not a "separate" subject from learning theory. The convergence rate of your optimizer determines the computational cost of learning. The properties of your objective (smoothness, strong convexity) determine both how fast you can optimize and how well the result generalizes (via algorithmic stability). Optimization and generalization are entangled.

Mental Model

A convex function is a bowl: any line segment between two points on the graph lies above the graph. This means gradient descent, which always moves "downhill," will reach the bottom. The questions are:

How fast? (convergence rate)
How close to the true minimum? (optimization error)
What properties of the function control the answers?

Formal Setup: Convex Sets and Functions

Definition

Convex Set

A set $\mathcal{C} \subseteq \mathbb{R}^d$ is convex if for all $x, y \in \mathcal{C}$ and all $\theta \in [0, 1]$ :

$\theta x + (1-\theta) y \in \mathcal{C}$

Every point on the line segment between $x$ and $y$ stays in $\mathcal{C}$ . Examples: balls, halfspaces, polyhedra, the probability simplex. Non-examples: the union of two disjoint balls, the set $\{x : \|x\| \geq 1\}$ .

Definition

Convex Function

A function $f: \mathcal{C} \to \mathbb{R}$ on a convex set $\mathcal{C}$ is convex if for all $x, y \in \mathcal{C}$ and $\theta \in [0, 1]$ :

$f(\theta x + (1-\theta) y) \leq \theta f(x) + (1-\theta) f(y)$

Equivalently, $f$ lies below its chords. If the inequality is strict for $x \neq y$ and $\theta \in (0, 1)$ , $f$ is strictly convex.

Definition

First-Order Condition for Convexity

If $f$ is differentiable, then $f$ is convex if and only if for all $x, y$ :

$f(y) \geq f(x) + \nabla f(x)^\top (y - x)$

This says: $f$ lies above every tangent hyperplane. The tangent at any point is a global lower bound on $f$ . This single inequality is the most useful characterization of convexity in practice.

Definition

Smoothness (L-smooth)

A differentiable function $f$ is $L$ -smooth if $\nabla f$ is $L$ -Lipschitz:

$\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\| \quad \forall x, y$

Equivalently, for all $x, y$ :

$f(y) \leq f(x) + \nabla f(x)^\top(y-x) + \frac{L}{2}\|y - x\|^2$

Smoothness says the function does not curve too sharply. $L$ is the maximum curvature. This is the key property that makes gradient descent work: it guarantees that a gradient step of size $1/L$ makes sufficient progress.

Definition

Strong Convexity

A function $f$ is $\mu$ -strongly convex (with $\mu > 0$ ) if for all $x, y$ :

$f(y) \geq f(x) + \nabla f(x)^\top(y-x) + \frac{\mu}{2}\|y - x\|^2$

This says $f$ curves at least as much as a quadratic with curvature $\mu$ . Strong convexity implies a unique minimizer $x^*$ and gives:

$f(x) - f(x^*) \geq \frac{\mu}{2}\|x - x^*\|^2$

Definition

Condition Number

The condition number of an $L$ -smooth, $\mu$ -strongly convex function is $\kappa = L/\mu$ . It measures how "elongated" the level sets are. $\kappa = 1$ means the function is a perfect isotropic quadratic. Large $\kappa$ means the function is badly conditioned: steep in some directions, flat in others.

The condition number controls the convergence rate of gradient descent: $O((1 - 1/\kappa)^t)$ , so ill-conditioned problems converge slowly.

Gradient Descent

The gradient descent algorithm with step size $\eta > 0$ :

$x_{t+1} = x_t - \eta \nabla f(x_t)$

Starting from $x_0$ , repeat until convergence. The step size $\eta$ is the single most important hyperparameter. Too large: diverge. Too small: crawl.

Main Theorems

Theorem

GD Convergence for Smooth Convex Functions

Statement

If $f$ is convex and $L$ -smooth, then gradient descent with step size $\eta = 1/L$ satisfies:

$f(x_T) - f(x^*) \leq \frac{L\|x_0 - x^*\|^2}{2T}$

That is, the optimization error decreases as $O(1/T)$ .

Intuition

Each gradient step with $\eta = 1/L$ makes progress proportional to $\|\nabla f(x_t)\|^2/L$ . Even when gradients become small near the optimum, the convexity of $f$ ensures that the iterates steadily approach $x^*$ . The $1/T$ rate means you need $T = O(1/\epsilon)$ iterations to reach $\epsilon$ -accuracy.

Proof Sketch

Step 1 (Descent Lemma): By $L$ -smoothness, choosing $\eta = 1/L$ gives:

$f(x_{t+1}) \leq f(x_t) - \frac{1}{2L}\|\nabla f(x_t)\|^2$

Step 2: By convexity, $f(x_t) - f(x^*) \leq \nabla f(x_t)^\top(x_t - x^*) \leq \|\nabla f(x_t)\| \cdot \|x_t - x^*\|$ .

Step 3: Track $\|x_t - x^*\|^2$ . By the update rule:

$\|x_{t+1} - x^*\|^2 = \|x_t - x^*\|^2 - \frac{2}{L}\nabla f(x_t)^\top(x_t - x^*) + \frac{1}{L^2}\|\nabla f(x_t)\|^2$

Combine using convexity: $\nabla f(x_t)^\top(x_t - x^*) \geq f(x_t) - f(x^*)$ . Sum from $t = 0$ to $T-1$ . The left side telescopes. Rearrange to get the $O(1/T)$ bound.

Why It Matters

This is the baseline convergence result. The $O(1/T)$ rate tells you that gradient descent works but is not spectacularly fast for merely convex problems. To do better, you need either (a) strong convexity or (b) acceleration (Nesterov's method gives $O(1/T^2)$ , which is optimal).

In ML, this rate determines the number of passes over the data needed to approximately solve the ERM problem.

Failure Mode

The bound scales with $\|x_0 - x^*\|^2$ : bad initialization hurts. Also, the $O(1/T)$ rate applies to the function value gap, not the parameter distance $\|x_T - x^*\|$ . For the parameter distance, you need strong convexity.

Theorem

GD Convergence for Smooth and Strongly Convex Functions

Statement

If $f$ is $\mu$ -strongly convex and $L$ -smooth, then gradient descent with $\eta = 1/L$ satisfies:

$f(x_T) - f(x^*) \leq \frac{L}{2}\Bigl(1 - \frac{1}{\kappa}\Bigr)^T \|x_0 - x^*\|^2$

where $\kappa = L/\mu$ is the condition number. The convergence is linear (exponential decrease): the error contracts by a factor $(1 - 1/\kappa)$ per iteration.

Intuition

Strong convexity ensures that when you are far from $x^*$ , the gradient is large, so gradient descent makes large steps. When you are close, the gradient is small, but you do not need large steps. The exponential convergence rate means the number of iterations to reach $\epsilon$ -accuracy is $O(\kappa \log(1/\epsilon))$ . logarithmic in the target accuracy.

Proof Sketch

By the descent lemma: $f(x_{t+1}) \leq f(x_t) - \frac{1}{2L}\|\nabla f(x_t)\|^2$ .

By strong convexity: $\|\nabla f(x_t)\|^2 \geq 2\mu(f(x_t) - f(x^*))$ .

Combining: $f(x_{t+1}) - f(x^*) \leq (1 - \mu/L)(f(x_t) - f(x^*))$ .

Iterate: $f(x_T) - f(x^*) \leq (1 - 1/\kappa)^T (f(x_0) - f(x^*))$ .

Replace $f(x_0) - f(x^*)$ with $\frac{L}{2}\|x_0 - x^*\|^2$ by smoothness.

Why It Matters

This is the workhorse convergence result for regularized ERM. Adding $\ell_2$ regularization $\lambda\|w\|^2$ makes any convex loss $\mu$ -strongly convex with $\mu = 2\lambda$ . The condition number becomes $\kappa = L/(2\lambda)$ , and the optimization converges in $O((L/\lambda)\log(1/\epsilon))$ iterations.

This directly connects to algorithmic stability: the same strong convexity that gives fast optimization also gives stability parameter $O(1/(\lambda n))$ .

Failure Mode

Large condition number $\kappa$ means slow convergence. For ridge regression with small regularization, $\kappa$ can be enormous. Preconditioning or second-order methods can help, but at higher per-iteration cost.

Duality Preview

Every convex optimization problem has a dual problem. For the primal:

$\min_x f(x) \quad \text{subject to } g_i(x) \leq 0, \; i = 1, \ldots, m$

The Lagrangian is $L(x, \lambda) = f(x) + \sum_i \lambda_i g_i(x)$ with $\lambda_i \geq 0$ . The dual problem is:

$\max_{\lambda \geq 0} \inf_x L(x, \lambda)$

Weak duality: dual optimal value $\leq$ primal optimal value (always). Strong duality: equality holds (under constraint qualifications like Slater's condition).

Why does duality matter for ML?

SVMs: the dual of the SVM problem is a quadratic program in the support vector coefficients, leading to the kernel trick
Regularization: the dual of constrained ERM relates to regularized ERM (Lagrangian multiplier $\leftrightarrow$ regularization parameter)
Lower bounds: dual certificates provide provable lower bounds on the optimal value, enabling stopping criteria

Canonical Examples

Example

Quadratic (least squares)

$f(w) = \frac{1}{2}\|Xw - y\|^2$ where $X \in \mathbb{R}^{n \times d}$ . This is $L$ -smooth with $L = \|X^\top X\|_{\text{op}} = \sigma_{\max}(X)^2$ and (if $X$ has full rank) $\mu$ -strongly convex with $\mu = \sigma_{\min}(X)^2$ . The condition number is $\kappa = (\sigma_{\max}/\sigma_{\min})^2$ , the squared condition number of $X$ .

GD converges in $O(\kappa \log(1/\epsilon))$ steps. For well-conditioned $X$ , this is fast. For ill-conditioned $X$ (nearly collinear features), this is slow.

Example

Logistic regression

$f(w) = \frac{1}{n}\sum_{i=1}^n \log(1 + e^{-y_i w^\top x_i})$ is convex and smooth (but not strongly convex without regularization). Adding $\lambda\|w\|^2$ makes it $2\lambda$ -strongly convex. The smoothness constant depends on $\|x_i\|$ : the logistic loss has Lipschitz gradient with constant $L = \frac{1}{4n}\sum_i \|x_i\|^2 + 2\lambda$ .

Example

Non-smooth: Lasso

$f(w) = \frac{1}{2n}\|Xw - y\|^2 + \lambda\|w\|_1$ . The $\ell_1$ penalty is not smooth (not differentiable at $0$ ). Standard gradient descent does not apply directly. You need proximal gradient descent, which handles the smooth part with a gradient step and the non-smooth part with a "prox" operator. The prox of $\lambda\|w\|_1$ is soft-thresholding, and the resulting algorithm (ISTA) converges at rate $O(1/T)$ .

Common Confusions

Watch Out

Convexity is about the objective, not the model

A linear model trained with a non-convex loss has a non-convex optimization problem. A neural network trained with cross-entropy has a non-convex problem (because the model is non-linear in parameters, even though cross-entropy is convex in predictions). Convexity of the optimization landscape depends on the composition of loss and model.

Watch Out

Smoothness and strong convexity are separate properties

Smoothness bounds curvature from above ( $f$ does not curve too fast). Strong convexity bounds curvature from below ( $f$ curves at least a certain amount). A function can be smooth but not strongly convex (e.g., $f(x) = |x|$ smoothed near $0$ ), or strongly convex but not smooth (e.g., $f(x) = x^2 + |x|$ ). You need both for the fast $O(\kappa \log(1/\epsilon))$ rate.

Watch Out

The step size 1/L is not always practical

The theoretical step size $\eta = 1/L$ requires knowing $L$ exactly, which is often unknown. In practice, you use line search or adaptive step sizes (Adam, AdaGrad). The theory with $\eta = 1/L$ gives a benchmark: this is the best GD can do, and practical methods should match or beat it.

Why Optimization is Not Separate from Learning Theory

The total error of a learning algorithm decomposes as:

$\underbrace{R(h_{\text{output}}) - R^*}_{\text{excess risk}} = \underbrace{R(h^*_{\mathcal{H}}) - R^*}_{\text{approximation}} + \underbrace{R(h_{\text{ERM}}) - R(h^*_{\mathcal{H}})}_{\text{estimation}} + \underbrace{R(h_{\text{output}}) - R(h_{\text{ERM}})}_{\text{optimization}}$

The optimization error is the gap between what the algorithm actually finds and the true ERM minimizer. Convex optimization theory directly controls this third term. If you can solve the ERM problem to $\epsilon$ -accuracy in $T$ iterations, and each iteration takes $O(nd)$ time, the total computational cost of learning is $O(ndT)$ .

Exercises

ExerciseCore

Problem

Prove that the function $f(x) = \frac{1}{2}x^\top A x - b^\top x$ is $\mu$ -strongly convex and $L$ -smooth when $A$ is symmetric with eigenvalues in $[\mu, L]$ . What is the condition number?

ExerciseCore

Problem

How many gradient descent iterations are needed to reach $\epsilon = 10^{-6}$ accuracy on a $\mu$ -strongly convex, $L$ -smooth function with $\kappa = 100$ ? Compare with the merely convex case (same $L$ , $\|x_0 - x^*\| = 1$ ).

ExerciseAdvanced

Problem

Show that adding $\ell_2$ regularization $\lambda\|w\|^2$ to a convex, $L$ -smooth function $f(w)$ produces a function that is $2\lambda$ -strongly convex and $(L + 2\lambda)$ -smooth. What is the new condition number?

Related Comparisons

References

Canonical:

Boyd & Vandenberghe, Convex Optimization (2004), Chapters 2-3, 9
Nesterov, Introductory Lectures on Convex Optimization (2004), Chapters 1-2
Nocedal & Wright, Numerical Optimization (2006), Chapters 2-3, 11
Bertsekas, Convex Optimization Algorithms (2015), Chapters 1-2

Current:

Bubeck, "Convex Optimization: Algorithms and Complexity" (2015), Found. & Trends in ML
Bottou, Curtis, Nocedal, "Optimization Methods for Large-Scale Machine Learning" (2018), SIAM Review

Next Topics

Natural next steps from convex optimization:

Regularization theory: how regularization connects optimization to generalization
Kernels and RKHS: convex optimization in infinite-dimensional function spaces
Online convex optimization: extending convex optimization to sequential, adversarial settings

Last reviewed: April 2026

Prerequisites

Foundations this topic depends on.

Differentiation in RnLayer 0A
Sets, Functions, and RelationsLayer 0A
Basic Logic and Proof TechniquesLayer 0A
Matrix Operations and PropertiesLayer 0A

Builds on This

Activation FunctionsLayer 1
Ascent Algorithms and Hill ClimbingLayer 1
Augmented Lagrangian and ADMMLayer 2
Bounded RationalityLayer 2
Conjugate Gradient MethodsLayer 2
Convex DualityLayer 0B
Coordinate DescentLayer 2
The EM AlgorithmLayer 2
Expected Utility TheoryLayer 2
Game Theory FoundationsLayer 2
Gradient Descent VariantsLayer 1
Interior Point MethodsLayer 3
K-Means ClusteringLayer 1
Kernels and Reproducing Kernel Hilbert SpacesLayer 3
Lasso RegressionLayer 2
Line Search MethodsLayer 2
Logistic RegressionLayer 1
Markov Decision ProcessesLayer 2
Minimax and Saddle PointsLayer 2
Mirror Descent and Frank-WolfeLayer 3
Nash EquilibriumLayer 2
Newton's MethodLayer 1
Online Convex OptimizationLayer 3
Optimizer Theory: SGD, Adam, and MuonLayer 3
Policy Gradient TheoremLayer 3
Preconditioned Optimizers: Shampoo, K-FAC, and Natural GradientLayer 3
Projected Gradient DescentLayer 2
Proximal Gradient MethodsLayer 2
Regularization TheoryLayer 2
Ridge RegressionLayer 2
Riemannian Optimization and Manifold ConstraintsLayer 3
Scaling LawsLayer 4
Stability and Optimization DynamicsLayer 2
Stochastic Approximation TheoryLayer 2
Support Vector MachinesLayer 2
Training Dynamics and Loss LandscapesLayer 4
Trust Region MethodsLayer 2

Next Topics

Regularization TheoryContinue →Kernels and RkhsContinue →