Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
Abstract
In high-dimensional online prediction, sparse comparators motivate regret bounds that depend on sparsity rather than ambient dimension. Feature priming seeks such adaptation by reweighting features using past data and refitting a minimum-norm predictor. At COLT 2023, Warmuth and Amid posed the open problem of whether the univariate, Pearson, or multivariate priming rules admit competitive online regret guarantees. Under the natural past-only Moore--Penrose protocol, we establish sparse-regret lower bounds that refute the corresponding sparse-logarithmic guarantee. The key obstruction is cheap nuisance interpolation, which permits exact interpolation of the history while assigning insufficient weight to the truly predictive coordinate. An exact target-mass identity and a two-sign argument convert this obstruction into clipped prediction loss. Hadamard constructions yield Ω(min{T,√d}) clipped regret for each of the three unit-power rules against a zero-loss one-sparse comparator. For every fixed power α≥1, one shared paired construction further yields linear regret simultaneously for all three powered rules and selectors among them in sufficiently high dimension. A rank upper bound is tight for powered univariate priming, even with Euclidean-unit inputs, and for unit-power Pearson priming with coordinatewise bounded inputs and target-preserving totalization. A separate algebraic construction gives Ω(min{T,d1/4}) regret for unit-power multivariate priming under Euclidean-unit inputs. The univariate lower bound persists under any nonnegative second-stage ridge schedule, while a paired ridge construction yields linear lower bounds for all three powered rules. Exploratory diagnostics on frozen language-model activations are consistent with the same qualitative mechanism. The exact multivariate frontier remains open.
Related
- Transfer Learning with Heterogeneous Feature Spaces in Linear Regression
- Online Change-Point Detection in Linear Regression with Autoregressive Errors via Streaming Variational Bayes
- Online Bayesian Model Averaging with Joint Uncertainty Quantification for Models and Regression Coefficients in Binary Regression
- Finite-Sample Distribution Theory and Efficient Large-Scale Inference for Online Quantile Regression
- Benign Overfitting Property of the Minimum ℓq -norm Interpolant Estimator in Regression Problem via Feature Space Decomposition
BibTeX
@misc{xu2026feature,
title = {{Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates}},
author = {Huibo Xu and Shi Fu and Qixin Zhang and Dacheng Tao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.17573},
eprint = {2608.17573},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.17573},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
AU - Huibo Xu
AU - Shi Fu
AU - Qixin Zhang
AU - Dacheng Tao
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2608.17573
UR - https://arxiv.org/abs/2608.17573
AB - In high-dimensional online prediction, sparse comparators motivate regret bounds that depend on sparsity rather than ambient dimension. Feature priming seeks such adaptation by reweighting features using past data and refitting a minimum-norm predictor. At COLT 2023, Warmuth and Amid posed the open problem of whether the univariate, Pearson, or multivariate priming rules admit competitive online regret guarantees. Under the natural past-only Moore--Penrose protocol, we establish sparse-regret lower bounds that refute the corresponding sparse-logarithmic guarantee. The key obstruction is cheap nuisance interpolation, which permits exact interpolation of the history while assigning insufficient weight to the truly predictive coordinate. An exact target-mass identity and a two-sign argument convert this obstruction into clipped prediction loss. Hadamard constructions yield Ω(min{T,√d}) clipped regret for each of the three unit-power rules against a zero-loss one-sparse comparator. For every fixed power α≥1, one shared paired construction further yields linear regret simultaneously for all three powered rules and selectors among them in sufficiently high dimension. A rank upper bound is tight for powered univariate priming, even with Euclidean-unit inputs, and for unit-power Pearson priming with coordinatewise bounded inputs and target-preserving totalization. A separate algebraic construction gives Ω(min{T,d^1/4}) regret for unit-power multivariate priming under Euclidean-unit inputs. The univariate lower bound persists under any nonnegative second-stage ridge schedule, while a paired ridge construction yields linear lower bounds for all three powered rules. Exploratory diagnostics on frozen language-model activations are consistent with the same qualitative mechanism. The exact multivariate frontier remains open.
ER -