Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and a Tight Univariate Rate

• URL: http://arxiv.org/abs/2608.17573v1
• Date: Tue, 18 Aug 2026 09:32:03 GMT
• Title: Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and a Tight Univariate Rate
• Abstract summary: In high-dimensional online prediction, the best predictor may depend on only a few features, so regret should scale with sparsity rather than the ambient dimension.<n>Warmuth and Amid asked at COLT 2023 whether any of three such rules admits a competitive online regret guarantee.<n>Our analysis identifies a common obstruction: cheap nuisance causes the refit to underweight the truly predictive coordinate.
• Score: 47.36630149538994
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: In high-dimensional online prediction, the best predictor may depend on only a few features, so regret should scale with sparsity rather than the ambient dimension. Feature priming pursues this goal by estimating feature weights from past data and refitting a minimum-norm predictor on the rescaled design. Warmuth and Amid asked at COLT 2023 whether any of three such rules admits a competitive online regret guarantee. Using the natural Moore--Penrose protocol based only on past data, we give a negative answer to the sparse-logarithmic form of this COLT open problem. Our analysis identifies a common obstruction: cheap nuisance interpolation causes the refit to underweight the truly predictive coordinate. An exact target-mass identity and a two-sign argument turn this effect into clipped prediction loss. Hadamard constructions force $Ω(\min\{T,\sqrt{d}\})$ regret for all three rules against a zero-loss one-sparse comparator, with extensions to fixed prime powers and selectors among the rules. Conversely, regret is controlled by data rank, and a Euclidean-normalized triangular construction matches this dependence for powered univariate priming, even under nonnegative second-stage ridge regularization; a paired ridge construction also covers all three powered rules. Exploratory diagnostics on frozen language-model activations exhibit the same relation among nuisance interpolation, target weight, and loss. The exact multivariate and Pearson frontiers remain open.

Related papers

• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Geometry-Calibrated Closed-Form Shrinkage for SAR Despeckling [0.7782912896579166]
  Synthetic aperture radar (SAR) despeckling is an inverse-recovery problem in which multiplicative non-Gaussian noise must be suppressed.<n>We revisit a nonlocal sparse estimator that applies a log--Yeo--Johnson transformation, stacks similar patches into groups, codes each group on its own left singular basis, and shrinks the resulting coefficients.
  arXiv  Detail & Related papers  (2026-08-15T04:28:27Z)
• The Quadrilateral Loss: Additivity as a Measurable Behavior of Dense Neural Networks [0.0]
  We introduce the quadrilateral loss, a differentiable penalty that treats additivity as a measurable behavior instead.<n>We compare routes to exact additivity, spanning structural masks, behavioral penalties, weight decay, backfitting, the shared-section model, and bagged boosted stumps.
  arXiv  Detail & Related papers  (2026-07-22T14:23:37Z)
• The Matching Principle: A Geometric Theory of Loss Functions for Nuisance-Robust Representation Learning [0.5854803320592717]
  We prove optimality in a linear-Gaussian model (Thm. A), necessity of range coverage for any quadratic penalty that zeros deployment drift (Thm. G)<n>Thirteen blocks (ML through Qwen2.5-7B) test matched vs isotropic vs wrong-direction penalties on geometry and deployment drift.<n>We claim a falsifiable design recipe: estimate Sigma_task, match Sigma', run the controls, report task and geometry separately.
  arXiv  Detail & Related papers  (2026-05-21T17:53:28Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs [52.709361620508595]
  ListOPD brings a student to in-domain with an 8B-SFT baseline at one-fifth the parameters.<n>On Amazon Fashion, three pre-registered tests--a fine-grid cliff interval test, and a small-clip cross-prediction--fall within their locked prediction windows--with the small-clip value matching the closed-form prediction below grid resolution.
  arXiv  Detail & Related papers  (2026-05-09T06:48:00Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
  We revisit the sequential variants of linear regression with the squared loss, classification problems with hinge loss, and logistic regression.<n>Our key tools are based on the exponential weights algorithm with carefully chosen transductive priors.
  arXiv  Detail & Related papers  (2024-10-29T00:01:04Z)
• Error Reduction from Stacked Regressions [12.657895453939298]
  Stacking regressions is an ensemble technique that forms linear combinations of different regression estimators to enhance predictive accuracy. In this paper, we learn these weights analogously by minimizing a regularized version of the empirical risk subject to a nonnegativity constraint. Thanks to an adaptive shrinkage effect, the resulting stacked estimator has strictly smaller population risk than best single estimator among them.
  arXiv  Detail & Related papers  (2023-09-18T15:42:12Z)
• Consistent Online Gaussian Process Regression Without the Sample Complexity Bottleneck [14.309243378538012]
  We propose an online compression scheme that fixes an error neighborhood with respect to the Hellinger metric centered at the current posterior. For constant error radius, POG converges to a neighborhood of the population posterior (Theorem 1(ii))but with finite memory at-worst determined by the metric entropy of the feature space.
  arXiv  Detail & Related papers  (2020-04-23T11:52:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.