Can the method stop when it finds a zero subgradient?

For an unconstrained convex objective, that certifies a global minimizer. Constraints require the appropriate combined optimality condition.

Does it require random sampling?

No. Basic subgradient methods can be deterministic; stochastic subgradient variants add sampling.

Why not use ordinary line search?

A selected negative subgradient need not be a descent direction, so smooth descent-based line-search logic does not apply unchanged.

AI Glossary / Mathematics and optimization / Intermediate

Subgradient descent

Definition

Subgradient descent is an iterative optimization method that replaces an ordinary gradient with a subgradient. It is commonly used for convex objectives with corners, where differentiability fails. Despite its name, its objective value need not decrease at every step.

What it means

An objective involving absolute values, a maximum of costs or a hinge loss can be convex without being smooth. A subgradient provides a supporting linear lower bound at the current point, allowing an update even at a corner.

The basic method is often called the subgradient method because “descent” can suggest a stronger property than it has. An update may move closer to an optimal set while raising the current objective, or a poorly chosen step may overshoot.

Its appeal is simplicity and relatively modest per-step requirements. That does not make it the fastest solver for every nonsmooth problem. Proximal methods, specialized solvers and other approaches may exploit additional structure more effectively.

How it works

At iteration k, choose gk from the subdifferential ∂f(xk), choose a positive step size αk and update x(k+1) = xk − αk gk. For a differentiable convex objective, the chosen subgradient is the ordinary gradient.

Because the objective can rise, keep track of the best feasible point or use a justified averaging scheme rather than assuming the final iterate is automatically best. The step-size policy must match the desired guarantee.

Under standard convex assumptions, including an existing minimizer and bounded subgradients along the iterates, suitable diminishing steps support convergence of the best objective values. A common sufficient schedule has a divergent sum of steps but a finite sum of squared steps, such as a positive multiple of 1/k. The assumptions matter as much as the formula.

For a closed convex constraint set, a projected variant maps the tentative update back to that set. Projection is an additional operation whose cost and correctness must be considered.

Three practical examples

A linear prediction model minimizes a convex loss with an absolute-value penalty.
A planning model reduces the worst of several affine cost estimates, using a subgradient of an active maximum term.
A distributed optimization experiment applies a subgradient method to a dual objective while tracking feasibility and objective bounds separately.

Think of it this way

Think of taking measured steps toward the low part of a sharply folded surface. The information at a fold can suggest several valid directions, and a step can cross from one face to another.

The analogy explains why step length matters. It does not establish convergence, which relies on the precise convexity, boundedness and scheduling conditions of the mathematical method.

Worked example

A constant step can create a cycle

Minimize f(x) = |x|, whose optimum is x = 0 with value zero. Away from zero, use subgradient +1 for positive x and −1 for negative x.

Start at x0 = 0.3 and take constant step size 0.5. The first update gives x1 = 0.3 − 0.5 = −0.2. The next gives x2 = −0.2 + 0.5 = 0.3. The process repeats between these two points, with objective values 0.3 and 0.2. It does not converge to the exact optimum.

Now restart at 0.3 with αk = 0.5/(k + 1). The first point is again −0.2. The second is −0.2 + 0.25 = 0.05. The third is 0.05 − 1/6, approximately −0.1167. The third objective is worse than the second, even though the step schedule diminishes.

The best value observed so far remains 0.05. These few steps do not prove convergence, but they explain why keeping the best point is useful. A valid convergence argument concerns the entire schedule and its assumptions, not whether a short displayed sequence decreases monotonically.

Illustrative case study

A fictional allocation-model team implements a subgradient update for a worst-case cost objective. Its monitoring system treats any objective increase as immediate failure, so it stops runs that are behaving consistently with the chosen algorithm.

The team adds a best-so-far record and reviews the step-size schedule. It also checks the constraint projection, discovering that a rounded display of a proposed allocation had been mistaken for a feasible solution.

The revised experiment compares feasible objective values with a trusted small-problem reference. The lesson is to monitor the properties the algorithm actually provides. Removing an inappropriate monotonicity alarm does not remove the need to detect divergence, infeasibility or incorrect subgradients.

Common misconceptions and mistakes

Every subgradient update decreases the objective. That property is not guaranteed.
Any decreasing step schedule is sufficient. Steps can shrink too quickly to reach the optimum.
The last point is necessarily the best. Earlier iterates can have lower objective values.
A smaller constant step guarantees exact convergence. It may only reduce the size of persistent error or oscillation under relevant assumptions.
Convex guarantees transfer unchanged to nonconvex problems. Generalized derivatives and convergence claims require separate treatment.

Business use

Subgradient methods are useful when a nonsmooth convex objective has inexpensive subgradients and limited memory is available. Evaluate them against methods that exploit the objective's structure, rather than assuming simplicity means superior total performance.

Record the step schedule, chosen subgradients, objective values and feasibility checks. Where possible, compare a feasible upper bound with a valid lower bound to assess progress. Distinguish convergence of objective values from convergence of parameters, and distinguish mathematical assumptions from empirical observations on a single dataset.

Check your understanding

In the diminishing-step example, which of the first three updated points should a best-so-far record retain?

Answer: x2 = 0.05, with objective 0.05. The next point has objective about 0.1167, so it should not replace the best record.

Related terms

Subgradient
Step size
nonsmooth optimization
projection
proximal gradient
dual optimization

Learn next

Read the subgradient definition and proximal operator. Repeat the absolute-value example with a smaller constant step, then explain why a narrower cycle is not the same as exact convergence. Compare best-so-far values with the raw iterate sequence.

Sources

Boyd, Subgradient Methods, Stanford EE364b notes: https://web.stanford.edu/class/ee364b/lectures/subgrad_method_notes.pdf. Basic iteration, step-size rules, assumptions and best-iterate analysis.

Aalto Dictionary of Machine Learning, subgradient descent: https://aaltodictionaryofml.github.io/ADictML_Main.pdf. Machine-learning context. Iterations and the fictional monitoring case are original examples.

Previous: Subgradient Next: Subgraph isomorphism