Proximal Gradient Methods

Proximal gradient descent minimizes a smooth term plus a nonsmooth term by taking a gradient step, then a proximal step.

The composite problem

Many objectives split as f(x) + g(x), where f is smooth with a computable gradient and g is convex but possibly nonsmooth, such as an L1 penalty or a constraint indicator. Plain gradient descent cannot handle g. Proximal gradient descent handles f with a gradient step and g with its proximal operator, alternating the two.

The update

Each iteration is x_{k+1} = prox_{t g}( x_k - t grad f(x_k) ). Read left to right: descend along the smooth gradient, then apply the proximal operator of g to that point. When g is the L1 norm this becomes the iterative shrinkage-thresholding algorithm (ISTA): a gradient step followed by soft-thresholding, which repeatedly pushes small coordinates to exactly zero and produces sparse solutions.

import numpy as np

def ista(A, b, lam, t, iters=500):
    x = np.zeros(A.shape[1])
    for _ in range(iters):
        grad = A.T @ (A @ x - b)      # gradient of 0.5||Ax-b||^2
        v = x - t*grad                 # smooth step
        x = np.sign(v)*np.maximum(np.abs(v)-t*lam, 0)  # prox of L1
    return x

Convergence and acceleration

With step size t no larger than 1/L, where L is the Lipschitz constant of grad f, proximal gradient descent reduces the objective gap at rate O(1/k). Nesterov-style momentum accelerates this to O(1/k^2); the accelerated version of ISTA is FISTA, which adds an extrapolation step between iterates and is a standard baseline for sparse recovery and image deblurring.

Why it matters

Proximal gradient methods let a single clean loop solve regularized regression, matrix completion, total-variation denoising, and constrained least squares by swapping only the proximal operator. That modularity, plus provable convergence, makes them a default choice whenever a problem is smooth-plus-simple-nonsmooth. In simulation-heavy engineering, they let a physically meaningful smooth residual be minimized subject to sparsity or bound constraints without abandoning gradient information.