Sparsity-Based Interpolation of External, Internal and Swap Regret
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913899250450432 |
|---|---|
| author | Lu, Zhou Sun, Y. Jennifer Zhang, Zhiyu |
| author_facet | Lu, Zhou Sun, Y. Jennifer Zhang, Zhiyu |
| contents | Focusing on the expert problem in online learning, this paper studies the interpolation of several performance metrics via $ϕ$-regret minimization, which measures the total loss of an algorithm by its regret with respect to an arbitrary action modification rule $ϕ$. With $d$ experts and $T\gg d$ rounds in total, we present a single algorithm achieving the instance-adaptive $ϕ$-regret bound \begin{equation*} \tilde O\left(\min\left\{\sqrt{d-d^{\mathrm{unif}}_ϕ+1},\sqrt{d-d^{\mathrm{self}}_ϕ}\right\}\cdot\sqrt{T}\right), \end{equation*} where $d^{\mathrm{unif}}_ϕ$ is the maximum amount of experts modified identically by $ϕ$, and $d^{\mathrm{self}}_ϕ$ is the amount of experts that $ϕ$ trivially modifies to themselves. By recovering the optimal $O(\sqrt{T\log d})$ external regret bound when $d^{\mathrm{unif}}_ϕ=d$, the standard $\tilde O(\sqrt{T})$ internal regret bound when $d^{\mathrm{self}}_ϕ=d-1$ and the optimal $\tilde O(\sqrt{dT})$ swap regret bound in the worst case, we improve upon existing algorithms in the intermediate regimes. In addition, the computational complexity of our algorithm matches that of the standard swap-regret minimization algorithm due to (Blum and Mansour, 2007).
Technically, building on the well-known reduction from $ϕ$-regret minimization to external regret minimization on stochastic matrices, our main idea is to further convert the latter to online linear regression using Haar-wavelet-inspired matrix features. Then, by associating the complexity of each $ϕ$ instance with its sparsity under the feature representation, we apply techniques from comparator-adaptive online learning to exploit the sparsity in this regression subroutine. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04543 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sparsity-Based Interpolation of External, Internal and Swap Regret Lu, Zhou Sun, Y. Jennifer Zhang, Zhiyu Machine Learning Focusing on the expert problem in online learning, this paper studies the interpolation of several performance metrics via $ϕ$-regret minimization, which measures the total loss of an algorithm by its regret with respect to an arbitrary action modification rule $ϕ$. With $d$ experts and $T\gg d$ rounds in total, we present a single algorithm achieving the instance-adaptive $ϕ$-regret bound \begin{equation*} \tilde O\left(\min\left\{\sqrt{d-d^{\mathrm{unif}}_ϕ+1},\sqrt{d-d^{\mathrm{self}}_ϕ}\right\}\cdot\sqrt{T}\right), \end{equation*} where $d^{\mathrm{unif}}_ϕ$ is the maximum amount of experts modified identically by $ϕ$, and $d^{\mathrm{self}}_ϕ$ is the amount of experts that $ϕ$ trivially modifies to themselves. By recovering the optimal $O(\sqrt{T\log d})$ external regret bound when $d^{\mathrm{unif}}_ϕ=d$, the standard $\tilde O(\sqrt{T})$ internal regret bound when $d^{\mathrm{self}}_ϕ=d-1$ and the optimal $\tilde O(\sqrt{dT})$ swap regret bound in the worst case, we improve upon existing algorithms in the intermediate regimes. In addition, the computational complexity of our algorithm matches that of the standard swap-regret minimization algorithm due to (Blum and Mansour, 2007). Technically, building on the well-known reduction from $ϕ$-regret minimization to external regret minimization on stochastic matrices, our main idea is to further convert the latter to online linear regression using Haar-wavelet-inspired matrix features. Then, by associating the complexity of each $ϕ$ instance with its sparsity under the feature representation, we apply techniques from comparator-adaptive online learning to exploit the sparsity in this regression subroutine. |
| title | Sparsity-Based Interpolation of External, Internal and Swap Regret |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.04543 |