Proximal Methods, Nonsmooth Objectives, and Sparsity

Absolute-value penalties, hinge losses, indicator functions, and group sparsity create corners or discontinuous slopes. Ordinary gradient calculus does not apply at every point. Nonsmooth optimization uses generalized derivatives and specialized update rules. The proximal operator solves a small regularized problem that balances staying near the current point with respecting a nonsmooth penalty. This framework explains soft thresholding, projected steps, and many sparse-learning algorithms.

None of it is recent folklore. The operator at the centre of the lesson is Moreau's proximity operator, from 1965. Everything below is machinery built on that one object: the shrinkage rule, the projected step, the accelerated iteration, and the failure modes of the sparse support it produces. Each piece carries a paper, a date and a number you can check.

Many ML objectives separate naturally into a smooth data-fit term and a nonsmooth structural penalty. The two-move split below is not a teaching device invented for the diagram. It is a published algorithm with a convergence proof. Daubechies, Defrise and De Mol proposed it in 2003 and published it in 2004, and their abstract gives both the moves and the guarantee: “To compute the corresponding regularized solutions we propose an iterative algorithm that amounts to a Landweber iteration with thresholding (or nonlinear shrinkage) applied at each iteration step. We prove that this algorithm converges in norm.” The result covers weighted l^p penalties with 1 <= p <= 2.

Beck and Teboulle later write the same scheme as ISTA: x_{k+1} = T_{lambda*t}(x_k − 2t A^T (A x_k − b)). One matrix-vector product, then one shrinkage. It belongs to a class of methods “where each iteration involves matrix-vector multiplication involving A and A^T followed by a shrinkage/soft-threshold step”, and they note that the scheme “can be traced back to the proximal forward-backward iterative scheme”, citing the 2004 paper. Gradient move, then proximal move, is a citation, not a metaphor.

Each object tells the step something different about the local shape. A gradient is a single number per coordinate, valid where the function is differentiable. A subgradient is a member of a set of admissible supporting slopes, and at a corner that set has more than one element, so the algorithm must choose. A proximal operator is not a slope at all. It is the solution of a small minimization posed around the current point, which is why it can return an exact zero where no derivative-based rule would.

The proximal operator of λ|x| has a simple coordinate-wise form, and three independent groups write down the same rule. Parikh and Boyd give it in three cases: (prox_{lambda*f}(v))_i = v_i - lambda if v_i >= lambda, 0 if |v_i| <= lambda, v_i + lambda if v_i <= -lambda. They restate it compactly as prox_{lambda*f}(v) = (v - lambda)_+ - (-v - lambda)_+, and name it in the line before: “This is known as the (elementwise) soft thresholding operator”. Combettes and Wajs give the same map as prox_{gamma*|.|} x = sign(x) * max{|x| - gamma, 0}, and call it “the well-known scalar soft-thresholding (also known as a shrinkage) operation”. Beck and Teboulle write it as the shrinkage operator T_alpha(x)_i = (|x_i| - alpha)_+ * sgn(x_i), sitting after the gradient step inside the ISTA iteration. Three notations, one rule — the steps below.

Whether a composite or constrained method is appropriate is decided in the order below. The last step, testing support stability, is usually left as advice. It has a published procedure and a bound with a number in it.

Meinshausen and Buhlmann set out stability selection in 2008 and revised it in 2009. The procedure is to run the selection method on random subsamples of size floor(n/2) and keep what is selected often enough. Their Theorem 1 bounds the expected number V of falsely selected variables by E(V) <= (1/(2*pi_thr - 1)) * (q_Lambda^2 / p). At the default cutoff pi_thr = 0.9, choosing the regularisation region so that q_Lambda = sqrt(0.8p) controls E(V) <= 1 — one falsely selected variable expected, stated as a quantity. Setting q_Lambda = sqrt(0.8*alpha*p) controls the familywise error rate at level alpha. Their abstract makes the claim in one sentence: “Stability selection provides finite sample control for some error rates of false discoveries and hence a transparent principle to choose a proper amount of regularisation for structure estimation.”

The assumptions are part of the number. The bound holds assuming exchangeability of the noise-variable selection indicators, and assuming the procedure is no worse than random guessing. Shah and Samworth reproduce the same inequality in 2013 — E|S_CPSS ∩ N| <= (1/(2*tau - 1))(q^2/p) — and add that it “is derived under a very strong exchangeability assumption on the selection of noise variables”. Step 6 is therefore not a vague instruction to resample. It is a choice of subsample size, a cutoff, a regularisation region, and an error rate you have agreed to control under conditions you should state.

An indicator function is zero inside a feasible set and infinite outside it, and its proximal operator is the closest feasible point. That is not an analogy offered here. It is an equation in the literature. Combettes and Wajs wrote it down in 2005: if phi = iota_C, the indicator of a nonempty closed convex set C, then prox_{gamma*phi} = P_C, the projector onto C. Immediately after it they draw the conclusion in one line: “Proximity operators are therefore a generalization of projection operators.”

Parikh and Boyd repeat the identity. For the indicator of a closed nonempty convex set C, “the proximal operator of f reduces to Euclidean projection onto C”, so that “Proximal operators can thus be viewed as generalized projections”. They also spell out the algorithmic consequence: “When g = I_C, prox_{lambda*g} is projection onto C, in which case (4.6) reduces to the projected gradient method”.

Projected gradient descent is therefore not a separate family of algorithms. It is the composite proximal step with one particular nonsmooth term. That does not make it cheap. The projection may be easy for a box or a simplex and difficult for a complex nonconvex set, and the geometry of “closest” depends on the norm or metric the projection uses. Both surveys trace the operator to the same origin, Moreau in 1965 — Combettes and Wajs describing it as introduced by Moreau “as a generalization of the notion of a convex projection operator”. The relationship in this section is the one the concept was built with, not a later observation about it.