Simple Algorithm
Artificial Intelligence · Deep Layer · 30 min

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 O(1/k)\order{1/k} 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, f(w)=12∥Xw−y∥2f(\mathbf w)=\tfrac12\norm{X\mathbf w-\mathbf y}^2 has the constant Hessian X⊤XX^\top X, so L=σmax⁡(X)2L=\sigma_{\max}(X)^2, μ=σmin⁡(X)2\mu=\sigma_{\min}(X)^2 (positive iff XX has full column rank) and κ=cond⁡(X)2\kappa=\operatorname{cond}(X)^2: nearly collinear features mean slow optimization. A ridge term λ2∥w∥2\tfrac\lambda2\norm{\mathbf w}^2 shifts both ends, giving κ=(σmax⁡2+λ)/(σmin⁡2+λ)\kappa=(\sigma_{\max}^2+\lambda)/(\sigma_{\min}^2+\lambda), so regularization also improves conditioning. The logistic loss is convex and smooth but not strongly convex: its Hessian ∑iσ(zi)(1−σ(zi))xixi⊤\sum_i\sigma(z_i)\big(1-\sigma(z_i)\big)\mathbf x_i\mathbf x_i^\top fades as ∥w∥\norm{\mathbf w} grows, and on separable data the infimum is not attained.

Think first Prove both inequalities, one line each.

Smoothness: f⋆≤f(x−1L∇f(x))≤f(x)−12L∥∇f(x)∥2f^\star\le f\big(\mathbf x-\tfrac1L\nabla f(\mathbf x)\big)\le f(\mathbf x)-\tfrac1{2L}\norm{\nabla f(\mathbf x)}^2 by the descent lemma. Strong convexity: minimize both sides of the defining inequality over y\mathbf y. The right side is a quadratic in y\mathbf y, minimized at y=x−∇f(x)/μ\mathbf y=\mathbf x-\nabla f(\mathbf x)/\mu, which gives f⋆≥f(x)−12μ∥∇f(x)∥2f^\star\ge f(\mathbf x)-\tfrac1{2\mu}\norm{\nabla f(\mathbf x)}^2. Together, μ≤∥∇f∥2/(2(f−f⋆))≤L\mu\le\norm{\nabla f}^2/\big(2(f-f^\star)\big)\le L: the size of the gradient pins down the suboptimality up to the factor κ\kappa.

Convergence rates of gradient descent

DerivationProof of the 1/k rate
  1. f(xt+1)−f⋆≤∇f(xt)⊤(xt−x⋆)−12L∥∇f(xt)∥2f(\mathbf x_{t+1})-f^\star\le\nabla f(\mathbf x_t)^\top(\mathbf x_t-\mathbf x^\star)-\frac1{2L}\norm{\nabla f(\mathbf x_t)}^2

    The descent lemma with η=1/L\eta=1/L, then convexity in the form f(xt)−f⋆≤∇f(xt)⊤(xt−x⋆)f(\mathbf x_t)-f^\star\le\nabla f(\mathbf x_t)^\top(\mathbf x_t-\mathbf x^\star):

  2. f(xt+1)−f⋆≤L2(∥xt−x⋆∥2−∥xt+1−x⋆∥2)f(\mathbf x_{t+1})-f^\star\le\frac L2\Big(\norm{\mathbf x_t-\mathbf x^\star}^2-\norm{\mathbf x_{t+1}-\mathbf x^\star}^2\Big)

    Complete the square using xt+1=xt−1L∇f(xt)\mathbf x_{t+1}=\mathbf x_t-\frac1L\nabla f(\mathbf x_t): expanding ∥xt+1−x⋆∥2\norm{\mathbf x_{t+1}-\mathbf x^\star}^2 shows that the right-hand side is exactly

  3. ∑t=1k(f(xt)−f⋆)≤L2∥x0−x⋆∥2\sum_{t=1}^{k}\big(f(\mathbf x_t)-f^\star\big)\le\frac L2\norm{\mathbf x_0-\mathbf x^\star}^2

    Sum over t=0,…,k−1t=0,\dots,k-1. The right side telescopes:

  4. f(xk)−f⋆≤1k∑t=1k(f(xt)−f⋆)≤L∥x0−x⋆∥22kf(\mathbf x_k)-f^\star\le\frac1k\sum_{t=1}^{k}\big(f(\mathbf x_t)-f^\star\big)\le\frac{L\norm{\mathbf x_0-\mathbf x^\star}^2}{2k}

    The descent lemma makes f(xt)f(\mathbf x_t) nonincreasing, so the last term is the smallest of the kk terms on the left:

Under strong convexity the proof is one line: the descent lemma and PL give f(xk+1)−f⋆≤f(xk)−f⋆−12L∥∇f(xk)∥2≤(1−μL)(f(xk)−f⋆)f(\mathbf x_{k+1})-f^\star\le f(\mathbf x_k)-f^\star-\frac1{2L}\norm{\nabla f(\mathbf x_k)}^2\le(1-\frac\mu L)\big(f(\mathbf x_k)-f^\star\big). Only PL was used, not convexity, a point that returns in step 5. With the step η=2/(μ+L)\eta=2/(\mu+L) the distance to x⋆\mathbf x^\star contracts by (κ−1)/(κ+1)(\kappa-1)/(\kappa+1) per step, exactly the rate on quadratics. With noisy gradients, SGD with decaying steps attains O(1/k)\order{1/\sqrt k} on convex Lipschitz problems and O(1/k)\order{1/k} under strong convexity (Nemirovski, Juditsky, Lan & Shapiro, 2009), and in general no stochastic first-order method can do better.

Predict before you look

Gradient descent with η=1/L\eta=1/L runs on a smooth, strongly convex function with κ=100\kappa=100. Using the bound (1−1/κ)k(1-1/\kappa)^k, about how many iterations guarantee f(xk)−f⋆≤10−6(f(x0)−f⋆)f(\mathbf x_k)-f^\star\le10^{-6}\big(f(\mathbf x_0)-f^\star\big)?

Show the answer

1375 iterations

Solve 0.99k≤10−60.99^k\le10^{-6}: k≥ln⁡(106)/(−ln⁡0.99)≈13.82/0.01005≈1,375k\ge\ln(10^6)/(-\ln0.99)\approx13.82/0.01005\approx1{,}375, close to the rule of thumb κln⁡(1/ε)≈1,380\kappa\ln(1/\varepsilon)\approx1{,}380. The iteration count grows linearly in κ\kappa; Nesterov's method (next step) needs on the order of κln⁡(1/ε)≈140\sqrt\kappa\ln(1/\varepsilon)\approx140.

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 y0=x0\mathbf y_0=\mathbf x_0,

xk+1=yk−1L∇f(yk),yk+1=xk+1+kk+3 (xk+1−xk).\mathbf x_{k+1}=\mathbf y_k-\tfrac1L\nabla f(\mathbf y_k),\qquad\mathbf y_{k+1}=\mathbf x_{k+1}+\tfrac{k}{k+3}\,(\mathbf x_{k+1}-\mathbf x_k).

For LL-smooth convex ff this guarantees f(xk)−f⋆≤2L∥x0−x⋆∥2/(k+1)2f(\mathbf x_k)-f^\star\le2L\norm{\mathbf x_0-\mathbf x^\star}^2/(k+1)^2. On μ\mu-strongly convex ff, the variant with constant momentum (κ−1)/(κ+1)(\sqrt\kappa-1)/(\sqrt\kappa+1) shrinks the error by a factor of about 1−1/κ1-1/\sqrt\kappa per step. To reach accuracy ε\varepsilon that is O(L/ε)\order{\sqrt{L/\varepsilon}} iterations instead of O(L/ε)\order{L/\varepsilon}, and O(κlog⁡(1/ε))\order{\sqrt\kappa\log(1/\varepsilon)} instead of O(κlog⁡(1/ε))\order{\kappa\log(1/\varepsilon)}.

DerivationProof idea: a chain that reveals one coordinate per query
  1. ∇2f=L4 A=L4(2−1−12⋱⋱⋱−1−12)⪯L I\nabla^2f=\frac L4\,A=\frac L4\begin{pmatrix}2&-1&&\\-1&2&\ddots&\\&\ddots&\ddots&-1\\&&-1&2\end{pmatrix}\preceq L\,I

    Take x0=0\mathbf x_0=\mathbf 0 and Nesterov's tridiagonal quadratic on mm coordinates, f(x)=L4(12x⊤Ax−x1)f(\mathbf x)=\frac L4\big(\tfrac12\mathbf x^\top A\mathbf x-x_1\big), where x⊤Ax=x12+∑i<m(xi−xi+1)2+xm2\mathbf x^\top A\mathbf x=x_1^2+\sum_{i<m}(x_i-x_{i+1})^2+x_m^2. The eigenvalues of AA lie in (0,4)(0,4), so ff is convex and LL-smooth:

  2. xk∈span⁡{e1,…,ek}after k gradient queries\mathbf x_k\in\operatorname{span}\{\mathbf e_1,\dots,\mathbf e_k\}\qquad\text{after }k\text{ gradient queries}

    Since ∇f(x)=L4(Ax−e1)\nabla f(\mathbf x)=\frac L4(A\mathbf x-\mathbf e_1) and AA is tridiagonal, the gradient at a vector supported on the first jj coordinates is supported on the first j+1j+1. By induction, every first-order method satisfies

  3. f(xk)−f⋆ ≥ min⁡x∈span⁡{e1,…,ek}f(x)−f⋆ ≥ 3L∥x0−x⋆∥232(k+1)2f(\mathbf x_k)-f^\star\ \ge\ \min_{\mathbf x\in\operatorname{span}\{\mathbf e_1,\dots,\mathbf e_k\}}f(\mathbf x)-f^\star\ \ge\ \frac{3L\norm{\mathbf x_0-\mathbf x^\star}^2}{32(k+1)^2}

    The minimizer solves Ax=e1A\mathbf x=\mathbf e_1, so xi⋆=1−im+1x^\star_i=1-\frac{i}{m+1} has every coordinate nonzero. After kk queries the method is stuck on a kk-dimensional face; taking m=2k+1m=2k+1 and computing the best value on that face gives the bound. A similar infinite chain with an added strongly convex term gives the κ\sqrt\kappa bound.

Polyak's heavy-ball method, xk+1=xk−η∇f(xk)+β(xk−xk−1)\mathbf x_{k+1}=\mathbf x_k-\eta\nabla f(\mathbf x_k)+\beta(\mathbf x_k-\mathbf x_{k-1}), attains the optimal rate (κ−1)/(κ+1)(\sqrt\kappa-1)/(\sqrt\kappa+1) on quadratics when η\eta and β\beta 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 f0(x)f_0(\mathbf x) subject to fi(x)≤0f_i(\mathbf x)\le0 (i=1,…,mi=1,\dots,m) and hj(x)=0h_j(\mathbf x)=0. Its Lagrangian prices each constraint, L(x,λ,ν)=f0(x)+∑iλifi(x)+∑jνjhj(x)\mathcal L(\mathbf x,\boldsymbol\lambda,\boldsymbol\nu)=f_0(\mathbf x)+\sum_i\lambda_if_i(\mathbf x)+\sum_j\nu_jh_j(\mathbf x) with λ≥0\boldsymbol\lambda\ge\mathbf 0. The dual function g(λ,ν)=inf⁡xL(x,λ,ν)g(\boldsymbol\lambda,\boldsymbol\nu)=\inf_{\mathbf x}\mathcal L(\mathbf x,\boldsymbol\lambda,\boldsymbol\nu) is concave even when the problem is not convex, as a pointwise infimum of affine functions. For any feasible x\mathbf x and λ≥0\boldsymbol\lambda\ge\mathbf 0, g(λ,ν)≤L(x,λ,ν)≤f0(x)g(\boldsymbol\lambda,\boldsymbol\nu)\le\mathcal L(\mathbf x,\boldsymbol\lambda,\boldsymbol\nu)\le f_0(\mathbf x): this is weak duality, d⋆≤p⋆d^\star\le p^\star. For convex problems, Slater's condition (a strictly feasible point exists) gives strong duality, d⋆=p⋆d^\star=p^\star.

DerivationMaximum entropy gives the softmax
  1. min⁡p ∑i=1Kpiln⁡pisubject to∑ipi=1,∑ipisi=m\min_{\mathbf p}\ \sum_{i=1}^Kp_i\ln p_i\quad\text{subject to}\quad\sum_ip_i=1,\quad\sum_ip_is_i=m

    Among distributions on outcomes with scores s1,…,sKs_1,\dots,s_K, find the one with the largest entropy whose expected score is mm. Maximizing HH means minimizing the strictly convex ∑ipiln⁡pi\sum_ip_i\ln p_i under affine constraints:

  2. ∂∂pi[∑kpkln⁡pk−α(∑kpk−1)−β(∑kpksk−m)]=ln⁡pi+1−α−βsi=0\frac{\partial}{\partial p_i}\Big[\sum_kp_k\ln p_k-\alpha\Big(\sum_kp_k-1\Big)-\beta\Big(\sum_kp_ks_k-m\Big)\Big]=\ln p_i+1-\alpha-\beta s_i=0

    Attach multipliers α\alpha and β\beta (signs chosen for convenience) and set the derivative in pip_i to zero:

  3. pi=eβsiZ(β),Z(β)=∑k=1Keβskp_i=\frac{e^{\beta s_i}}{Z(\beta)},\qquad Z(\beta)=\sum_{k=1}^Ke^{\beta s_k}

    So pi∝eβsip_i\propto e^{\beta s_i}: a softmax of the scores at inverse temperature β\beta, the Gibbs distribution of statistical physics. Every pip_i is positive, so the constraints pi≥0p_i\ge0 are inactive and complementary slackness gives them zero multipliers:

  4. β⋆=arg min⁡β(ln⁡Z(β)−βm),dln⁡Zdβ=∑ipisi=m\beta^\star=\argmin_\beta\big(\ln Z(\beta)-\beta m\big),\qquad\frac{d\ln Z}{d\beta}=\sum_ip_is_i=m

    Eliminating α\alpha leaves a one-dimensional convex dual, whose optimality condition is the moment constraint. Maximizing the likelihood of an exponential family pβ(i)=eβsi/Z(β)p_\beta(i)=e^{\beta s_i}/Z(\beta) given data with mean score mm is the same problem: maximum entropy and maximum likelihood are dual.

Check your understanding

In a hard-margin SVM, the multiplier αi\alpha_i of the constraint yi(w⊤xi+b)≥1y_i(\mathbf w^\top\mathbf x_i+b)\ge1 is zero for every training point strictly outside the margin. Which KKT condition forces this?

  1. Stationarity
  2. Dual feasibility
  3. Complementary slackness
  4. Primal feasibility
Show the answer

C. Complementary slackness

Complementary slackness, αi(1−yi(w⊤xi+b))=0\alpha_i\big(1-y_i(\mathbf w^\top\mathbf x_i+b)\big)=0: if the constraint is slack, its multiplier must vanish. Only points on the margin can have αi>0\alpha_i>0, and these support vectors alone determine w=∑iαiyixi\mathbf w=\sum_i\alpha_iy_i\mathbf x_i (from stationarity).

Nonconvex landscapes

Without convexity the realistic goal is a stationary point. Gradient descent finds ∥∇f∥≤ε\norm{\nabla f}\le\varepsilon within O(L(f(x0)−f⋆)/ε2)\order{L(f(\mathbf x_0)-f^\star)/\varepsilon^2} 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 λmin⁡(∇2f)<0\lambda_{\min}(\nabla^2f)<0 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 x2+3sin⁡2xx^2+3\sin^2x 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, μI⪯∇2f⪯LI\mu I\preceq\nabla^2f\preceq LI, defines the condition number κ=L/μ\kappa=L/\mu; for least squares κ=cond⁡(X)2\kappa=\operatorname{cond}(X)^2, and ridge regularization lowers it.
  • Gradient descent with η=1/L\eta=1/L: f(xk)−f⋆≤L∥x0−x⋆∥2/(2k)f(\mathbf x_k)-f^\star\le L\norm{\mathbf x_0-\mathbf x^\star}^2/(2k) for smooth convex ff, a factor (1−1/κ)(1-1/\kappa) per step under strong convexity or PL, and min⁡t∥∇f∥2=O(1/k)\min_t\norm{\nabla f}^2=\order{1/k} without convexity.
  • Nesterov's method achieves O(1/k2)\order{1/k^2} and (1−1/κ)k(1-1/\sqrt\kappa)^k, 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.

Question 1

For an LL-smooth convex function, what suboptimality f(xk)−f⋆f(\mathbf x_k)-f^\star does gradient descent with η=1/L\eta=1/L guarantee after kk steps, in general?

  1. O(1/k2)\order{1/k^2}
  2. O(e−k)\order{e^{-k}}
  3. O(1/k)\order{1/k}
  4. O(1/k)\order{1/\sqrt k}
Show the answer

C. O(1/k)\order{1/k}

f(xk)−f⋆≤L∥x0−x⋆∥2/(2k)f(\mathbf x_k)-f^\star\le L\norm{\mathbf x_0-\mathbf x^\star}^2/(2k). Faster rates need more: acceleration for O(1/k2)\order{1/k^2}, strong convexity or PL for a linear rate.

Question 2

Why can no first-order method guarantee better than O(1/k2)\order{1/k^2} on smooth convex functions in high dimension?

  1. Because gradient descent is the only first-order method
  2. Because on a worst-case quadratic each gradient reveals at most one new coordinate, so after kk queries the iterates cannot reach the minimizer's remaining coordinates
  3. Because smooth convex functions have at most kk stationary points
  4. Because rounding errors grow like k2k^2
Show the answer

B. Because on a worst-case quadratic each gradient reveals at most one new coordinate, so after kk queries the iterates cannot reach the minimizer's remaining coordinates

For Nesterov's tridiagonal quadratic, xk∈span⁡{e1,…,ek}\mathbf x_k\in\operatorname{span}\{\mathbf e_1,\dots,\mathbf e_k\} for any method whose steps lie in the span of past gradients, while the minimizer has all coordinates nonzero; this yields f(xk)−f⋆≥3L∥x0−x⋆∥2/(32(k+1)2)f(\mathbf x_k)-f^\star\ge3L\norm{\mathbf x_0-\mathbf x^\star}^2/\big(32(k+1)^2\big).

Question 3

You maximize the entropy of a distribution p\mathbf p over KK outcomes with scores sis_i, subject to a fixed expected score ∑ipisi=m\sum_ip_is_i=m. What is the solution?

  1. The uniform distribution, whatever mm is
  2. A point mass on the highest-scoring outcome
  3. A Gaussian with mean mm
  4. pi∝eβsip_i\propto e^{\beta s_i}, a softmax of the scores, with the multiplier β\beta chosen so the constraint holds
Show the answer

D. pi∝eβsip_i\propto e^{\beta s_i}, a softmax of the scores, with the multiplier β\beta chosen so the constraint holds

Stationarity of the Lagrangian gives −ln⁡pi−1+α+βsi=0-\ln p_i-1+\alpha+\beta s_i=0, so pi=eβsi/Z(β)p_i=e^{\beta s_i}/Z(\beta). The objective is strictly concave and the constraints are affine, so this KKT point is the global maximum; β\beta solves ddβln⁡Z(β)=m\frac{d}{d\beta}\ln Z(\beta)=m.

Question 4

Which condition guarantees a linear rate for gradient descent with η=1/L\eta=1/L on an LL-smooth function, without assuming convexity?

  1. The Polyak–Łojasiewicz inequality 12∥∇f∥2≥μ(f−f⋆)\tfrac12\norm{\nabla f}^2\ge\mu(f-f^\star)
  2. Having no saddle points
  3. A bounded Hessian
  4. A unique stationary point
Show the answer

A. The Polyak–Łojasiewicz inequality 12∥∇f∥2≥μ(f−f⋆)\tfrac12\norm{\nabla f}^2\ge\mu(f-f^\star)

The descent lemma and PL give f(xk+1)−f⋆≤(1−μ/L)(f(xk)−f⋆)f(\mathbf x_{k+1})-f^\star\le(1-\mu/L)\big(f(\mathbf x_k)-f^\star\big). PL allows nonconvex functions such as x2+3sin⁡2xx^2+3\sin^2x, 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).