Timezone: »

 
Poster
Optimal Rates for Random Order Online Optimization
Uri Sherman · Tomer Koren · Yishay Mansour

Thu Dec 09 08:30 AM -- 10:00 AM (PST) @
in Poster Session 6 »

We study online convex optimization in the random order model, recently proposed by Garber et al. (2020), 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 Garber et al. (2020), completely removing the dimension dependence and improve 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.

Keywords: Optimization · Online Learning

Author Information

Uri Sherman (Tel Aviv University)
Tomer Koren (Tel Aviv University & Google)
Yishay Mansour (Tel Aviv University & Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors