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.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Cao, X., Li, J., Liang, L., Xu, M., & Zhang, X. (2026). New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression. https://omanscience.com/en/articles/new-lower-bound-and-upper-bounds-on-the-regret-for-online-sparse-linear-regression
MLA 9
Cao, Xiaofeng, et al. "New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression." https://omanscience.com/en/articles/new-lower-bound-and-upper-bounds-on-the-regret-for-online-sparse-linear-regression.
Chicago (author–date)
Cao, Xiaofeng, Junfan Li, Langzhang Liang, Mingwei Xu, and Xiao Zhang. 2026. "New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression." https://omanscience.com/en/articles/new-lower-bound-and-upper-bounds-on-the-regret-for-online-sparse-linear-regression.
Harvard
Cao, X., Li, J., Liang, L., Xu, M. and Zhang, X. (2026) 'New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression', Available at: https://omanscience.com/en/articles/new-lower-bound-and-upper-bounds-on-the-regret-for-online-sparse-linear-regression.
Vancouver
Cao X, Li J, Liang L, Xu M, Zhang X. New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression. https://omanscience.com/en/articles/new-lower-bound-and-upper-bounds-on-the-regret-for-online-sparse-linear-regression
IEEE
X. Cao, J. Li, L. Liang, M. Xu, and X. Zhang, "New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression," https://omanscience.com/en/articles/new-lower-bound-and-upper-bounds-on-the-regret-for-online-sparse-linear-regression.