Proximal Gradient Methods

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.

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.

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.

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.

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.