Coordinate Descent and Block-Coordinate Methods

Intuition Beginner

Suppose you must tune a machine with hundreds of dials to make some reading as small as possible. Adjusting all the dials together is hard: you would need to feel how every dial pulls against every other one at once. Coordinate descent says: stop trying. Fix all the dials but one, and turn that single dial to its best setting while the rest stay frozen. Then move to the next dial and do the same. Sweep through the dials again and again. Each move is a one-dial problem, which is far easier than the all-dials problem, and the reading keeps dropping.

The win is that a one-dial move is cheap. For many large problems, turning one dial only touches a small slice of the data, not all of it, so a single coordinate update can be hundreds of times faster than a full step that touches everything. When the problem has millions of variables but each one connects to only a little data, this cheapness is decisive.

Which dial should you turn next? Three honest choices. Go in order, dial one then dial two, and repeat — the cyclic rule. Pick a dial at random each time — the randomized rule. Or look at all the dials and turn the one that is most out of tune right now — the greedy rule, also called Gauss-Southwell. Cyclic is simplest; random is easy to analyse and avoids bad orderings; greedy makes the most progress per move but costs more to decide.

There is a catch. Turning one dial at a time only reaches the true best setting when the dials do not fight in a tangled way. If the cost has a smooth part plus a penalty that splits cleanly into one piece per dial, the method lands at the genuine minimum. When the pieces are tangled together, one-dial-at-a-time can get stuck circling a spot that is not the best — so the structure of the problem, not just the method, decides whether it works.

Visual Beginner

Picture a bowl-shaped cost over two dials, drawn as oval contour rings. A full step heads straight downhill across both dials. Coordinate descent instead moves only sideways, then only up-and-down, then sideways again — a staircase of axis-aligned moves that still spirals into the centre. Each leg of the staircase is one cheap one-dial solve.

   full step (both dials)            coordinate descent (one dial at a time)

      .-''''-.                          .-''''-.
    /  ____    \                      /  ___|___ \      x0
   |  /    \    |                    |  /    |    |---->  horizontal move (dial 1)
   | | min  |   |   straight         | | min--+   |      |
   |  \____/    | <-- downhill       |  \__|_/    |      v  vertical move (dial 2)
    \          /     path             \   |      /       horizontal, vertical, ...
      '-....-'                          '-..|..-'        staircase into the centre

selection rule	how the next dial is chosen	trade-off
cyclic	sweep in fixed order $1,2,\dots ,n$	simplest; a bad order can be slow
randomized	pick a dial at random each step	easy to analyse; avoids worst orders
Gauss-Southwell (greedy)	turn the most out-of-tune dial	most progress per move; costs more to pick

Worked example Beginner

We minimise a two-dial cost by hand, one dial at a time. Take the cost $f(x_1,x_2)=x_1^2+x_1{x}_2+x_2^2-3x_1$, and start at $x=(0,0)$. The cleanest move per dial is "freeze the other dial, set this one to its best value."

Step 1. Turn dial one, freezing $x_2=0$. The cost in $x_1$ alone is $x_1^2-3x_1$. Its slope is $2x_1-3$; setting the slope to zero gives $x_1=1.5$. So the point moves to $(1.5,0)$.

Step 2. Turn dial two, freezing $x_1=1.5$. The cost in $x_2$ alone is $1.5x_2+x_2^2$ (plus constants). Its slope is $1.5+2x_2$; setting it to zero gives $x_2=-0.75$. The point moves to $(1.5,-0.75)$.

Step 3. Turn dial one again, freezing $x_2=-0.75$. The cost in $x_1$ is $x_1^2-0.75x_1-3x_1=x_1^2-3.75x_1$. Slope $2x_1-3.75=0$ gives $x_1=1.875$. The point moves to $(1.875,-0.75)$.

Step 4. See the drift toward the true minimum. The exact minimum solves $2x_1+x_2=3$ and $x_1+2x_2=0$, giving $x_1=2$, $x_2=-1$. Our staircase $(0,0)\to (1.5,0)\to (1.5,-0.75)\to (1.875,-0.75)$ is closing in on $(2,-1)$, dial by dial.

What this tells us. Each step was a one-variable minimisation — a single slope set to zero — yet the sequence marches toward the genuine two-variable minimum. The cost dropped at every move, and we never had to handle both dials at once.

Check your understanding Beginner

Formal definition Intermediate+

Throughout, $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex and differentiable with optimal value $f^{\star }$ and minimiser $x^{\star }$; the subdifferential and proximal calculus are as in 44.06.02, and $e_i$ denotes the $i$-th standard basis vector. Write ${\nabla }_{i}f(x)=⟨\nabla f(x),e_i⟩$ for the $i$-th partial derivative.

Definition (coordinate Lipschitz constants). $f$ has coordinate Lipschitz constants $L_i>0$ if for all $x$ and $h\in \mathbb{R}$,

$$|{\nabla }_{i}f(x+h{e}_i)-{\nabla }_{i}f(x)|\le L_i|h|,i=1,\dots ,n.$$

Each $L_i\le L$, the global gradient Lipschitz constant, and often $L_i\ll L$ for large $n$, which is the source of the per-iteration advantage. The coordinate descent lemma is the one-variable descent lemma along $e_i$: $f(x+h{e}_i)\le f(x)+h{\nabla }_{i}f(x)+\frac{L_i}{2}{h}^2$.

Definition (coordinate descent step). Given a coordinate $i$, the exact-minimisation step is

$$x^{+}=x+(t^{\star }-x_i)e_i,t^{\star }\in \arg \underset{t\in \mathbb{R}}{\min }f(x+(t-x_i)e_i),$$

and the coordinate-gradient step (minimising the coordinate descent lemma's quadratic model) is

$$x^{+}=x-\frac{1}{L_i}{\nabla }_{i}f(x)e_i.$$

Both change one coordinate while freezing the rest.

Definition (coordinate-selection rules). A coordinate descent method iterates $x_{k+1}=$ a coordinate step at $x_k$ on coordinate $i_k$, where $i_k$ is chosen by one of:

• Cyclic (Gauss-Seidel): $i_k=(k\mathrm{mod}n)+1$, sweeping $1,2,\dots ,n,1,2,\dots$.
• Randomized: $i_k=i$ with probability $p_i>0$ (e.g. $p_i\propto L_i^{\alpha }$), drawn independently of the history.
• Gauss-Southwell (greedy): $i_k\in \arg {\max }_i|{\nabla }_{i}f(x_k)|$, the steepest coordinate.

Definition (separable-composite model and the proximal coordinate step). For the composite objective

$$F(x)=f(x)+\sum _{i=1}^n{g}_i(x_i),$$

with $f$ convex $L$-smooth and each $g_i$ proper closed convex (so the nonsmooth part is block-separable), the proximal coordinate-gradient step on coordinate $i$ is

$$x_i^{+}={\mathrm{prox}}_{(1/L_i)g_i}(x_i-\frac{1}{L_i}{\nabla }_{i}f(x)),x_j^{+}=x_j(j\ne i),$$

using the scalar proximal operator of 44.06.02. Separability is what makes this single-coordinate prox well-defined: ${\mathrm{prox}}_{(1/L_i)g}$ for a sum-separable $g$ acts coordinatewise.

Definition (block-coordinate descent). Partition the coordinates into blocks $x=(x^{(1)},\dots ,x^{(p)})$. Block-coordinate (Gauss-Seidel) minimisation updates one block at a time by exact minimisation,

$$x^{(j)}\leftarrow \arg \underset{u}{\min }F(x^{(1)},\dots ,x^{(j-1)},u,x^{(j+1)},\dots ,x^{(p)}),$$

and the two-block case is alternating minimisation.

Counterexamples to common slips Intermediate+

• "Coordinate descent always converges to a minimiser of a convex function." For smooth convex $f$ it does, but for a nonsmooth nonseparable convex $f$ it can stall at a non-minimiser. The classic obstruction is Powell's example (1973): a smooth nonconvex three-variable function on which cyclic exact coordinate minimisation cycles among the vertices of a set and never reaches a stationary point. The cure is the smooth-plus-separable structure — the nonsmoothness must split coordinatewise.

• "The exact-minimisation step and the coordinate-gradient step are the same." They coincide only for a coordinate-quadratic $f$. In general exact minimisation solves ${\nabla }_{i}f(x^{+})=0$ along $e_i$, while the gradient step moves by $-{\nabla }_{i}f(x)/L_i$; both decrease $f$, but the rate analysis is cleanest for the gradient step via the coordinate descent lemma.

• "Greedy is always best." Gauss-Southwell makes the most progress per iteration, but picking $\arg {\max }_i|{\nabla }_{i}f|$ costs $O(n)$ to scan unless special structure permits cheap maintenance; randomized CD with an $O(1)$ draw can win on wall-clock time despite needing more iterations.

Key theorem with proof Intermediate+

The convergence of every coordinate method rests on one per-step inequality — the coordinate descent lemma's guaranteed decrease — from which the cyclic, randomized, and greedy rates each follow by a different accounting of the chosen coordinate.

Theorem (coordinate sufficient-decrease and the randomized $O(1/k)$ rate). Let $f$ be convex with coordinate Lipschitz constants $L_i$. Then the coordinate-gradient step $x^{+}=x-\frac{1}{L_i}{\nabla }_{i}f(x)e_i$ satisfies

$$f(x)-f(x^{+})\ge \frac{1}{2L_i}({\nabla }_{i}f(x){)}^2.\text{\hspace{1em}(∗)}$$

Consequently, for randomized coordinate descent with $p_i=L_i/S$, $S={\sum }_j{L}_j$, and any minimiser $x^{\star }$,

$$\mathbb{E}[f(x_k)]-f^{\star }\le \frac{2S{R}^2}{k},R^2=\underset{x:f(x)\le f(x_0)}{\max }\Vert x-x^{\star }{\Vert }^2.\text{\hspace{1em}(∗∗)}$$

Proof. Apply the coordinate descent lemma at $x$ along $e_i$ with $h=-\frac{1}{L_i}{\nabla }_{i}f(x)$:

$$f(x^{+})\le f(x)+h{\nabla }_{i}f(x)+\frac{L_i}{2}{h}^2=f(x)-\frac{1}{L_i}({\nabla }_{i}f(x){)}^2+\frac{1}{2L_i}({\nabla }_{i}f(x){)}^2,$$

which collapses to $f(x^{+})\le f(x)-\frac{1}{2L_i}({\nabla }_{i}f(x){)}^2$, i.e. $(\ast )$.

For the rate, take conditional expectation over the random coordinate $i_k$ drawn with $p_i=L_i/S$. By $(\ast )$,

$$\mathbb{E}[f(x_{k+1})\mid x_k]\le f(x_k)-\sum _{i=1}^n\frac{L_i}{S}\cdot \frac{1}{2L_i}({\nabla }_{i}f(x_k){)}^2=f(x_k)-\frac{1}{2S}\Vert \nabla f(x_k){\Vert }^2.$$

Convexity gives $f(x_k)-f^{\star }\le ⟨\nabla f(x_k),x_k-x^{\star }⟩\le \Vert \nabla f(x_k)\Vert \Vert x_k-x^{\star }\Vert \le R\Vert \nabla f(x_k)\Vert$, so $\Vert \nabla f(x_k){\Vert }^2\ge (f(x_k)-f^{\star }{)}^2/R^2$. Writing ${\delta }_k=\mathbb{E}[f(x_k)]-f^{\star }$ and taking total expectation (using Jensen, $\mathbb{E}[(f(x_k)-f^{\star }{)}^2]\ge {\delta }_k^2$, and that $\{f(x_k)\le f(x_0)\}$ by $(\ast )$),

$${\delta }_{k+1}\le {\delta }_k-\frac{1}{2S{R}^2}{\delta }_k^2.$$

Divide by ${\delta }_k{\delta }_{k+1}>0$ and use ${\delta }_{k+1}\le {\delta }_k$:

$$\frac{1}{{\delta }_{k+1}}\ge \frac{1}{{\delta }_k}+\frac{1}{2S{R}^2}\cdot \frac{{\delta }_k}{{\delta }_{k+1}}\ge \frac{1}{{\delta }_k}+\frac{1}{2S{R}^2}.$$

Summing this telescoping bound from $0$ to $k-1$ gives $1/{\delta }_k\ge 1/{\delta }_0+k/(2S{R}^2)\ge k/(2S{R}^2)$, hence ${\delta }_k\le 2S{R}^2/k$, which is $(\ast \ast )$. $\square$

Bridge. This single per-step decrease $(\ast )$ is the foundational reason coordinate methods converge, and it builds toward the strongly-convex linear rate and the block and accelerated variants of the Advanced results, where the same inequality is summed under a different coordinate accounting. This is exactly the coordinate analogue of the descent lemma behind the proximal-gradient method of 44.06.02: where that argument decreased $F$ by a full-gradient quadratic, here only the $i$-th term survives, so the proof generalises full-gradient descent to a one-coordinate move at $1/n$ of the cost. The randomized rate is dual to the stochastic-gradient rate of 44.06.05 — both read an expected one-step decrease against convexity — and the central insight is that sampling coordinate $i$ with probability $L_i/S$ turns the sum ${\sum }_i({\nabla }_{i}f{)}^2/L_i$ into the full $\Vert \nabla f{\Vert }^2/S$, recovering a clean rate whose constant $S={\sum }_i{L}_i$ replaces the global $L$. Putting these together, the deterministic, randomized, and greedy methods share one inequality, and it appears again in the asynchronous-parallel analysis where the expectation is taken over both the coordinate and a bounded staleness delay.

Exercises Intermediate+

Advanced results Master

Coordinate descent is the iteration $x_{k+1}=$ a one-coordinate (or one-block) update of $x_k$ on a coordinate $i_k$, and the results below extend the single decrease $(\ast )$ to the strongly-convex linear rate, the cyclic and greedy rules, the block and accelerated variants, and the asynchronous-parallel setting.

Theorem 1 (rates of randomized coordinate descent). For convex $f$ with coordinate Lipschitz constants $L_i$ and randomized sampling $p_i=L_i/S$, $S={\sum }_i{L}_i$, randomized coordinate descent attains $\mathbb{E}[f(x_k)]-f^{\star }\le 2S{R}^2/k$ (Key theorem). If $f$ is $\mu$-strongly convex, the rate is linear, $\mathbb{E}[f(x_k)]-f^{\star }\le (1-\mu /S{)}^k(f(x_0)-f^{\star })$ (Exercise 6) ^{[Nesterov, Yu. — Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems (2012)]}. The constant $S={\sum }_i{L}_i$, the sum of coordinate Lipschitz constants, replaces the global $L$ of full-gradient descent; when coordinates are well-conditioned ($L_i\approx L/n$ so $S\approx L$) the iteration count matches full-gradient descent at $1/n$ of the per-iteration cost, which is the precise sense in which CD dominates on huge-scale problems.

Theorem 2 (the separable-composite model and proximal coordinate descent). For $F=f+{\sum }_i{g}_i(x_i)$ with $f$ convex $L$-smooth and each $g_i$ proper closed convex, randomized proximal coordinate descent with the step $x_i^{+}={\mathrm{prox}}_{(1/L_i)g_i}(x_i-\frac{1}{L_i}{\nabla }_{i}f(x))$ converges with the same $O(1/k)$ and strongly-convex linear rates, because the prox step satisfies a coordinate sufficient-decrease analogue of $(\ast )$ and the optimality condition $0\in \nabla f(x^{\star })+\partial g(x^{\star })$ decouples coordinatewise into $0\in {\nabla }_{i}f(x^{\star })+\partial g_i(x_i^{\star })$ ^{[Wright, S. J. — Coordinate Descent Algorithms (2015)]}. This separability is the hypothesis that makes coordinatewise minimisation equivalent to global minimisation; without it the equivalence fails. Powell's 1973 example — cyclic exact coordinate minimisation cycling on a smooth nonconvex function whose level sets couple the variables — is the canonical demonstration that the structural hypothesis cannot be dropped, and it is the reason the separable model, not mere convexity, is the right setting for coordinate methods. The model covers LASSO ($g_i=\lambda |x_i|$, prox is soft-thresholding), elastic net, group structure with block separability, and the box-constrained SVM dual ($g_i={\iota }_{[0,C]}$, prox is clipping, Exercise 8).

Theorem 3 (Gauss-Southwell and the cyclic rule). The greedy Gauss-Southwell rule $i_k\in \arg {\max }_i|{\nabla }_{i}f(x_k)|$ satisfies the per-step decrease $f(x_k)-f(x_{k+1})\ge \frac{1}{2L_{\max }}\Vert \nabla f(x_k){\Vert }_{\infty }^2$, giving a deterministic rate that, on coordinates with comparable $L_i$, can outpace randomized CD by a factor up to $n$ in the iteration count because $\Vert \nabla f{\Vert }_{\infty }^2$ replaces the averaged $\Vert \nabla f{\Vert }^2/n$ — the gain is real whenever the $\arg \max$ scan or its incremental maintenance is affordable ^{[Wright, S. J. — Coordinate Descent Algorithms (2015)]}. The cyclic rule has a worse worst-case dependence (a factor up to $O(L^2/L_{\min }^2)$ or $O(n)$ over randomized in adversarial orderings) yet is often the fastest in practice for well-ordered problems; its analysis sums $(\ast )$ over a full sweep rather than in expectation, which is why a single bad coordinate can dominate a sweep.

Theorem 4 (block-coordinate descent and the Gauss-Seidel / alternating-minimisation connection). Block-coordinate exact minimisation, $x^{(j)}\leftarrow \arg {\min }_{u}F(\dots ,u,\dots )$ cycling over blocks $j=1,\dots ,p$, is the nonlinear Gauss-Seidel method; for the quadratic $F(x)=\frac{1}{2}{x}^{\top }Qx-b^{\top }x$ with the natural block partition of $Q=D-L-U$ it is exactly the matrix Gauss-Seidel iteration $x_{k+1}=(D-L{)}^{-1}(U{x}_k+b)$ solving $Qx=b$ ^{[Beck, A. — First-Order Methods in Optimization (SIAM, 2017)]}. The two-block case is alternating minimisation, which underlies the EM algorithm, nonnegative matrix factorisation, and iteratively reweighted schemes. Block exact minimisation is monotone (each block solve cannot increase $F$) and converges to a minimiser under block-separability of the nonsmooth part and a uniqueness or strict-convexity condition per block; the failure of plain two-block alternating minimisation when the blocks are coupled non-separably is again the Powell phenomenon at the block level.

Theorem 5 (accelerated, parallel, and asynchronous coordinate descent). Inserting a Nesterov momentum extrapolation into randomized coordinate descent yields accelerated coordinate descent with the optimal expected rate $\mathbb{E}[f(x_k)]-f^{\star }=O(\bar{L}{R}^2/k^2)$, where $\bar{L}$ is an averaged coordinate constant ^{[Nesterov, Yu. — Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems (2012)]}. Parallel coordinate descent updates a random subset of coordinates per round, with a step-size penalty governed by a separability/sparsity measure of $\nabla f$; asynchronous (Hogwild!-style) coordinate descent lets cores read and write shared coordinates without locks, and converges provided the staleness (the delay between a coordinate read and its write) is bounded — the convergence proof extends $(\ast )$ by taking expectation jointly over the sampled coordinate and the delay, absorbing the inconsistency into a contraction-factor penalty ^{[Wright, S. J. — Coordinate Descent Algorithms (2015)]}. These are the variants that make coordinate descent a default engine for very large sparse machine-learning problems on multicore hardware.

Synthesis. The single per-coordinate decrease $(\ast )$ is the foundational reason the entire coordinate-method family coheres, and the central insight is that the coordinate Lipschitz constants $L_i$, not the global $L$, set the rate — this is exactly why sampling $i$ with probability $L_i/S$ collapses ${\sum }_i({\nabla }_{i}f{)}^2/L_i$ into $\Vert \nabla f{\Vert }^2/S$ and replaces $L$ by the typically far smaller $S/n$ per unit of work. The randomized $O(1/k)$ and strongly-convex linear rates are the in-expectation form of $(\ast )$ summed against convexity, and they are dual to the stochastic-gradient rates of 44.06.05: coordinate sampling and data sampling are two faces of one stochastic-first-order template, each extracting a rate from an expected one-step inequality. The proximal coordinate step generalises the proximal-gradient method of 44.06.02 to one coordinate at a time, and the foundational reason it is valid is the decoupling of the optimality condition $0\in \nabla f+\partial g$ under separability — the structural hypothesis whose failure Powell's example exhibits, which is exactly why the smooth-plus-separable composite, not mere convexity, is the correct domain. Putting these together, the cyclic, greedy, block, accelerated, and asynchronous variants are one inequality read under different coordinate accountings, and the bridge from this unit to large-scale machine learning is precisely the cheapness of a single coordinate update — touching one column of the data rather than all of it — which is why coordinate descent generalises full-gradient descent into the dominant solver for LASSO, the SVM dual, and huge sparse regression.

Full proof set Master

Proposition 1 (coordinate descent lemma). If $f$ has coordinate Lipschitz constant $L_i$ along $e_i$, then for all $x$ and $h\in \mathbb{R}$, $f(x+h{e}_i)\le f(x)+h{\nabla }_{i}f(x)+\frac{L_i}{2}{h}^2$.

Proof. This is Exercise 3. Let $\varphi (t)=f(x+t{e}_i)$, so ${\varphi }^{\prime }(t)={\nabla }_{i}f(x+t{e}_i)$ and $f(x+h{e}_i)-f(x)={\int }_0^h{\nabla }_{i}f(x+t{e}_i)dt$. Decompose the integrand as ${\nabla }_{i}f(x)+[{\nabla }_{i}f(x+t{e}_i)-{\nabla }_{i}f(x)]$; the constant integrates to $h{\nabla }_{i}f(x)$, and $|{\nabla }_{i}f(x+t{e}_i)-{\nabla }_{i}f(x)|\le L_i|t|$ bounds the remainder by ${\int }_0^{|h|}{L}_{i}tdt=\frac{L_i}{2}{h}^2$. $\square$

Proposition 2 (coordinate sufficient-decrease). For convex $f$ with coordinate constant $L_i$, the step $x^{+}=x-\frac{1}{L_i}{\nabla }_{i}f(x)e_i$ satisfies $f(x)-f(x^{+})\ge \frac{1}{2L_i}({\nabla }_{i}f(x){)}^2$.

Proof. Apply Proposition 1 with $h=-\frac{1}{L_i}{\nabla }_{i}f(x)$: $f(x^{+})\le f(x)-\frac{1}{L_i}({\nabla }_{i}f(x){)}^2+\frac{L_i}{2}\frac{1}{L_i^2}({\nabla }_{i}f(x){)}^2=f(x)-\frac{1}{2L_i}({\nabla }_{i}f(x){)}^2$. Rearranging gives the claim; the right side is nonnegative, so the step is monotone. $\square$

Proposition 3 (expected one-step decrease, randomized rule). For randomized coordinate descent with $p_i=L_i/S$, $S={\sum }_i{L}_i$, $\mathbb{E}[f(x_{k+1})\mid x_k]\le f(x_k)-\frac{1}{2S}\Vert \nabla f(x_k){\Vert }^2$.

Proof. Conditioning on $x_k$ and averaging Proposition 2 over the sampled coordinate, $\mathbb{E}[f(x_{k+1})\mid x_k]\le f(x_k)-{\sum }_i{p}_i\frac{1}{2L_i}({\nabla }_{i}f(x_k){)}^2$. With $p_i=L_i/S$ each term is $\frac{1}{2S}({\nabla }_{i}f(x_k){)}^2$; summing over $i$ gives $\frac{1}{2S}\Vert \nabla f(x_k){\Vert }^2$. $\square$

Proposition 4 (randomized $O(1/k)$ rate). For convex $f$ with $R^2={\max }_{x:f(x)\le f(x_0)}\Vert x-x^{\star }{\Vert }^2<\infty$, randomized CD with $p_i=L_i/S$ gives $\mathbb{E}[f(x_k)]-f^{\star }\le 2S{R}^2/k$.

Proof. By Proposition 2 the iterates stay in the sublevel set $\{f\le f(x_0)\}$, so $\Vert x_k-x^{\star }\Vert \le R$ along the trajectory. Convexity gives $f(x_k)-f^{\star }\le ⟨\nabla f(x_k),x_k-x^{\star }⟩\le R\Vert \nabla f(x_k)\Vert$, hence $\Vert \nabla f(x_k){\Vert }^2\ge (f(x_k)-f^{\star }{)}^2/R^2$. Insert into Proposition 3 and take total expectation; with ${\delta }_k=\mathbb{E}[f(x_k)]-f^{\star }$ and Jensen ($\mathbb{E}[(f(x_k)-f^{\star }{)}^2]\ge {\delta }_k^2$), ${\delta }_{k+1}\le {\delta }_k-{\delta }_k^2/(2S{R}^2)$. Dividing by ${\delta }_k{\delta }_{k+1}$ and using ${\delta }_{k+1}\le {\delta }_k$ gives $1/{\delta }_{k+1}\ge 1/{\delta }_k+1/(2S{R}^2)$; telescoping from $0$ to $k-1$ yields $1/{\delta }_k\ge k/(2S{R}^2)$, i.e. ${\delta }_k\le 2S{R}^2/k$. $\square$

Proposition 5 (linear rate under strong convexity). If $f$ is additionally $\mu$-strongly convex, randomized CD with $p_i=L_i/S$ gives $\mathbb{E}[f(x_k)]-f^{\star }\le (1-\mu /S{)}^k(f(x_0)-f^{\star })$.

Proof. Strong convexity gives the Polyak-Łojasiewicz inequality $\frac{1}{2}\Vert \nabla f(x){\Vert }^2\ge \mu (f(x)-f^{\star })$: minimising $f(y)\ge f(x)+⟨\nabla f(x),y-x⟩+\frac{\mu }{2}\Vert y-x{\Vert }^2$ over $y$ (the minimiser is $y=x-\frac{1}{\mu }\nabla f(x)$) gives $f^{\star }\ge f(x)-\frac{1}{2\mu }\Vert \nabla f(x){\Vert }^2$. Substituting into Proposition 3, $\mathbb{E}[f(x_{k+1})\mid x_k]-f^{\star }\le (1-\mu /S)(f(x_k)-f^{\star })$. Taking total expectation and iterating gives the geometric bound; $0<\mu \le L_i$ for some $i$ keeps $\mu /S\in (0,1)$. $\square$

Proposition 6 (block Gauss-Seidel for quadratics). For $F(x)=\frac{1}{2}{x}^{\top }Qx-b^{\top }x$ with $Q$ symmetric positive definite and the splitting $Q=D-L-U$ ($D$ block-diagonal, $-L$ strictly block-lower, $-U$ strictly block-upper), block-coordinate exact minimisation in natural order equals the Gauss-Seidel iteration $x_{k+1}=(D-L{)}^{-1}(U{x}_k+b)$, which converges to $x^{\star }=Q^{-1}b$.

Proof. Exact minimisation over block $j$ with earlier blocks already updated and later blocks at their old values sets the $j$-th block-gradient to zero: $(Qx{)}_j=b_j$ evaluated with the partially-updated $x$. Sweeping $j=1,\dots ,p$ in order is precisely substituting the new blocks as they become available, which collects to $(D-L)x_{k+1}=U{x}_k+b$, i.e. $x_{k+1}=(D-L{)}^{-1}(U{x}_k+b)$. The iteration matrix $M=(D-L{)}^{-1}U$ satisfies $\rho (M)<1$ for symmetric positive-definite $Q$ (a standard fact: Gauss-Seidel converges for SPD systems), so $x_k\to (I-M{)}^{-1}(D-L{)}^{-1}b=Q^{-1}b=x^{\star }$. $\square$

Proposition 7 (Gauss-Southwell per-step decrease). For convex $f$ with coordinate constants $L_i\le L_{\max }$, the greedy step $i_k\in \arg {\max }_i|{\nabla }_{i}f(x_k)|$ with the coordinate-gradient update satisfies $f(x_k)-f(x_{k+1})\ge \frac{1}{2L_{\max }}\Vert \nabla f(x_k){\Vert }_{\infty }^2$.

Proof. By Proposition 2 applied to the chosen coordinate $i_k$, $f(x_k)-f(x_{k+1})\ge \frac{1}{2L_{i_k}}({\nabla }_{i_k}f(x_k){)}^2\ge \frac{1}{2L_{\max }}({\nabla }_{i_k}f(x_k){)}^2$. Since $i_k$ maximises $|{\nabla }_{i}f(x_k)|$, $({\nabla }_{i_k}f(x_k){)}^2=\Vert \nabla f(x_k){\Vert }_{\infty }^2$, giving the claim. Because $\Vert \nabla f{\Vert }_{\infty }^2\ge \frac{1}{n}\Vert \nabla f{\Vert }^2$, the greedy decrease is at least the expected randomized decrease and can be up to $n$ times larger. $\square$

Connections Master

• Coordinate descent is the coordinatewise specialisation of the proximal-gradient method of 44.06.02: the proximal coordinate step $x_i^{+}={\mathrm{prox}}_{(1/L_i)g_i}(x_i-\frac{1}{L_i}{\nabla }_{i}f(x))$ is one coordinate of forward-backward splitting, the coordinate descent lemma is the descent lemma restricted to $e_i$, and the separable-composite optimality condition $0\in {\nabla }_{i}f+\partial g_i$ is the composite Fermat rule of that unit read coordinatewise. The soft-thresholding prox that unit derives is exactly the per-coordinate update that makes coordinate descent the standard LASSO solver.

• Randomized coordinate descent is the coordinate-sampling sibling of the stochastic gradient method of 44.06.05: both replace an $O(n)$ deterministic step by a cheap randomised step, both extract their rate from an expected one-step-decrease inequality, and the strongly-convex linear rate $(1-\mu /S{)}^k$ here mirrors the variance-reduced linear rate there. Where SGD samples a summand of a finite-sum objective, CD samples a coordinate of the variable; the two stochastic-first-order analyses share one template, and accelerated CD parallels accelerated SGD.

• The subgradient method of 44.06.01 supplies the baseline that coordinate descent improves on for structured problems: where the black-box subgradient method is stuck at $O(1/\sqrt{k})$, coordinate descent exploits the separable structure to reach $O(1/k)$ (and linear under strong convexity) at $1/n$ of the per-iteration cost, just as the proximal-gradient method does, so coordinate descent inherits and refines the structural-exploitation argument that lets first-order methods beat the nonsmooth black-box lower bound.

Historical & philosophical context Master

Coordinate-wise relaxation is among the oldest iterative ideas in numerical computation: the Gauss-Seidel method for linear systems, in which one solves for each variable in turn using the most recent values of the others, descends from work of Gauss and was formalised by Seidel in 1874 ^{[Seidel 1874]}. The recognition that cyclic coordinate minimisation can fail to converge on a smooth problem is due to M. J. D. Powell, whose 1973 note exhibited a differentiable function of three variables on which cyclic exact coordinate search cycles among non-stationary points ^{[Powell 1973]}, establishing that convexity alone is insufficient and motivating the separable-structure hypotheses used since. The modern complexity theory of coordinate descent for huge-scale problems was set by Yurii Nesterov in 2012 ^{[Nesterov 2012]}, who introduced the coordinate-Lipschitz / sampling-probability framework, proved the expected $O(1/k)$ and strongly-convex linear rates, and gave the accelerated $O(1/k^2)$ variant; the comprehensive survey unifying the cyclic, randomized, greedy, block, and asynchronous variants and their application to LASSO and the SVM dual is Stephen J. Wright's 2015 review ^{[Wright 2015]}. The sequential-minimal-optimization specialisation that made coordinate ascent the practical SVM-dual solver is due to John Platt in 1998 ^{[Platt 1998]}.

Bibliography Master

@article{nesterov2012coordinate,
  author  = {Nesterov, Yurii},
  title   = {Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems},
  journal = {SIAM Journal on Optimization},
  volume  = {22},
  number  = {2},
  pages   = {341--362},
  year    = {2012}
}

@article{wright2015coordinate,
  author  = {Wright, Stephen J.},
  title   = {Coordinate Descent Algorithms},
  journal = {Mathematical Programming},
  volume  = {151},
  number  = {1},
  pages   = {3--34},
  year    = {2015}
}

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

@article{powell1973search,
  author  = {Powell, M. J. D.},
  title   = {On search directions for minimization algorithms},
  journal = {Mathematical Programming},
  volume  = {4},
  number  = {1},
  pages   = {193--201},
  year    = {1973}
}

@incollection{platt1998smo,
  author    = {Platt, John C.},
  title     = {Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines},
  booktitle = {Advances in Kernel Methods: Support Vector Learning},
  publisher = {MIT Press},
  year      = {1998}
}

@article{seidel1874,
  author  = {Seidel, Ludwig},
  title   = {{\"U}ber ein Verfahren, die Gleichungen, auf welche die Methode der kleinsten Quadrate f{\"u}hrt, sowie line{\"a}re Gleichungen {\"u}berhaupt durch successive Ann{\"a}herung aufzul{\"o}sen},
  journal = {Abhandlungen der Bayerischen Akademie der Wissenschaften},
  volume  = {11},
  pages   = {81--108},
  year    = {1874}
}