Convergence of Gradient Descent
Projection adds a constraint-enforcing second stage to the ordinary SGD update.
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.
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
w = Proj_H(w − ηg)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
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
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.
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?
Form the candidate: Start with the current weights w and subtract the scaled subgradient ηg. This creates the proposed vector w − ηg.
Restrict the choices: Consider only candidate vectors u that belong to H. Vectors outside H are not eligible as the projected result.
Choose by distance: Among the eligible candidates, select the one minimizing the distance ‖w − u‖ from the vector being projected.
The projection retains the closest permitted point in H, so the final result satisfies the chosen constraint.
The B-Bounded Hypothesis Class
H = {w : ‖w‖ ≤ B}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
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.
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
Treating w − ηg as the final update.
The ordinary step only forms the proposed vector. It does not enforce membership in the permitted set.
Fix:
Apply Proj_H after forming w − ηg.Assuming projection determines the direction of optimization.
The subgradient determines the proposed movement, while projection determines which permitted vector is retained.
Fix:
Keep the optimization role of the subgradient separate from the constraint-enforcing role of projection.Reading H as an unrestricted collection of weights.
The B-bounded class includes only vectors whose norm is at most B.
Fix:
Check whether a candidate satisfies the defining membership condition for H.Defining projection as any point inside H.
For a closed convex set, projection means selecting the closest point in H.
Fix:
Use the minimum-distance definition when interpreting Proj_H.
Check Your Understanding
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.
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
- Projected SGD has two stages: form w − ηg, then apply Proj_H.
- The gradient or subgradient proposes the movement; projection enforces the constraint.
- For a closed convex set H, projection selects the closest point in H.
- A B-bounded hypothesis class contains weight vectors satisfying ‖w‖ ≤ B.
- Repeating the gradient step followed by projection keeps each retained weight vector in the permitted set.
Key Takeaways
- 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.