Proximal Methods: Why Splitting a Nonsmooth Problem Beats Solving It Directly

Many problems in machine learning look deceptively simple: minimise a smooth loss plus a penalty that encourages structure. The loss is differentiable, the penalty is not, and that one nonsmooth term breaks gradient descent. Proximal methods are the standard answer, and they work for a reason that is easy to miss: they do not try to smooth the hard part away. They isolate it, solve it exactly in a small subproblem, and then combine the pieces.

This article explains the proximal operator, why it is a generalisation of a gradient step, how splitting algorithms such as ISTA, FISTA, and ADMM use it, and where these methods fail in practice.

The problem proximal methods are built for

Consider a composite objective:

$$\min_x \; f(x) + g(x)$$

Here $f$ is smooth, often a data-fitting loss, and $g$ is convex but possibly nonsmooth, often a regulariser. Two canonical examples make the point.

First, the lasso:

$$\min_x \; \frac{1}{2}|Ax - b|_2^2 + \lambda |x|_1$$

Second, a constrained problem written with an indicator function, where $g(x) = 0$ if $x$ lies in a set $C$ and $g(x) = \infty$ otherwise. The same machinery handles both cases, which is part of its appeal.

Gradient descent cannot be applied directly because $g$ may have no gradient at the very points we care about, such as zero in the lasso. Subgradient methods can be applied, but they are slow, typically converging at a rate of order $1/\sqrt{k}$ in the nonsmooth case, and they rarely produce the exact sparsity or exact feasibility that the penalty was meant to enforce.

The proximal operator: a gradient step, generalised

The proximal operator of $g$ with step size $\tau > 0$ is defined as:

$$\mathrm{prox}_{\tau g}(v) = \arg\min_x \; g(x) + \frac{1}{2\tau}|x - v|_2^2$$

Read it as a trade-off. The first term pulls $x$ toward a point that makes $g$ small. The second term keeps $x$ close to the input $v$ . When $\tau$ is small, the operator stays near $v$ ; when $\tau$ is large, it moves aggressively toward minimising $g$ .

The connection to gradient descent is exact, not just suggestive. If $g$ were smooth, one gradient step with step size $\tau$ from $v$ would be $v - \tau \nabla g(v)$ . The proximal operator is the implicit version of that step: it solves for a point whose subgradient condition matches the same balance, but without requiring differentiability. In fact, for smooth $g$ , the proximal step approximates the gradient step, and for nonsmooth $g$ , it remains well defined where the gradient does not exist.

The reason proximal methods are practical is that $\mathrm{prox}_{\tau g}$ has a closed form for many penalties that matter:

• For $g(x) = \lambda |x|_1$ , it is soft thresholding: shrink each coordinate toward zero by $\lambda \tau$ , and set it exactly to zero if it would cross zero.
• For the indicator of a convex set, it is Euclidean projection onto that set.
• For $g(x) = \lambda |x|_2$ , it is block soft thresholding, shrinking the whole vector toward zero.
• For the nuclear norm, it is singular value soft thresholding, which is why proximal methods appear in matrix completion.

This is the central bargain of the whole family: pay for one exact solve of the nonsmooth part, in closed form, and the rest of the algorithm can stay simple.

Proximal gradient descent and ISTA

Proximal gradient descent, also called ISTA in the sparse recovery literature, alternates the two kinds of step:

$$x^{k+1} = \mathrm{prox}_{\tau g}\left(x^k - \tau \nabla f(x^k)\right)$$

First take a gradient step on the smooth part, then apply the proximal operator of the nonsmooth part. For the lasso, this is: take a least-squares gradient step, then soft-threshold. The result is genuinely sparse, not just small, because soft thresholding sets coordinates exactly to zero.

If $f$ has an $L$ -Lipschitz gradient and we choose $\tau = 1/L$ , the objective gap shrinks at a rate of order $1/k$ . That is already much better than a subgradient method, and the iterates have the structural property, sparsity or feasibility, that we wanted from the start.

A minimal implementation makes the pattern concrete:

import numpy as np

def soft_threshold(v, threshold):
    return np.sign(v) * np.maximum(np.abs(v) - threshold, 0.0)

def ista(A, b, lam, steps=200):
    # Step size 1 / L, where L is the largest eigenvalue of A^T A.
    L = np.linalg.eigvalsh(A.T @ A)[-1]
    x = np.zeros(A.shape[1])
    for _ in range(steps):
        grad = A.T @ (A @ x - b)
        x = soft_threshold(x - grad / L, lam / L)
    return x

Notice what is not in this code: no smoothing parameter for the l1 penalty, no inner optimisation loop, and no tolerance for near-zero coefficients. The proximal step does the structural work in one line.

Acceleration: FISTA and why momentum helps

ISTA converges at order $1/k$ . FISTA, the fast iterative shrinkage-thresholding algorithm, adds a carefully chosen momentum term and improves this to order $1/k^2$ for the objective gap, which is optimal for first-order methods on this problem class.

The update keeps an auxiliary sequence $y^k$ :

$$x^{k+1} = \mathrm{prox}_{\tau g}\left(y^k - \tau \nabla f(y^k)\right)$$

$$t_{k+1} = \frac{1 + \sqrt{1 + 4 t_k^2}}{2}, \qquad y^{k+1} = x^{k+1} + \frac{t_k - 1}{t_{k+1}}\left(x^{k+1} - x^k\right)$$

The momentum coefficient is not a tuning knob to be set by feel. It grows toward one in a specific schedule, and that schedule is what delivers the faster rate. Two practical warnings follow. First, FISTA is not monotone: the objective can increase from one iteration to the next, so a restart scheme that resets momentum when the objective rises often helps in practice. Second, acceleration improves the objective gap, but it does not necessarily improve the iterates at the same rate, and it can amplify noise when gradients are estimated stochastically. For stochastic problems, plain proximal gradient with averaging is often the safer choice.

When one proximal operator is not enough: ADMM

Proximal gradient descent needs $f$ to be smooth and needs a single proximal operator for $g$ . Many real problems have two nonsmooth terms, or a term composed with a linear operator, such as total variation denoising or a problem with both sparsity and a linear constraint. Splitting again is the answer.

The alternating direction method of multipliers, ADMM, is built for problems of the form:

$$\min_{x, z} \; f(x) + g(z) \quad \text{subject to} \quad Ax + Bz = c$$

By introducing a dual variable and an augmented Lagrangian, ADMM alternates three simple updates: minimise over $x$ with $z$ fixed, minimise over $z$ with $x$ fixed, then update the dual variable by the constraint residual. Each minimisation is itself a proximal-like step, so a problem that looked inseparable becomes a sequence of small, solvable pieces.

ADMM is popular because it is flexible and because its updates often parallelise naturally, for example across clients, sensors, or blocks of variables. Its weakness is equally well known: it can converge slowly to high accuracy, and its speed depends heavily on the penalty parameter in the augmented Lagrangian. A common practical pattern is to use ADMM to reach moderate accuracy quickly, then switch to a more specialised solver if high accuracy is genuinely needed.

Limitations and common pitfalls

Proximal methods are not a universal solver, and four pitfalls recur.

First, the proximal operator must be cheap. If $\mathrm{prox}_{\tau g}$ has no closed form and needs its own iterative solver, the outer algorithm inherits that cost at every step, and the simplicity that motivated the method is gone.

Second, the step size matters. Proximal gradient descent with $\tau > 1/L$ can diverge, just like gradient descent. Backtracking line search on $f$ is the standard fix, and it costs only extra evaluations of $f$ , not of the proximal operator.

Third, structure is not free. The lasso example produces sparsity because soft thresholding is exact, but that sparsity is a property of the estimator, not a guarantee about the truth. A proximal method will faithfully solve the optimisation problem you wrote down; it will not tell you whether that problem was the right one.

Fourth, nonconvex problems break the theory. Proximal gradient methods are widely used for nonconvex penalties and neural network training with structured regularisers, and they often work well, but the convergence rates quoted above assume convexity. In the nonconvex case, expect convergence to a stationary point at best, and treat the result as a good local solution rather than a global one.

When to choose a proximal method

Use a proximal method when your objective splits cleanly into a smooth part you can differentiate and a nonsmooth part whose proximal operator you can compute in closed form. That covers sparse regression, constrained optimisation by projection, low-rank matrix completion, and many image reconstruction problems. Reach for ADMM when the splitting needs to go further, across two blocks of variables or a linear constraint.

Do not use one when the nonsmooth term has no cheap proximal operator, when the smooth part is itself expensive or stochastic at a scale where second-order or variance-reduced methods win, or when you need very high accuracy and a specialised interior-point solver is available. Proximal methods win on structure and simplicity, not on raw speed to machine precision.

The deeper lesson is a design principle: do not smooth a problem just to make gradient descent applicable. If the nonsmooth term encodes something you actually want, sparsity, feasibility, or low rank, keep it exact and build the algorithm around it. The proximal operator is the tool that lets you do that without paying for a generic nonsmooth solver.

---

Connect with me on LinkedIn: linkedin.com/in/umeshtharukaofficial