Concepts / Convergence of Gradient Descent

Convergence of Gradient Descent

The projection is not a replacement for the gradient step. It is a second stage that enforces membership in the chosen hypothesis set.

  • Programming

Why Projection Enters the Update

Stochastic gradient descent moves the current weight vector in the direction suggested by a subgradient. That proposed movement can be useful for optimization, but it can also carry the weights outside the region allowed by the learning problem. Projected SGD resolves this tension by separating movement from constraint enforcement: it first makes the ordinary update and then brings the result back into the permitted set H.

Key point

The projection is not a replacement for the gradient step. It is a second stage that enforces membership in the chosen hypothesis set.

The Two-Stage Update

wcurrent weightsw − ηgproposed weightsProj_Hconstraint stepwpermitted weightssubtract ηgapply projectionretain point in H
What happens first during the ordinary SGD step, and what happens next during the projection step?
Formula

Read the update from inside to outside. Begin with the current weight vector w. Subtract the scaled subgradient ηg to form the intermediate vector w − ηg. Then apply Proj_H to that intermediate vector. The first stage determines the proposed movement; the second stage determines which permitted vector is retained.

Leaving and Re-entering the Hypothesis Set

win Hw − ηgpossibly outside HProj_H(w − ηg)in HSGD stepprojection
How can an unconstrained gradient step leave the permitted hypothesis class, and how does projection bring it back?

The gradient step does not by itself guarantee that the proposed vector belongs to H. This is why the update must be understood as two linked operations rather than as an unconstrained movement. Projection restores the constraint after the proposed movement has been calculated.

Projection as Nearest Permitted Point

woutside Hvclosest point in HHclosed convex setprojectionbelongs to
Given a weight vector outside the allowed set, which point in the set is closest to it after projection?
Definition

For a closed convex set H, the projection of a vector w onto H is the vector v in H that is closest to w. In notation, v = argmin_{u ∈ H} ‖w − u‖. The candidates are the vectors u that belong to H, and projection selects the candidate with the smallest distance from w.

Worked example

Tracing a projection abstractly

An ordinary SGD step produces an intermediate vector w − ηg that is not in the permitted set H. What does the projection stage retain?

  1. 1
    Form the candidate

    Start with the current weights w and subtract the scaled subgradient ηg. This creates the proposed vector w − ηg.

  2. 2
    Restrict the choices

    Consider only candidate vectors u that belong to H. Vectors outside H are not eligible as the projected result.

  3. 3
    Choose by distance

    Among the eligible candidates, select the one minimizing the distance ‖w − u‖ from the vector being projected.

Result

The projection retains the closest permitted point in H, so the final result satisfies the chosen constraint.

The B-Bounded Hypothesis Class

HB-bounded class‖w‖ ≤ Bmembership conditionweight vectorsallowed hypothesesdefinescontains
What region of weight-vector space contains all vectors whose norm is at most B?
Formula

A B-bounded hypothesis class consists of the weight vectors whose norm is at most B. The condition ‖w‖ ≤ B describes the permitted region of weight-vector space. In analyses using this class, the target weight w⋆ is required to satisfy the same bound, or equivalently to belong to H.

Following Repeated Updates

w₀current permitted vectorw₀ − ηg₀first candidatew₁projected vectorw₁ − ηg₁next candidatew₂next projected vectorgradient stepprojectiongradient stepprojection
How does the weight vector move through successive gradient and projection steps toward convergence?

The same two-stage pattern is repeated at each update. From the current permitted vector, SGD forms a new candidate by subtracting a scaled subgradient. Projection then selects the permitted result. This trace makes convergence analysis easier to read because every iteration has the same structure: propose a movement, then enforce membership in H.

Key point

At every iteration, the projected vector is the state carried into the next update. The intermediate gradient result is only a proposed vector until the projection stage has been applied.

Mistakes in Reading Projected SGD

  • Common mistake

    Treating w − ηg as the final update.

    What it looks like

    Stopping after the ordinary SGD step even when the candidate is outside H.

    Why it fails

    The ordinary step only forms the proposed vector. It does not enforce membership in the permitted set.

    Do this instead

    Apply Proj_H after forming w − ηg.

  • Common mistake

    Assuming projection determines the direction of optimization.

    What it looks like

    Describing the projection as the operation that chooses the gradient direction.

    Why it fails

    The subgradient determines the proposed movement, while projection determines which permitted vector is retained.

    Do this instead

    Keep the optimization role of the subgradient separate from the constraint-enforcing role of projection.

  • Common mistake

    Reading H as an unrestricted collection of weights.

    What it looks like

    Allowing every weight vector even when H is defined by ‖w‖ ≤ B.

    Why it fails

    The B-bounded class includes only vectors whose norm is at most B.

    Do this instead

    Check whether a candidate satisfies the defining membership condition for H.

  • Common mistake

    Defining projection as any point inside H.

    What it looks like

    Selecting a permitted vector without considering its distance from the vector being projected.

    Why it fails

    For a closed convex set, projection means selecting the closest point in H.

    Do this instead

    Use the minimum-distance definition when interpreting Proj_H.

Check Your Understanding

MEDIUM

Explain the update w = Proj_H(w − ηg) in two sentences. Your response should identify what w − ηg represents, what Proj_H does, and why the final vector belongs to the permitted set.

Hints
  • Name the operation that happens before projection.
  • Use the closest-point meaning of projection.
  • Relate membership in H to the learning constraint.
EASY

Suppose H is the B-bounded class H = {w : ‖w‖ ≤ B}. A proposed SGD vector does not satisfy the bound. Describe what the projection stage must accomplish, without calculating a particular vector.

Hints
  • The projected result must be an element of H.
  • Among eligible points, projection chooses the closest one to the proposed vector.

Key Takeaways

  1. 1
    Projected SGD has two stages: form w − ηg, then apply Proj_H.
  2. 2
    The gradient or subgradient proposes the movement; projection enforces the constraint.
  3. 3
    For a closed convex set H, projection selects the closest point in H.
  4. 4
    A B-bounded hypothesis class contains weight vectors satisfying ‖w‖ ≤ B.
  5. 5
    Repeating the gradient step followed by projection keeps each retained weight vector in the permitted set.

At a glance

  • An SGD step may leave the permitted hypothesis class, so projected SGD adds a constraint-enforcing stage.
  • The update first forms w − ηg and then projects that candidate onto H.
  • Projection onto a closed convex set means choosing the closest point in that set.
  • The B-bounded class H = {w : ‖w‖ ≤ B} restricts the allowed weight vectors by their norm.
  • Each repeated update proposes movement and then retains a permitted projected vector.

Related Topics

Related concepts

More concepts starting with C