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

Abstract

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.

arXiv commentadded more experimental results

References in corpus (10)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Nearly unbiased variable selection under minimax concave penalty
• On the Convergence of Adam and Beyond
• Learning to Reweight Examples for Robust Deep Learning
• Train faster, generalize better: Stability of stochastic gradient descent
• AdaGrad stepsizes: Sharp convergence over nonconvex landscapes
• Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
• Learning with Non-Convex Truncated Losses by SGD
• Constrained Deep Learning using Conditional Gradient and Applications in Computer Vision

Cited by in corpus (4)

• First-order Convergence Theory for Weakly-Convex-Weakly-Concave Min-max Problems
• Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Stochastic Optimization for Non-convex Inf-Projection Problems