提出一种在线稀疏线性逼近新方法，可高效应对动态数据预测挑战。
Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation
- 设计近似稀疏领袖追踪策略，实现在线稀疏逼近
- 理论证明静态后悔上界为亚线性，可达对数或平方根级
- 适合医疗试验、资源分配等需实时决策的场景
我们研究在线稀疏线性逼近问题，即在给定测量矩阵列的线性组合中，逐时预测最优稀疏近似。此类问题广泛存在于医疗试验、网页缓存和资源分配等领域。由于离线恢复的固有难度，该在线问题极具挑战性。本文提出一种名为跟随近似稀疏领袖（Follow-The-Approximate-Sparse-Leader）的高效在线元策略。通过详尽的理论分析，在测量序列满足一定假设条件下，证明该策略的静态后悔具有数据相关的亚线性上界，范围从对数到平方根级。数值模拟验证了理论结果，并展示了所提策略的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。