# Online Linear Regression with Paid Stochastic Features

arXiv: https://arxiv.org/abs/2511.08073 · HTML: https://mlsanity.com/paper/2511.08073/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 37 references that are in the map.
- First posted on arXiv 11 Nov 2025.

## Builds on (most cited first, 13 of 13)

- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Locally Differentially Private (Contextual) Bandits Learning](https://mlsanity.com/paper/2006.00701/) (2020)
- [Local Differential Privacy and Its Applications: A Comprehensive Survey](https://mlsanity.com/paper/2008.03686/) (2020)
- [Differential Privacy: An Economic Method for Choosing Epsilon](https://mlsanity.com/paper/1402.3329/) (2014)
- [On Robustness of Principal Component Regression](https://mlsanity.com/paper/1902.10920/) (2019)
- [Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms](https://mlsanity.com/paper/2201.03968/) (2022)
- [Differentially Private Empirical Risk Minimization with Input Perturbation](https://mlsanity.com/paper/1710.07425/) (2017)
- [Causal Inference with Corrupted Data: Measurement Error, Missing Values, Discretization, and Differential Privacy](https://mlsanity.com/paper/2107.02780/) (2021)
- [Improved Algorithms for Contextual Dynamic Pricing](https://mlsanity.com/paper/2406.11316/) (2024)
- [Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individuals](https://mlsanity.com/paper/1401.4092/) (2014)
- [Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles](https://mlsanity.com/paper/1703.01347/) (2017)
- [The Value of Privacy: Strategic Data Subjects, Incentive Mechanisms and Fundamental Limits](https://mlsanity.com/paper/1603.06870/) (2016)
- [Trading-Off Payments and Accuracy in Online Classification with Paid Stochastic Experts](https://mlsanity.com/paper/2307.00836/) (2023)

## Built on by (most cited first, 1 of 1)

- [Beyond Second-Order Information: Paid Logistic Regression with Noisy Features](https://mlsanity.com/paper/2610.12919/) (2026)

## Abstract (arXiv)

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. When the mapping between payments and noise covariance is known, we prove that the rate √T is optimal for regret if logarithmic factors are ignored. When the noise covariance is unknown, we show that the optimal regret rate becomes of order T2/3 (ignoring log factors). Our analysis leverages matrix martingale concentration, showing that the empirical loss uniformly converges to the expected one for all payments and linear predictors.