From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model

arXiv:2602.09457v2 Announce Type: replace-cross Abstract: We study online learning in the random-order model, where the multiset of loss functions is chosen adversarially but revealed in a uniformly random order. By extending the batch-to-online transformation of Dong and Yoshida (2023), we show that if an offline algorithm enjoys a (1+arepsilon)-approximation guarantee, an average sensitivity bound controlled by a function arphi(arepsilon), and stability with respect to arepsilon, then we can obtain a small-loss regret bound typically of order ilde O(arphi^{star}(OPT_T)), where arphi^{star} is the concave conjugate of arphi, OPT_T is the offline optimum over T rounds, and ilde O hides polylogarithmic factors in T. Our result refines their original (1+arepsilon)-approximate regret guarantee and applies to a broad class of problems, including online k-means clustering and online low-rank approximation. We further apply our approach to online submodular function minimization using (1pmarepsilon)-cut sparsifiers of submodular hypergraphs, obtaining a small-loss regret bound of ilde O(n^3 + n^{3/4}OPT_T^{3/4}), where n is the ground-set size; we also demonstrate its applicability to online ell_1 regression. Our work sheds light on the power of sparsification and related algorithmic techniques in achieving small-loss regret bounds in the random-order model, without requiring structural assumptions on loss functions, such as linearity or smoothness.

Source: arXiv cs.LG | 2026-05-11