Local vs global minima - maxima — AI-ML notes

Overview

Understanding the difference between local and global extrema is critical in machine learning because gradient descent and other optimization algorithms can get trapped in local minima, preventing us from finding the best possible solution. This concept explains why neural network training is hard and why we need techniques like random restarts, momentum, and adaptive learning rates.

Figure — Local vs global minima - maxima

Core Concepts

Definition Formal Definitions

Let $f: \mathbb{R}^n \to \mathbb{R}$ be a function and $\mathbf{x}^* \in \mathbb{R}^n$ a point. Local Minimum: $\mathbf{x}^*$ is a local minimum if there exists $\epsilon > 0$ such that: $f(\mathbf{x}^*) \leq f(\mathbf{x}) \quad \forall \mathbf{x} \text{ where } \|\mathbf{x} - \mathbf{x}^*\| < \epsilon$ Global Minimum: $\mathbf{x}^*$ is a global minimum if: $f(\mathbf{x}^*) \leq f(\mathbf{x}) \quad \forall \mathbf{x} \in \text{domain}$

Why these definitions work: The local definition uses a "neighborhood" ( $\epsilon$ -ball)—it only compares nearby points. The global definition compares against every possible point. Local is a weaker condition; every global minimum is also local, but not vice versa.

(Analogous definitions hold for maxima by reversing inequalities.)

First-Principles Derivation

How Do We Identify Extrema?

Step 1: Necessary Condition (Critical Points)

At any local extremum, if $f$ is differentiable, the gradient must vanish:

$\nabla f(\mathbf{x}^*) = \mathbf{0}$

Why? Suppose $\mathbf{x}^*$ is a local minimum but $\nabla f(\mathbf{x}^*) \neq \mathbf{0}$ . Then there exists a direction $\mathbf{d} = -\nabla f(\mathbf{x}^*)$ where $f$ decreases (by definition of gradient). Moving slightly in that direction: $\mathbf{x}^* + \epsilon \mathbf{d}$ gives $f(\mathbf{x}^* + \epsilon \mathbf{d}) < f(\mathbf{x}^*)$ for small $\epsilon > 0$ , contradicting that $\mathbf{x}^*$ is a minimum.

But: $\nabla f = \mathbf{0}$ is necessary but not sufficient. Critical points can be minima, maxima, or saddle points.

Step 2: Second-Order Condition (Classifying Critical Points)

For a function $f: \mathbb{R}^n \to \mathbb{R}$ , compute the Hessian matrix:

$H_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}$

At a critical point $\mathbf{x}^*$ :

Local minimum: $H$ is positive definite (all eigenvalues $> 0$ )
Local maximum: $H$ is negative definite (all eigenvalues $< 0$ )
Saddle point: $H$ has mixed-sign eigenvalues

Why does this work? The second-order Taylor expansion near $\mathbf{x}^*$ is:

$f(\mathbf{x}^* + \mathbf{h}) \approx f(\mathbf{x}^*) + \nabla f(\mathbf{x}^*)^T \mathbf{h} + \frac{1}{2} \mathbf{h}^T H \mathbf{h}$

Since $\nabla f(\mathbf{x}^*) = \mathbf{0}$ :

$f(\mathbf{x}^* + \mathbf{h}) - f(\mathbf{x}^*) \approx \frac{1}{2} \mathbf{h}^T H \mathbf{h}$

If $H$ positive definite: $\mathbf{h}^T H \mathbf{h} > 0$ for all $\mathbf{h} \neq \mathbf{0}$ → function increases in all directions → local min
If $H$ negative definite: opposite → local max
If mixed eigenvalues: increases in some directions, decreases in others → sadle

Step 3: Distinguishing Local from Global

There's no local test for global optimality. You must:

Find all critical points
Evaluate $f$ at each
Check boundaries (if domain is bounded)
Compare all values—the smallest is the global minimum

Why is this hard in ML? Neural networks have millions of parameters, making exhaustive search impossible. We rely on optimization algorithms and empirical tricks.

Worked Examples

Worked example Example 1: One-Dimensional Function

Consider $f(x) = x^3 - 3x^2 + 2$ on $x \in [-1, 3]$ .

Step 1: Find critical points $f'(x) = 3x^2 - 6x = 3x(x - 2)$ Critical points: $x = 0, x = 2$

Why this step? We need $f'(x) = 0$ to find where the slope is flat (necessary condition for extrema).

Step 2: Second derivative test $f''(x) = 6x - 6$

At $x = 0$ : $f''(0) = -6 < 0$ → local maximum
At $x = 2$ : $f''(2) = 6 > 0$ → local minimum

Why this step? The sign of $f''$ tells us if the function curves upward (minimum) or downward (maximum).

Step 3: Evaluate at critical points and boundaries

$f(-1) = -1 - 3 + 2 = -2$
$f(0) = 2$ (local max)
$f(2) = 8 - 12 + 2 = -2$ (local min)
$f(3) = 27 - 27 + 2 = 2$

Result: The global minimum is $-2$ (achieved at both $x = -1$ and $x = 2$ ). The global maximum is $2$ , and it is achieved at two points: the interior local max $x = 0$ and the right endpoint $x = 3$ . So $x = 0$ is a global maximum here—just not the unique one. This illustrates a subtle point: a local extremum can also be a global extremum, and global extrema need not be unique.

Worked example Example 2: Two-Dimensional Loss Surface

Consider $f(x, y) = x^2 + y^2 - 2\cos(2\pi x) - 2\cos(2\pi y)$ (a simplified Rastrigin function).

Step 1: This function has many local minima due to the oscillating cosine terms.

Intuition: The $x^2 + y^2$ term creates a parabolic bowl (one global min at origin). The cosine terms add "bumps" that create multiple valleys.

Step 2: Compute gradient $\nabla f = \begin{bmatrix} 2x + 4\pi \sin(2\pi x) \\ 2y + 4\pi \sin(2\pi y) \end{bmatrix}$

Why this step? We need critical points where both partial derivatives vanish.

Step 3: Critical points occur where:

$2x + 4\pi \sin(2\pi x) = 0$
$2y + 4\pi \sin(2\pi y) = 0$ These equations have multiple solutions! For example, $(0, 0)$ is one (where $\sin(0) = 0$ ), but so is approximately $(0.5, 0)$ and many others.

Step 4: Evaluate

$f(0, 0) = 0 - 2 - 2 = -4$ ← global minimum
Other critical points give higher values (local minima)

Why this matters: If gradient descent starts at $(1.5, 1.5)$ , it might get stuck in a local minimum near $(1, 1)$ and never reach the global minimum at $(0, 0)$ .

Worked example Example 3: Neural Network Loss Landscape

A neural network's loss $\mathcal{L}(\mathbf{w})$ as a function of weights $\mathbf{w}$ is non-convex with:

Countless local minima (due to non-linear activations)
Sadle points (often more common than local minima in high dimensions)
One global minimum (lowest achievable loss)

Practical implication:

Starting from random initialization, SGD follows $\mathbf{w}_{t+1} = \mathbf{w}_t - \eta \nabla \mathcal{L}(\mathbf{w}_t)$
Might converge to a local minimum with training loss =0.15
Global minimum might have training loss = 0.08
We use techniques like momentum, learning rate schedules, and multiple random restarts to escape poor local minima

Why this step? Understanding this explains why identical architectures can achieve different final accuracies based purely on initialization and optimization hyperparameters.

Common Mistakes

Connections to Machine Learning

Gradient Descent Convergence:

Vanilla gradient descent with small learning rate converges to a local minimum (or saddle point)
No guarantee of finding the global minimum in non-convex problems
Links to: Gradient Descent, Learning Rate Tuning

Optimization Algorithms:

Momentum helps escape shallow local minima by accumulating velocity
Simulated anealing and genetic algorithms use randomness to explore the landscape
Adam optimizer adapts learning rates per parameter
Links to: Momentum and Nesterov, Adam Optimizer

Loss Surface Geometry:

High-dimensional spaces have exponentially many sadle points
Mode connectivity: different local minima often lie on connected low-loss paths
Links to: Loss Landscape Visualization, Neural Network Optimization

Regularization Effects:

L2 regularization modifies the loss landscape to be "smother"
Can turn sharp local minima into broader basins, aiding generalization
Links to: Regularization Techniques, Generalization in Deep Learning

Active Recall Practice

Recall Explain to a 12-Year-Old (Feynman Technique)

Imagine you're playing a video game where you're blindfolded and trying to find the lowest point in a huge park with hills and valleys. You can only feel if the ground is sloping up or down under your feet.

A local minimum is like finding a small dip—maybe a pudle. If you take any step from that pudle, you go uphill, so it feels like the lowest point. But there might be a huge lake on the other side of the park that's way lower—that's the global minimum.

In machine learning, the "park" is all the possible ways to set your AI's brain (the numbers in the neural network). The "height" is how many mistakes the AI makes. We want the lowest point (fewest mistakes), but our algorithm (like taking downhill steps) might get stuck in a pudle instead of finding the lake.

That's why training AI is tricky—we need clever tricks to help it explore more of the park, not just settle for the first low spot it finds!

Think: "When building with LEGOs, you might make a small tower (local max) but miss that you could build a huge castle (global max) if you explored more pieces."

Flashcards

#flashcards/ai-ml

What is a local minimum? :: A point where the function value is lower than all nearby points within some neighborhood, but not necessarily the lowest point overall.

What is a global minimum?

The point where the function achieves its absolute lowest value across the entire domain.

What is the necessary condition for a point to be a local extremum?

The gradient must be zero:

\nabla f(\mathbf{x}^*) = \mathbf{0}

(making it a critical point).

How do you use the Hessian to classify a critical point?

Check eigenvalues—positive definite (all positive) means local min, negative definite means local max, mixed signs mean saddle point.

Why can gradient descent get stuck in local minima?

It only takes downhill steps based on local gradient information, so it converges to the first local minimum it encounters without exploring the full landscape.

Is every local minimum also a global minimum?

No—only in convex functions. In non-convex functions (like neural networks), local minima can have higher values than the global minimum.

Can a local extremum also be a global extremum?

Yes—an interior local extremum can coincide with the global extremum, and global extrema need not be unique (they can be achieved at multiple points, e.g. an interior point and an endpoint).

What is a saddle point?

A critical point where the Hessian has both positive and negative eigenvalues—the function decreases in some directions and increases in others, so it's neither a min nor max.

Why are saddle points common in high-dimensional optimization?

In high dimensions, the chance that all eigenvalues have the same sign (all positive or all negative) decreases exponentially, making saddle points more likely than local minima.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab bhi hum machine learning model train karte hain, toh ek "loss function" hota hai jo bata hai ki model kitna galat hai. Optimization ka matlab hai us loss ko kam karna—minimum dhoondhna. Lekin problem yeh hai ki local minimum aur global minimum mein fark hota hai.

Local minimum ek aisa point hai jahan loss apne as-pas ke points se kam hai, matlabagar thoda left ya right jao toh loss badhta hai. Lekin pore landscape mein dekhoge toh kahin aur ek aur bhi neeche point mil sakta hai—woh global minimum hai. Jaise ek gaon mein sabse neechi jagah ek kuan ho, lekin pore district mein ek gehri nadi ho—woh nadi global minimum hai.

Gradient descent jaisa algorithm sirf neeche ki taraf steps leta hai.Agar woh ek chhote kuan mein fas gaya, toh woh wahi ruk jayega, chahe gehri nadi kahi aur ho. Isliye deep learning mein hum momentum, adaptive learning rates, ya multiple random starts use karte hain taki algorithm landscape explore kar sake aur ek acha minimum dhundh sake. Non-convex functions (jaise neural networks) mein yeh problem bohot zyada hoti hai kyunki bahut sare local minima hote hain. Samajhna zaroori hai ki har critical point (jahan gradient zero ho) minimum nahi hota—woh sadle point bhi ho sakta hai, jahan kuch directions

Local vs global minima - maxima