Consider two hikers, each blindfolded, trying to reach the lowest point of a mountain range at night. The first hiker walks through the Alps—a jagged landscape of peaks, valleys, ridges, and hidden ravines. They might descend into a valley that seems like the lowest point, only to learn later that a much deeper valley exists beyond the next ridge. Without global information, they're trapped by local geography.

The second hiker walks through a single giant bowl—a smooth, convex depression with one obvious lowest point. No matter where they start, following the downward slope leads inexorably to the same destination: the true bottom.

This metaphor captures the essence of local vs. global optimization. In machine learning, we're often the blindfolded hiker, using local gradient information to navigate loss landscapes we cannot fully observe. Whether we find the true optimum or get stuck in a suboptimal basin depends fundamentally on the geometry of our optimization problem.

Before proving anything, we need precise definitions. These definitions apply to minimization; for maximization, simply reverse the inequalities.

Definition: Global Minimum

A point $x^* \in \text{dom}(f)$ is a global minimum of $f$ if:

$$f(x^*) \leq f(x) \quad \forall x \in \text{dom}(f)$$

The function value at $x^*$ is the smallest possible over the entire domain.

Definition: Local Minimum

A point $x^*$ is a local minimum of $f$ if there exists $\epsilon > 0$ such that:

$$f(x^) \leq f(x) \quad \forall x \text{ with } |x - x^| < \epsilon$$

The function value at $x^*$ is the smallest in some neighborhood—but perhaps not globally.

The Fundamental Challenge:

Every global minimum is also a local minimum (just take $\epsilon$ large enough). But the converse fails spectacularly in general: a function can have many local minima, only some of which are global.

For optimization algorithms that only use local information (gradients, Hessians), there's no way to distinguish a local minimum from a global minimum without exploring the entire domain—which is computationally intractable for high-dimensional problems.

This is why convexity is so precious:

For convex functions, every local minimum is a global minimum.

This single theorem transforms optimization from an impossibly hard search problem into a tractable computation.

We now prove the central result that makes convex optimization tractable.

Theorem: Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be a convex function. If $x^$ is a local minimum of $f$, then $x^$ is a global minimum of $f$.

Proof:

Suppose $x^$ is a local minimum but not a global minimum. Then there exists some point $y$ with $f(y) < f(x^)$.

Since $x^$ is a local minimum, there exists $\epsilon > 0$ such that $f(x^) \leq f(x)$ for all $x$ with $|x - x^*| < \epsilon$.

Consider the line segment from $x^*$ toward $y$. For small enough $\theta > 0$, the point:

$$z = \theta y + (1 - \theta) x^* = x^* + \theta(y - x^*)$$

satisfies $|z - x^| = \theta |y - x^| < \epsilon$ (by choosing $\theta < \frac{\epsilon}{|y - x^*|}$).

By convexity of $f$:

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

Since $f(y) < f(x^*)$:

$$f(z) < \theta f(x^) + (1 - \theta) f(x^) = f(x^*)$$

But $z$ is within the $\epsilon$-neighborhood of $x^$, and $f(z) < f(x^)$, contradicting that $x^*$ is a local minimum.

Conclusion: Our assumption was wrong; $x^*$ must be a global minimum. $\square$

Corollary: Strict Convexity Implies Uniqueness

If $f$ is strictly convex and has a minimum, that minimum is unique.

Proof: Suppose $x^$ and $y^$ are both global minima with $x^* \neq y^$, so $f(x^) = f(y^) = f^$.

Consider $z = \frac{1}{2}x^* + \frac{1}{2}y^*$. By strict convexity:

$$f(z) < \frac{1}{2}f(x^) + \frac{1}{2}f(y^) = f^*$$

This contradicts $f^*$ being the minimum. $\square$

Corollary: Strong Convexity Guarantees Existence and Uniqueness

If $f$ is strongly convex, it has exactly one global minimum (assuming the domain is all of $\mathbb{R}^n$ or is closed and convex).

Strong convexity also provides convergence rate guarantees for optimization algorithms—we'll see this when studying gradient descent.

To appreciate convexity, we must understand what can go wrong without it. Non-convex optimization is notoriously difficult, and gradient-based methods offer no guarantees of finding global optima.

Common Pathologies in Non-Convex Landscapes:

The Rastrigin Function: A Classic Nightmare

The Rastrigin function is a standard benchmark for global optimization:

$$f(x) = 10n + \sum_{i=1}^{n} \left[ x_i^2 - 10 \cos(2\pi x_i) \right]$$

This function has:

• A global minimum at $x = 0$ with $f(0) = 0$
• Approximately $10^n$ local minima for $x \in [-5.12, 5.12]^n$

For $n = 10$, there are roughly 10 billion local minima. Gradient descent from a random starting point almost certainly finds a local (not global) minimum.

Non-Convexity in ML:

Many important ML problems are non-convex:

• Neural network training (composition of nonlinearities)
• Matrix factorization / collaborative filtering
• Clustering (e.g., k-means objective)
• Deep reinforcement learning policy optimization

For these problems, we use heuristics, multiple random restarts, and theoretical results about "benign" non-convexity (e.g., certain neural networks have no spurious local minima).

For convex functions, we can characterize global minima using first-order (gradient) and sometimes second-order (Hessian) conditions.

First-Order Condition (Unconstrained):

For a differentiable convex function $f$ on $\mathbb{R}^n$, $x^*$ is a global minimum if and only if:

$$\nabla f(x^*) = 0$$

Proof: We showed earlier that $f(y) \geq f(x) + \nabla f(x)^T(y - x)$ for convex $f$. At $x^$ with $\nabla f(x^) = 0$, this becomes $f(y) \geq f(x^*)$ for all $y$—exactly the definition of global minimum.

Conversely, if $x^$ is a global minimum and $\nabla f(x^) \neq 0$, we can decrease $f$ by moving in the direction $-\nabla f(x^*)$.

First-Order Condition (Constrained):

For minimizing convex $f$ over convex set $C$, $x^*$ is a global minimum if and only if:

$$\nabla f(x^)^T (y - x^) \geq 0 \quad \forall y \in C$$

This says the gradient must point "outward" from the constraint set at $x^*$: any feasible direction is non-descent.

For an interior point ($x^$ strictly inside $C$), this reduces to $\nabla f(x^) = 0$.

For a boundary point, the gradient can be nonzero but must point away from the feasible region.

Second-Order Condition:

For twice-differentiable convex $f$, if $\nabla f(x^) = 0$ and $\nabla^2 f(x^) \succ 0$ (positive definite), then $x^*$ is a strict local minimum—and by convexity, a strict global minimum.

For strongly convex $f$ (where $\nabla^2 f \succeq m I$ everywhere with $m > 0$), any stationary point is automatically a strict global minimum.

The "loss landscape" metaphor is powerful but must be used carefully. Let's refine our intuition.

Convex Landscapes:

A convex function's sublevel sets are convex (nested "bowls"). As you descend, the feasible region shrinks but remains well-behaved:

• No isolated pockets or "holes" to get trapped in
• No ridges separating different basins
• Gradient information is always useful: moving downhill makes global progress

Non-Convex Landscapes:

Non-convex functions exhibit complex topology:

• Multiple disconnected regions at each height level
• Saddle points that look flat but have escape routes
• Ridges and valleys that can mislead gradient-based methods
• Basin boundaries that depend sensitively on initialization

Benign Non-Convexity:

Recent ML research has identified cases where non-convex problems are still tractable:

1. No spurious local minima: All local minima are global (even though the function isn't convex). Examples: certain matrix sensing problems, some neural network architectures.

2. Saddle points are escapable: With noise or second-order methods, saddle points can be escaped efficiently.

3. Local minima are "good enough": Even if not global, local minima may generalize well in practice.

4. Overparameterization helps: Neural networks with more parameters than data points often have loss landscapes where gradient descent finds global minima.

These results don't make non-convex optimization equivalent to convex—the guarantees are weaker and problem-specific—but they explain why deep learning works in practice.

Understanding local vs. global optima has direct implications for ML practice.

Convex ML Problems (Global Optimality Guaranteed):

Non-Convex ML Problems (No Guarantees):

Design Principles:

1. Start convex when possible: If a convex model achieves acceptable accuracy, prefer it over non-convex alternatives.

2. Convexify when you can: Sometimes a non-convex problem can be relaxed to a convex one (e.g., nuclear norm relaxation for rank minimization).

3. Understand your landscape: For non-convex problems, analyze whether the landscape is "benign" (no bad local minima) or challenging.

4. Use multiple initializations: For non-convex problems, run optimization from multiple starting points and take the best result.

5. Regularize toward convexity: Adding L2 regularization makes objectives "more convex" (increases minimum curvature).

The connection between convexity and optimization goes deeper through the lens of curvature.

Curvature and the Hessian:

The Hessian matrix $\nabla^2 f(x)$ captures the local curvature of $f$ at $x$. Its eigenvalues determine:

• All eigenvalues $\geq 0$: Positive semidefinite (PSD) Hessian → locally convex
• All eigenvalues $> 0$: Positive definite (PD) Hessian → strictly locally convex
• All eigenvalues $\geq m > 0$: Bounded below → strongly convex
• Some eigenvalues $< 0$: Hessian has negative eigenvalue → non-convex; if at stationary point, it's a saddle point

Condition Number:

For a strongly convex function such that $mI \preceq \nabla^2 f(x) \preceq MI$ for all $x$, the condition number is:

$$\kappa = \frac{M}{m}$$

This measures how "stretched" the landscape is. A well-conditioned problem ($\kappa$ close to 1) is approximately isotropic—all directions have similar curvature. A poorly conditioned problem ($\kappa \gg 1$) has very different curvatures in different directions, causing gradient descent to zigzag.

Convergence Rate Implications:

For gradient descent with step size $\eta$, minimizing a $m$-strongly convex function with $M$-Lipschitz gradient:

$$f(x_k) - f(x^) \leq \left(1 - \frac{m}{M}\right)^k (f(x_0) - f(x^))$$

The convergence rate depends on $\kappa = M/m$. Low condition number means fast convergence; high condition number means slow convergence.

This is why ill-conditioned problems (long narrow valleys) are hard for gradient descent: they have high condition numbers, so the convergence factor $(1 - 1/\kappa)$ is close to 1.

We've established one of the most important results in optimization—the equivalence of local and global minima for convex functions. Let's consolidate:

What's Next:

Knowing that local minima are global is powerful, but how do we find them? The next pages will develop the first-order and second-order optimality conditions that characterize minima for convex functions, providing actionable stopping criteria for optimization algorithms.