SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2106.06880 · 2021

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

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

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

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2106.06880")
get_code_for_paper("2106.06880")
have("2106.06880")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2106.06880.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2106.06880.svg)](https://syntology.ai/paper/2106.06880)

Connect an agent — have() is free.