arXiv：cs.LG· Xiaofeng Cao, Junfan Li, Langzhang Liang, Mingwei Xu, Xiao Zhang·· 4 小时前
在线稀疏线性回归（OSLR）的最小最大 regret 首个下界与更优上界
New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression
AI 导读
针对每实例仅可访问 d 个属性中 b 个、预测后再访问 b0 个额外属性的在线稀疏线性回归（OSLR），研究者给出了首个 minimax regret 下界，并在无正则性假设下设计了上界更优的算法。
正文
Abstract:We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only $b$ out of $d$ attributes per instance for prediction and $b_0\geq 0$ additional attributes after prediction, which was proved to be NP-hard. Previous work focused on designing computationally efficient algorithms under regularity assumptions, but did not characterize its information theoretic complexity. In this work, we give the first lower bound on the minimax regret of OSLR and design algorithms with better upper bounds without regularity assumptions. We characterize how minimax regret scales with problem-dependent parameters, capturing the information theoretic complexity of OSLR.
| Comments: | This work was accepted by IJTCS-FAW 2026 |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.11551 [cs.LG] |
| (or arXiv:2610.11551v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.11551 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Junfan Li [view email]
[v1]
Thu, 8 Oct 2026 09:15:01 UTC (45 KB)
来源：arXiv：cs.LG · arxiv.org