A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
arXiv:2006.06171
Abstract
One of the challenges in analyzing learning algorithms is the circular entanglement between the objective value and the stochastic noise. This is also known as the "chicken and egg" phenomenon and traditionally, there is no principled way to tackle this issue. People solve the problem by utilizing the special structure of the dynamic, and hence the analysis would be difficult to generalize. In this work, we present a streamlined three-step recipe to tackle the "chicken and egg" problem and give a general framework for analyzing stochastic dynamics in learning algorithms. Our framework composes standard techniques from probability theory, such as stopping time and martingale concentration. We demonstrate the power and flexibility of our framework by giving a unifying analysis for three very different learning problems with the last iterate and the strong uniform high probability convergence guarantee. The problems are stochastic gradient descent for strongly convex functions, streaming principal component analysis, and linear bandit with stochastic gradient descent updates. We either improve or match the state-of-the-art bounds on all three dynamics.
References in corpus (12)
- Overcoming catastrophic forgetting in neural networks
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Provably Efficient Reinforcement Learning with Linear Function Approximation
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
- On the Convergence Rate of Training Recurrent Neural Networks
- Near-Optimal Stochastic Approximation for Online Principal Component Estimation
- Double Quantization for Communication-Efficient Distributed Optimization
- Rates of Convergence for Large-scale Nearest Neighbor Classification
- ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA