Subgradient Methods

When optimizing real-world problems in machine learning, engineering, or economics, you will inevitably encounter functions that are not smoothly differentiable. Hinge losses, L1 regularization, and ReLU activations are cornerstone examples. The subgradient method is the fundamental workhorse for minimizing such nonsmooth convex functions. Unlike gradient descent, which fails when the gradient does not exist, subgradient methods provide a robust, iterative framework for navigating the slopes of functions with "kinks" and corners, trading off the speed of smooth optimization for broad applicability.

Subgradients and Subdifferentials: The Foundation

For a smooth convex function $f:{\mathbb{R}}^n\to \mathbb{R}$, the gradient at a point $\mathbf{x}$, $\nabla f(\mathbf{x})$, defines a unique supporting hyperplane to the function's graph. For a nonsmooth convex function, this unique tangent is replaced by a set of supporting hyperplanes. A vector $\mathbf{g}\in {\mathbb{R}}^n$ is called a subgradient of $f$ at a point $\mathbf{x}$ if it satisfies the supporting hyperplane inequality for all $\mathbf{y}$: $$f(\mathbf{y})\ge f(\mathbf{x})+{\mathbf{g}}^{\top }(\mathbf{y}-\mathbf{x}).$$

Geometrically, each subgradient defines a line (or plane) that lies completely below the graph of $f$. The set of all subgradients at $\mathbf{x}$ is called the subdifferential, denoted $\partial f(\mathbf{x})$. This is always a closed, convex set. At a point where $f$ is differentiable, the subdifferential contains only the gradient: $\partial f(\mathbf{x})=\{\nabla f(\mathbf{x})\}$. At a "kink," like the vertex of the absolute value function $|x|$ at $x=0$, the subdifferential is an interval of slopes. For $f(x)=|x|$, we have $\partial f(0)=[-1,1]$.

Understanding the subdifferential is crucial because it generalizes the first-order optimality condition. For a convex function, a point ${\mathbf{x}}^{\ast }$ is a global minimizer if and only if $0\in \partial f({\mathbf{x}}^{\ast })$. This is the nonsmooth counterpart to $\nabla f({\mathbf{x}}^{\ast })=0$.

The Subgradient Method Algorithm and Step Size Rules

The basic subgradient method mimics gradient descent but uses an arbitrary subgradient. Starting from an initial point ${\mathbf{x}}_0$, the iteration for $k=0,1,2,...$ is: $${\mathbf{x}}_{k+1}={\mathbf{x}}_k-{\alpha }_k{\mathbf{g}}_k,\text{where }{\mathbf{g}}_k\in \partial f({\mathbf{x}}_k).$$

A critical distinction from gradient descent is that $-{\mathbf{g}}_k$ is not necessarily a descent direction. The function value $f({\mathbf{x}}_{k+1})$ can increase from the previous iteration. Therefore, the algorithm must keep track of the best point found so far, ${\mathbf{x}}_{\text{best}}^k={\text{argmin}}_{i=0,...,k}f({\mathbf{x}}_i)$.

The choice of step size ${\alpha }_k$ is paramount and follows different rules than smooth optimization due to the lack of a guaranteed descent direction. Common, theoretically sound step size rules include:

• Constant Step Size: ${\alpha }_k=\alpha$. Simple but only converges to within a neighborhood of the optimum.
• Diminishing Step Sizes: Step sizes that satisfy the conditions ${\alpha }_k>0$, ${\sum }_{k=1}^{\infty }{\alpha }_k=\infty$, and ${\sum }_{k=1}^{\infty }{\alpha }_k^2<\infty$. A typical choice is ${\alpha }_k=a/(b+k)$. These rules guarantee asymptotic convergence to the optimum.
• Square Summable but Not Summable: A stricter diminishing rule like ${\alpha }_k=1/(k+1)$.

Unlike in gradient descent, you cannot use line searches to choose ${\alpha }_k$ adaptively, as the function may not decrease along $-{\mathbf{g}}_k$.

Convergence Analysis and Rates

The convergence theory for the subgradient method is more nuanced than for gradient descent. A standard result states that for a convex function $f$ with minimum value $f^{\ast }$, using a diminishing step size rule, we have $f({\mathbf{x}}_{\text{best}}^k)\to f^{\ast }$ as $k\to \infty$.

More informatively, we can analyze the rate. A fundamental inequality drives the analysis: $$\Vert {\mathbf{x}}_{k+1}-{\mathbf{x}}^{\ast }{\Vert }^2\le \Vert {\mathbf{x}}_k-{\mathbf{x}}^{\ast }{\Vert }^2-2{\alpha }_k(f({\mathbf{x}}_k)-f^{\ast })+{\alpha }_k^2\Vert {\mathbf{g}}_k{\Vert }^2.$$ Assuming the subgradients are bounded, $\Vert {\mathbf{g}}_k\Vert \le G$, this inequality can be manipulated to show an $O(1/\sqrt{k})$ convergence rate for the best function value. Specifically, with a step size rule ${\alpha }_k=c/\sqrt{k}$, you can achieve: $$f({\mathbf{x}}_{\text{best}}^k)-f^{\ast }\le \frac{O(1)}{\sqrt{k}}.$$

This is markedly slower than the $O(1/k)$ rate for gradient descent on smooth convex functions or the $O(1/k^2)$ rate with acceleration. This is the price paid for nonsmoothness. The subgradient method is robust but inherently slow.

Advanced Methods: Bundle Techniques

To improve upon the slow convergence of the basic subgradient method, more sophisticated bundle methods were developed. These methods leverage memory—a "bundle" of past subgradients—to build a better local model of the function.

The core idea is to use past iterates ${\mathbf{x}}_i$ and their subgradients ${\mathbf{g}}_i\in \partial f({\mathbf{x}}_i)$ to construct a cutting-plane model of $f$: $${\hat{f}}_k(\mathbf{x})=\underset{i\in I_k}{\max }\left[f({\mathbf{x}}_i)+{\mathbf{g}}_i^{\top }(\mathbf{x}-{\mathbf{x}}_i)\right],$$ where $I_k$ is an index set of past iterates. This model ${\hat{f}}_k$ is a piecewise linear, convex function that under-estimates $f$. Bundle methods then minimize this model (plus a stabilizing quadratic term to keep the next iterate close to the current best point) to compute a candidate point. If the candidate point yields significant descent, a "serious step" is taken. Otherwise, a "null step" is taken, but the subgradient information from the candidate point is added to the bundle, enriching the model.

This use of history allows bundle methods to detect the structure of the nonsmooth function, often leading to faster practical convergence and even finite termination for piecewise linear problems, a significant advantage over the basic subgradient method.

Application to Machine Learning with Non-differentiable Losses

Subgradient methods are directly applicable to many core machine learning problems. Consider L1-regularized empirical risk minimization, such as Lasso: $$\underset{\mathbf{w}}{\min }\frac{1}{m}\sum _{i=1}^{m}L(\mathbf{w};{\mathbf{x}}_i,y_i)+\lambda \Vert \mathbf{w}{\Vert }_1.$$

The regularizer $\Vert \mathbf{w}{\Vert }_1={\sum }_j|w_j|$ is nonsmooth at any $w_j=0$. Its subgradient for component $j$ is $g_j\in \partial |w_j|$, where $g_j=\text{sign}(w_j)$ if $w_j\ne 0$, and $g_j\in [-1,1]$ if $w_j=0$. A subgradient method can be applied directly to the entire objective. The update for a component $w_j$ at zero becomes: $$w_j^{(k+1)}=w_j^{(k)}-{\alpha }_k\left({\text{(gradient of loss)}}_j+\lambda g_j\right),g_j\in [-1,1].$$ This can be interpreted as a form of soft-thresholding when combined with specific step sizes.

Similarly, training a linear support vector machine (SVM) with the hinge loss $L(y,\hat{y})=\max (0,1-y\hat{y})$ involves a nonsmooth objective. The subgradient of the hinge loss with respect to the model parameters is straightforward to compute, making the subgradient method a simple, though not always the fastest, baseline solver.

Common Pitfalls

1. Expecting Monotonic Descent: The most frequent mistake is expecting $f({\mathbf{x}}_{k+1})<f({\mathbf{x}}_k)$ on every iteration. This is not guaranteed. You must track the best iterate ${\mathbf{x}}_{\text{best}}^k$ separately to monitor convergence.
2. Using Inappropriate Step Sizes: Applying a line search or an adaptive step-size rule designed for smooth functions (like Adam, without modification) to a raw subgradient method often fails, as the direction is not a descent direction. Stick to theoretically justified rules like diminishing step sizes or use specialized methods like subgradient clipping with momentum.
3. Misidentifying the Subdifferential: For complex functions, correctly computing an element $\mathbf{g}\in \partial f(\mathbf{x})$ is essential. A common error is to use a gradient formula at a point of non-differentiability. Always refer to the definition: $\mathbf{g}$ is valid if it satisfies the supporting hyperplane inequality.
4. Overlooking Better Alternatives: While the subgradient method is universally applicable, it is often slow. For specific problems like L1 regularization, more efficient proximal gradient methods exist, which handle the nonsmooth part explicitly and elegantly. Always check if a specialized solver is available for your problem structure.

Summary

• Subgradients generalize gradients to nonsmooth convex functions, and the subdifferential $\partial f(\mathbf{x})$ is the set of all subgradients at a point. The condition $0\in \partial f({\mathbf{x}}^{\ast })$ characterizes a global minimum.
• The subgradient method iteratively updates parameters using any subgradient and a pre-defined step size rule. Crucially, it does not guarantee descent at each step, requiring you to track the best iterate found.
• Convergence is robust but slow, with a theoretical rate of $O(1/\sqrt{k})$ for diminishing step sizes, which is a fundamental consequence of nonsmoothness.
• Bundle methods improve performance by maintaining a history of subgradients to build an approximating cutting-plane model, allowing for more intelligent step choices.
• These methods are directly applicable to key machine learning problems involving non-differentiable components like the hinge loss for SVMs and L1 regularization for sparse model induction.