Metraipolis › archive › dc_ad3e33ab6ebf

New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression — arXiv:2610.11551

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.11551
License (as archived)
CC0-1.0
Archived
2026-10-09T06:23:22.724Z
SHA-256 of the archived text
7b8ee373138df3ec7e2cdd2005416c6132774db6f29f0d4a66f6d3f71a1d3bc7
Stable URL of this page
https://metraipolis.com/documento/dc_ad3e33ab6ebf

How to cite

New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression — arXiv:2610.11551 — arXiv (en), https://arxiv.org/abs/2610.11551 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ad3e33ab6ebf (Metraipolis archive dc_ad3e33ab6ebf, sha256 7b8ee373138df3ec7e2cdd2005416c6132774db6f29f0d4a66f6d3f71a1d3bc7)
BibTeX
@misc{dcad3e33ab6ebf,
  title = {New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression — arXiv:2610.11551},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.11551},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ad3e33ab6ebf; sha256 7b8ee373138df3ec7e2cdd2005416c6132774db6f29f0d4a66f6d3f71a1d3bc7},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.11551. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2610.11551 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:50:31.514Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).