1 Introduction
1.1 Motivation and scope
Subgradient methods are a class of iterative optimization algorithms designed to minimize convex functions that may be nondifferentiable. Classical gradient descent requires the existence of a gradient, but many important objectives—such as those arising from hinge loss, absolute value regularization, or piecewise-linear formulations—are not differentiable everywhere. Subgradient methods overcome this limitation by replacing the gradient with any subgradient from the subdifferential. They are widely used in machine learning, signal processing, and operations research where nondifferentiable convex optimization problems appear. The algorithms are conceptually simple, use only first-order information, and provide convergence guarantees under mild assumptions, making them a fundamental tool in applied mathematics.
1.2 Definition of subgradient and subdifferential
Let \( f : \mathbb{R}^n \to \mathbb{R} \) be a convex function. A vector \( g \in \mathbb{R}^n \) is a subgradient of \( f \) at \( x \) if for all \( y \in \mathbb{R}^n \), \[ f(y) \ge f(x) + g^\top (y - x). \]
| The set of all subgradients at \( x \) is called the subdifferential, denoted \( \partial f(x) \). For differentiable functions, the subdifferential contains exactly the gradient. For nondifferentiable points, the subdifferential is a nonempty convex compact set (e.g., for \( f(x)= | x | \), \( \partial f(0) = [-1,1] \)). |
|---|
1.3 Relationship to gradient descent
Gradient descent uses the negative gradient \( -\nabla f(x_k) \) as the direction, which guarantees descent in smooth settings. Subgradient methods may not produce a descent direction—the objective value can increase between iterates. However, by employing appropriate step-size rules, the iterates converge to the optimal set. The key trade-off is that subgradient methods typically achieve slower convergence rates (sublinear) compared to gradient descent on smooth functions (linear or superlinear).
2 Subgradient Method Algorithm
2.1 Basic update rule
Given an initial point \( x_0 \), the subgradient method generates a sequence \[ x_{k+1} = x_k - \alpha_k g_k, \] where \( g_k \in \partial f(x_k) \) is any subgradient at \( x_k \), and \( \alpha_k > 0 \) is the step size. Unlike gradient descent, the direction \( -g_k \) is not necessarily a descent direction; the algorithm relies on step-size selection to ensure convergence.
2.2 Step-size selection
Step-size rules are critical for convergence and dictate the trade-off between speed and robustness.
2.2.1 Constant step size
A fixed step size \( \alpha_k = \alpha > 0 \) leads to convergence of the iterates to a neighborhood of the optimal set, with the error bounded proportional to \( \alpha \). It is simple but does not guarantee exact convergence to the optimum.
2.2.2 Diminishing step size (e.g., 1/k)
Step sizes that decrease to zero, such as \( \alpha_k = 1/k \), ensure convergence to the exact minimum under standard assumptions (convexity, bounded subgradients). Two common conditions are \( \sum \alpha_k = \infty \) and \( \sum \alpha_k^2 < \infty \). A classic example is \( \alpha_k = 1/k \).
2.2.3 Polyak's step size
When the optimal value \( f^* \) is known, Polyak’s step size is
| \[ \alpha_k = \frac{f(x_k) - f^*}{\|g_k\|^2}. \] |
|---|
This adaptive rule often leads to faster convergence in practice and can achieve a rate comparable to the best possible for subgradient methods.
2.3 Projected subgradient method
For constrained problems \( \min_{x \in C} f(x) \) where \( C \) is a convex set, the update becomes \[ x_{k+1} = P_C(x_k - \alpha_k g_k), \] where \( P_C \) is the projection onto \( C \). This ensures feasibility at every iteration.
2.3.1 Projection onto convex sets
Projection onto a convex set \( C \) is defined as
| \[ P_C(y) = \arg\min_{x \in C} \|x - y\|. \] |
|---|
For simple sets (e.g., boxes, Euclidean balls, halfspaces), projection has a closed form and is computationally cheap.
2.4 Stopping criteria and optimality condition
Since subgradient methods do not decrease monotonically, typical stopping criteria rely on the subgradient norm or the distance to a known optimal value. For convex functions, a necessary and sufficient optimality condition is \( 0 \in \partial f(x^*) \). In practice, the algorithm is halted when the objective value stabilizes or when the step size becomes very small.
3 Convergence Analysis
3.1 Assumptions (convexity, boundedness)
| Standard convergence results assume \( f \) is convex (or strongly convex) and that subgradients are bounded: there exists \( G > 0 \) such that \( \|g\| \le G \) for all subgradients \( g \) encountered. Additionally, the optimal set is assumed nonempty, and for constrained problems, the feasible set is convex and closed. |
|---|
3.2 Convergence for convex functions
3.2.1 Average iterate convergence
Under a diminishing step-size rule, the averaged iterate \[ \bar{x}_k = \frac{1}{k} \sum_{i=0}^{k-1} x_i \] converges to the optimal set for convex functions. This is often proved using the inequality \[ f(\bar{x}_k) - f^* \le \frac{1}{k} \sum_{i=0}^{k-1} (f(x_i) - f^*) \] and bounding the right-hand side.
3.2.2 Last iterate behavior
The last iterate \( x_k \) does not necessarily converge to the optimum for convex functions; it may oscillate. However, with certain step-size rules (e.g., Polyak’s), the last iterate can converge. Strong convexity improves the behavior, often guaranteeing last-iterate convergence.
3.3 Convergence rate
3.3.1 O(1/√k) for general convex
For convex functions with bounded subgradients, the subgradient method achieves a rate \( \mathcal{O}(1/\sqrt{k}) \) in terms of the objective gap \( f(x_k) - f^* \). This rate is optimal for first-order methods on general convex nondifferentiable problems.
3.3.2 O(1/k) for strongly convex
If \( f \) is \( \mu \)-strongly convex, the rate improves to \( \mathcal{O}(1/k) \) (or even geometric convergence under certain step sizes). This is achieved, for example, with step sizes like \( \alpha_k = (1/\mu k) \).
3.4 Nonmonotonicity of objective value
A distinctive feature of subgradient methods is that the objective value \( f(x_k) \) may increase from one iteration to the next. This is because \( -g_k \) is not necessarily a descent direction. Despite this, the sequence of best values found (or the average) converges to the optimum.
4 Variants and Extensions
4.1 Stochastic subgradient method
4.1.1 Noisy subgradients
| When only a noisy estimate of a subgradient is available, the update uses \( \tilde{g}_k \) where \( \mathbb{E}[\tilde{g}_k | x_k] \in \partial f(x_k) \). The stochastic subgradient method converges under appropriate step-size and variance conditions, with similar rates. |
|---|
4.1.2 Applications in online learning
In online convex programming, the stochastic subgradient method processes a stream of data points. The algorithm’s regret—the cumulative loss compared to the best fixed decision—can be bounded, making it a cornerstone of online learning.
4.2 Incremental subgradient method
For a sum of convex functions \( f(x) = \sum_{i=1}^m f_i(x) \), the incremental method cycles through the components, taking a subgradient step for each \( f_i \) sequentially. This is useful when the full gradient is expensive, and it is closely related to stochastic gradient descent.
4.3 Mirror descent
4.3.1 Relation to Bregman divergence
Mirror descent generalizes the subgradient method by using a non-Euclidean distance measure defined by a Bregman divergence. It replaces the usual projection with a mirror step, often leading to better performance on problems with geometric constraints (e.g., probability simplex).
4.4 Bundle methods
4.4.1 Cutting-plane idea
Bundle methods store a selection of past subgradients to build a piecewise-linear model of the objective. The cutting-plane idea uses these to construct a lower bound and then find a candidate point by solving a quadratic or linear subproblem.
4.4.2 Proximal bundle method
| The proximal bundle method adds a regularization term (like \( \|x - x_k\|^2 \)) to the cutting-plane model, stabilizing the iterates. It converges linearly and is one of the most robust methods for nondifferentiable convex optimization. |
|---|
5 Applications
5.1 Machine learning
5.1.1 Support vector machines (hinge loss)
The SVM primal problem minimizes the hinge loss \( \max(0, 1 - y_i (w^\top x_i + b)) \) plus a regularization term. The hinge loss is nondifferentiable, making the subgradient method a natural choice for training linear SVMs.
5.1.2 L1-regularized problems (Lasso)
| Lasso regression minimizes \( \frac{1}{2}\|Ax - b\|^2 + \lambda \|x\|_1 \). The \( \ell_1 \) norm is nonsmooth at zero. Subgradient methods can handle this, though specialized methods like FISTA or coordinate descent are often faster. |
|---|
5.2 Signal processing
5.2.1 Sparse recovery (basis pursuit)
| Basis pursuit solves \( \min \|x\|_1 \) subject to \( Ax = b \). This is a nondifferentiable convex problem. The subgradient method, possibly with projection onto the affine subspace, provides a simple iterative approach. |
|---|
5.3 Operations research
5.3.1 Lagrangian relaxation
In integer programming, dual problems often involve nondifferentiable concave functions. Subgradient methods are used to update Lagrange multipliers, providing bounds for branch-and-bound algorithms.
6 Comparison with Other Methods
6.1 Gradient descent (smooth case)
For smooth functions, gradient descent achieves linear or superlinear convergence, far faster than subgradient methods. However, gradient descent fails when the function is nondifferentiable, whereas subgradient methods remain applicable.
6.2 Proximal gradient method
6.2.1 When subgradient is preferred
Proximal gradient methods excel for composite objectives with a smooth part and a nonsmooth part (e.g., lasso). They often achieve \( \mathcal{O}(1/k) \) rates. Subgradient methods are preferred when the objective is not of composite form, when projections are cheap, or when simplicity of implementation is paramount.
6.3 Subgradient vs. subgradient-free methods
Subgradient-free methods (e.g., finite-difference, random search) require only function evaluations. They are useful when subgradients are unavailable or too expensive, but their convergence rates are typically much worse, often \( \mathcal{O}(1/\sqrt{k}) \) in high dimensions compared to the subgradient method’s \( \mathcal{O}(1/k) \) for strongly convex cases.