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

We study stochastic gradient descent {\em without replacement} (\sgdwor) forsmooth convex functions. \sgdwor is widely observed to converge faster thantrue \sgd where each sample is drawn independently {\em with replacement}\cite{bottou2009curiously} and hence, is more popular in practice. But it'sconvergence properties are not well understood as sampling without replacementleads to coupling between iterates and gradients. By using method ofexchangeable pairs to bound Wasserstein distance, we provide the firstnon-asymptotic results for \sgdwor when applied to {\em general smooth,strongly-convex} functions. In particular, we show that \sgdwor converges at arate of $O(1/K^2)$ while \sgd is known to converge at $O(1/K)$ rate, where $K$denotes the number of passes over data and is required to be {\em largeenough}. Existing results for \sgdwor in this setting require additional {\emHessian Lipschitz assumption} \cite{gurbuzbalaban2015random,haochen2018random}.  For {\em small} $K$, we show \sgdwor can achieve same convergence rate as\sgd for {\em general smooth strongly-convex} functions. Existing results inthis setting require $K=1$ and hold only for generalized linear models\cite{shamir2016without}. In addition, by careful analysis of the coupling, forboth large and small $K$, we obtain better dependence on problem dependentparameters like condition number.

SGD without Replacement: Sharper Rates for General Smooth Convex Functions