Convex Optimization

Imagine you're lost in a foggy mountain landscape, trying to find the lowest valley. If the terrain is arbitrary—with cliffs, plateaus, and hidden ravines—your task is nearly impossible. You might descend into a local depression, only to realize you're still far above the true valley floor hidden somewhere beyond.

But now imagine the terrain forms a single, smooth bowl. No matter where you start, if you simply walk downhill, you're guaranteed to reach the absolute lowest point. There are no false bottoms, no deceptive dips—just one inevitable destination.

This is the essence of convexity—the mathematical property that transforms intractable optimization into a guaranteed journey to the global optimum. In machine learning, convexity is not merely a convenience; it's the fundamental distinction between algorithms that provably work and algorithms that hope for the best.

A convex set captures a simple but powerful geometric idea: if you can see from any point to any other point without leaving the set, the set is convex.

Formal Definition:

A set $C \subseteq \mathbb{R}^n$ is convex if for any two points $x, y \in C$ and any scalar $\theta \in [0, 1]$, the point

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

In other words, the entire line segment connecting $x$ and $y$ lies within $C$. This seemingly simple property has profound implications for optimization.

Understanding the Convex Combination:

The expression $\theta x + (1 - \theta) y$ with $\theta \in [0, 1]$ is called a convex combination of $x$ and $y$. Let's understand this geometrically:

• When $\theta = 0$: the point is $y$
• When $\theta = 1$: the point is $x$
• When $\theta = 0.5$: the point is the midpoint $\frac{x + y}{2}$
• For any $\theta \in (0, 1)$: the point lies on the line segment between $x$ and $y$

The convex combination parameters always sum to 1: $\theta + (1 - \theta) = 1$. This constraint ensures we're talking about points on the line segment, not the extended line.

Understanding which operations preserve convexity allows us to build complex convex sets from simpler ones—a crucial skill for formulating optimization problems in machine learning.

Fundamental Convexity-Preserving Operations:

Why Intersection is Central:

The fact that intersection preserves convexity is enormously powerful. Many important convex sets in ML can be expressed as intersections of simpler convex sets:

• Polyhedra = intersection of halfspaces
• Polytopes = bounded polyhedra (intersection of halfspaces forming a bounded region)
• Norm balls = intersection of infinitely many halfspaces (for polyhedral norms like $L_1$, $L_\infty$)
• Positive semidefinite cone = intersection of halfspaces defined by all possible quadratic forms

This compositional view allows us to verify convexity of complex sets by decomposing them into simpler convex building blocks.

While convex sets describe where we can search, convex functions describe what we're optimizing. A convex function is one where the graph lies below any line segment connecting two points on the graph—it "curves upward."

Formal Definition:

A function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is convex if its domain $\text{dom}(f)$ is a convex set and for all $x, y \in \text{dom}(f)$ and $\theta \in [0, 1]$:

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

The left side is the function value at the interpolated point; the right side is the linear interpolation of function values. For convex functions, the actual value is always at or below the interpolation.

Strict Convexity:

A function is strictly convex if the inequality is strict for $\theta \in (0, 1)$ and $x eq y$:

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

Strict convexity guarantees a unique global minimum (if one exists), not just that local minima are global.

Strong Convexity:

A function $f$ is $m$-strongly convex (with $m > 0$) if:

$$f(\theta x + (1 - \theta) y) \leq \theta f(x) + (1 - \theta) f(y) - \frac{m}{2} \theta (1 - \theta) |x - y|^2$$

Strong convexity implies strict convexity but adds a quantitative "curvature" bound. This has crucial implications for optimization convergence rates.

Concave Functions:

A function $f$ is concave if $-f$ is convex. Equivalently:

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

Since minimizing a convex function is equivalent to maximizing a concave function, all our convexity theory applies to maximization problems with concave objectives.

Building intuition requires familiarity with common convex functions. These form the building blocks for constructing convex objectives in machine learning.

Understanding Through Key Examples:

1. Quadratic Functions:

The function $f(x) = \frac{1}{2} x^T Q x + b^T x + c$ where $Q$ is a symmetric matrix is:

• Convex if and only if $Q \succeq 0$ (positive semidefinite)
• Strictly convex if and only if $Q \succ 0$ (positive definite)
• $\lambda_{\min}(Q)$-strongly convex if $Q \succ 0$

This is why the Hessian (second derivative matrix) plays such a central role in convexity verification.

2. Norms:

Every norm on $\mathbb{R}^n$ is convex. This follows from the triangle inequality:

$$|\theta x + (1 - \theta) y| \leq |\theta x| + |(1 - \theta) y| = \theta |x| + (1 - \theta) |y|$$

This is why L1 and L2 regularization terms are convex, making regularized optimization tractable.

3. Log-Sum-Exp (Softmax):

$$f(x) = \log\left(\sum_{i=1}^{n} e^{x_i}\right)$$

This is convex and serves as a smooth approximation to $\max_i x_i$. It's fundamental to softmax classification and attention mechanisms.

Just as certain operations preserve set convexity, analogous operations preserve function convexity. These rules are essential for constructing and verifying convex objectives.

The Power of Pointwise Maximum:

The fact that $\max$ preserves convexity is surprisingly powerful and underlies many ML loss functions:

Hinge Loss: $\ell(y, \hat{y}) = \max(0, 1 - y \cdot \hat{y})$

This is the maximum of two affine functions (0 and $1 - y \cdot \hat{y}$), hence convex.

ReLU Activation: $\text{ReLU}(x) = \max(0, x)$

While individual ReLUs are convex, compositions of linear layers and ReLUs create non-convex networks—an important distinction.

Piecewise Linear Convex Functions:

Any piecewise linear convex function can be written as a maximum of affine functions: $$f(x) = \max_{i=1,\ldots,k} (a_i^T x + b_i)$$

This representation is central to problems like linear programming robustness and the design of activation functions.

Jensen's Inequality is arguably the single most important result in convex analysis. It generalizes the definition of convexity from two points to arbitrary weighted combinations.

Theorem (Jensen's Inequality):

Let $f$ be a convex function, let $x_1, \ldots, x_k$ be points in the domain of $f$, and let $\lambda_1, \ldots, \lambda_k$ be non-negative weights summing to 1. Then:

$$f\left(\sum_{i=1}^{k} \lambda_i x_i\right) \leq \sum_{i=1}^{k} \lambda_i f(x_i)$$

In words: the function value at the weighted average is at most the weighted average of function values.

Proof Intuition:

Jensen's inequality follows from repeated application of the basic convexity definition. For two points, it's exactly the definition. For three points, we first combine two of them:

$$f(\lambda_1 x_1 + \lambda_2 x_2 + \lambda_3 x_3) = f\left((\lambda_1 + \lambda_2) \cdot \frac{\lambda_1 x_1 + \lambda_2 x_2}{\lambda_1 + \lambda_2} + \lambda_3 x_3\right)$$

Then apply convexity twice, using the fact that $\frac{\lambda_1 x_1 + \lambda_2 x_2}{\lambda_1 + \lambda_2}$ is itself a convex combination.

Applications in Machine Learning:

Jensen's inequality appears throughout ML:

Example: Proving KL Divergence is Non-negative

The Kullback-Leibler divergence is:

$$D_{KL}(p | q) = \mathbb{E}_p\left[\log \frac{p(x)}{q(x)}\right] = -\mathbb{E}_p\left[\log \frac{q(x)}{p(x)}\right]$$

Since $-\log$ is convex and $\frac{q(x)}{p(x)}$ is a ratio of densities with $\mathbb{E}_p\left[\frac{q(x)}{p(x)}\right] = \int p(x) \cdot \frac{q(x)}{p(x)} dx = \int q(x) dx = 1$:

$$D_{KL}(p | q) = -\mathbb{E}_p\left[\log \frac{q(x)}{p(x)}\right] \geq -\log \mathbb{E}_p\left[\frac{q(x)}{p(x)}\right] = -\log(1) = 0$$

Jensen's gives us this fundamental non-negativity of KL divergence.

The connection between convex functions and convex sets runs deeper than analogy—there's a precise equivalence through the concept of epigraphs.

Definition: Epigraph

The epigraph of a function $f: \mathbb{R}^n \rightarrow \mathbb{R}$ is the set of points "on or above" the graph:

$$\text{epi}(f) = {(x, t) \in \mathbb{R}^{n+1} : x \in \text{dom}(f), t \geq f(x)}$$

Fundamental Theorem:

A function $f$ is convex if and only if its epigraph $\text{epi}(f)$ is a convex set.

This equivalence is powerful: it means we can translate any statement about convex functions into a statement about convex sets, and vice versa.

Sublevel Sets:

The $\alpha$-sublevel set of $f$ is:

$$S_\alpha = {x \in \text{dom}(f) : f(x) \leq \alpha}$$

Key Property: If $f$ is convex, all its sublevel sets are convex.

Proof: Let $x, y \in S_\alpha$, so $f(x) \leq \alpha$ and $f(y) \leq \alpha$. For any $\theta \in [0, 1]$:

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

So $\theta x + (1 - \theta) y \in S_\alpha$, proving $S_\alpha$ is convex.

Caution: The converse is FALSE—having convex sublevel sets doesn't imply the function is convex. The function $f(x) = \sqrt{|x|}$ has convex sublevel sets (intervals around 0) but is not convex (it's concave for $|x| > 0$).

Quasiconvexity:

A function with convex sublevel sets is called quasiconvex. This is a strictly weaker condition than convexity:

$$f \text{ convex} \Rightarrow f \text{ quasiconvex}$$

but the converse doesn't hold. Quasiconvex functions still have nice optimization properties (local minima are still global for strictly quasiconvex functions), but the analysis is more delicate.

Practical Use of Sublevel Sets:

In constrained optimization, we often restrict our search to a sublevel set:

$$\min_x , g(x) \quad \text{subject to} \quad f(x) \leq \alpha$$

If $f$ is convex, the feasible region $S_\alpha$ is convex, preserving the tractability of the optimization.

When functions are differentiable, we gain powerful calculus-based characterizations of convexity that are often easier to verify than the basic definition.

First-Order Characterization:

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

$$f(y) \geq f(x) + abla f(x)^T (y - x)$$

This says the function lies above its tangent hyperplane at every point. The tangent is a global underestimator.

Second-Order Characterization:

If $f$ is twice differentiable, then $f$ is convex if and only if the Hessian is positive semidefinite everywhere:

$$ abla^2 f(x) \succeq 0 \quad \forall x \in \text{dom}(f)$$

For strict convexity, we need $ abla^2 f(x) \succ 0$ (positive definite).

For $m$-strong convexity, we need $ abla^2 f(x) \succeq m I$ (eigenvalues at least $m$).

Practical Hessian Analysis:

For functions of the form $f(x) = g(Ax)$ where $g$ is convex:

$$ abla^2 f(x) = A^T abla^2 g(Ax) A$$

This is PSD whenever $ abla^2 g \succeq 0$, confirming that composition with affine transformations preserves convexity.

We've established the foundational concepts of convex analysis that underpin all tractable optimization in machine learning. Let's consolidate the key insights:

What's Next:

With the definitions of convex sets and functions established, we'll explore why convexity matters for optimization. The next page examines local vs. global optima — showing that for convex problems, we never need to worry about getting stuck in suboptimal solutions.