Concepts / Gradients

Gradients

A subgradient is a vector that supplies a lower-supporting linear slope at a point.

  • Programming

When Gradients Are Unavailable

Gradient descent is normally described using the gradient of a function. That requirement becomes restrictive when the function is not differentiable at some points. Subgradients extend the descent idea by allowing the method to use a vector that satisfies a supporting inequality at the current point instead of requiring an ordinary gradient.

Differentiablefunctiongradient ∇f(w)Descent stepuse the gradientNondifferentiablefunctionno gradient at wSubgradientvalid supporting vectorDescent stepuse a subgradientsuppliesrequires an extensionsupplies
What changes when the current point does not provide an ordinary gradient?

The Supporting Slope

For a convex function, a subgradient at w is a vector that supplies a lower-supporting linear slope at that point. Geometrically, the associated linear expression touches the function at the reference point and remains below the function elsewhere in its domain. This lower-supporting behavior is the central idea behind a subgradient.

wreference pointfconvex functionlower bound≤ f(u)vcandidate vectorsupporting expressionf(w) + vᵀ(u − w)evaluates atdefinesis compared withmust remain below
How can a linear object meet a convex function at w while remaining below it at other points?
Definition

A subgradient of a convex function f at a point w is a vector v for which the linear expression f(w) + vᵀ(u − w) remains no greater than f(u) for every u in the domain.

Testing a Candidate Vector

The supporting-slope picture becomes precise through the subgradient inequality. Begin with the reference point w and a candidate vector v. Form the linear expression f(w) + vᵀ(u − w). Then compare it with f(u) for every u in the function's domain. If the expression is no greater than f(u) everywhere, v has the required subgradient property at w.

Formula, step by step
  1. 1
    Choose the reference point w.
  2. 2
    Choose a candidate vector v.
  3. 3
    Evaluate the supporting expression f(w) + vᵀ(u − w).
  4. 4
    Compare that expression with f(u) for every u in the domain.
  5. 5
    Accept v as a subgradient at w only when the inequality holds everywhere.
Reference point widentify wCandidate vchoose vf(w) + vᵀ(u − w)form supporting expressionCompare with f(u)for every uValid subgradientinequality holdsNot a subgradientinequality failsthen chooseuse intest againstholds everywherefails somewhere
How does checking the inequality for every point determine whether v is a valid subgradient at w?
Worked example

Checking one candidate

Determine how to test whether a proposed vector v can be a subgradient of f at w.

  1. 1
    Set the reference point

    Use the point w at which the subgradient is being considered.

  2. 2
    Build the supporting expression

    Form f(w) + vᵀ(u − w) using the proposed vector v.

  3. 3
    Check every domain point

    Compare the expression with f(u) for every u in the domain, rather than checking only one selected point.

  4. 4
    Decide

    If the expression never exceeds f(u), the candidate has the subgradient property at w. If it exceeds f(u) at any domain point, the candidate fails the required test.

Result

The inequality provides a precise validity test for the candidate vector.

Gradient and Subdifferential

A gradient is tied to differentiability. A subgradient is selected through the supporting inequality, so it can be used in the broader setting that includes nondifferentiable functions. For a convex function, the subdifferential set ∂f(w) contains all subgradients of f at w.

Gradient ∇f(w)available whendifferentiableSubgradient vpasses supportinginequality∂f(w)all subgradients{∇f(w)}when f is differentiable atwis the sole member ofis a member ofcollapses to
What is the relationship between the gradient and the potentially broader collection of valid subgradients?
ObjectHow it is identifiedRole
Gradient ∇f(w)Tied to differentiability at wProvides the single subgradient when differentiability is known
Subgradient vSatisfies the supporting inequality at wAllows the descent discussion to include nondifferentiable functions
Subdifferential ∂f(w)Contains all subgradients at wProvides the set from which a usable subgradient can be selected

The gradient is a special case within the subgradient framework described by the source material.

Choosing One Useful Member

The subdifferential set may contain all valid subgradients, but many practical uses do not require calculating every member. The practical goal is often to construct one element of ∂f(w). If f is differentiable at w, that construction is immediate: use the gradient ∇f(w).

Convex f at wstarting informationDifferentiable at wavailable?∇f(w)single subgradientOne member of ∂f(w)often sufficientPointwise maximumuse its construction methodcheckyesotherwise considerprovidesconstruction provides
How does the construction process aim at one usable member of the subdifferential set?

Pointwise maximum functions are another situation for which the source material introduces a construction method. The important practical role of that method is to produce a subgradient of the maximum function. The objective is not necessarily to list the entire subdifferential set; obtaining one member can be enough for many uses.

Best practice

Use a disciplined workflow: identify w, determine whether the function is differentiable there, use ∇f(w) when it is available, and otherwise seek a vector that satisfies the subgradient inequality. Treat the full set ∂f(w) as the collection of valid choices, not as a requirement to calculate every choice.

Mistakes in Subgradient Reasoning

  • Common mistake

    Treating a subgradient as automatically identical to a gradient.

    What it looks like

    Assuming that every valid subgradient must be the gradient of f at w.

    Why it fails

    A gradient is tied to differentiability, while a subgradient is identified through the supporting inequality and can extend the discussion to nondifferentiable functions.

    Do this instead

    Check the subgradient condition. If f is differentiable at w, the subdifferential is the singleton containing ∇f(w); otherwise, use the supporting inequality to identify a valid vector.

  • Common mistake

    Checking the inequality at only one point u.

    What it looks like

    Verifying f(w) + vᵀ(u − w) ≤ f(u) for one selected u and declaring v valid.

    Why it fails

    The subgradient inequality must hold for every u in the domain.

    Do this instead

    Treat the comparison as a domain-wide test.

  • Common mistake

    Assuming that finding every subgradient is always necessary.

    What it looks like

    Trying to enumerate the entire set ∂f(w) before using a subgradient.

    Why it fails

    For many practical uses, constructing one member of the subdifferential set is sufficient.

    Do this instead

    Focus first on obtaining one valid subgradient.

  • Common mistake

    Ignoring the reference point.

    What it looks like

    Discussing whether v is a subgradient without specifying the point w.

    Why it fails

    The subgradient property is defined at a particular point w through f(w) and the displacement u − w.

    Do this instead

    Identify w before forming and checking the supporting expression.

Practice Check

EASY

Suppose you are given a convex function f, a point w, and a candidate vector v. Describe the complete procedure you would use to decide whether v belongs to ∂f(w).

Hints
  • Start by writing the supporting expression involving f(w), v, u, and w.
  • Remember that the comparison must cover every u in the domain.
  • State what conclusion follows if the inequality holds everywhere.

What do you think happens?

If f is differentiable at w, what does the subdifferential set contain?

  • Every vector in the domain

  • Only the gradient ∇f(w)

  • No vectors

  • A construction method for a pointwise maximum

Reveal answer
Answer:

Only the gradient ∇f(w)

Differentiability makes the subdifferential set a singleton containing the gradient at w.

Key Takeaways

  1. 1
    A subgradient is a vector that supplies a lower-supporting linear slope at a point.
  2. 2
    The subgradient inequality tests whether a candidate vector remains below the function everywhere in the required sense.
  3. 3
    The subdifferential set ∂f(w) contains all subgradients at w.
  4. 4
    When f is differentiable at w, ∂f(w) is the singleton containing ∇f(w).
  5. 5
    For many practical uses, constructing one subgradient is sufficient, including through a suitable construction method for pointwise maximum functions.

At a glance

  • Subgradients extend gradient-descent reasoning to nondifferentiable functions.
  • A valid subgradient supplies a lower-supporting linear expression at the reference point w.
  • The inequality f(w) + vᵀ(u − w) ≤ f(u) for every u is the precise validity test.
  • The subdifferential ∂f(w) contains all valid subgradients and becomes {∇f(w)} when f is differentiable at w.
  • Many practical applications need only one constructed member of the subdifferential set.

Related Topics

Related concepts

More concepts starting with G