pipette
ENEnglish

New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression

Xiaofeng Cao, Junfan Li, Langzhang Liang, Mingwei Xu, Xiao Zhang

Preprint

En palabras de los autores

We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only out of attributes per instance for prediction and 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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: This work was accepted by IJTCS-FAW 2026