Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 38 · Proximal and Stochastic Methods

Proximal Gradient and ISTA

Solve composite problems smooth + non-smooth with proximal gradient descent. Implement ISTA for the lasso, accelerate it to FISTA and check the result with optimality conditions.

Many machine-learning objectives have two parts: a smooth loss f(x) (differentiable) and a simple non-smooth regularizer h(x) such as the L1 norm or a constraint indicator:

Text
minimize    F(x) = f(x) + h(x)

Proximal gradient descent takes a gradient step on f and then applies the prox of h:

Text
x_{k+1} = prox_{t h}( x_k − t ∇f(x_k) )

You saw the ingredients in the previous lesson. If h = 0, the prox is the identity, and this is ordinary gradient descent. If h is an indicator, it is projected gradient descent. If h = λ‖x‖₁, the method is called ISTA, the Iterative Shrinkage-Thresholding Algorithm.

Why it works

If ∇f is L-Lipschitz (its gradient changes at most L per unit distance) and t ≤ 1/L, then the quadratic model

Text
f(x) + ∇f(x)ᵀ(y − x) + (1/2t)‖y − x‖²

is an upper bound on f(y). The prox step minimizes this upper bound plus h(y), so F can only go down at each step. With t = 1/L, the error shrinks like O(1/k).

The lasso problem

The lasso (least absolute shrinkage and selection operator) is least squares with an L1 penalty:

Text
minimize    ½ ‖A x − b‖² + λ ‖x‖₁

Here f(x) = ½‖Ax − b‖² has gradient Aᵀ(Ax − b) and Lipschitz constant L = σ_max(A)² (the largest singular value of A, squared). The ISTA update is:

Text
x ← soft( x − (1/L) Aᵀ(Ax − b),  λ/L )

The L1 term drives many entries of x to exactly zero, which gives a sparse model.

Implementing ISTA

We build synthetic data where the truth is sparse: 60 samples, 25 features, but only 4 non-zero true coefficients. We then check that ISTA finds them.

Python ISTA for the lasso

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 optimality check is the KKT condition for the lasso: at a minimizer, −∇f(x) ∈ λ ∂‖x‖₁. For non-zero entries, the gradient must equal −λ·sign(x_i); for zero entries, its magnitude must not exceed λ.

The estimates for the non-zero entries come out slightly smaller than the true values (3, −2, 1.5, 2.5). That shrinkage is the price of the L1 penalty: it lowers variance and zeroes out irrelevant features but biases the kept coefficients toward zero.

Acceleration: FISTA

ISTA's O(1/k) rate can be improved to O(1/k²) by adding momentum, a technique from Nesterov. The FISTA algorithm (Fast ISTA) evaluates the gradient at an extrapolated point:

Text
x_{k+1} = prox_{t h}( y_k − t ∇f(y_k) )
s_{k+1} = (1 + √(1 + 4 s_k²)) / 2
y_{k+1} = x_{k+1} + ((s_k − 1) / s_{k+1}) · (x_{k+1} − x_k)

starting with y_0 = x_0 and s_0 = 1. Each iteration costs about the same as ISTA. The extra work is a few vector additions.

To compare the two, we first compute a very accurate reference value F* with many iterations, then measure how far each method is from it after the same number of steps.

Python ISTA versus FISTA

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.

In the first few dozen iterations FISTA's gap is clearly smaller than ISTA's. This small, well-conditioned problem is solved to machine precision by both methods within about 100 iterations, so the later rows are close to a tie; the advantage of acceleration grows on harder, ill-conditioned problems. FISTA is also not monotone (the objective can rise for a step, as in the row at 50 iterations), which is normal for accelerated methods.

Choosing the step size

  • Use t = 1/L. Computing L as the squared spectral norm needs one SVD or a few power iterations.
  • If L is unknown, use backtracking: start with a guess, and shrink t by half until the upper-bound inequality above holds.
  • A larger step is tempting but can make the iterates diverge, since the quadratic model stops being an upper bound.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is one proximal gradient step for F = f + h?

    x_{k+1} = prox_{t h}(x_k − t ∇f(x_k)): move along −∇f, then apply the prox of the simple part.
  2. 2. For the lasso ½‖Ax − b‖² + λ‖x‖₁, what threshold does ISTA use with step 1/L?

    The prox of (λ‖x‖₁) with step t = 1/L is soft thresholding at level tλ = λ/L.
  3. 3. What does FISTA add to ISTA?

    FISTA evaluates the gradient at an extrapolated point y_k, which accelerates convergence at nearly the same cost per step.
  4. 4. At a lasso minimizer, a zero coefficient x_i = 0 must satisfy which condition?

    The subgradient of |x_i| at zero is [−1, 1], so the smooth gradient must stay inside [−λ, λ].

Summary

  • Proximal gradient handles f + h with smooth f and prox-friendly h: x ← prox_{t h}(x − t∇f(x)).
  • ISTA is the case h = λ‖x‖₁; its update is a gradient step followed by soft thresholding.
  • Take t = 1/L, where L is the Lipschitz constant of ∇f.
  • FISTA adds Nesterov momentum and converges as O(1/k²).
  • Check results with the lasso optimality conditions.

Next: Stochastic Gradient Descent