44.06.01 · optimization-control / 06-first-order-large-scale

Subgradient Methods for Nonsmooth Convex Optimization

shipped3 tiersLean: none

Anchor (Master): Nesterov 2018 Lectures on Convex Optimization (Springer) §3.2 (the O(1/√k) upper bound, Polyak's step, and the matching Ω(1/√k) lower bound for nonsmooth first-order methods via the resisting-oracle construction); Beck 2017 First-Order Methods in Optimization (SIAM) Ch. 8; Bertsekas 2015 Convex Optimization Algorithms (Athena) §3.2

Intuition Beginner

Suppose you are standing in a foggy valley whose floor is full of sharp creases, and you want to reach the lowest point. Where the floor is smooth you can feel the downhill direction under your feet and step that way. But right on a crease there is no single downhill direction — the slope on your left differs from the slope on your right. You still have to pick some direction and step. The honest replacement for "the downhill direction" at a crease is any one of the supporting slopes you met earlier as the subdifferential. Picking one of them is picking a subgradient, and stepping against it is the subgradient method.

Here is the catch that makes this method different from anything smooth. When you step against a subgradient, the ground where you land can be higher than where you started. A subgradient is not guaranteed to point downhill — it only certifies a supporting line. So unlike rolling a ball down a smooth bowl, your height can bob up and down as you go. This is not a bug to be fixed; it is the price of working at creases.

Because the height bobs around, you cannot judge progress by your current height. Instead you remember the lowest height you have ever recorded and treat that as your answer so far. The method works because, even though any single step might go uphill, your distance to the true bottom shrinks on average when your steps are the right size.

What size? Too-large steps and you jitter forever near the bottom without settling. Fixed-size steps settle only into a neighbourhood, never the exact point. The fix is steps that shrink toward zero — but not too fast, so their total length is still infinite and you can travel any distance you need. That single rule, "shrink the steps but let their lengths add up to infinity," is what carries the best recorded height down to the true minimum.

Visual Beginner

Picture the path of a subgradient method on a bowl with a crease running through the bottom. The iterate does not march straight in; it zig-zags across the crease, sometimes landing higher than the step before, while the record-low height ratchets steadily downward.

   height f(x_k)  (bobs up and down)        best-so-far f_best (only falls)
     |                                         |
   5 *                                       5 *
     |  *      *                               | *
   4 |     *      *    *                      4 |  *
     |        *           *   *                |   *_____
   3 |           *   *        *  *            3 |        *_______
     |   step uphill!  ^         *  * *         |               *_____ ...
   2 +----------------------------------> k    2 +----------------------> k
     current value is NOT monotone            the recorded minimum IS monotone

step size rule	long-run behaviour
constant, large	jitters in a wide band around the minimum, never settles
constant, small	settles into a small neighbourhood, never the exact point
shrinking, lengths still sum to infinity	best-so-far height converges to the true minimum

Worked example Beginner

Minimise $f (x) = ∣ x ∣$ on the real line, starting at $x_{0} = 1$ . The lowest value is $f = 0$ at $x = 0$ . A subgradient of $∣ x ∣$ is $+ 1$ when $x > 0$ , $- 1$ when $x < 0$ , and any value in $[- 1, 1]$ at the crease $x = 0$ .

We use the shrinking step $α_{k} = 1/ (k + 1)$ , so the steps are $1, \frac{1}{2}, \frac{1}{3}, \dots$ . The update is $x_{k + 1} = x_{k} - α_{k} g_{k}$ with $g_{k}$ the sign of $x_{k}$ .

Step 0. $x_{0} = 1 > 0$ , so $g_{0} = 1$ and $α_{0} = 1$ . Then $x_{1} = 1 - 1 \cdot 1 = 0$ . Height $f (x_{1}) = 0$ .

Step 1. $x_{1} = 0$ is the crease; a valid subgradient is $g_{1} = 1$ , and $α_{1} = \frac{1}{2}$ . Then $x_{2} = 0 - \frac{1}{2} \cdot 1 = - \frac{1}{2}$ . Height $f (x_{2}) = \frac{1}{2}$ — note this is higher than the previous height of $0$ .

Step 2. $x_{2} = - \frac{1}{2} < 0$ , so $g_{2} = - 1$ and $α_{2} = \frac{1}{3}$ . Then $x_{3} = - \frac{1}{2} - \frac{1}{3} (- 1) = - \frac{1}{2} + \frac{1}{3} = - \frac{1}{6}$ . Height $f (x_{3}) = \frac{1}{6}$ .

Step 3. $x_{3} = - \frac{1}{6} < 0$ , so $g_{3} = - 1$ and $α_{3} = \frac{1}{4}$ . Then $x_{4} = - \frac{1}{6} + \frac{1}{4} = \frac{1}{12}$ . Height $f (x_{4}) = \frac{1}{12}$ .

The heights recorded are $1, 0, \frac{1}{2}, \frac{1}{6}, \frac{1}{12}$ . They are not decreasing — step 1 jumped from $0$ up to $\frac{1}{2}$ . But the best-so-far record is $1, 0, 0, 0, 0$ , and the iterates $1, 0, - \frac{1}{2}, - \frac{1}{6}, \frac{1}{12}$ are squeezing toward $0$ .

What this tells us. A single subgradient step can raise the height. We therefore track the smallest height seen, and the shrinking-but-not-too-fast steps pull the iterates in toward the true minimiser. The method is slow and wobbly, but it never needs the function to be smooth.

Check your understanding Beginner

Exercise (easy, multiple-choice).

Why do we use steps that shrink toward zero but whose lengths still add up to infinity?

So the method runs faster than a smooth gradient method.
So the steps are small enough to settle near the minimum, yet their total length is large enough to travel any distance to reach it.
Because subgradients do not exist for small steps.
To make the function value decrease at every step.

Hint

Think about what a fixed step size fails to do, and what a too-fast-shrinking step size fails to do.

Answer

B. Shrinking steps let the iterates settle rather than jitter; keeping the total length infinite means the iterates can still reach a starting-point-to-minimum distance of any size. Feedback-correct: both halves of the rule matter — shrink to settle, sum to infinity to travel. Feedback-wrong: A is false (subgradient methods are slower, not faster), C confuses existence with size, and D is impossible since the value need not decrease.

Formal definition Intermediate+

Let $f : R^{n} \to R$ be convex (notation from 44.01.01) with a nonempty set of minimisers and optimal value $f^{⋆} = in f_{x} f (x) > - \infty$ . Fix a minimiser $x^{⋆}$ . By the subgradient inequality of 44.02.05, $g \in \partial f (x)$ means

f (y) \geq f (x) + ⟨ g, y - x ⟩ for all y \in R^{n} .

Definition (subgradient method). Choose $x_{0} \in R^{n}$ and step sizes $α_{k} > 0$ . The subgradient method generates

x_{k + 1} = x_{k} - α_{k} g_{k}, g_{k} \in \partial f (x_{k}) .

Because $g_{k}$ is an arbitrary element of $\partial f (x_{k})$ , the direction $- g_{k}$ need not be a descent direction: $f (x_{k + 1})$ may exceed $f (x_{k})$ . The convergence object is therefore the best-so-far value

f_{best}^{k} := 0 \leq i \leq k min f (x_{i}),

which is nonincreasing by construction.

Definition (Lipschitz / bounded-subgradient class). $f$ is $L$ -Lipschitz on a set containing the iterates if $∣ f (x) - f (y) ∣ \leq L ∥ x - y ∥$ , equivalently $∥ g ∥ \leq L$ for every $g \in \partial f (x)$ at every relevant $x$ . This bounded-subgradient hypothesis is the standing assumption for the rate.

Definition (step-size rules). With $G := sup_{k} ∥ g_{k} ∥ \leq L$ :

Constant step size: $α_{k} = α$ fixed.
Constant step length: $α_{k} = s /∥ g_{k} ∥$ , so $∥ x_{k + 1} - x_{k} ∥ = s$ fixed.
Diminishing nonsummable: $α_{k} \to 0$ with $\sum_{k} α_{k} = \infty$ ; often also square-summable, $\sum_{k} α_{k}^{2} < \infty$ .
Polyak's step (optimal, $f^{⋆}$ known): $α_{k} = (f (x_{k}) - f^{⋆}) /∥ g_{k} ∥^{2}$ .

Definition (projected subgradient method). For the constrained problem $min_{x \in C} f (x)$ with $C$ closed convex and nonempty, let $P_{C}$ denote Euclidean projection onto $C$ . The projected subgradient method is

x_{k + 1} = P_{C} (x_{k} - α_{k} g_{k}), g_{k} \in \partial f (x_{k}) .

Projection onto a closed convex set is firmly nonexpansive, in particular $∥ P_{C} (u) - P_{C} (v) ∥ \leq ∥ u - v ∥$ , which is the only property of $P_{C}$ the analysis uses; the unconstrained method is the case $C = R^{n}$ , $P_{C} = id$ .

Counterexamples to common slips Intermediate+

"The subgradient method is a descent method." It is not. For $f (x) = ∣ x ∣$ at $x = 0$ a valid subgradient is $g = 1$ , and any positive step raises the value. One must monitor $f_{best}^{k}$ , never $f (x_{k})$ .
"A constant step size converges to $f^{⋆}$ ." It does not in general. With $α_{k} = α$ the best value converges only to a band, $lim inf_{k} f_{best}^{k} \leq f^{⋆} + L^{2} α /2$ ; exact convergence needs $α_{k} \to 0$ .
" $\sum_{k} α_{k}^{2} < \infty$ alone gives convergence." Square-summability controls the noise term but kills travel: if also $\sum_{k} α_{k} < \infty$ the iterates cannot move farther than a fixed distance from $x_{0}$ , so a minimiser beyond that distance is unreachable. Nonsummability $\sum_{k} α_{k} = \infty$ is the indispensable half.

Key theorem with proof Intermediate+

The entire convergence theory rests on one recursion relating the squared distance to a minimiser at consecutive iterates. Every step-size rule is then a corollary of how one telescopes and bounds that single inequality.

Theorem (fundamental inequality and the $O (1/ k)$ rate). Let $f$ be convex and $L$ -Lipschitz with minimiser $x^{⋆}$ , and run the projected subgradient method $x_{k + 1} = P_{C} (x_{k} - α_{k} g_{k})$ with $x^{⋆} \in C$ . Then for every $k$ ,

∥ x_{k + 1} - x^{⋆} ∥^{2} \leq ∥ x_{k} - x^{⋆} ∥^{2} - 2 α_{k} (f (x_{k}) - f^{⋆}) + α_{k}^{2} ∥ g_{k} ∥^{2} . (*)

Consequently, writing $R = ∥ x_{0} - x^{⋆} ∥$ and $G = sup_{i} ∥ g_{i} ∥ \leq L$ ,

f_{best}^{k} - f^{⋆} \leq \frac{R ^{2} + G ^{2} \sum _{i = 0}^{k} α _{i}^{2}}{2 \sum _{i = 0}^{k} α _{i}} . (* *)

With the fixed-horizon choice $α_{i} = R / (G k + 1)$ for $i = 0, \dots, k$ , this gives $f_{best}^{k} - f^{⋆} \leq R G / k + 1$ .

Proof. Set $u_{k} = x_{k} - α_{k} g_{k}$ , so $x_{k + 1} = P_{C} (u_{k})$ . Since $x^{⋆} \in C$ and projection is nonexpansive, $∥ x_{k + 1} - x^{⋆} ∥ = ∥ P_{C} (u_{k}) - P_{C} (x^{⋆}) ∥ \leq ∥ u_{k} - x^{⋆} ∥$ . Hence

∥ x_{k + 1} - x^{⋆} ∥^{2} \leq ∥ u_{k} - x^{⋆} ∥^{2} = ∥ x_{k} - x^{⋆} ∥^{2} - 2 α_{k} ⟨ g_{k}, x_{k} - x^{⋆} ⟩ + α_{k}^{2} ∥ g_{k} ∥^{2} .

The subgradient inequality at $x_{k}$ with $y = x^{⋆}$ reads $f^{⋆} = f (x^{⋆}) \geq f (x_{k}) + ⟨ g_{k}, x^{⋆} - x_{k} ⟩$ , i.e. $⟨ g_{k}, x_{k} - x^{⋆} ⟩ \geq f (x_{k}) - f^{⋆}$ . Substituting this lower bound (it appears with a minus sign) gives $(*)$ .

Now telescope $(*)$ from $i = 0$ to $k$ . Dropping the nonnegative final distance,

0 \leq ∥ x_{k + 1} - x^{⋆} ∥^{2} \leq ∥ x_{0} - x^{⋆} ∥^{2} - 2 i = 0 \sum k α_{i} (f (x_{i}) - f^{⋆}) + i = 0 \sum k α_{i}^{2} ∥ g_{i} ∥^{2} .

Each $f (x_{i}) - f^{⋆} \geq f_{best}^{k} - f^{⋆}$ since $f_{best}^{k}$ is the smallest, so $\sum_{i} α_{i} (f (x_{i}) - f^{⋆}) \geq (f_{best}^{k} - f^{⋆}) \sum_{i} α_{i}$ . Using $∥ g_{i} ∥ \leq G$ and rearranging,

2 (i = 0 \sum k α_{i}) (f_{best}^{k} - f^{⋆}) \leq R^{2} + G^{2} i = 0 \sum k α_{i}^{2},

which is $(* *)$ . For the final claim put $α_{i} = R / (G k + 1)$ : then $\sum_{i = 0}^{k} α_{i} = (k + 1) \cdot R / (G k + 1) = R k + 1 / G$ and $\sum_{i = 0}^{k} α_{i}^{2} = (k + 1) R^{2} / (G^{2} (k + 1)) = R^{2} / G^{2}$ , so the right side of $(* *)$ is $(R^{2} + R^{2}) / (2 R k + 1 / G) = R G / k + 1$ . $□$

Bridge. This single recursion $(*)$ is the foundational reason every step-size rule works, and it builds toward the convergence statements of the Advanced results, where diminishing nonsummable and Polyak steps are read off $(* *)$ directly. This is exactly the nonsmooth analogue of the descent lemma behind smooth gradient methods, except that the $- 2 α_{k} (f (x_{k}) - f^{⋆})$ term replaces a guaranteed decrease in $f$ by a guaranteed decrease in distance to the optimum on average — the central insight that distance, not value, is the Lyapunov quantity. The bound $(* *)$ generalises the smooth case to arbitrary subgradients, and the resulting $O (1/ k)$ rate is dual to the $Ω (1/ k)$ lower bound proved later: putting these together, the subgradient method is exactly optimal for the nonsmooth black-box class, and it appears again in the proximal and accelerated methods 44.06.0244.06.03 precisely as the baseline they must beat by exploiting structure this rate ignores.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Derive Polyak's step $α_{k} = (f (x_{k}) - f^{⋆}) /∥ g_{k} ∥^{2}$ by minimising the right-hand side of $(*)$ over $α_{k}$ , and show it yields $∥ x_{k + 1} - x^{⋆} ∥^{2} \leq ∥ x_{k} - x^{⋆} ∥^{2} - (f (x_{k}) - f^{⋆})^{2} /∥ g_{k} ∥^{2}$ .

Hint

The right side of $(*)$ is a quadratic in $α_{k}$ ; set its derivative to zero.

Answer

Treat $q (α) = ∥ x_{k} - x^{⋆} ∥^{2} - 2 α (f (x_{k}) - f^{⋆}) + α^{2} ∥ g_{k} ∥^{2}$ . Then $q^{'} (α) = - 2 (f (x_{k}) - f^{⋆}) + 2 α ∥ g_{k} ∥^{2} = 0$ gives $α = (f (x_{k}) - f^{⋆}) /∥ g_{k} ∥^{2}$ , the unique minimiser since $q$ is convex in $α$ . Substituting back, the linear and quadratic terms combine to $- (f (x_{k}) - f^{⋆})^{2} /∥ g_{k} ∥^{2}$ , giving the stated guaranteed distance decrease. This step is "optimal" in the sense of maximising the per-step contraction of the distance, and it requires knowing $f^{⋆}$ .

Exercise 6 (hard, symbolic).

Prove that diminishing nonsummable steps converge: if $α_{k} \to 0$ and $\sum_{k} α_{k} = \infty$ (with $∥ g_{k} ∥ \leq G$ ), then $f_{best}^{k} \to f^{⋆}$ .

Hint

In $(* *)$ show $\sum_{i = 0}^{k} α_{i}^{2} / \sum_{i = 0}^{k} α_{i} \to 0$ using that $α_{i} \to 0$ and the denominator diverges.

Answer

From $(* *)$ , $f_{best}^{k} - f^{⋆} \leq R^{2} / (2 S_{k}) + G^{2} T_{k} / (2 S_{k})$ with $S_{k} = \sum_{i = 0}^{k} α_{i}$ , $T_{k} = \sum_{i = 0}^{k} α_{i}^{2}$ . Since $\sum α_{i} = \infty$ , $S_{k} \to \infty$ , so $R^{2} / (2 S_{k}) \to 0$ . For the second term, fix $ε > 0$ ; since $α_{i} \to 0$ there is $N$ with $α_{i} \leq ε$ for $i > N$ , so $T_{k} = \sum_{i \leq N} α_{i}^{2} + \sum_{N < i \leq k} α_{i}^{2} \leq C_{N} + ε \sum_{N < i \leq k} α_{i} \leq C_{N} + ε S_{k}$ where $C_{N} = \sum_{i \leq N} α_{i}^{2}$ is constant. Then $T_{k} / S_{k} \leq C_{N} / S_{k} + ε \to ε$ as $k \to \infty$ . As $ε$ was arbitrary, $T_{k} / S_{k} \to 0$ , so the whole bound tends to $0$ and $f_{best}^{k} \to f^{⋆}$ . Square-summability $\sum α_{i}^{2} < \infty$ is not even required; nonsummability of $\sum α_{i}$ and $α_{i} \to 0$ suffice.

Exercise 7 (hard, symbolic).

For the projected method on $min_{x \in C} f (x)$ , suppose $f$ is the support of a sparsity-promoting term, e.g. $f (x) = ∥ x ∥_{1}$ on the simplex $C = {x \geq 0, \sum_{i} x_{i} = 1}$ . Using Exercise 2 of 44.02.05 ( $\partial ι_{C} = N_{C}$ ), explain why the projected subgradient step $x_{k + 1} = P_{C} (x_{k} - α_{k} g_{k})$ is exactly the Fermat condition $0 \in \partial f (x^{⋆}) + N_{C} (x^{⋆})$ in the limit.

Hint

A fixed point of the projected iteration satisfies $x^{⋆} = P_{C} (x^{⋆} - α g)$ ; characterise projection fixed points via the normal cone.

Answer

A fixed point obeys $x^{⋆} = P_{C} (x^{⋆} - α g)$ for some $g \in \partial f (x^{⋆})$ , $α > 0$ . The projection characterisation says $z = P_{C} (u)$ iff $u - z \in N_{C} (z)$ ; here $u - z = (x^{⋆} - α g) - x^{⋆} = - α g$ , so $- α g \in N_{C} (x^{⋆})$ , i.e. $- g \in N_{C} (x^{⋆})$ (the cone is invariant under positive scaling). Thus $0 = g + (- g) \in \partial f (x^{⋆}) + N_{C} (x^{⋆})$ , the constrained Fermat/optimality condition derived in Exercise 3 of 44.02.05. The projected subgradient iteration is the algorithmic realisation of that variational inequality: its fixed points are exactly the constrained stationary points, which for convex $f$ are the constrained minimisers.

Exercise 8 (hard, symbolic).

Show the rate $O (1/ k)$ cannot be improved to $o (1/ k)$ by the choice of step alone: for $f (x) = ∣ x ∣$ on $R$ with $L = 1$ and any nonincreasing positive steps, exhibit the order of $f_{best}^{k}$ in the worst case over $x_{0}$ , and contrast with the smooth $O (1/ k)$ gradient-descent rate.

Hint

The bound $(* *)$ optimised over constant-on-a-horizon steps is $Θ (1/ k)$ ; you only need to argue the bound is tight in order, not exhibit the exact constant.

Answer

Optimising $(* *)$ over the step schedule for fixed horizon $k$ gives $f_{best}^{k} - f^{⋆} = O (R G / k + 1)$ , and the matching information-based lower bound (Advanced results) shows no first-order method can beat $Ω (R G / k)$ on the nonsmooth Lipschitz class, of which $f (x) = ∣ x ∣$ is the one-dimensional witness once embedded with a moving kink. So the order is $Θ (1/ k)$ and cannot be improved to $o (1/ k)$ within the black-box subgradient model. The contrast is structural: gradient descent on an $L$ -smooth (not merely Lipschitz) convex $f$ attains $O (L R^{2} / k)$ because the smoothness yields a genuine per-step decrease in value; the subgradient method has no such decrease, and the slower $1/ k$ is the cost of nonsmoothness, not of a poor algorithm. Acceleration 44.06.03 recovers the smooth rate only by exploiting smoothness the nonsmooth class lacks.

Advanced results Master

The subgradient method is the iteration $x_{k + 1} = P_{C} (x_{k} - α_{k} g_{k})$ with $g_{k} \in \partial f (x_{k})$ , and the results below convert the fundamental inequality $(*)$ into the convergence of each step-size rule, then bound the method from below to show the $O (1/ k)$ rate is unimprovable for the nonsmooth first-order class.

Theorem 1 (step-size rules: a unified convergence table). Under $∥ g_{k} ∥ \leq G$ and $f$ convex with minimiser $x^{⋆}$ , the bound $(* *)$ specialises as follows. Constant step $α_{k} = α$ : $lim inf_{k} f_{best}^{k} \leq f^{⋆} + G^{2} α /2$ , convergence to a band of half-width $G^{2} α /2$ . Constant step length $α_{k} = s /∥ g_{k} ∥$ : $lim inf_{k} f_{best}^{k} \leq f^{⋆} + G s /2$ . Diminishing nonsummable $α_{k} \to 0$ , $\sum_{k} α_{k} = \infty$ : $f_{best}^{k} \to f^{⋆}$ (Exercise 6). Square-summable nonsummable $\sum α_{k}^{2} < \infty$ , $\sum α_{k} = \infty$ (e.g. $α_{k} = c / (k + 1)$ ): not only $f_{best}^{k} \to f^{⋆}$ but the iterates themselves converge, $x_{k} \to$ some minimiser, because $(*)$ makes $∥ x_{k} - x^{⋆} ∥^{2}$ a quasi-Fejér sequence with summable perturbation ^{[Beck, A. — First-Order Methods in Optimization]}. Only the constant rules leave a residual band; the diminishing rules achieve exact optimality, at the cost of an asymptotically vanishing step.

Theorem 2 (Polyak's step and its dynamic variant). When $f^{⋆}$ is known, Polyak's step $α_{k} = (f (x_{k}) - f^{⋆}) /∥ g_{k} ∥^{2}$ minimises the per-step distance bound (Exercise 4) and yields $∥ x_{k + 1} - x^{⋆} ∥^{2} \leq ∥ x_{k} - x^{⋆} ∥^{2} - (f (x_{k}) - f^{⋆})^{2} / G^{2}$ ; summing, $\sum_{k} (f (x_{k}) - f^{⋆})^{2} \leq G^{2} R^{2}$ , so $f (x_{k}) \to f^{⋆}$ and the same $O (1/ k)$ best-iterate rate holds with the best constant among all step rules. When $f^{⋆}$ is unknown a running estimate $f_{est}^{⋆}$ (e.g. a level-set or target-value update, the basis of the level method) replaces it; this is the practical entry point to bundle methods ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}.

Theorem 3 (the $Ω (1/ k)$ lower bound for nonsmooth first-order methods). Consider the black-box model: an algorithm queries a subgradient oracle and forms iterates in the affine span of past subgradients, $x_{k} \in x_{0} + span {g_{0}, \dots, g_{k - 1}}$ . Then for every such method there is a convex $L$ -Lipschitz function on a ball of radius $R$ in $R^{k + 1}$ for which

f (x_{k}) - f^{⋆} \geq \frac{L R}{2 ( 1 + k + 1 )} = Ω (\frac{L R}{k}) .

The witness is the resisting-oracle function $f (x) = max_{1 \leq i \leq k + 1} x_{i} + \frac{μ}{2} ∥ x ∥^{2}$ (Nesterov's "worst function in the world" for the nonsmooth class): an adversarial oracle returns the subgradient of a coordinate not yet activated, so after $k$ queries the iterate has touched only $k$ of the $k + 1$ coordinates and cannot have reduced the max below a fixed gap ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}. Because the subgradient method attains $O (L R / k)$ (Key theorem), the two bounds match in order: the subgradient method is optimal for the nonsmooth black-box class, and no first-order method can be faster without leaving that class.

Theorem 4 (stochastic and incremental subgradient methods). Replacing $g_{k}$ by an unbiased estimator $\tilde{g}_{k}$ with $E [\tilde{g}_{k} ∣ x_{k}] \in \partial f (x_{k})$ and $E ∥ \tilde{g}_{k} ∥^{2} \leq G^{2}$ leaves $(*)$ valid in expectation, so the stochastic subgradient method retains the $O (1/ k)$ rate on $E [f_{best}^{k}] - f^{⋆}$ — the foundational fact behind stochastic-gradient training of nonsmooth convex losses. The incremental variant, cycling subgradients of the components of a finite sum $f = \sum_{i} f_{i}$ , fits the same template with a component-wise bound, giving the cheap-per-iteration method used at large scale ^{[Bertsekas, D. P. — Convex Optimization Algorithms]}. In all variants the analysis is the one recursion $(*)$ ; only the bound on the noise term changes.

Synthesis. The fundamental inequality $(*)$ is the single invariant from which the entire theory descends, and the central insight is that the squared distance to the optimum, not the function value, is the Lyapunov quantity — this is exactly why the method need not be a descent method yet still converges. The foundational reason every step rule succeeds or fails is visible in $(* *)$ : convergence needs $\sum α_{i} = \infty$ (to make the $R^{2} / \sum α_{i}$ term vanish) while exactness needs $\sum α_{i}^{2} / \sum α_{i} \to 0$ (to kill the noise term), and the constant rules fail the second test, leaving the residual band of Theorem 1. Polyak's step is the pointwise optimiser of $(*)$ and generalises to the level and bundle methods when $f^{⋆}$ is estimated. The $O (1/ k)$ upper bound is dual to the $Ω (1/ k)$ resisting-oracle lower bound, and putting these together pins the complexity of the nonsmooth black-box class exactly: the subgradient method is optimal there, and the bridge to the rest of the chapter is precisely this optimality barrier — proximal-gradient 44.06.02 and accelerated 44.06.03 methods beat $1/ k$ only by leaving the black-box model, splitting off a smooth part and exploiting its gradient, a structural escape the lower bound shows is the only one available.

Full proof set Master

Proposition 1 (fundamental inequality). Let $f$ be convex with minimiser $x^{⋆} \in C$ , $C$ closed convex, and run $x_{k + 1} = P_{C} (x_{k} - α_{k} g_{k})$ , $g_{k} \in \partial f (x_{k})$ . Then $∥ x_{k + 1} - x^{⋆} ∥^{2} \leq ∥ x_{k} - x^{⋆} ∥^{2} - 2 α_{k} (f (x_{k}) - f^{⋆}) + α_{k}^{2} ∥ g_{k} ∥^{2}$ .

Proof. Let $u_{k} = x_{k} - α_{k} g_{k}$ . Projection onto a closed convex set is nonexpansive and $P_{C} (x^{⋆}) = x^{⋆}$ , so $∥ x_{k + 1} - x^{⋆} ∥^{2} = ∥ P_{C} (u_{k}) - P_{C} (x^{⋆}) ∥^{2} \leq ∥ u_{k} - x^{⋆} ∥^{2}$ . Expand $∥ u_{k} - x^{⋆} ∥^{2} = ∥ x_{k} - x^{⋆} ∥^{2} - 2 α_{k} ⟨ g_{k}, x_{k} - x^{⋆} ⟩ + α_{k}^{2} ∥ g_{k} ∥^{2}$ . The subgradient inequality 44.02.05 at $x_{k}$ evaluated at $x^{⋆}$ gives $f^{⋆} \geq f (x_{k}) + ⟨ g_{k}, x^{⋆} - x_{k} ⟩$ , i.e. $⟨ g_{k}, x_{k} - x^{⋆} ⟩ \geq f (x_{k}) - f^{⋆}$ . Replacing $- 2 α_{k} ⟨ g_{k}, x_{k} - x^{⋆} ⟩$ by its upper bound $- 2 α_{k} (f (x_{k}) - f^{⋆})$ yields the claim. $□$

Proposition 2 (best-iterate bound). Under Proposition 1 and $∥ g_{i} ∥ \leq G$ , $f_{best}^{k} - f^{⋆} \leq (R^{2} + G^{2} \sum_{i = 0}^{k} α_{i}^{2}) / (2 \sum_{i = 0}^{k} α_{i})$ with $R = ∥ x_{0} - x^{⋆} ∥$ .

Proof. Sum Proposition 1 for $i = 0, \dots, k$ ; the distances telescope, and dropping $∥ x_{k + 1} - x^{⋆} ∥^{2} \geq 0$ ,

2 i = 0 \sum k α_{i} (f (x_{i}) - f^{⋆}) \leq R^{2} + G^{2} i = 0 \sum k α_{i}^{2} .

Since $f (x_{i}) - f^{⋆} \geq f_{best}^{k} - f^{⋆} \geq 0$ , the left side is $\geq 2 (f_{best}^{k} - f^{⋆}) \sum_{i} α_{i}$ . Divide by $2 \sum_{i} α_{i} > 0$ . $□$

Proposition 3 (optimal fixed-horizon rate). Choosing $α_{i} = R / (G k + 1)$ for $i \leq k$ gives $f_{best}^{k} - f^{⋆} \leq R G / k + 1$ , and this $α$ minimises the right side of Proposition 2 over constant schedules.

Proof. With $α_{i} = α$ constant, Proposition 2 reads $g (α) := R^{2} / (2 (k + 1) α) + G^{2} α /2$ . Then $g^{'} (α) = - R^{2} / (2 (k + 1) α^{2}) + G^{2} /2 = 0$ gives $α^{2} = R^{2} / ((k + 1) G^{2})$ , i.e. $α = R / (G k + 1)$ , a minimum since $g^{''} > 0$ . At this $α$ , $g (α) = R^{2} / (2 (k + 1)) \cdot G k + 1 / R + G^{2} /2 \cdot R / (G k + 1) = R G / (2 k + 1) + R G / (2 k + 1) = R G / k + 1$ . $□$

Proposition 4 (Polyak step optimality and convergence). With $α_{k} = (f (x_{k}) - f^{⋆}) /∥ g_{k} ∥^{2}$ and $∥ g_{k} ∥ \leq G$ , one has $∥ x_{k + 1} - x^{⋆} ∥^{2} \leq ∥ x_{k} - x^{⋆} ∥^{2} - (f (x_{k}) - f^{⋆})^{2} / G^{2}$ , hence $\sum_{k} (f (x_{k}) - f^{⋆})^{2} \leq G^{2} R^{2}$ and $f (x_{k}) \to f^{⋆}$ .

Proof. The right side of Proposition 1 is a convex quadratic in $α_{k}$ minimised at $α_{k} = (f (x_{k}) - f^{⋆}) /∥ g_{k} ∥^{2}$ , where its value is $∥ x_{k} - x^{⋆} ∥^{2} - (f (x_{k}) - f^{⋆})^{2} /∥ g_{k} ∥^{2} \leq ∥ x_{k} - x^{⋆} ∥^{2} - (f (x_{k}) - f^{⋆})^{2} / G^{2}$ using $∥ g_{k} ∥ \leq G$ . Telescoping, $\sum_{k = 0}^{N} (f (x_{k}) - f^{⋆})^{2} / G^{2} \leq ∥ x_{0} - x^{⋆} ∥^{2} - ∥ x_{N + 1} - x^{⋆} ∥^{2} \leq R^{2}$ , so $\sum_{k} (f (x_{k}) - f^{⋆})^{2} \leq G^{2} R^{2} < \infty$ ; the summand tends to $0$ , so $f (x_{k}) \to f^{⋆}$ . The partial-sum bound also gives $min_{k \leq N} (f (x_{k}) - f^{⋆})^{2} \leq G^{2} R^{2} / (N + 1)$ , recovering the $O (1/ N)$ best-iterate rate. $□$

Proposition 5 ( $Ω (1/ k)$ lower bound, resisting-oracle construction). In the black-box first-order model with iterates in $x_{0} + span {g_{0}, \dots, g_{k - 1}}$ and $x_{0} = 0$ , there is a convex $1$ -Lipschitz $f$ on the unit ball of $R^{k + 1}$ with $f (x_{k}) - f^{⋆} = Ω (1/ k)$ .

Proof. Take $f (x) = max_{1 \leq i \leq k + 1} x_{i}$ , which is convex and $1$ -Lipschitz in $ℓ_{2}$ on the unit ball (a single coordinate subgradient $e_{i}$ at points where $x_{i}$ is the max). Run the oracle so that at $x_{j}$ it returns $g_{j} = e_{i (j)}$ for the smallest index $i (j)$ attaining the max; with $x_{0} = 0$ all coordinates tie, and an adversarial tie-break returns $e_{1}$ , then $e_{2}$ , and so on. By induction $x_{j} \in span {e_{1}, \dots, e_{j}}$ , so $x_{k}$ has its last coordinate $x_{k, k + 1} = 0$ , giving $f (x_{k}) \geq 0$ . The minimiser of $f$ on the ball of radius $R$ is the balanced point $x^{⋆}$ with all coordinates equal to $- R / k + 1$ , where $f (x^{⋆}) = - R / k + 1$ . Hence $f (x_{k}) - f^{⋆} \geq 0 - (- R / k + 1) = R / k + 1$ . Adding the regulariser $\frac{μ}{2} ∥ x ∥^{2}$ and optimising $μ$ sharpens the constant to the stated $L R / (2 (1 + k + 1))$ without changing the order; the iterate, having activated only $k$ coordinates, is provably $Ω (1/ k)$ from optimal ^{[Nesterov, Y. — Lectures on Convex Optimization (2nd ed.)]}. $□$

Proposition 6 (projection fixed points are constrained minimisers). For convex $f$ and closed convex $C$ , $x^{⋆}$ is a fixed point of $x \mapsto P_{C} (x - α g (x))$ for some $g (x^{⋆}) \in \partial f (x^{⋆})$ and $α > 0$ iff $0 \in \partial f (x^{⋆}) + N_{C} (x^{⋆})$ , iff $x^{⋆}$ minimises $f$ over $C$ .

Proof. The variational characterisation of Euclidean projection states $z = P_{C} (u) ⟺ ⟨ u - z, y - z ⟩ \leq 0$ for all $y \in C ⟺ u - z \in N_{C} (z)$ . With $u = x^{⋆} - α g$ , $z = x^{⋆}$ : fixed-point means $- α g \in N_{C} (x^{⋆})$ , i.e. $- g \in N_{C} (x^{⋆})$ by positive homogeneity of the cone, i.e. $0 \in \partial f (x^{⋆}) + N_{C} (x^{⋆})$ . By the constrained Fermat rule (Exercise 3 of 44.02.05) this is equivalent to $x^{⋆} \in ar g min_{x \in C} f (x)$ for convex $f$ . $□$

Connections Master

The subgradient inequality and the Fermat rule of 44.02.05 are the only facts about $f$ the method uses: the fundamental inequality $(*)$ is the subgradient inequality applied at the minimiser, and the projected method's fixed points are exactly the constrained-Fermat points $0 \in \partial f (x^{⋆}) + N_{C} (x^{⋆})$ assembled from the normal-cone subdifferential of an indicator and the sum rule proved there. The whole convergence theory is one corollary of that unit's calculus.
The convexity theory of 44.01.01 supplies the structural guarantee that converts the iteration's stationarity into optimality: $(*)$ delivers only that the squared distance to a minimiser contracts on average, but convexity makes every Fermat/stationary point a global minimiser and makes the best-so-far value a meaningful certificate, while the Lipschitz/bounded-subgradient hypothesis that fixes the $O (1/ k)$ constant is the first-order regularity condition that unit formalises through the support function.
The proximal-gradient method 44.06.02 and accelerated (momentum) methods 44.06.03 are the direct successors that exist precisely to beat the $Ω (1/ k)$ lower bound proved here: by splitting the objective into a smooth part (handled by its gradient) and a nonsmooth part (handled by a proximal step rather than an arbitrary subgradient), they leave the black-box model in which $1/ k$ is unimprovable and reach $O (1/ k)$ and $O (1/ k^{2})$ . The lower bound of this unit is the exact boundary marking where that structural escape becomes necessary.

Historical & philosophical context Master

The subgradient method originates with Naum Z. Shor in the early-to-mid 1960s, who introduced subgradient (generalised-gradient) steps for nonsmooth minimisation arising in large-scale linear and network problems; his work, with that of Boris T. Polyak and Yurii M. Ermoliev, established the method and the diminishing-step convergence theory in the Soviet optimisation school ^{[Shor 1985]}. Polyak contributed the optimal step $α_{k} = (f (x_{k}) - f^{⋆}) /∥ g_{k} ∥^{2}$ that bears his name and the quasi-Fejér convergence analysis of the distance sequence ^{[Polyak 1987]}. The information-based complexity viewpoint — that the $O (1/ k)$ rate is not a deficiency of a particular algorithm but a hard limit of the nonsmooth black-box oracle model — is due to Arkadi Nemirovski and David Yudin, whose 1983 monograph proved the matching lower bound by the resisting-oracle construction ^{[Nemirovski & Yudin 1983]}. The modern textbook synthesis, including the projected variant, the unified step-size analysis, and the lower bound in the "worst function in the world" form, is given by Nesterov ^{[Nesterov 2018]} and by Beck ^{[Beck 2017]}, the source from which this unit's notation and fundamental inequality are taken.

Bibliography Master

@book{beck2017fom,
  author    = {Beck, Amir},
  title     = {First-Order Methods in Optimization},
  series    = {MOS-SIAM Series on Optimization},
  number    = {25},
  publisher = {SIAM},
  year      = {2017}
}

@book{nesterov2018lectures,
  author    = {Nesterov, Yurii},
  title     = {Lectures on Convex Optimization},
  edition   = {2},
  series    = {Springer Optimization and Its Applications},
  volume    = {137},
  publisher = {Springer},
  year      = {2018}
}

@book{bertsekas2015convex,
  author    = {Bertsekas, Dimitri P.},
  title     = {Convex Optimization Algorithms},
  publisher = {Athena Scientific},
  year      = {2015}
}

@book{shor1985minimization,
  author    = {Shor, Naum Z.},
  title     = {Minimization Methods for Non-Differentiable Functions},
  series    = {Springer Series in Computational Mathematics},
  volume    = {3},
  publisher = {Springer},
  year      = {1985}
}

@book{polyak1987introduction,
  author    = {Polyak, Boris T.},
  title     = {Introduction to Optimization},
  publisher = {Optimization Software, Inc.},
  address   = {New York},
  year      = {1987}
}

@book{nemirovskiyudin1983,
  author    = {Nemirovski, Arkadi S. and Yudin, David B.},
  title     = {Problem Complexity and Method Efficiency in Optimization},
  publisher = {Wiley-Interscience},
  year      = {1983}
}

Prerequisites

44.01.01
44.02.05

Tier anchors

beginner: Boyd, Xiao & Mutapcic 2003 EE364b Subgradient Methods notes (Stanford) — the why-it-is-not-a-descent-method picture and the diminishing-step intuition; Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §3.1.3 on subgradients
intermediate: Beck 2017 First-Order Methods in Optimization (SIAM) §8.2-8.3 (the projected subgradient method, the fundamental inequality, and the O(1/√k) rate); Nesterov 2018 Lectures on Convex Optimization (Springer) §3.2.3
master: Nesterov 2018 Lectures on Convex Optimization (Springer) §3.2 (the O(1/√k) upper bound, Polyak's step, and the matching Ω(1/√k) lower bound for nonsmooth first-order methods via the resisting-oracle construction); Beck 2017 First-Order Methods in Optimization (SIAM) Ch. 8; Bertsekas 2015 Convex Optimization Algorithms (Athena) §3.2

References

Beck, A. — First-Order Methods in Optimization · MOS-SIAM Series on Optimization 25 (SIAM, 2017). Ch. 8 'The Subgradient Method': the projected subgradient iteration x_{k+1}=P_C(x_k-t_k g_k) with g_k in partial-f(x_k); the fundamental recursion ||x_{k+1}-x*||^2 <= ||x_k-x*||^2 - 2 t_k (f(x_k)-f*) + t_k^2 ||g_k||^2 obtained from nonexpansiveness of the projection and the subgradient inequality; the resulting bound min_{i<=k}(f(x_i)-f*) <= (||x_0-x*||^2 + L^2 sum t_i^2)/(2 sum t_i) for L-Lipschitz f; the step-size rules (constant t, constant step length t_k=s/||g_k||, diminishing nonsummable t_k->0 with sum t_k = infinity, and Polyak's t_k=(f(x_k)-f*)/||g_k||^2 when f* is known) and the O(1/sqrt(k)) rate t_k = D/(L sqrt(k+1)); the dynamic/Polyak choices and convergence of the best-so-far value.
Nesterov, Y. — Lectures on Convex Optimization (2nd ed.) · Springer Optimization and Its Applications 137 (2018). §3.2 'Nonsmooth Convex Optimization': the subgradient method as the canonical black-box method for the nonsmooth Lipschitz class, the O(1/sqrt(k)) efficiency estimate for the best iterate under a bounded-subgradient assumption, the optimal fixed-horizon step t_k = R/(M sqrt(k+1)), and §3.2.1 the lower-complexity bound Omega(1/sqrt(k)) (the f(x)=max_i x_i + (mu/2)||x||^2 resisting-oracle / worst-function-in-the-world construction) proving the subgradient rate is unimprovable for first-order methods on the nonsmooth class; the projected variant and the relation to the level/bundle methods.
Boyd, S., Xiao, L. & Mutapcic, A. — Subgradient Methods (EE364b course notes) · Stanford University, lecture notes for EE364b (2003, revised 2008). The subgradient iteration x_{k+1}=x_k - alpha_k g_k; the observation that f(x_k) need not decrease so f_best^k = min_{i<=k} f(x_i) is the right convergence object; the basic inequality ||x_{k+1}-x*||^2 <= ||x_k-x*||^2 - 2 alpha_k (f(x_k)-f*) + alpha_k^2 ||g_k||^2 and the suboptimality bound it yields; the catalogue of step rules (constant size, constant length, square-summable-but-not-summable, nonsummable diminishing, and Polyak's optimal step f(x_k)-f* over ||g_k||^2); numerical behaviour on the least-1-norm and piecewise-linear examples.

Estimated time

beginner: 18m
intermediate: 48m
master: 85m