Optimization & Convexity
Gradients, convex sets, Lagrange multipliers and duality.
Gradient descent is a one-line algorithm, yet how fast it converges, whether any method could do better, and what changes with constraints or nonconvexity all have sharp answers. This lesson proves the rates, meets the lower bounds that make Nesterov's method optimal, derives the softmax from a constrained problem, and ends with what is still unknown about training neural networks.
What you’ll learn
- Use the characterizations of strong convexity and smoothness, and compute the condition number of least squares with and without ridge regularization.
- Prove the rate of gradient descent on smooth convex functions and its linear rate under strong convexity or the PL inequality.
- State Nesterov's accelerated rates and the first-order lower bounds that make them optimal.
- Solve constrained problems with Lagrange multipliers and the KKT conditions, and derive the maximum-entropy (softmax) distribution.
- Explain strict saddles, how gradient methods escape them, and the open problems of nonconvex training.
Strong convexity, smoothness and conditioning
For least squares, has the constant Hessian , so , (positive iff has full column rank) and : nearly collinear features mean slow optimization. A ridge term shifts both ends, giving , so regularization also improves conditioning. The logistic loss is convex and smooth but not strongly convex: its Hessian fades as grows, and on separable data the infimum is not attained.
Think first Prove both inequalities, one line each.
Smoothness: by the descent lemma. Strong convexity: minimize both sides of the defining inequality over . The right side is a quadratic in , minimized at , which gives . Together, : the size of the gradient pins down the suboptimality up to the factor .
Convergence rates of gradient descent
The descent lemma with , then convexity in the form :
Complete the square using : expanding shows that the right-hand side is exactly
Sum over . The right side telescopes:
The descent lemma makes nonincreasing, so the last term is the smallest of the terms on the left:
Under strong convexity the proof is one line: the descent lemma and PL give . Only PL was used, not convexity, a point that returns in step 5. With the step the distance to contracts by per step, exactly the rate on quadratics. With noisy gradients, SGD with decaying steps attains on convex Lipschitz problems and under strong convexity (Nemirovski, Juditsky, Lan & Shapiro, 2009), and in general no stochastic first-order method can do better.
Gradient descent with runs on a smooth, strongly convex function with . Using the bound , about how many iterations guarantee ?
Show the answer
1375 iterations
Solve : , close to the rule of thumb . The iteration count grows linearly in ; Nesterov's method (next step) needs on the order of .
Acceleration and lower bounds
Plain gradient descent forgets everything but the current gradient. Nesterov's accelerated gradient method (1983) adds a carefully scheduled extrapolation. Starting from ,
For -smooth convex this guarantees . On -strongly convex , the variant with constant momentum shrinks the error by a factor of about per step. To reach accuracy that is iterations instead of , and instead of .
Take and Nesterov's tridiagonal quadratic on coordinates, , where . The eigenvalues of lie in , so is convex and -smooth:
Since and is tridiagonal, the gradient at a vector supported on the first coordinates is supported on the first . By induction, every first-order method satisfies
The minimizer solves , so has every coordinate nonzero. After queries the method is stuck on a -dimensional face; taking and computing the best value on that face gives the bound. A similar infinite chain with an added strongly convex term gives the bound.
Polyak's heavy-ball method, , attains the optimal rate on quadratics when and are tuned, but not in general: Lessard, Recht & Packard (2016) exhibited a smooth, strongly convex function on which heavy ball with those parameters fails to converge. Nesterov's method keeps its guarantee on every smooth, strongly convex function.
Constraints, multipliers and duality
A constrained problem minimizes subject to () and . Its Lagrangian prices each constraint, with . The dual function is concave even when the problem is not convex, as a pointwise infimum of affine functions. For any feasible and , : this is weak duality, . For convex problems, Slater's condition (a strictly feasible point exists) gives strong duality, .
Among distributions on outcomes with scores , find the one with the largest entropy whose expected score is . Maximizing means minimizing the strictly convex under affine constraints:
Attach multipliers and (signs chosen for convenience) and set the derivative in to zero:
So : a softmax of the scores at inverse temperature , the Gibbs distribution of statistical physics. Every is positive, so the constraints are inactive and complementary slackness gives them zero multipliers:
Eliminating leaves a one-dimensional convex dual, whose optimality condition is the moment constraint. Maximizing the likelihood of an exponential family given data with mean score is the same problem: maximum entropy and maximum likelihood are dual.
In a hard-margin SVM, the multiplier of the constraint is zero for every training point strictly outside the margin. Which KKT condition forces this?
- Stationarity
- Dual feasibility
- Complementary slackness
- Primal feasibility
Show the answer
C. Complementary slackness
Complementary slackness, : if the constraint is slack, its multiplier must vanish. Only points on the margin can have , and these support vectors alone determine (from stationarity).
Nonconvex landscapes
Without convexity the realistic goal is a stationary point. Gradient descent finds within steps, and in high dimensions no deterministic first-order method can do better in the worst case (Carmon, Duchi, Hinder & Sidford, 2020). But a stationary point may be a saddle. Call it a strict saddle if there, so that some direction curves downward. In several problems, such as low-rank matrix recovery and phase retrieval under suitable statistical assumptions, every saddle is strict and every local minimum is global, so escaping saddles is all that is needed.
Measure zero is not the same as fast: without perturbations, gradient descent can take time exponential in the dimension to escape a sequence of saddles, even from a random start (Du et al., 2017). Another route to guarantees replaces convexity with the PL inequality of step 1, under which the one-line proof of step 2 gives a linear rate. The function is PL but not convex (Karimi, Nutini & Schmidt, 2016), and wide neural networks satisfy PL-type conditions near their initialization (Liu, Zhu & Belkin, 2022).
Key takeaways
- Sandwiching the Hessian, , defines the condition number ; for least squares , and ridge regularization lowers it.
- Gradient descent with : for smooth convex , a factor per step under strong convexity or PL, and without convexity.
- Nesterov's method achieves and , matching the lower bounds for first-order methods; the heavy-ball method is optimal on quadratics but can fail on general strongly convex functions.
- Duality: weak duality always holds, strong duality under Slater's condition; the KKT conditions characterize optima, and maximum entropy under a moment constraint gives the softmax.
- On nonconvex losses, gradient descent avoids strict saddles from almost every start, perturbations make escaping efficient, and PL-type conditions give linear rates without convexity.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
For an -smooth convex function, what suboptimality does gradient descent with guarantee after steps, in general?
Show the answer
C.
. Faster rates need more: acceleration for , strong convexity or PL for a linear rate.
Why can no first-order method guarantee better than on smooth convex functions in high dimension?
- Because gradient descent is the only first-order method
- Because on a worst-case quadratic each gradient reveals at most one new coordinate, so after queries the iterates cannot reach the minimizer's remaining coordinates
- Because smooth convex functions have at most stationary points
- Because rounding errors grow like
Show the answer
B. Because on a worst-case quadratic each gradient reveals at most one new coordinate, so after queries the iterates cannot reach the minimizer's remaining coordinates
For Nesterov's tridiagonal quadratic, for any method whose steps lie in the span of past gradients, while the minimizer has all coordinates nonzero; this yields .
You maximize the entropy of a distribution over outcomes with scores , subject to a fixed expected score . What is the solution?
- The uniform distribution, whatever is
- A point mass on the highest-scoring outcome
- A Gaussian with mean
- , a softmax of the scores, with the multiplier chosen so the constraint holds
Show the answer
D. , a softmax of the scores, with the multiplier chosen so the constraint holds
Stationarity of the Lagrangian gives , so . The objective is strictly concave and the constraints are affine, so this KKT point is the global maximum; solves .
Which condition guarantees a linear rate for gradient descent with on an -smooth function, without assuming convexity?
- The Polyak–Łojasiewicz inequality
- Having no saddle points
- A bounded Hessian
- A unique stationary point
Show the answer
A. The Polyak–Łojasiewicz inequality
The descent lemma and PL give . PL allows nonconvex functions such as , and it implies that every stationary point is a global minimizer.
Further reading
- Y. Nesterov, Lectures on Convex Optimization, 2nd ed. (Springer, 2018).
- S. Bubeck, "Convex optimization: Algorithms and complexity," Foundations and Trends in Machine Learning 8(3–4) (2015).
- S. Boyd & L. Vandenberghe, Convex Optimization (Cambridge University Press, 2004), chapter 5.
- Y. Nesterov, "A method for solving the convex programming problem with convergence rate O(1/k²)," Soviet Mathematics Doklady 27 (1983).
- J. D. Lee, M. Simchowitz, M. I. Jordan & B. Recht, "Gradient descent only converges to minimizers," COLT (2016).