Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD For Gradient-Dominated Functions
Nov 28, 2022
Speakers
Saeed Masiha
Speaker · 0 followers
Saber Salehkaleybar
Speaker · 0 followers
Negar Kiyavash
Speaker · 1 follower
Patrick Thiran
Speaker · 0 followers
About
We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that SCRN improves the best-known sample complexity of stochastic gradient descent in achieving ϵ-global optimum by a factor of 𝒪(ϵ^-1/2). Even under a weak version of gradient dominance property, which is applicable to policy-based reinforcement learning (RL), SCRN achieves the same improvement over stochastic policy gradient methods. Additionally, we show that the sample complexity of SCRN can be improved by a factor of 𝒪(ϵ^-1/2) using a variance reduction method with time-varying batch sizes. Experimental results in various RL settings showcase the remarkable performance of SCRN compared to first-order methods.We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property which holds in a wide range of applications in machine learning and signal processing. This condition ensures that any first-order stationary point is a global optimum. We prove that SCRN improves the best-known sample complexity of stochastic gradient descent in achieving ϵ-global optimum by a factor of 𝒪(ϵ^-1/2). Even under a weak version of gradient dominance…
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
Deep learning-based bias adjustment of decadal climate predictions
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Gradient Knowledge Distillation for Pre-trained Language Models
Watch later
Lean Wang, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
A Kernelised Stein Statistic for Assessing Implicit Generative Models
Watch later
Wenkai Xu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction
Watch later
Hansheng Xue, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Decentralized Training of Foundation Models in Heterogeneous Environments
Watch later
Binhang Yuan, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Adversarial Attack on Attackers: Post-Process to Mitigate Black-Box Score-Based Query Attacks
Watch later
Sizhe Chen, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%