Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein...

Area of Science:

• Machine Learning
• Optimization Theory
• Convex Analysis

Background:

• Stochastic Gradient Descent (SGD) is fundamental to machine learning.
• Projected SGD is used for constrained optimization, but convergence analysis for non-convex losses is challenging.
• Existing convergence measures (e.g., Moreau envelopes) differ from unconstrained settings, and gradient mapping requires variance reduction.

Purpose of the Study:

• Analyze projected SGD for non-convex losses over compact convex sets.
• Develop a convergence criterion comparable to unconstrained SGD.
• Obtain convergence guarantees without relying on variance reduction techniques.

Main Methods:

• Convergence analysis using the distance to the Goldstein subdifferential.
• Theoretical analysis for independent and identically distributed (IID) and mixing data.
• Derivation of asymptotic and non-asymptotic convergence bounds.

Main Results:

• Achieved convergence for projected SGD without variance reduction.
• Derived asymptotic convergence and O(N^{-1/3}) non-asymptotic bounds for IID/mixing data.
• Established first high-probability non-asymptotic O(N^{-1/5}) bounds for projected SGD with non-convex losses on sub-Gaussian data.

Conclusions:

• The proposed convergence criterion unifies projected and unconstrained SGD analysis.
• The study provides novel theoretical guarantees for projected SGD in non-convex settings.
• These findings advance the understanding and application of constrained optimization in machine learning.