Timezone: »

 
Poster
Closing the convergence gap of SGD without replacement
Shashank Rajput · Anant Gupta · Dimitris Papailiopoulos

Tue Jul 14 08:00 AM -- 08:45 AM & Tue Jul 14 09:00 PM -- 09:45 PM (PDT) @ Virtual
in Poster Session 2 »
Stochastic gradient descent without replacement sampling is widely used in practice for model training. However, the vast majority of SGD analyses assumes data is sampled with replacement, and when the function minimized is strongly convex, an $\mathcal{O}\left(\frac{1}{T}\right)$ rate can be established when SGD is run for $T$ iterations. A recent line of breakthrough works on SGD without replacement (SGDo) established an $\mathcal{O}\left(\frac{n}{T^2}\right)$ convergence rate when the function minimized is strongly convex and is a sum of $n$ smooth functions, and an $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^3}{T^3}\right)$ rate for sums of quadratics. On the other hand, the tightest known lower bound postulates an $\Omega\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ rate, leaving open the possibility of better SGDo convergence rates in the general case. In this paper, we close this gap and show that SGD without replacement achieves a rate of $\mathcal{O}\left(\frac{1}{T^2}+\frac{n^2}{T^3}\right)$ when the sum of the functions is a quadratic, and offer a new lower bound of $\Omega\left(\frac{n}{T^2}\right)$ for strongly convex functions that are sums of smooth functions.
Keywords: Convex Optimization · Information Theory and Estimation · Large Scale Learning and Big Data · Optimization - Convex
[ Slides] 

Author Information

Shashank Rajput (University of Wisconsin - Madison)
Shashank Rajput

I am a 5th year graduate student in the CS department at UW-Madison. I am advised by Prof. Dimitris Papailiopoulos. I am interested in sparsity in Deep Learning and Distributed Optimization.

Anant Gupta (University of Wisconsin Madison)
Dimitris Papailiopoulos (University of Wisconsin-Madison)

More from the Same Authors