Primal Averaging: A New Gradient Evaluation Step to Attain the Optimal Individual Convergence

Area of Science:

• Machine Learning
• Optimization Theory

Background:

• First-order gradient methods struggle with optimal individual convergence for large-scale composite problems in machine learning.
• Achieving optimal individual convergence for stochastic gradient descent (SGD), especially for strongly convex problems, remains a challenge.

Purpose of the Study:

• To develop a novel gradient operation step that improves individual convergence rates for convex and strongly convex problems.
• To extend these improvements to stochastic settings for regularized nonsmooth learning problems.

Main Methods:

• Introduction of a new Primal Averaging (PA) gradient operation step.
• Modification of Mirror Descent (MD) with the PA strategy.
• Application of PA-MD to stochastic settings for regularized nonsmooth learning.

Main Results:

• The PA strategy recovers the optimal individual convergence rate for general convex problems when applied to Mirror Descent (MD).
• Optimal individual convergence rates for strongly convex problems are achieved by incorporating strong convexity into the PA-MD gradient operation.
• PA-MD demonstrates effectiveness in solving regularized nonsmooth learning problems in the stochastic setting.

Conclusions:

• The Primal Averaging strategy is a simple yet effective method for achieving optimal individual convergence in gradient-based optimization.
• PA-MD offers a significant advancement for the theoretical understanding and practical application of stochastic gradient descent (SGD).
• Experimental results on sparse learning and SVM problems validate the theoretical findings.