From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917470588108800 |
|---|---|
| author | Sakaue, Shinsaku Yoshida, Yuichi |
| author_facet | Sakaue, Shinsaku Yoshida, Yuichi |
| contents | 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+\varepsilon)$-approximation guarantee, an average sensitivity bound controlled by a function $φ(\varepsilon)$, and stability with respect to $\varepsilon$, then we can obtain a small-loss regret bound typically of order $\tilde O(φ^{\star}(\mathrm{OPT}_T))$, where $φ^{\star}$ is the concave conjugate of $φ$, $\mathrm{OPT}_T$ is the offline optimum over $T$ rounds, and $\tilde O$ hides polylogarithmic factors in $T$. Our result refines their original $(1+\varepsilon)$-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 $(1\pm\varepsilon)$-cut sparsifiers of submodular hypergraphs, obtaining a small-loss regret bound of $\tilde O(n^3 + n^{3/4}\mathrm{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09457 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model Sakaue, Shinsaku Yoshida, Yuichi Machine Learning Data Structures and Algorithms 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+\varepsilon)$-approximation guarantee, an average sensitivity bound controlled by a function $φ(\varepsilon)$, and stability with respect to $\varepsilon$, then we can obtain a small-loss regret bound typically of order $\tilde O(φ^{\star}(\mathrm{OPT}_T))$, where $φ^{\star}$ is the concave conjugate of $φ$, $\mathrm{OPT}_T$ is the offline optimum over $T$ rounds, and $\tilde O$ hides polylogarithmic factors in $T$. Our result refines their original $(1+\varepsilon)$-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 $(1\pm\varepsilon)$-cut sparsifiers of submodular hypergraphs, obtaining a small-loss regret bound of $\tilde O(n^3 + n^{3/4}\mathrm{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. |
| title | From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.09457 |