An One-Shot Framework for Analyzing Stochastic Dynamics Streaming ModelSpeaker: Chi-Ning
Title: An One-Shot Framework for Analyzing Stochastic Dynamics Streaming Model
Date: 27 Jan 2020 5:30pm-7:00pm
Location: Maxwell-Dworkin 221
Abstract: Stochastic dynamics appear everywhere in computer science, for example, stochastic gradient descent etc. Traditionally, people analyze these dynamics step by step by taking expectation. Namely, showing that the dynamics “improve” with good probability at each step. However, this step-by-step approach becomes complicated once the dynamic is non-linear and many hacks are required to make the analysis tight.
In a recent work with Brabeeba Wang, we developed an one-shot framework in analyzing stochastic dynamics using stopping time techniques. This one-shot approach gives a clean analysis template for understanding stochastic dynamics. For instance, we instantiated on the analysis of Oja’s rule in solving the streaming PCA problem and gave the first efficient analysis and achieved information-theoretic lower bound. In this talk, I will present the one-shot framework and use the analysis for Oja’s rule as a running example.