RandomShufflingBeatsSGDOnlyAfterMany EpochsonIll-ConditionedProblems

However, known lower bounds ignore the problem's geometry,including itscondition number,whereas theupper bounds explicitly depend on it. Perhaps surprisingly, we prove that when the condition number is taken into account, without-replacement SGDdoesnotsignificantly improveon withreplacement SGD in terms of worst-case bounds, unless the number of epochs (passes overthedata) islargerthanthecondition number.