11.3 Gradients and Optimization: From Descent Direction to Verifiable Solutions

A gradient describes only the function's first-order behavior at the current point. Moving in the negative-gradient direction is a natural start, but an optimizer must still choose a step size, define a stopping rule, handle constraints, and determine whether the result is a local minimum, a saddle point, or a provable global solution.

Learning Objectives

• Derive gradient descent from a first-order local approximation;
• Distinguish between convex problems, local minima, saddle points, and stationary points;
• Understand the roles of learning rate, stochastic gradients, and momentum;
• Build a more reliable optimization checklist than simply "the loss decreased."

1. Getting a Descent Step from a Local Model

For a differentiable function $f$, near point $\mathbf{x}$, we have:

$$f(\mathbf{x}+\mathrm{\Delta }\mathbf{x})\approx f(\mathbf{x})+\mathrm{\nabla }f(\mathbf{x}{)}^{\mathsf{T}}\mathrm{\Delta }\mathbf{x}.$$

For a nonzero gradient under the Euclidean norm, the negative gradient points in the direction of steepest local descent, leading to the update:

$${\mathbf{x}}_{t+1}={\mathbf{x}}_t-{\eta }_t\mathrm{\nabla }f({\mathbf{x}}_t),$$

where ${\eta }_t>0$ is the step size or learning rate.

This derivation is local. If the step size is too large, the first-order approximation breaks down, potentially overshooting the minimum or diverging entirely. If it's too small, progress becomes sluggish, and the algorithm may appear to stall within numerical precision limits.

2. A Checkable Single-Variable Example

For the function

$$f(x)=x^2+3x+2,$$

the derivative is $f^{\prime }(x)=2x+3$, and the analytical minimum occurs at $x=-1.5$.

def loss(x: float) -> float:
    return x * x + 3 * x + 2

def gradient(x: float) -> float:
    return 2 * x + 3

x = 8.0
learning_rate = 0.2

for step in range(100):
    grad = gradient(x)
    if abs(grad) < 1e-10:
        break
    x -= learning_rate * grad

print(f"{x:.8f} {loss(x):.8f}")   # -1.50000000 -0.25000000
print(abs(gradient(x)) < 1e-10)  # True

This problem is a strictly convex quadratic function with a very clean structure. Extending its behavior directly to neural networks ignores non-convexity, stochastic gradient descent, pathological curvature, and parameter redundancy.

The step-size boundary follows directly. Let $e_t=x_t+1.5$; then $e_{t+1}=(1-2\eta )e_t$. Unless the initial point is already optimal, convergence holds exactly for $0<\eta <1$. At $\eta =0.5$ one update reaches the minimum; $\eta =1$ oscillates between two points without shrinking, and $\eta >1$ grows in amplitude. Different curvature changes this range.

3. Stationary Points Do Not Necessarily Mean Minima

A point where $\mathrm{\nabla }f(\mathbf{x})=0$ is called a stationary point, and it may represent:

• A local minimum;
• A local maximum;
• A saddle point;
• A higher-order flat point.

In one dimension, the second derivative can help determine the nature of the stationary point. For multivariate functions, the Hessian matrix is composed of second-order partial derivatives:

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

For a function twice continuously differentiable near an interior stationary point, a positive-definite Hessian at that point guarantees a strict local minimum; negative definite gives a strict local maximum, and indefinite gives a saddle. A positive-semidefinite Hessian is inconclusive: $x^4$ and $-x^4$ have zero Hessians at zero but give a minimum and maximum respectively. Boundary points also require feasible-direction analysis.

If the feasible set is convex and the objective is convex on it, any local minimum is also a global minimum. If the function is strictly convex, there is at most one minimum. However, gradient descent alone does not guarantee convergence: additional constraints on smoothness, step size, and other factors are required. For general non-convex functions, it is not safe to claim that the algorithm will converge to a local optimum, instead, it might get stuck near saddle points, oscillate, or diverge entirely.

Strict convexity gives at most one minimizer, not existence. The strictly convex function $e^x$ on the real line approaches infimum 0 without attaining it at any finite point. For unconstrained differentiable convex problems, any stationary point is globally optimal; with constraints, an optimum need not have zero ordinary gradient.

4. Learning Rate Control for the Trustworthy Range of Local Models

Common learning rate strategies:

• Fixed learning rate: simple, but requires manual tuning;
• Decaying learning rate: reduces oscillations in later stages;
• Line search: attempts to satisfy the sufficient decrease condition;
• Adaptive methods: adjust effective step sizes for different parameters based on historical gradients.

Adam, RMSprop, and momentum-based SGD all use historical information, but they differ in behavior, memory overhead, and convergence properties. It is incorrect to assume that all of them are equivalent across all problems simply because they ultimately subtract some update amount.

One form of momentum is:

$${\mathbf{v}}_{t+1}=\beta {\mathbf{v}}_t+\mathrm{\nabla }f({\mathbf{x}}_t),{\mathbf{x}}_{t+1}={\mathbf{x}}_t-\eta {\mathbf{v}}_{t+1}.$$

This formulation accumulates velocity when gradients point in the same direction, helping to smooth out oscillations in narrow valleys. However, it also introduces new hyperparameters and risks of overshooting.

This is an unnormalized momentum convention, commonly with $0\le \beta <1$ and zero initial velocity. Some implementations multiply the gradient by $1-\beta$, changing the learning-rate scale. Check conventions before comparing formulas.

5. Full-Batch, Stochastic, and Mini-Batch Gradients

The objective in machine learning is often expressed as the average of sample losses:

$$F(\mathbf{w})=\frac{1}{N}\sum _{i=1}^N{\ell }_i(\mathbf{w}).$$

• Full-batch gradient uses all samples per step, providing stable updates but at a high computational cost;
• Stochastic gradient uses only one sample per step, offering low cost but introducing significant noise;
• Mini-batch gradient strikes a balance between hardware parallelism, estimation noise, and throughput.

Randomness can sometimes help escape flat regions of the loss landscape, but it does not guarantee global optimality. The sampling strategy, batch size, and data ordering all influence the training trajectory.

For differentiable sample losses, drawing one sample uniformly conditional on the current parameters makes its gradient an unbiased estimate of the empirical mean gradient. Nonuniform sampling needs appropriate weights; dependence, fixed order, and stateful preprocessing can change the argument. Full batches remove this sampling noise but can still diverge with excessive step sizes.

6. Constrained Optimization Cannot Be Reduced to Simple Updates

If parameters must satisfy constraints (such as non-negative probabilities that sum to one) standard gradient descent may drive the solution outside the feasible region. Common approaches include:

• Projected gradient: After updating, project the parameters back into the feasible set;
• Reparameterization: Use structured functions like softmax to enforce constraints inherently;
• Lagrange multipliers: Analyze necessary conditions under equality constraints;
• Penalty or barrier methods: Transform constraint violations into the objective function.

Euclidean projection onto a nonempty closed convex set is unique. Softmax with finite parameters produces strictly positive probabilities and cannot exactly represent simplex-boundary zeros, so reparameterization can change which feasible points are representable. Below we minimize (x-2)² with 0≤x≤1, clipping each update back to the interval:

def constrained_gradient(x):
    return 2 * (x - 2)

def project(x):
    return min(1.0, max(0.0, x))

x, eta = 0.0, 0.25
for _ in range(5):
    x = project(x - eta * constrained_gradient(x))
mapping = (x - project(x - eta * constrained_gradient(x))) / eta
print(x, constrained_gradient(x), mapping)  # 1.0 -2.0 0.0

The optimum is 1, where the ordinary gradient is still -2 but another projected update changes nothing: mapping is zero. Constrained problems need projected-gradient or suitable KKT checks instead of always waiting for an ordinary zero gradient. Projection onto a general nonconvex set need not be unique.

7. Checklist for Verifying Optimization Results

Before stopping training, at least verify the following:

1. The objective trend matches the method; stochastic gradients need not decrease it every step;
2. A stationarity residual appropriate to the constraints, or the update size, is sufficiently small;
3. No NaN, infinity, or obvious oscillations are present;
4. Constraints are being satisfied;
5. Validation set metrics align with the training objectives;
6. Results remain consistent when initial values or random seeds are changed;
7. Numerical gradient checks validate the automatic differentiation results.

Looking only at training loss hides issues like overfitting, data leakage, and incorrect objective functions. The optimizer only searches for what you've defined, it does not evaluate whether that objective reflects actual real-world needs.

Common Misconceptions

• Negative gradient points to global minimum: It only indicates the local descent direction at the current point.
• Gradient zero means training is successful: It could also signal a saddle point, a local maximum, or numerical underflow.
• Loss reduction means the model is correct: Incorrect labels, leaked features, or inappropriate objectives can still be optimized.
• Adaptive optimizers don’t need a learning rate: They still rely on global step size and other critical hyperparameters.

Exercise

1. Modify the learning rate in the single-variable example and observe the regions of stability, oscillation, and divergence.
2. Analyze the gradient and Hessian of $f(x,y)=x^2-y^2$ at the origin and explain why it is a saddle point.
3. Write the Lagrangian function for the minimization problem subject to the constraint $x+y=1$.
4. Design a stopping condition for a training loop to prevent reliance solely on a fixed number of iterations.

Summary

Gradient descent stems from a local linear approximation, and the learning rate determines how far we trust that approximation in one step. Convexity provides a global structure, while the Hessian describes local curvature. Stochastic gradients and momentum alter computational cost and trajectory. Truly reliable optimization results also require constraint checks, numerical stability checks, and validation against task-specific metrics.

The final chapter addresses two kinds of boundaries often hidden behind formulas: how information is actually measured, and why the same mathematical expression can yield completely different results when evaluated on finite-precision computers.