# Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions

arXiv: https://arxiv.org/abs/1808.06296 · HTML: https://mlsanity.com/paper/1808.06296/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Aug 2018.

## Built on by (most cited first, 9 of 9)

- [Robustness to Unbounded Smoothness of Generalized SignSGD](https://mlsanity.com/paper/2208.11195/) (2022)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Towards Practical Adam: Non-Convexity, Convergence Theory, and Mini-Batch Acceleration](https://mlsanity.com/paper/2101.05471/) (2021)
- [Toward Communication Efficient Adaptive Gradient Method](https://mlsanity.com/paper/2109.05109/) (2021)
- [On the Convergence of Step Decay Step-Size for Stochastic Optimization](https://mlsanity.com/paper/2102.09393/) (2021)
- [Differentially Private Zeroth-Order Methods for Scalable Large Language Model Finetuning](https://mlsanity.com/paper/2402.07818/) (2024)
- [Bandwidth-based Step-Sizes for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/2106.02888/) (2021)
- [Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Optimization](https://mlsanity.com/paper/2106.10022/) (2021)
- [Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms](https://mlsanity.com/paper/2410.02559/) (2024)

## Abstract (arXiv)

Although stochastic gradient descent (SGD) method and its variants (e.g., stochastic momentum methods, AdaGrad) are the choice of algorithms for solving non-convex problems (especially deep learning), there still remain big gaps between the theory and the practice with many questions unresolved. For example, there is still a lack of theories of convergence for SGD and its variants that use stagewise step size and return an averaged solution in practice. In addition, theoretical insights of why adaptive step size of AdaGrad could improve non-adaptive step size of sgd is still missing for non-convex optimization. This paper aims to address these questions and fill the gap between theory and practice. We propose a universal stagewise optimization framework for a broad family of bf non-smooth non-convex (namely weakly convex) problems with the following key features: (i) at each stage any suitable stochastic convex optimization algorithms (e.g., SGD or AdaGrad) that return an averaged solution can be employed for minimizing a regularized convex problem; (ii) the step size is decreased in a stagewise manner; (iii) an averaged solution is returned as the final solution that is selected from all stagewise averaged solutions with sampling probabilities it increasing as the stage number. Our theoretical results of stagewise AdaGrad exhibit its adaptive convergence, therefore shed insights on its faster convergence for problems with sparse stochastic gradients than stagewise SGD. To the best of our knowledge, these new results are the first of their kind for addressing the unresolved issues of existing theories mentioned earlier. Besides theoretical contributions, our empirical studies show that our stagewise SGD and ADAGRAD improve the generalization performance of existing variants/implementations of SGD and ADAGRAD.