Stagewise Training Accelerates Convergence of Testing Error Over SGD

Abstract

Stagewise training strategy is widely used for learning neural networks, which runs a stochastic algorithm (e.g., SGD) starting with a relatively large step size (aka learning rate) and geometrically decreasing the step size after a number of iterations. It has been observed that the stagewise SGD has much faster convergence than the vanilla SGD with a polynomially decaying step size in terms of both training error and testing error. {\it But how to explain this phenomenon has been largely ignored by existing studies.} This paper provides some theoretical evidence for explaining this faster convergence. In particular, we consider a stagewise training strategy for minimizing empirical risk that satisfies the Polyak-Łojasiewicz (PL) condition, which has been observed/proved for neural networks and also holds for a broad family of convex functions. For convex loss functions and two classes of "nice-behaviored" non-convex objectives that are close to a convex function, we establish faster convergence of stagewise training than the vanilla SGD under the PL condition on both training error and testing error. Experiments on stagewise learning of deep residual networks exhibits that it satisfies one type of non-convexity assumption and therefore can be explained by our theory. Of independent interest, the testing error bounds for the considered non-convex loss functions are dimensionality and norm independent.

arXiv commentMore experiments on deep learning are added to verify the assumptions

References in corpus (9)

• Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)
• Non-convex Finite-Sum Optimization Via SCSG Methods
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Data-Dependent Stability of Stochastic Gradient Descent
• On exponential convergence of SGD in non-convex over-parametrized learning
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• Characterization of Gradient Dominance and Regularity Conditions for Neural Networks
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions

Cited by in corpus (5)

• Adam revisited: a weighted past gradients perspective
• Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data
• From low probability to high confidence in stochastic convex optimization
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Invexifying Regularization of Non-Linear Least-Squares Problems