Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation
This addresses online prediction challenges in applications like medical trials and web caching, but it is incremental as it builds on existing online learning frameworks.
The paper tackles the problem of online sparse linear approximation by proposing the Follow-The-Approximate-Sparse-Leader policy, which achieves a data-dependent sublinear static regret bound ranging from logarithmic to square-root under certain assumptions.
We consider the problem of \textit{online sparse linear approximation}, where one predicts the best sparse approximation of a sequence of measurements in terms of linear combination of columns of a given measurement matrix. Such online prediction problems are ubiquitous, ranging from medical trials to web caching to resource allocation. The inherent difficulty of offline recovery also makes the online problem challenging. In this letter, we propose Follow-The-Approximate-Sparse-Leader, an efficient online meta-policy to address this online problem. Through a detailed theoretical analysis, we prove that under certain assumptions on the measurement sequence, the proposed policy enjoys a data-dependent sublinear upper bound on the static regret, which can range from logarithmic to square-root. Numerical simulations are performed to corroborate the theoretical findings and demonstrate the efficacy of the proposed online policy.