# Proximal Gradient Methods

Splitting an objective into a smooth part handled by a gradient step and a nonsmooth part handled by a proximal operator, which has a closed form for common penalties.

**Rests on:** Gradient Descent, Nonsmooth Optimization

*Mathematical Foundations · Optimization*


## Why learn this

You are learning this because it allows you to train models that automatically ignore most of your inputs. When you want a model that only uses a few key features from a large set, you use a technique called L1 regularisation. This creates 'sparse models', meaning most of the weights in the model are exactly zero. Without this method, you cannot effectively build such models using standard optimisation tools. It also explains why your software can combine 'error measurement' and 'penalty for complexity' into a single fast step: it uses two smaller, simpler steps instead of trying to do everything at once.


## The intuition

Imagine you are walking in a valley trying to find the lowest point. The ground is smooth everywhere except for a sharp, V-shaped ridge running across the floor. This ridge represents the penalty for having non-zero values in your model. If you use ordinary gradient descent, you look at the slope under your feet and step down. But when you hit the V-shaped ridge, the ground has a sharp corner (a 'kink'), so there is no clear single direction to go down. The method splits the walk into two parts. First, you ignore the ridge. You take a step downhill as if the ground were flat all the way to the bottom of the valley. This gets you close. Second, you look at where you landed. If you have overshot the sharp corner or are too close to it, you apply a simple rule: if your value is small, push it all the way to zero; if it is large, pull it closer to zero by a fixed amount. This second step is the 'proximal operator'. For common cases like L1 regularisation, this adjustment is just basic arithmetic: subtracting a fixed number and snapping to zero if you go below it. So the whole process is: take a standard step downhill, then snap the result towards zero. You repeat this until you settle at the lowest possible point.


## An analogy

Think of a ball rolling down a bumpy hill that ends in a sharp V-shaped trench. The ball rolls freely on the smooth parts of the hill (the gradient step). When it reaches the V-shaped trench, it cannot sit exactly on the sharp bottom line because the slope is undefined there. Instead, the 'proximal operator' acts like a clamp that grabs the ball and holds it at the nearest point on the side of the V that it can reach. If the ball is close to the center, the clamp pushes it all the way to zero (the center line). If the ball is far away, the clamp pulls it in by a fixed distance. This snapping action ensures the final position respects the shape of the trench. The analogy has limits: a real ball would bounce, but this mathematical method settles steadily; also, the 'clamp' is an algebraic rule, not a physical force.


## Definition

Proximal gradient methods are an iterative technique that finds the minimum of a function by alternating between a standard gradient step on the smooth part and a simple adjustment (the proximal operator) on the non-smooth part. This adjustment pushes values toward zero according to a fixed rule, allowing you to handle sharp corners in the function that ordinary gradient descent cannot navigate.


## How it connects

This extends Gradient Descent by adding the ability to handle sharp kinks in the function, which standard gradient descent avoids because it requires smooth slopes. It connects to Lasso Regression, which is the specific application of this method to create sparse models using L1 regularisation.


## The mathematics

This concept rests on two branches of mathematics: calculus (specifically, the idea of a derivative — the slope of a function at a point, which tells you which direction is downhill) and convex analysis (the study of functions that have a single bowl shape, where the kink is the only complication). You already met the derivative in your study of gradient descent: it is the number that says how steep the function is at a particular input. The problem this method solves is that some functions have a point where the slope is not defined — a sharp corner, like the bottom of a V. Ordinary gradient descent cannot take a step from that corner because it has no slope to follow. Proximal gradient methods say: 'Let's not try to compute the slope at the corner. Instead, we will take a step as if the function were smooth, then apply a small correction that accounts for the sharp corner.' The correction is called the proximal operator. For a V-shaped function, the proximal operator has a very simple form: shrink the value towards zero by a fixed amount. For other nonsmooth penalties, the operator may be more complicated, but for many practical cases it is a simple arithmetic operation. The key is that the correction is not a step in the direction of steepest descent — it is a projection-like operation that brings you back to a point where the nonsmooth part is well-behaved.

Let f(x) be the smooth part and g(x) the nonsmooth part. The proximal gradient iteration is:

x_{k+1} = prox_{t, g}( x_k - t * ∇f(x_k) )

where ∇f is the gradient (derivative) of f, t is the step size, and prox_{t, g}(z) is the proximal operator defined as:

prox_{t, g}(z) = argmin_x ( g(x) + (1/(2t)) * (x - z)^2 )

For g(x) = λ * |x|, the proximal operator is soft thresholding:

prox_{t, g}(z) = S_{λt}(z) = sign(z) * max(|z| - λt, 0)

Each symbol means: x is the variable we are optimising; f is the smooth function; g is the nonsmooth function; t is the step size (positive number); ∇f is the slope of f; z is any input to the proximal operator; λ is the strength of the L1 penalty; sign(z) is +1 if z is positive, -1 if negative, 0 if zero; |z| is the absolute value.


## A worked example

```
We want to minimise the function f(x) + g(x), where f(x) = (x - 3)^2 (smooth, like a bowl) and g(x) = |x| (nonsmooth, the V shape). We will start at x = 5 and use a step size (learning rate) of 0.5. The gradient step for f is: x_new = x - step_size * (2 * (x - 3)) (because the derivative of (x - 3)^2 is 2(x - 3)). Then we apply the proximal operator for g, which is soft thresholding with parameter step_size: shrink x by 0.5 towards zero, but not past zero.

Step 1: Start: x = 5, step_size = 0.5   # Initial position.
Step 2: Gradient step: x = 5 - 0.5 * (2 * (5 - 3)) = 5 - 0.5 * 4 = 5 - 2 = 3   # Move downhill on the smooth part.
Step 3: Proximal step (soft threshold): x = shrink(3, 0.5) = max(3 - 0.5, 0) = 2.5   # Since 3 is positive and larger than 0.5, subtract 0.5.
Step 4: Iterate: gradient step from 2.5: x = 2.5 - 0.5 * (2 * (2.5 - 3)) = 2.5 - 0.5 * (-1) = 2.5 + 0.5 = 3   # Second gradient step.
Step 5: Proximal step: x = shrink(3, 0.5) = 2.5 again   # Still positive, shrink again.
Step 6: Continue: after many steps, x tends to a value where the gradient step and the shrink balance, which is around 1.5   # The method converges to the minimum of (x-3)^2 + |x|, which is not x=3 but slightly less, because the absolute value pulls it towards zero.

Result: The minimum is approximately x = 1.5. The exact solution can be found by solving, but the key is that the proximal step changed the final answer compared to just minimising the smooth part alone.
```


## From scratch, in Python

```python
# We will minimise f(x) = (x-3)^2 + 0.5 * |x| from scratch.
# No libraries, just Python arithmetic.

def gradient_f(x):
    # derivative of (x-3)^2 is 2*(x-3)
    return 2 * (x - 3)

def soft_threshold(z, threshold):
    # The proximal operator for 0.5 * |x| with step size t
    # is shrink by t * 0.5, but not past zero.
    if z > threshold:
        return z - threshold
    elif z < -threshold:
        return z + threshold
    else:
        return 0.0

# Initialise
x = 5.0
t = 0.5  # step size
lambda_ = 0.5  # L1 strength

# Run a few iterations, printing each step
for i in range(10):
    # Gradient step on the smooth part
    x_grad = x - t * gradient_f(x)
    # Proximal step (soft threshold) on the nonsmooth part
    x = soft_threshold(x_grad, t * lambda_)
    print('iteration', i, 'x =', x)

print('Final x =', x)
```


## The same thing, with a framework

```python
import numpy as np

# This is the same iteration, but using NumPy arrays so it works for many
# parameters at once.

x = np.array([5.0, -3.0, 0.5])
t = 0.5
lambda_ = 0.5
# Smooth part: f(x) = sum((x - 3)^2) (just for illustration)
def grad_f(x):
    return 2 * (x - 3.0)

for i in range(10):
    x_grad = x - t * grad_f(x)
    # Soft threshold, elementwise on the array
    x = np.sign(x_grad) * np.maximum(np.abs(x_grad) - t * lambda_, 0)
    print('iteration', i, x)

print('Final x', x)
```


## What the code does

This code does exactly what the mathematics section described. Let's walk through it line by line.

First, we define `gradient_f(x)`, which returns the slope of the smooth part at `x`. This is a function: it takes a number `x` and returns another number, `2*(x-3)`. Functions are a basic building block in Python — they package a calculation so you can reuse it.

Then we define `soft_threshold(z, threshold)`. This is the proximal operator for the L1 penalty. It takes a number `z` and a threshold, and returns a new number. The rule is: if `z` is bigger than `threshold`, subtract the threshold; if `z` is smaller than `-threshold`, add the threshold; otherwise (if `z` is between -threshold and threshold), return 0. This is the shrink-towards-zero step. This is our first use of conditional statements (`if`, `elif`, `else`) — they let the code make a choice based on the value of `z`. We also use a parameter `threshold`, which we will set to `t * lambda_`.

Then we set the start point `x = 5.0`, the step size `t = 0.5`, and the regularisation strength `lambda_ = 0.5`. We then run a loop that repeats ten times. A loop (`for i in range(10)`) is a building block that repeats the same block of code ten times, with `i` taking values 0, 1, ..., 9.

Inside the loop, we do the two steps. First, `x_grad = x - t * gradient_f(x)` — this is the gradient step. Then `x = soft_threshold(x_grad, t * lambda_)` — this is the proximal step. We print the value of `x` each iteration so you can watch it converge.

The final `print` outside the loop shows the result. Try changing `lambda_` to a bigger number, like 2.0, and you will see the final `x` gets closer to zero — the regularisation is pulling harder.

This is the whole method. In practice, you would use a library, but now you know exactly what the library is doing underneath.


## Common misconceptions

**The proximal operator is a gradient step** — The proximal operator is just another way to take a downhill step.

A gradient step uses the slope to move a certain distance. The proximal operator is not about the slope at all — it is a fixed point that brings you back to the nearest point where the nonsmooth part is 'happy'. It is a projection-like operation, not a step in the direction of steepest descent. In fact: The proximal operator is a separate operation defined by a small minimisation problem: it finds the value that balances being close to the input with making the nonsmooth part small. For L1, it is simply 'shrink towards zero'.

**Soft thresholding is the same as rounding to zero** — Soft thresholding just rounds all small values to zero and keeps the rest unchanged.

Rounding is a hard cut: anything below a threshold becomes exactly zero, and anything above stays exactly the same. Soft thresholding shrinks all values by a constant amount — large values are reduced by that amount, not just passed through. In fact: Soft thresholding subtracts the threshold from the magnitude of every value, and only sets to zero if the value is below the threshold.

**The proximal step size must equal the gradient step size** — The proximal operator uses the same t as the gradient step, and changing one changes the other automatically.

They are linked in the formula (both use t), but you can theoretically choose different step sizes for the gradient part and the proximal part in some variants. In the basic algorithm, they are the same t, but that is a choice, not a law. In fact: In the standard proximal gradient method, the same step size t appears in both places. There are accelerated variants that use a different combination.

**Proximal gradient methods are only for L1** — The only nonsmooth penalty you can use with this method is L1.

The proximal operator exists for many nonsmooth functions — for example, the group lasso (which operates on groups of variables), total variation (used in image processing), and nuclear norm (for matrices). L1 just happens to have a simple closed form. In fact: The method works for any function g for which you can compute the proximal operator, and for many common penalties this is a simple formula.


## In short

Proximal gradient methods split an optimisation problem into a smooth part (gradient step) and a nonsmooth part (proximal step). For L1 regularisation, the proximal step is soft thresholding: shrink each value towards zero, and set small values exactly to zero. This is how lasso is solved. Each step is cheap, respects the kink, and you now understand exactly what happens under the hood of a `Lasso` call or a train step with sparsity penalties.


## Where this is used

Proximal gradient methods are everywhere in machine learning, mostly behind the scenes. They are the standard way to fit L1-regularised models (lasso and its variations), which are used across the industry for feature selection and interpretable models.

In **large language models**, proximal methods are not directly used for the main training (which is smooth and uses Adam or similar), but they appear in specialised settings: when you want to impose sparsity on attention heads or on weights for pruning, L1 regularisation is added, and the training step becomes a proximal gradient step. For example, a method called 'sparse attention' adds an L1 penalty on attention weights, and the update is exactly a gradient step followed by soft thresholding.

In **small language models running on phones or laptops**, sparsity is crucial for reducing model size and memory. Quantisation and pruning are often combined with an L1 penalty, and proximal gradient methods are used during fine-tuning to push small weights to exactly zero, so they can be dropped from the model. The developer writes a training loop that calls the optimiser (like PyTorch's `SGD` with a custom proximal step), or uses a library like `scikit-learn` for simpler sparse models.

In **retrieval-augmented generation (RAG)**, the embedding vectors are sometimes regularised to produce sparse embeddings, so that similarity search can use faster inverted indexes. Proximal gradient methods are used to train these sparse embeddings — the L1 penalty forces most dimensions to zero, and the proximal step enforces that exactly. A developer using `scikit-learn`'s `Lasso` or `ElasticNet` is secretly using a coordinate descent variant, but the principle is the same.

In **agentic systems that plan and call tools**, optimisation is used in the planning loop, for example to choose which tools to call (a sparse selection problem). The planner's objective includes a cost for each tool call, which is L1-like, and the solution is found by proximal gradient or a related method.

In **everyday applied machine learning**, lasso is the go-to for feature selection: you have 1000 features, you suspect only 10 matter, so you add an L1 penalty and fit with proximal gradient. `scikit-learn`'s `Lasso` and `glmnet` in R do exactly this. In **signal processing and image reconstruction** (your library notes mention inverse problems), proximal methods solve denoising and deblurring: the objective is a smooth data-fidelity term plus a nonsmooth sparsity penalty, and the proximal step is a soft threshold in a transformed domain.

What a developer actually writes: in Python with `scikit-learn`, they write `Lasso(alpha=0.1).fit(X, y)`. Under the hood, that calls a coordinate descent solver, which is related to but not identical to proximal gradient. For custom objectives, they might use `scikit-learn`'s `SparseCoder` or write a custom PyTorch optimiser. What breaks when done badly: if the step size `t` is too large, the iteration diverges; if `lambda` is too big, the model becomes too sparse and underfits; if you try to use ordinary gradient descent on the nonsmooth objective, it oscillates around the kink and never converges. Also, if you forget to apply the proximal step, you are just doing gradient descent with a non-differentiable loss, which will misbehave.


---

Read this on the web: https://basavapurushottam.com/learn-ai/proximal-gradient-methods
