Projected, Proximal and Constrained First-Order Methods

Unconstrained gradient descent needs one modification to handle constraints and non-smooth regularisers, and the modification is the same in every case: replace "take a gradient step" by "take a gradient step, then do something that respects the structure". This page collects the four standard choices of "something".

Projection

DefinitionEuclidean projection

For a closed convex $\mathcal{C}\subseteq\R^d$, $\Pi_{\mathcal{C}}(x) = \argmin_{z\in\mathcal{C}}\norm{x-z}_2$. The minimiser exists and is unique by strong convexity of the objective on the closed convex feasible set.

LemmaProjection is non-expansive

For all $x,y\in\R^d$ and all $z\in\mathcal{C}$,

$$\text{(i)}\quad \ip{x - \Pi_\mathcal{C}(x)}{z - \Pi_\mathcal{C}(x)} \le 0, \qquad \text{(ii)}\quad \norm{\Pi_\mathcal{C}(x)-\Pi_\mathcal{C}(y)}_2 \le \norm{x-y}_2 .$$

ProofReveal

TheoremConvergence of projected gradient descent

Let $f$ be convex and $L$-smooth on a closed convex $\mathcal{C}$, with minimiser $x^\star$ over $\mathcal{C}$. The iteration

$$x_{t+1} = \Pi_\mathcal{C}\big(x_t - \tfrac1L\nabla f(x_t)\big)$$

satisfies $f(x_t) - f(x^\star) \le \dfrac{L\norm{x_0-x^\star}_2^2}{2t}$, the same rate as in the unconstrained case.

ProofReveal

The proximal operator

DefinitionProximal operator

For a convex, closed, proper $h:\R^d\to\R\cup\{+\infty\}$ and $\eta>0$,

$$\prox_{\eta h}(v) = \argmin_{z}\left\{h(z) + \frac{1}{2\eta}\norm{z-v}_2^2\right\}.$$

The minimiser is unique because the objective is strongly convex.

Taking $h = \iota_\mathcal{C}$, the indicator function of a convex set ($0$ on $\mathcal{C}$, $+\infty$ off it), recovers $\prox_{\eta\iota_\mathcal{C}} = \Pi_\mathcal{C}$. So projection is a special case of the proximal operator, and the theory below subsumes the theory above.

PropositionProx of the l1 norm is soft thresholding

For $h(z) = \norm{z}_1$,

$$\big[\prox_{\eta h}(v)\big]_i = \sign(v_i)\max\big(|v_i| - \eta,\ 0\big) =: S_\eta(v_i).$$

ProofReveal

TheoremConvergence of proximal gradient descent

Let $F = f + h$ with $f$ convex and $L$-smooth and $h$ convex closed proper. The iteration

$$x_{t+1} = \prox_{h/L}\big(x_t - \tfrac1L\nabla f(x_t)\big)$$

satisfies $F(x_t)-F^\star \le \dfrac{L\norm{x_0-x^\star}_2^2}{2t}$. The accelerated variant (FISTA) attains $O(1/t^2)$.

Quoted from Beck–Teboulle. The structure of the proof is the projected-gradient proof with the non-expansiveness of $\Pi_\mathcal{C}$ replaced by the firm non-expansiveness of $\prox$; the references give it in full.

1. Input. Design $X\in\R^{n\times p}$, response $y$, regularisation $\lambda$, step $\eta = 1/L$ with $L = \norm{X^\top X}/n$.
2. Repeat for $t = 0,1,2,\dots$:
3. gradient step $v_t = \beta_t - \dfrac{\eta}{n} X^\top(X\beta_t - y)$;
4. soft threshold $\beta_{t+1} = S_{\eta\lambda}(v_t)$, coordinatewise;
5. Until $\norm{\beta_{t+1}-\beta_t}_2 \le \text{tol}$.

Frank–Wolfe

When projection is expensive but linear minimisation over $\mathcal{C}$ is cheap — as for the $\ell^1$ ball, the nuclear-norm ball, or a combinatorial polytope — the conditional gradient method applies.

TheoremFrank–Wolfe convergence

Let $f$ be convex and $L$-smooth on a compact convex $\mathcal{C}$ of diameter $D$. The iteration

$$s_t = \argmin_{s\in\mathcal{C}}\ip{\nabla f(x_t)}{s}, \qquad x_{t+1} = (1-\gamma_t)x_t + \gamma_ts_t, \quad \gamma_t = \frac{2}{t+2},$$

satisfies $f(x_t) - f^\star \le \dfrac{2LD^2}{t+2}$.

ProofReveal

Mirror descent

PropositionMirror descent and geometry

Let $\Phi$ be $1$-strongly convex with respect to a norm $\norm{\cdot}$ on $\mathcal{C}$, and define the Bregman divergence $D_\Phi(x,y) = \Phi(x)-\Phi(y)-\ip{\nabla\Phi(y)}{x-y}$. The iteration

$$x_{t+1} = \argmin_{x\in\mathcal{C}}\left\{\eta\ip{\nabla f(x_t)}{x} + D_\Phi(x,x_t)\right\}$$

satisfies, for convex $f$ with $\norm{\nabla f}_* \le G$ in the dual norm,

$$f(\bar x_T) - f^\star \le \frac{D_\Phi(x^\star,x_0)}{\eta T} + \frac{\eta G^2}{2},$$

so with optimal $\eta$ the rate is $G\sqrt{2D_\Phi(x^\star,x_0)/T}$.

The proof is the subgradient-method proof with $\tfrac12\norm{\cdot}_2^2$ replaced by $D_\Phi$ throughout; it is in Bubeck's survey. The content is the choice of $\Phi$:

$\mathcal{C}$	$\Phi$	Norm	Rate constant
$\R^d$	$\tfrac12\norm{x}_2^2$	$\ell^2$	$\norm{x^\star}_2\norm{\nabla f}_2$
simplex $\Delta_d$	$\sum_ix_i\log x_i$	$\ell^1$	$\sqrt{\log d}\,\norm{\nabla f}_\infty$

On the simplex the entropic choice gives a $\sqrt{\log d}$ dependence on dimension where the Euclidean choice would give $\sqrt d$. That is a genuinely large gain for large $d$, and it is obtained by measuring the gradient in $\ell^\infty$ rather than $\ell^2$ — the geometry of the problem, not the algorithm, is what changed.

Problems

Projection onto the probability simplexProof · Advanced · 1 hour The proximal operator of the l1 normProof · Beginner · 15 min The Frank–Wolfe duality gap certificateProof · Intermediate · 30 min Mirror descent on the simplex beats Euclidean projectionProof · Graduate · 1 hour