Sparsity-Based Interpolation of External, Internal and Swap Regret

Zhou Lu, Y. Jennifer Sun, Zhiyu Zhang

Introduction

In the classic framework of Learning from Expert Advice (LEA), a learner sequentially selects actions from a set of $d$ experts, aiming to minimize the cumulative loss relative to a benchmark. This performance metric, known as regret, traditionally takes several forms depending on the strength of the benchmark. External regret compares the learner to the single best expert in hindsight. Internal regret considers a rule that modifies a specific expert's actions. Swap regret, the most general and stringent, compares the learner to a rule that can modify every expert's actions simultaneously.

While swap regret is a powerful metric—notably because algorithms with vanishing swap regret converge to correlated equilibria in games—it comes at a cost. The optimal regret bound for swap regret is $O(\sqrt{dT})$, which is a factor of $\sqrt{d}$ worse than the $O(\sqrt{T \log d})$ bound achievable for external regret. Historically, researchers have relied on specialized algorithms for each regime. This paper addresses the lack of a unified, computationally efficient algorithm that automatically adapts its performance based on the complexity of the modification rule, interpolating gracefully between these regret extremes.

Methodology

The authors propose a unified algorithm that minimizes $\phi$-regret, a generalized metric where $\phi$ represents a modification rule (a mapping from the set of experts to itself). The core innovation lies in how these modification rules are represented and learned.

Haar-Wavelet Matrix Features

Instead of the standard canonical basis for matrices, the authors represent modification rules using a basis derived from Haar wavelets. In signal processing, Haar wavelets are prized for their ability to sparsely represent signals with low local variation. In this context, they provide an inductive bias: if a modification rule treats groups of "similar" experts identically, it will have a sparse representation in the wavelet domain. This allows the algorithm to exploit the underlying structure of the modification rule.

Algorithmic Framework

The algorithm builds upon the standard reduction of $\phi$-regret to external regret on stochastic matrices. The process involves:

  1. Decomposition: Transforming the matrix prediction problem into a series of one-dimensional online linear optimization (OLO) problems, one for each wavelet feature.
  2. Adaptive Oracles: Utilizing "comparator-adaptive" subroutines (variants of Follow the Regularized Leader). These oracles do not require prior knowledge of the magnitude of the optimal modification rule, enabling the learner to automatically exploit sparsity.
  3. Constraint Management: A two-stage constraint wrapper ensures the algorithm outputs valid probability distributions (stochastic matrices) while maintaining adaptive regret guarantees through a novel projection and gradient-processing mechanism.

Key Results

The primary contribution is a single algorithm that achieves an instance-adaptive $\phi$-regret bound:

$$\tilde{O}\left(\min\left\{\sqrt{d - d^{unif}_\phi + 1}, \sqrt{d - d^{self}_\phi}\right\} \cdot \sqrt{T}\right)$$

Here, $d^{unif}_\phi$ measures how many experts are modified identically (Uniformity), and $d^{self}_\phi$ measures how many experts are left unchanged (Degree of self-map). This bound is significant because it recovers known optimal rates for specific cases within a single framework:

  • External Regret: Recovers $O(\sqrt{T \log d})$ when the rule is a constant function.
  • Internal Regret: Recovers $\tilde{O}(\sqrt{T})$ when only a single expert is modified.
  • Swap Regret: Recovers the optimal $\tilde{O}(\sqrt{dT})$ in the worst-case scenario.
  • Quantile Regret: Achieves the optimal $O(\sqrt{T \log \epsilon^{-1}})$ bound for comparing against the top $\epsilon$-fraction of experts.

Crucially, this adaptivity does not come at the expense of speed. The computational complexity remains $O(d^3)$ per round, matching the efficiency of the standard non-adaptive swap-regret algorithm by Blum and Mansour (2007).

Discussion and Future Work

The paper demonstrates that the "simplicity" of a modification rule can be effectively captured through wavelet-based sparsity. However, the effectiveness of this approach is partially dependent on the ordering of experts. While the authors provide a relabeling strategy, a key open challenge is developing methods to automatically learn the optimal permutation of experts during the learning process.

Additionally, the current analysis focuses on the regime where $T \gg d$. Future research could explore merging these multi-resolution analysis techniques with recent breakthroughs that improve $d$-dependence exponentially at the cost of faster growth in $T$. Finally, applying these "ordered" regret bounds to games where experts are embedded in metric spaces remains a promising avenue for practical application.

Summary updated

BibTeX
@inproceedings{lu2025sparsity,
  author = {Zhou Lu and Y. Jennifer Sun and Zhiyu Zhang},
  title = {{Sparsity-Based Interpolation of External, Internal and Swap Regret}},
  booktitle = {Conference on Learning Theory},
  year = {2025},
}
Figure