# Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation

arXiv: https://arxiv.org/abs/2501.00799 · HTML: https://mlsanity.com/paper/2501.00799/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 31 references that are in the map.
- First posted on arXiv 1 Jan 2025.

## Builds on (most cited first, 8 of 8)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [An Online Convex Optimization Approach to Dynamic Network Resource Allocation](https://mlsanity.com/paper/1701.03974/) (2017)
- [Online Caching with Optimal Switching Regret](https://mlsanity.com/paper/2101.07043/) (2021)
- [Adaptive Feature Selection: Computationally Efficient Online Sparse Linear Regression under RIP](https://mlsanity.com/paper/1706.04690/) (2017)
- [ktexttt-experts -- Online Policies and Fundamental Limits](https://mlsanity.com/paper/2110.07881/) (2021)
- [Online Sparse Linear Regression](https://mlsanity.com/paper/1603.02250/) (2016)
- [Centralized and distributed online learning for sparse time-varying optimization](https://mlsanity.com/paper/2001.11939/) (2020)

## Abstract (arXiv)

We consider the problem of textitonline 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.