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

Multi-epoch, small-batch, Stochastic Gradient Descent (SGD) has been themethod of choice for learning with large over-parameterized models. A populartheory for explaining why SGD works well in practice is that the algorithm hasan implicit regularization that biases its output towards a good solution.Perhaps the theoretically most well understood learning setting for SGD is thatof Stochastic Convex Optimization (SCO), where it is well known that SGD learnsat a rate of $O(1/\sqrt{n})$, where $n$ is the number of samples. In thispaper, we consider the problem of SCO and explore the role of implicitregularization, batch size and multiple epochs for SGD. Our main contributionsare threefold:  (a) We show that for any regularizer, there is an SCO problem for whichRegularized Empirical Risk Minimzation fails to learn. This automatically rulesout any implicit regularization based explanation for the success of SGD.  (b) We provide a separation between SGD and learning via Gradient Descent onempirical loss (GD) in terms of sample complexity. We show that there is an SCOproblem such that GD with any step size and number of iterations can only learnat a suboptimal rate: at least $\widetilde{\Omega}(1/n^{5/12})$.  (c) We present a multi-epoch variant of SGD commonly used in practice. Weprove that this algorithm is at least as good as single pass SGD in the worstcase. However, for certain SCO problems, taking multiple passes over thedataset can significantly outperform single pass SGD.  We extend our results to the general learning setting by showing a problemwhich is learnable for any data distribution, and for this problem, SGD isstrictly better than RERM for any regularization function. We conclude bydiscussing the implications of our results for deep learning, and show aseparation between SGD and ERM for two layer diagonal neural networks.

SGD: The Role of Implicit Regularization, Batch-size and Multiple-epochs