Sparsity-Based Interpolation of External, Internal and Swap Regret

Abstract

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≫ d rounds in total, we present a single algorithm achieving the instance-adaptive ϕ-regret bound Õ{min{√(d-d^unif_ϕ+1),√(d-d^self_ϕ)}·√(T)}, where d^unif_ϕ is the maximum amount of experts modified identically by ϕ, and d^self_ϕ is the amount of experts that ϕ trivially modifies to themselves. By recovering the optimal O(√(Tlog d)) external regret bound when d^unif_ϕ=d, the standard Õ(√(T)) internal regret bound when d^self_ϕ=d-1 and the optimal Õ(√(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.