Stability and Generalization for Markov Chain Stochastic Gradient Methods
Nov 28, 2022
Speakers
Yunwen Lei
Speaker · 0 followers
Yiming Ying
Speaker · 0 followers
Ding-Xuan Zhou
Speaker · 1 follower
About
Recently there is a large amount of work devoted to the study of Markov chain stochastic gradient methods (MC-SGMs) which mainly focus on their convergence analysis for solving minimization problems. In this paper, we provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems through the lens of algorithmic stability in the framework of statistical learning theory. For empirical risk minimization (ERM) problems, we establish the optimal excess population risk bounds for both smooth and non-smooth cases by introducing on-average argument stability. For minimax problems, we develop a quantitative connection between on-average argument stability and generalization error which extends the existing results for uniform stability (Lei et al., 2021). We further develop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability, which, combined with our stability results, show that the optimal generalization bounds can be attained for both smooth and non-smooth cases. To the best of our knowledge, this is the first generalization analysis of SGMs when the gradients are sampled from a Markov process.Recently there is a large amount of work devoted to the study of Markov chain stochastic gradient methods (MC-SGMs) which mainly focus on their convergence analysis for solving minimization problems. In this paper, we provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems through the lens of algorithmic stability in the framework of statistical learning theory. For empirical risk minimization (ERM) problems, we establish the optimal excess populatio…
Organizer
NeurIPS 2022
Account · 953 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Watermarking for Out-of-distribution Detection
Watch later
Qizhou Wang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Learning NP-Hard Multi Agent Assignment Planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-iteration
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Guaranteed Conservation of Momentum for Learning Particle-based Fluid Dynamics
Watch later
Lukas Prantl, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Sleep and Activity Prediction Using Continuous Glucose Monitoring
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Learning to Prioritize Planning Updates in Model-based Reinforcement Learning
Watch later
Brad Burega, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
On Leave-One-Out Conditional Mutual Information For Generalization
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%