Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned\n Problems

Recently, there has been much interest in studying the convergence rates of\nwithout-replacement SGD, and proving that it is faster than with-replacement\nSGD in the worst case. However, known lower bounds ignore the problem's\ngeometry, including its condition number, whereas the upper bounds explicitly\ndepend on it. Perhaps surprisingly, we prove that when the condition number is\ntaken into account, without-replacement SGD \\emph{does not} significantly\nimprove on with-replacement SGD in terms of worst-case bounds, unless the\nnumber of epochs (passes over the data) is larger than the condition number.\nSince many problems in machine learning and other areas are both\nill-conditioned and involve large datasets, this indicates that\nwithout-replacement does not necessarily improve over with-replacement sampling\nfor realistic iteration budgets. We show this by providing new lower and upper\nbounds which are tight (up to log factors), for quadratic problems with\ncommuting quadratic terms, precisely quantifying the dependence on the problem\nparameters.\n