Sign Stochastic Gradient Descents without bounded gradient assumption for the finite sum minimization

Area of Science:

• Optimization Theory
• Machine Learning Algorithms
• Distributed Computing

Background:

• Sign-based SGDs reduce communication costs by using gradient signs.
• Existing convergence analyses rely on a bounded gradient assumption, limiting applicability.
• This assumption is often violated in real-world finite sum optimization problems.

Purpose of the Study:

• To develop a novel convergence framework for Sign-based SGDs without the bounded gradient assumption.
• To provide ergodic convergence rates under a weaker, smooth objective function assumption.
• To extend the analysis to variants like signSGD, majority vote, and zeroth-order methods.

Main Methods:

• Developed a new theoretical framework for analyzing Sign-based SGDs.
• Established ergodic convergence rates for smooth objective functions.
• Adapted the framework to analyze signSGD and its variants.

Main Results:

• Achieved convergence guarantees for Sign-based SGDs without requiring bounded gradients.
• Demonstrated that smooth objective functions are sufficient for convergence rate analysis.
• The framework successfully removes the bounded gradient assumption for signSGD and its variants.

Conclusions:

• The proposed framework broadens the applicability of Sign-based SGDs to a wider range of optimization problems.
• This work provides a more robust theoretical foundation for Sign-based SGDs in practical scenarios.
• The findings pave the way for more efficient and widely applicable optimization algorithms.