Online Linear Regression with Paid Stochastic Features

AI summary

Overview

Research area: Online learning theory and statistical learning, specifically online linear regression with costly, noise-reducible feature acquisition (an intersection of regret minimization, errors-in-variables statistics, and local differential privacy).

Technical level: Advanced. The paper relies on matrix martingale concentration inequalities, positive semi-definite ordering of covariance matrices, minimax lower bounds, and bandit-style optimism. A reader should be comfortable with regret analysis and linear algebra.

Scope: This paper characterizes the optimal regret rates for online linear regression when a learner can pay to reduce noise in the observed features, proving an O~(√T) rate when the payment-to-noise-covariance mapping is known and an O~(T^{2/3}) rate when it is not, with matching lower bounds in both cases.

What This Paper Is About

In standard online linear regression, a learner sees feature vectors and predicts outputs, but the features are usually assumed to be clean. In reality, features are often noisy — measurements have error, user data is only sampled, or noise is deliberately injected to protect privacy. This paper studies a setting where the learner can pay a cost to reduce that noise: a higher payment yields a smaller noise covariance. The goal is to choose both a payment level and a linear predictor at every round so as to minimize a combined objective of prediction error plus payment, measured by regret against the best fixed linear predictor in hindsight.

Key Contributions

1. A loss estimator that transfers information across payment levels (known-covariance setting). When the noise covariance profile Σ_n(c) is known for every payment c, the authors construct an empirical loss that adds a correction term ν^⊤(Σ_n(c) − Σ_n(c_s))ν, allowing samples collected at one payment to estimate the loss at any other payment. They prove this estimator uniformly converges to the true expected loss over all payments in [0,1] and all predictors with ||ν|| ≤ S.

2. Order-optimal regret with known noise covariances. Using this estimator, Algorithm 1 greedily picks the best payment on a discretized grid (K = ⌈λT⌉) and the best corresponding linear predictor, achieving regret Õ(S²(R²d + S²)√T + λ). A matching lower bound of √T/240 on a one-dimensional instance shows this is optimal up to logarithmic factors.

3. Order-optimal regret with unknown noise covariances. When the noise covariance profile is unknown, information sharing is impossible, so the authors restrict payments to a grid, add an optimistic (UCB-like) loss estimator that encourages under-explored payments, and prove a regret bound of Õ(T^{2/3}), again matched by a lower bound up to log factors.

4. A lower-bound framework connecting to Lipschitz bandits. The unknown-covariance lower bound is built by designing noise covariance profiles that mimic hard instances in Lipschitz bandits, and the known-covariance lower bound is reduced to a two-armed bandit instance. The paper also generalizes the one-dimensional lower bound to Ω(√(Td)) in d dimensions.

Main Findings

• Known covariances give √T and no exploration is needed. Because only one term in the loss depends on the noise covariance, the correction term lets the algorithm exploit all past samples simultaneously. This removes the need for explicit payment exploration entirely; regret is Õ(S²(R²d + S²)√T + λ) with δ = 1/T and K = ⌈λT⌉.

• The paid-feature rate is exponentially worse than the noise-free rate. The paper notes that the optimal rate Θ(ln T) for noise-free online linear regression is not achievable here: even in one dimension, the authors show 𝔼[R(T)] ≥ √T/240. They conjecture this stems from discontinuity in the noise variance.

• Unknown covariances make the problem harder: O~(T^{2/3}). Without knowing Σ_n(c), the learner can only estimate the loss at a payment using samples taken at that exact payment (L̂^uc_t(c,ν) = Σ_s (……) 𝟙{c_s = c}), forcing a trade-off between exploration and exploitation.

• Uniform concentration holds across all payments and predictors. With probability at least 1 − 3δ, |L̂^kc_t(c,ν) − t·ℓ(c,ν)| ≤ 9S²√(8tβ_t² ln(3dt(t+1)/δ)), where β_t = R²(d + 2√(d ln(3t(t+1)/δ)) + 2 ln(3t(t+1)/δ)) + S²(1 + 2√(ln(3t(t+1)/δ)/d)) = Õ(R²d + S²). The same event guarantees the regularized loss is strictly convex in ν.

• The loss is only one-sided Lipschitz. Claim 2 shows ℓ*(c₂) ≤ ℓ*(c₁) + λ(c₂ − c₁) for 0 ≤ c₁ ≤ c₂ ≤ 1. Increasing the payment always reduces prediction error, so loss can only rise through the λc term. This near-Lipschitzness justifies discretizing payments onto a finite grid.

• A closed-form characterization of the optimal predictor. Claim 1 gives ℓ(c,ν) = ν^⊤Σ_x̂(c)ν − 2ν^⊤Σ_xθ* + θ*^⊤Σ_xθ* + λc, with ν̄(c) = (Σ_x̂(c))^{-1}Σ_xθ*. Notably, the optimal predictor is not the true parameter θ*, but depends on the noise level.

• Adding output noise is free. Remark 3 notes that the concentration bound extends to noisy regression outputs y_t = x_t^⊤θ* + η_t with conditionally zero-mean subgaussian noise η_t, without changing the algorithm or the rate.

• Computational tractability is preserved. Although the correction term can make the loss nonconvex, the regularization γ_t||ν||² with γ_t = 2√(8tβ_t² ln(3dt(t+1)/δ)) yields a strictly convex objective over a ball. The unregularized minimization is also solvable as a trust-region subproblem even when nonconvex.

Methodology in Plain English

The authors set up an online game over T rounds. At each round the environment draws a true feature vector x_t from an unknown distribution and an output y_t = x_t^⊤θ*, and the learner pays a cost c_t ∈ [0,1] to observe a noisy version x_t + n_t(c_t). The learner then predicts a linear function of the noisy features and suffers squared error plus λc_t. Performance is measured as regret against the best linear predictor for the best payment level.

The key technical trick for the known-covariance case is a "shift" term: since the learner knows how much noise covariance changes between payment levels, it can take a sample measured at payment c_s and add the difference Σ_n(c) − Σ_n(c_s) to pretend it was measured at payment c. This correction is unbiased, so all past data becomes usable at every payment simultaneously — eliminating exploration. The authors then prove that the resulting empirical loss approximates the true loss uniformly, using martingale matrix concentration (adapting Tropp's 2012 results) applied to the empirical covariance of subgaussian vectors. The algorithm simply minimizes this empirical loss over a grid and picks the cheapest-looking option.

For the unknown-covariance case, the correction term is unavailable, so the algorithm first plays each grid payment once to obtain initial estimates, then selects payments via an optimistic estimator that favors less-played levels — inspired by UCB algorithms (Auer 2002). Tuning the grid size carefully sets the balance between discretization error and estimation error, yielding T^{2/3}. Both lower bounds are proven by constructing adversarial instances: the known-covariance bound reduces to a two-armed bandit with a noise variance fixed at N(0,1) for c < 1/2 and zero for c ≥ 1/2, while the unknown-covariance bound uses covariance profiles that imitate hard Lipschitz bandit instances.

Why This Matters

Impact on research: The paper opens a new axis in online regression — treating feature noise as a controllable, purchasable resource rather than a fixed nuisance. It shows that the classical Θ(ln T) rate collapses to √T when payments interact with non-smooth noise profiles, and it gives the first order-optimal rates for this setting. The information-sharing estimator is a general technique that could transfer to other online problems where a parameter controls noise structure. This also extends beyond the closest prior work (Van Der Hoeven et al. 2023), which covered only binary classification with independent per-coordinate noise and a d²(ln T)√T bound, whereas this paper handles correlated noise in regression.

Real-world applications:

• Laboratory experiments where renting better equipment or hiring more experienced staff reduces measurement error but costs money.
• Data collection pipelines where extending measurement duration or averaging more raw samples lowers noise at a time cost.
• Local differential privacy, where paying users (directly or via free services) compensates them for reduced privacy protection — a setting where the noise mechanism, and thus the covariance, is often known in advance.
• Crowdsourced or survey-based data acquisition, where paying more per respondent yields higher-quality responses.

Industry relevance: Any production system that must decide how much to spend on data quality per prediction — recommendation systems buying cleaner user signals, industrial sensor networks deciding sampling precision, or analytics platforms negotiating data-sharing agreements — faces exactly this accuracy-versus-cost trade-off. The paper's key practical message is that knowing the payment-to-noise relationship is enormously valuable: it eliminates exploration overhead and improves the regret rate from T^{2/3} to √T.

Future Directions

1. Smooth noise covariance profiles. The authors hypothesize that the √T rate results from discontinuity in the noise variance and that for sufficiently smooth noise, an O(ln T) rate might be achievable. They explicitly leave this for future work.

2. Nonlinear predictors. Remark 1 notes that a nonlinear optimal predictor would require computing 𝔼[x_t | x̂_t]^⊤θ*, which depends on the full feature and noise distributions, renders estimation extremely complicated, and typically requires intractable computation.

3. Lipschitz rather than monotone covariances. Remark 2 observes that monotonicity and Lipschitzness of noise covariance are incomparable assumptions; all positive results would still hold under Lipschitzness provided Σ_x̂(c) ≻ 0, suggesting a broader applicability worth exploring.

4. Multidimensional unknown-covariance lower bounds. The known-covariance lower bound is extended to Ω(√(Td)) in d dimensions, but the paper does not report an analogous d-dimensional generalization for the T^{2/3} unknown-covariance case.

5. Correlated noise over time. The paper notes that unknown covariances may arise when noise reduction comes from extended data collection periods, "especially if the noise is temporally correlated" — a scenario the current i.i.d.-noise analysis does not cover.

Target Audience

This paper is for researchers in online learning, regret minimization, and statistical learning theory who are interested in extensions of online linear regression beyond clean feature assumptions. It will also interest privacy researchers working on incentive-compatible data collection and local differential privacy, since the payment model directly maps onto compensating users for privacy loss. Practitioners designing cost-aware data acquisition systems may benefit from the high-level insight that known noise profiles eliminate exploration, though the full analysis requires a strong theoretical background. Readers should be comfortable with subgaussian concentration, matrix analysis, and bandit lower-bound techniques.

Authors’ abstract

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 $\sqrt{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 $T^{2/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.