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

The recently proposed stochastic Polyak stepsize (SPS) and stochasticline-search (SLS) for SGD have shown remarkable effectiveness when trainingover-parameterized models. However, in non-interpolation settings, bothalgorithms only guarantee convergence to a neighborhood of a solution which mayresult in a worse output than the initial guess. While artificially decreasingthe adaptive stepsize has been proposed to address this issue (Orvieto et al.[2022]), this approach results in slower convergence rates for convex andover-parameterized models. In this work, we make two contributions: Firstly, wepropose two new variants of SPS and SLS, called AdaSPS and AdaSLS, whichguarantee convergence in non-interpolation settings and maintain sub-linear andlinear convergence rates for convex and strongly convex functions when trainingover-parameterized models. AdaSLS requires no knowledge of problem-dependentparameters, and AdaSPS requires only a lower bound of the optimal functionvalue as input. Secondly, we equip AdaSPS and AdaSLS with a novel variancereduction technique and obtain algorithms that require$\smash{\widetilde{\mathcal{O}}}(n+1/\epsilon)$ gradient evaluations to achievean $\mathcal{O}(\epsilon)$-suboptimality for convex functions, which improvesupon the slower $\mathcal{O}(1/\epsilon^2)$ rates of AdaSPS and AdaSLS withoutvariance reduction in the non-interpolation regimes. Moreover, our resultmatches the fast rates of AdaSVRG but removes the inner-outer-loop structure,which is easier to implement and analyze. Finally, numerical experiments onsynthetic and real datasets validate our theory and demonstrate theeffectiveness and robustness of our algorithms.

Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence and Variance Reduction