Optimization Foundations and Basic Descent Methods

Chapter Overview

This chapter establishes the optimization language used throughout the course: objective functions, gradients, Hessians, level sets, convexity assumptions, conditioning, and the first two baseline descent procedures. It is the point where the machine-learning training problem is explicitly rewritten as an optimization problem.

It matters because every later optimizer is described as a modification of these baseline ideas. It also connects directly to deep learning: backpropagation computes gradients, while the optimization chapters explain what is done with these gradients and why some problems are easier than others.

The main storyline is simple: local information about a function is all we can afford in high dimension, so we need assumptions that make this local information globally useful. Convexity, smoothness, and strong convexity are the course's main regularity assumptions for that purpose.

Important Definitions

• Optimization problem. Find a minimizer or maximizer of a function over a feasible set. In the lecture language, optimization is "finding the minimal (maximal) value of a function over a set".
• Empirical risk minimization (ERM). In supervised learning, the objective often has the finite-sum form f(θ) = (1/n) ∑i=1n fi(θ), where each fi is the loss contribution of one observation.
• Gradient. For a differentiable function f : Rd -> R, the gradient ∇f(θ) is the vector of partial derivatives and gives the steepest increase direction.
• Hessian. ∇2f(θ) is the matrix of second-order partial derivatives and captures local curvature.
• Level set. Cc = {θ : f(θ) = c}. Level sets are the main geometric way to read a function in dimension at least two.
• Critical point. A point where the gradient is zero. It is a necessary condition for a local extremum, but not every critical point is a minimum.
• Convexity. A function is convex if its graph lies below the line segment joining any two points, equivalently if it stays above all of its tangents, equivalently if its Hessian is positive semidefinite when twice differentiable.
• L-smoothness. f is L-smooth when its gradient is L-Lipschitz. This gives a global quadratic upper bound around each point.
• μ-strong convexity. f is strongly convex when it dominates its tangent plus a quadratic term. This forces a unique minimizer and enables linear convergence rates for gradient descent.
• Condition number. For an L-smooth, μ-strongly convex function, κ = L / μ. A large condition number means highly anisotropic curvature and a harder optimization problem.
• Gradient descent (GD). Deterministic first-order method using the full gradient at each step.
• Stochastic gradient descent (SGD). First-order method replacing the full gradient with a random gradient estimate based on one sample or a mini-batch.

Key Concepts and Intuition

• Local information is the only scalable information. In high dimension, plotting or exhaustively searching the objective is impossible. The course therefore starts from derivatives, Taylor expansion, and geometry of level sets.
• The gradient is geometric, not just algebraic. It points toward the steepest increase and is orthogonal to level sets. This explains why -∇f is the canonical local descent direction.
• Regularity assumptions tell you how trustworthy local information is. Convexity says tangent information is globally informative from below; smoothness says a quadratic upper bound exists from above; strong convexity adds coercive curvature that prevents flat wandering.
• Conditioning is a speed issue. Poorly conditioned level sets are elongated: one direction varies quickly, another slowly. Vanilla gradient descent then zig-zags and needs many iterations.
• Machine-learning objectives create scale tension. When n and d are large, the full gradient can be too expensive. This is the motivation for SGD: accept noise to reduce per-iteration cost.

Mathematical Content

Core local formulas.

Regularity inequalities used all course long.

Gradient descent.

The lecture gives two justifications for this update. First, it minimizes the first-order Taylor approximation inside a ball around the current point. Second, for an L-smooth function, the update with η = 1/L minimizes the global quadratic upper bound around the current iterate.

Convergence rates for GD.

The first regime is sublinear: dividing the error by 10 costs roughly 10 times more iterations. The second is linear: each iteration multiplies the error by a contraction factor.

Stochastic gradient descent.

On smooth convex objectives, the lecture emphasizes the averaged iterate and the rate O(1 / sqrt(T)), versus O(1 / T) for GD, together with a much cheaper per-iteration cost. The practical conclusion is that SGD is preferred for large-scale ML when moderate precision is enough.

Distinctions and Comparisons

• Gradient vs Hessian. The gradient gives direction; the Hessian gives curvature. Later second-order methods depend on this distinction.
• Critical point vs minimizer. ∇f(θ)=0 is only necessary in general. Convexity plus second-order conditions are what turn local statements into global ones.
• Convex vs strongly convex. Strong convexity adds uniform curvature. The practical effect is not a cosmetic strengthening: it changes the rate from sublinear to linear.
• GD vs SGD. GD uses the whole dataset and has stable descent directions; SGD uses noisy cheaper directions and is often better when data are huge or only moderate accuracy is needed.
• Iteration count vs wall-clock cost. A method with fewer iterations is not automatically cheaper if each iteration is far more expensive.

Exam-Oriented Understanding

• A strong answer gives both the update equation and the reason behind it. For gradient descent, that means mentioning the steepest descent interpretation or the first-order/quadratic-upper-bound argument.
• When stating a convergence rate, always attach the assumptions: convexity, smoothness, and strong convexity are not interchangeable.
• For conditioning, do not just define κ. Explain that large κ means one direction is much flatter than another, which slows first-order methods.
• For GD versus SGD, compare three things: convergence rate, per-iteration complexity, and the accuracy regime where one becomes preferable to the other.
• Easy mistake to avoid: talking about SGD as if it were always better. The lecture's conclusion is conditional, not absolute.

Source References

• Optimization Lecture 1 (APM52445_Optimization_2026_Lect1_annot.pdf), slides 17-24: From supervised machine learning to optimization, ERM motivation, optimization challenges.
• Optimization Lecture 1 (APM52445_Optimization_2026_Lect1_annot.pdf), slides 30-56: Gradients, Hessians, Taylor expansion, level sets, optimality conditions, convexity, smoothness, strong convexity, conditioning.
• Optimization Lecture 2 (APM52445-Optimization-Lect2.pdf), slides 4-17: Gradient descent intuition, grounded formulations, convex and strongly convex convergence rates.
• Optimization Lecture 2 (APM52445-Optimization-Lect2.pdf), slides 18-33: SGD motivation, unbiased gradient oracle, averaged iterate, smooth-convex rate, GD versus SGD tradeoffs.

Relevant Exam Alignment

The sample exam directly targets this chapter's material: define SGD, justify the gradient descent direction, explain the assumption needed for consistency, compute how rates scale over more iterations, define conditioning, and compare GD with SGD at different target precisions.

To answer well, state the update, state the assumption class, and then interpret the rate. The exam style rewards short but complete reasoning chains more than isolated formulas.