EUVIMEDEUVIMED entdecken
Crossref

Online Linear Regression with Paid Stochastic Features

Nadav Merlis, Kyoungseok Jang, Nicolò Cesa-Bianchi

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (29) · 24370-24378

DOI: 10.1609/aaai.v40i29.39618 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Nadav Merlis und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study an online linear regression setting in which the observed feature vectors are corrupted by noise and the learner can pay to reduce the noise level. In practice, this may happen for several reasons: for example, because features can be measured more accurately using more expensive equipment, or because data providers can be incentivized to release less private features. Assuming feature vectors are drawn i.i.d. from a fixed but unknown distribution, we measure the learner's regret against the linear predictor minimizing a notion of loss that combines the prediction error and payment. We first study the case in which the mapping between payments and noise covariance is known and prove order-optimal regret bounds in the interaction length (up to log-factors). We then derive order-optimal bounds also when the noise covariance is unknown and prove that the regret rate is worse than the case of known covariances. Our analysis leverages matrix martingale concentration, showing that the empirical loss uniformly converges to the expected one for all payments and linear predictors.

Zitieren

APA

Merlis, N., Jang, K., & Cesa-Bianchi, N. (2026). Online Linear Regression with Paid Stochastic Features. Proceedings of the AAAI Conference on Artificial Intelligence, 40(29), 24370-24378. https://doi.org/10.1609/aaai.v40i29.39618

Vancouver

Merlis N, Jang K, Cesa-Bianchi N. Online Linear Regression with Paid Stochastic Features. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(29):24370-24378. doi:10.1609/aaai.v40i29.39618

BibTeX
@article{Merlis2026,
  author = {Merlis, Nadav and Jang, Kyoungseok and Cesa-Bianchi, Nicolò},
  title = {Online Linear Regression with Paid Stochastic Features},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {29},
  pages = {24370--24378},
  doi = {10.1609/aaai.v40i29.39618}
}
Kostenlos starten →