Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 38 · Proximal and Stochastic Methods

Proximal Operators

Meet the proximal operator, the building block for non-smooth convex optimization. Derive soft thresholding for the L1 norm, relate projections to prox, and verify each by brute force.

Gradient descent needs a derivative. But many useful objectives are not smooth: the L1 norm |x| has a corner at 0, and a constraint like x ≥ 0 is a wall with a vertical drop. The proximal operator is the tool that lets simple gradient-like methods handle such terms. It turns "minimize a non-smooth function" into small, often closed-form subproblems.

Definition

For a convex function f and a step size t > 0, the proximal operator is:

Text
prox_{t f}(v) = argmin over x of  f(x) + (1 / (2t)) · ‖x − v‖²

Read it as a tug of war: x wants to make f small, but pays a quadratic price for moving away from the anchor point v. A large t weakens the pull toward v; a small t keeps x close to v. Because the sum of a convex function and a strongly convex quadratic is strongly convex, the minimizer exists and is unique for every v.

Key property: x* minimizes f if and only if x* = prox_{t f}(x*). That is, minimizers are the fixed points of the prox map. This is why iterating a prox step makes sense.

Three important examples

1. A quadratic. For f(x) = ½‖x‖², set the gradient of ½‖x‖² + (1/2t)‖x − v‖² to zero: x + (x − v)/t = 0, so x = v / (1 + t). The prox shrinks v toward zero.

2. The L1 norm (soft thresholding). For f(x) = λ|x| in one variable, the answer is:

Text
prox_{t f}(v) = sign(v) · max(|v| − tλ, 0)

Values with |v| ≤ tλ are set to exactly 0; larger values are pulled toward 0 by tλ. This "soft threshold" is why L1 methods produce sparse vectors. For a vector, apply it to each entry.

Why? For x > 0 the objective's derivative is λ + (x − v)/t, zero at x = v − tλ, valid when v > tλ. Symmetric for x < 0. In between, 0 is the minimizer because the subdifferential of |x| at 0 is the whole interval [−1, 1], which absorbs the pull (v − 0)/t when |v| ≤ tλ.

3. An indicator function (projection). Let I_C(x) = 0 if x ∈ C and +∞ otherwise. Then prox_{t I_C}(v) = argmin over x ∈ C of ‖x − v‖², the Euclidean projection of v onto C, for every t. So projected gradient descent is a special case of proximal gradient descent. Two projections you can write by hand:

  • Box [l, u]: clip each entry, x_i = min(max(v_i, l_i), u_i).
  • Ball of radius r: x = v if ‖v‖ ≤ r, otherwise x = r · v / ‖v‖.
Python Check soft thresholding by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The prox of f(x) = λ|x| depends only on the product tλ. That is why algorithms later in this chapter write the threshold as tλ, where t is the gradient step.

Projections as prox operators

The next TryIt checks that clipping and ball scaling really give the closest point, by comparing against random feasible points. A projection p of v onto C must satisfy ‖p − v‖ ≤ ‖z − v‖ for every z ∈ C.

Python Projections onto a box and a ball

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Moreau envelope and gradients

The prox also hides a smooth object. The Moreau envelope f_t(v) = min_x { f(x) + (1/2t)‖x − v‖² } is a smoothed version of f that is differentiable everywhere, with gradient ∇f_t(v) = (v − prox_{t f}(v)) / t. So a prox step is a gradient step on the smoothed function. For f = |x| the envelope is the Huber function: quadratic near 0, linear far away.

A short catalog

Function f prox_{t f}(v)
λ‖x‖₁ soft threshold with level tλ
I_C (indicator of C) projection onto C
½‖x‖² v / (1 + t)
(λ/2)‖x‖² v / (1 + tλ)
0 v (identity)
λ‖x‖₂ (not squared) max(1 − tλ/‖v‖, 0) · v (block soft threshold)

The practical rule: use prox for the "simple but non-smooth" part of your objective and a gradient for the smooth part. The next lesson combines the two.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is prox_{t f}(v) for f(x) = λ|x| when |v| ≤ tλ?

    Soft thresholding sets every entry with magnitude at most tλ to exactly zero.
  2. 2. What is the proximal operator of an indicator function I_C?

    Minimizing I_C(x) + ‖x − v‖²/(2t) forces x into C and picks the closest such point to v.
  3. 3. How are the minimizers of f related to the prox operator?

    A point is a minimizer of a convex f if and only if a prox step leaves it unchanged.
  4. 4. Why is the prox of a closed convex f always well defined (a unique answer)?

    Convex plus strongly convex is strongly convex, which has exactly one minimizer.

Summary

  • prox_{t f}(v) = argmin f(x) + ‖x − v‖²/(2t) balances making f small against staying near v.
  • For λ‖x‖₁ it is soft thresholding sign(v)·max(|v| − tλ, 0); for an indicator it is projection.
  • Minimizers of f are the fixed points of the prox map.
  • Prox lets simple iterations handle non-smooth terms.

Next: Proximal Gradient and ISTA