Proximal Gradient Methods

Why This Matters

Many important ML objectives have the form "smooth loss plus nonsmooth regularizer." Lasso is the canonical example: squared error (smooth) plus an $\ell_1$ penalty (nonsmooth). You cannot just take gradients of the full objective because the $\ell_1$ norm is not differentiable everywhere.

Proximal gradient methods solve this cleanly. They handle the smooth and nonsmooth parts separately: a gradient step on the smooth part, then a proximal step on the nonsmooth part. This is the algorithmic backbone of sparse optimization in ML.

Mental Model

Imagine sliding down a smooth hill (gradient descent on the smooth part), then snapping to the nearest point that respects some structural constraint (the proximal step). The proximal operator acts like a "project and shrink" operation. For the $\ell_1$ norm, it is soft-thresholding: it pushes small coordinates exactly to zero, producing sparsity.

Formal Setup and Notation

We want to solve the composite minimization problem:

$\min_{x \in \mathbb{R}^d} \; F(x) = f(x) + g(x)$

where $f$ is convex and smooth (has $L$-Lipschitz continuous gradient) and $g$ is convex but possibly nonsmooth (e.g., $g(x) = \lambda \|x\|_1$).

Definition

Proximal Operator

The proximal operator of a convex function $g$ at point $x$ is:

$\mathrm{prox}_g(x) = \arg\min_{y} \left( g(y) + \frac{1}{2}\|y - x\|^2 \right)$

It finds the point that balances being close to $x$ (the quadratic term) with having small $g$ value. The proximal operator always exists and is unique when $g$ is convex, lower semicontinuous, and proper.

Definition

Moreau Envelope

The Moreau envelope of $g$ with parameter $\gamma > 0$ is:

$M_g^\gamma(x) = \min_{y} \left( g(y) + \frac{1}{2\gamma}\|y - x\|^2 \right)$

It is a smooth approximation of $g$. Even when $g$ is nonsmooth, the Moreau envelope $M_g^\gamma$ is differentiable with gradient $\nabla M_g^\gamma(x) = \frac{1}{\gamma}(x - \mathrm{prox}_{\gamma g}(x))$. As $\gamma \to 0$, the Moreau envelope converges to $g$ itself.

Core Definitions

For the $\ell_1$ norm $g(x) = \lambda \|x\|_1$, the proximal operator is soft-thresholding:

$[\mathrm{prox}_{\lambda \|\cdot\|_1}(x)]_i = \mathrm{sign}(x_i) \max(|x_i| - \lambda, 0)$

This shrinks each coordinate toward zero and sets coordinates with $|x_i| \leq \lambda$ exactly to zero. This is how proximal methods produce sparse solutions.

For the indicator function of a convex set $C$, $g(x) = I_C(x)$ (zero if $x \in C$, infinity otherwise), the proximal operator is the Euclidean projection onto $C$.

The ISTA Algorithm

The Iterative Shrinkage-Thresholding Algorithm (ISTA) repeats:

$x_{k+1} = \mathrm{prox}_{t_k g}\!\left(x_k - t_k \nabla f(x_k)\right)$

where $t_k \leq 1/L$ is the step size and $L$ is the Lipschitz constant of $\nabla f$.

Step by step: (1) take a gradient step on the smooth part $f$, producing an intermediate point $z = x_k - t_k \nabla f(x_k)$; (2) apply the proximal operator of $g$ to $z$, handling the nonsmooth part.

The FISTA Algorithm

Fast ISTA (FISTA) adds Nesterov momentum:

Initialize $x_0 = y_1$, $t_1 = 1$. Then repeat:

$x_k = \mathrm{prox}_{s \cdot g}\!\left(y_k - s \cdot \nabla f(y_k)\right)$

$t_{k+1} = \frac{1 + \sqrt{1 + 4t_k^2}}{2}$

$y_{k+1} = x_k + \frac{t_k - 1}{t_{k+1}}(x_k - x_{k-1})$

The extrapolation step $y_{k+1}$ looks ahead using momentum, which is what gives the acceleration.

Main Theorems

Theorem

ISTA Convergence Rate

Statement

Let $F^* = \min_x F(x)$. ISTA with constant step size $t = 1/L$ satisfies:

$F(x_k) - F^* \leq \frac{L \|x_0 - x^*\|^2}{2k}$

where $x^*$ is a minimizer of $F$.

Intuition

The convergence rate is $O(1/k)$. After $k$ iterations, the suboptimality shrinks like $1/k$. This matches gradient descent on smooth functions. The proximal step handles nonsmoothness without slowing convergence.

Proof Sketch

Show that the proximal gradient step guarantees sufficient decrease: $F(x_{k+1}) \leq F(x) + \nabla f(x_k)^T(x_{k+1} - x) + \frac{L}{2}\|x_{k+1} - x\|^2 + g(x_{k+1}) - g(x)$ for all $x$. Set $x = x^*$ and telescope the resulting inequality.

Why It Matters

This shows proximal gradient descent is as fast as gradient descent, even though the objective is nonsmooth. The proximal operator absorbs the nonsmoothness at no cost to the convergence rate.

Failure Mode

The $O(1/k)$ rate is tight for ISTA. You cannot do better without modification. Also, if $L$ is unknown you need a line search or adaptive step size, which adds cost per iteration.

Theorem

FISTA Accelerated Convergence Rate

Statement

FISTA satisfies:

$F(x_k) - F^* \leq \frac{2L \|x_0 - x^*\|^2}{(k+1)^2}$

Intuition

Acceleration improves the rate from $O(1/k)$ to $O(1/k^2)$. After 100 iterations, ISTA reduces the gap by $100\times$; FISTA reduces it by $10{,}000\times$. The momentum term lets the algorithm "look ahead" using the trajectory, extracting more information per step.

Proof Sketch

Define a Lyapunov function $E_k = t_k^2(F(x_k) - F^*) + \frac{L}{2}\|v_k - x^*\|^2$ where $v_k$ is an auxiliary sequence. Show $E_{k+1} \leq E_k$ by using the descent property and the specific choice of momentum parameters. Since $t_k = \Theta(k)$, this gives the $O(1/k^2)$ rate.

Why It Matters

$O(1/k^2)$ is the optimal rate for first-order methods on convex problems with Lipschitz gradients (Nesterov 1983). FISTA achieves this optimal rate for composite objectives. The improvement from $O(1/k)$ to $O(1/k^2)$ is substantial in practice.

Failure Mode

FISTA's iterates can oscillate because of the momentum term. It is not a monotone algorithm: $F(x_{k+1})$ can be larger than $F(x_k)$. Monotone variants exist but may sacrifice some speed. Also, for strongly convex $f$, you can get linear convergence with a restarting strategy.

Canonical Examples

Example

Lasso via ISTA

The Lasso problem is $\min_x \frac{1}{2}\|Ax - b\|^2 + \lambda\|x\|_1$. Here $f(x) = \frac{1}{2}\|Ax - b\|^2$ with $\nabla f(x) = A^T(Ax - b)$ and $L = \|A^TA\|$. The proximal step is soft-thresholding. Each ISTA iteration: compute $z = x_k - \frac{1}{L} A^T(Ax_k - b)$, then $x_{k+1} = \mathrm{sign}(z) \odot \max(|z| - \lambda/L, 0)$.

Example

Projected gradient descent as a special case

When $g = I_C$ is the indicator of a convex set $C$, the proximal operator is projection onto $C$. So ISTA becomes projected gradient descent: $x_{k+1} = \Pi_C(x_k - t \nabla f(x_k))$. Constrained smooth optimization is a special case of proximal gradient methods.

Common Confusions

Watch Out

Proximal operator is not projection

The proximal operator for a general $g$ is not a projection onto a set. It is a projection-like operation that balances proximity to the input with minimizing $g$. Projection is the special case where $g$ is an indicator function. For the $\ell_1$ norm, the proximal operator is soft-thresholding, which shrinks coordinates rather than projecting.

Watch Out

FISTA does not always beat ISTA in practice

FISTA has a better worst-case rate, but its oscillatory behavior can make it slower on some problems. Restarting FISTA (resetting momentum when the objective increases) often works better in practice. The theoretical guarantee is about worst-case, not every-case.

Summary

• Proximal operator: $\mathrm{prox}_g(x) = \arg\min_y (g(y) + \|y-x\|^2/2)$
• ISTA: gradient step on smooth $f$, then proximal step on nonsmooth $g$
• ISTA converges at $O(1/k)$; FISTA with momentum at $O(1/k^2)$
• For $\ell_1$ regularization, the proximal operator is soft-thresholding
• The Moreau envelope smooths a nonsmooth function while preserving minimizers

Exercises

ExerciseCore

Problem

Compute $\mathrm{prox}_{\lambda \|\cdot\|_1}(x)$ for $x = (3, -1, 0.5)$ and $\lambda = 1$. Which coordinates become zero?

Hint

Reveal Solution

ExerciseAdvanced

Problem

Show that the proximal operator of the indicator function $I_C$ of a closed convex set $C$ is the Euclidean projection $\Pi_C$.

Hint

Reveal Solution

ExerciseResearch

Problem

Prove that the Moreau envelope $M_g^\gamma$ is differentiable even when $g$ is not, and show $\nabla M_g^\gamma(x) = \frac{1}{\gamma}(x - \mathrm{prox}_{\gamma g}(x))$.

Hint

Reveal Solution

References

Canonical:

• Beck & Teboulle, "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems" (2009)
• Nesterov, Introductory Lectures on Convex Optimization (2004), Chapter 2

Current:

• Parikh & Boyd, "Proximal Algorithms," Foundations and Trends in Optimization (2014)

• Hastie, Tibshirani, Friedman, The Elements of Statistical Learning (2009)

Next Topics

The natural next steps from proximal gradient methods:

• Coordinate descent: an alternative for separable penalties
• Stochastic gradient descent: scaling to large datasets