A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
This provides a principled, generalizable method for analyzing stochastic dynamics in learning algorithms, addressing a long-standing bottleneck in the field, though it is incremental in building on standard probability techniques.
The authors tackled the 'chicken and egg' problem in analyzing stochastic dynamics of learning algorithms by developing a general three-step framework, which improved or matched state-of-the-art bounds for three diverse learning problems, including stochastic gradient descent for strongly convex functions, streaming PCA, and linear bandit with SGD updates.
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.