Timezone: »

 
Accelerating Perturbed Stochastic Iterates in Asynchronous Lock-Free Optimization
Kaiwen Zhou · Anthony Man-Cho So · James Cheng

@
in OPT 2022: Optimization for Machine Learning »
Event URL: https://openreview.net/forum?id=ZuAOo-e85T6 »

We show that stochastic acceleration can be achieved under the perturbed iterate framework (Mania et al., 2017) in asynchronous lock-free optimization, which leads to the optimal incremental gradient complexity for finite-sum objectives. We prove that our new accelerated method requires the same linear speed-up condition as existing non-accelerated methods. Our key algorithmic discovery is a new accelerated SVRG variant with sparse updates. Empirical results are presented to verify our theoretical findings.

Author Information

Kaiwen Zhou (The Chinese University of Hong Kong)
Anthony Man-Cho So (CUHK)
James Cheng (The Chinese University of Hong Kong)

More from the Same Authors