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

Autor:	Mukhopadhyay, Samrat, Mukherjee, Debasmita
Rok vydání:	2025
Předmět:	Computer Science - Machine Learning Mathematics - Optimization and Control
Druh dokumentu:	Working Paper
Popis:	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. Comment: 12 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2501.00799 Zobrazit plný text záznamu View this record from Arxiv