New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression
📅
👥 5 authors
arXiv:2610.11551v1
Authors
Xiaofeng CaoJunfan LiLangzhang LiangMingwei XuXiao Zhang
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.
Paper Information
- arXiv ID:
- 2610.11551v1
- Published: