Search papers, labs, and topics across Lattice.
This paper investigates the effectiveness of feature priming in high-dimensional online linear regression, revealing that traditional methods may fail to achieve competitive regret guarantees due to nuisance interpolation that undermines the identification of truly predictive features. The authors provide a negative answer to a COLT 2023 open problem by demonstrating that the Moore鈥揚enrose protocol leads to a lower bound of \(\Omega(\min\{T,\sqrt{d}\})\) regret against a zero-loss comparator, highlighting the limitations of existing approaches. Additionally, they propose a triangular construction that aligns regret with data rank, offering insights into the relationship between feature selection and prediction loss.
Nuisance interpolation in feature priming can lead to significant underperformance in online regression, revealing a fundamental limitation in existing regret guarantees.
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 $\Omega(\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.
