Optimal Rates for Random Order Online Optimization
This work addresses a theoretical challenge in online optimization for machine learning, offering incremental improvements over prior results.
The paper tackles the problem of online convex optimization in the random order model, where adversarial loss functions are presented in random order, achieving optimal bounds by removing dimension dependence and improving scaling with the strong convexity parameter.
We study online convex optimization in the random order model, recently proposed by \citet{garber2020online}, where the loss functions may be chosen by an adversary, but are then presented to the online algorithm in a uniformly random order. Focusing on the scenario where the cumulative loss function is (strongly) convex, yet individual loss functions are smooth but might be non-convex, we give algorithms that achieve the optimal bounds and significantly outperform the results of \citet{garber2020online}, completely removing the dimension dependence and improving their scaling with respect to the strong convexity parameter. Our analysis relies on novel connections between algorithmic stability and generalization for sampling without-replacement analogous to those studied in the with-replacement i.i.d.~setting, as well as on a refined average stability analysis of stochastic gradient descent.