Proximal gradient steps

For f(w)+λ||w||₁, proximal gradient takes u=w−η∇f(w) and applies soft thresholding at ηλ.

2 min read1 figureSources & further reading

On this page 8 sections

Overview
Understand the idea
For a vector, first compute every coordinate of u
The threshold is the product of step size and L1 penalty weight
A closer look
Key takeaway
Sources & further reading
Concept connections

01Understand the idea#

Proximal gradient separates two jobs in an objective: improve a smooth data loss, then handle a nonsmooth penalty. For an L1 penalty, that second job is soft thresholding. This avoids pretending that absolute value has an ordinary derivative at zero.

For an L1 proximal-gradient step, use η>0 and λ≥0. With smooth gradient g=∇f(w), take:

u=w-\eta g

Then apply soft thresholding at ηλ to each coordinate: w′=S_(ηλ)(u).

For w=4, g=2, η=0.5 and λ=2, the smooth step gives u=3. Threshold 1 shrinks it to w′=2.

Figure 1Starting w=4, smooth gradient 2 and rate .5 give intermediate u=3. Lambda 2 produces threshold eta lambda=1; S1(3)=2. Both steps share the same numerical parameter axis.

Link to this figure ↗Download SVG Download PNG

For $w=4$ , smooth gradient 2, rate 0.5, and penalty weight 2, first take the smooth step: $u=4-0.5(2)=3$ . Compute threshold $\eta\lambda=1$ , then shrink 3 to 2. The intermediate 3 is not the final parameter, and using threshold $\lambda=2$ would give the wrong final value.

Check your reasoning

For f(w)+λ||w||₁, use u=w−ηg then w′=S_(ηλ)(u), where g=∇f(w). (w,g,η,λ)=(4, 4, 0.5, 1). Find w′.

Show answer and explanation

1.5

u=2, threshold=0.5, output=1.5.

02For a vector, first compute every coordinate of u#

For a vector, first compute every coordinate of u. Then apply the same threshold ηλ to each scalar coordinate.

Some coordinates can become exactly zero while others survive. This is a proximal step for the stated L1 objective.

Check your reasoning

For f(w)+λ||w||₁, use u=w−ηg then w′=S_(ηλ)(u), where g=∇f(w). w= $(4, -2)$ , g= $(2, -1)$ , η=0.5, λ=2. Find w′.

A $(2, 0.5)$
B $(2, -0.5)$
C $(3, -0.5)$

Show answer and explanation

$(2, -0.5)$

u=(3,−1.5); τ=1.

03The threshold is the product of step size and L1 penalty weight#

The threshold is the product of step size and L1 penalty weight. Using λ alone changes the update when η differs from one.

Keep the order: smooth-gradient step, then threshold. This avoids pretending the absolute-value penalty has an ordinary derivative at zero.

Check your reasoning

For f(w)+λ||w||₁, use u=w−ηg then w′=S_(ηλ)(u), where g=∇f(w). (w,g,η,λ)=(-4, -2, 0.5, 3). Draft uses threshold λ and gets 0. Correct w′.

Show answer and explanation

-1.5

u=-3, threshold=1.5, output=-1.5.

04A closer look#

In a sparse regression update, apply the smooth step to all coefficients, then threshold each penalized coordinate. Some become exactly zero while others survive. The loss normalization, penalty weight, and learning rate all belong to the specified objective and update convention.

Key takeaway

Take the smooth step first, compute the scaled threshold ηλ, then soft-threshold each coordinate.

Compute a supplied proximal-gradient step for an L1-regularized objective.

Sources & further reading

[1]
Parikh & Boyd §4.2 equation4.6 and §6.5.2 equation 6.9 ↗Parikh & Boyd §4.2 equation4.6 and §6.5.2 equation 6.9 · Article

01Understand the idea#

02For a vector, first compute every coordinate of u#

03The threshold is the product of step size and L1 penalty weight#

04A closer look#

Take the smooth step first, compute the scaled threshold ηλ, then soft-threshold each coordinate.

Sources & further reading

Reference this concept