English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Momentum methods such as Polyak's heavy ball (HB) method, Nesterov'saccelerated gradient (AG) as well as accelerated projected gradient (APG)method have been commonly used in machine learning practice, but theirperformance is quite sensitive to noise in the gradients. We study thesemethods under a first-order stochastic oracle model where noisy estimates ofthe gradients are available. For strongly convex problems, we show that thedistribution of the iterates of AG converges with the accelerated$O(\sqrt{\kappa}\log(1/\varepsilon))$ linear rate to a ball of radius$\varepsilon$ centered at a unique invariant distribution in the 1-Wassersteinmetric where $\kappa$ is the condition number as long as the noise variance issmaller than an explicit upper bound we can provide. Our analysis alsocertifies linear convergence rates as a function of the stepsize, momentumparameter and the noise variance; recovering the accelerated rates in thenoiseless case and quantifying the level of noise that can be tolerated toachieve a given performance. In the special case of strongly convex quadraticobjectives, we can show accelerated linear rates in the $p$-Wasserstein metricfor any $p\geq 1$ with improved sensitivity to noise for both AG and HB througha non-asymptotic analysis under some additional assumptions on the noisestructure. Our analysis for HB and AG also leads to improved non-asymptoticconvergence bounds in suboptimality for both deterministic and stochasticsettings which is of independent interest. To the best of our knowledge, theseare the first linear convergence results for stochastic momentum methods underthe stochastic oracle model. We also extend our results to the APG method andweakly convex functions showing accelerated rates when the noise magnitude issufficiently small.

Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances