PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Huibo Xu, Shi Fu, Qixin Zhang, Dacheng Tao

arXiv:2608.17573v1stat.MLcs.LGstat.AP

TL;DR

The paper asks whether feature-priming rules can achieve sparse-logarithmic regret under the natural past-only Moore–Penrose protocol. It analyzes nuisance interpolation and shows matching lower and upper regret frontiers, while leaving some multivariate and Pearson cases open.

  • Problem

    The paper studies whether any feature-priming rule guarantees O(k log(ed/k)) regret uniformly over comparators supported on at most k coordinates.

  • Method

    Using past-data Moore–Penrose refits, the paper isolates nuisance interpolation and constructs Hadamard and triangular sequences to analyze powered priming.

  • Results

    Ω(min{T, √d}) lower bounds hold for all three rules, while regret is at most 4 rank(X1:T) and powered univariate priming attains Θ_α(min{T, d}).

  • Takeaways & Limitations

    Successful empirical feature recovery does not by itself imply sparse online adaptation because nuisance features determine interpolant selection and rank limits the duration of costly errors.

  • Takeaways & Limitations

    Matching frontiers for multivariate and Pearson priming remain open, and the shared powered-rule witness is not claimed sharp.

Abstract

from arXiv · show

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.

1. Introduction

The paper gives a clipping-robust negative answer to sparse-logarithmic regret for three feature-priming rules, tracing failure to nuisance interpolation that suppresses the predictive coordinate. It also establishes rank-controlled regret and matching powered-univariate lower bounds, while exploratory activation tests reproduce the same geometric pattern.

  • Problem and contribution: The three priming rules do not guarantee O(k log(ed/k)) regret under the natural nonanticipating past-data implementation.This negative result does not rule out dimension-dependent guarantees.
  • Geometric obstruction: Cheap nuisance-only interpolation lets the second minimum-norm fit match past labels while assigning little weight to the truly predictive coordinate.The target weight satisfies w1 = π2_1κ/(1 + π2_1κ), and a two-sign argument converts missing target mass into clipped prediction loss.
  • Lower bounds: Hadamard constructions force Ω(min{T,√d}) regret against bounded sequences realizable with zero loss by the one-sparse comparator e1.The regret is linear when d = Θ(T^2). Pairing each query with its negative also defeats all three powered rules, switchers, and convex mixtures on one fixed sequence.
  • Rank-controlled guarantees: A clipped predictor that interpolates completed history has regret at most 4 rank(X1:T), because errors occur only when the current input adds a new row-space direction.A rational triangular construction matches this dependence for powered univariate priming, giving exact order Θ_α(min{T,d}) even when ∥x_t∥2 ≤ 1.
  • Empirical diagnostics: Stress tests on frozen Qwen2.5 and Qwen3.8 activations show that greater nuisance capacity lowers learned target mass and increases normalized regret.The diagnostics illustrate the proof geometry but do not establish that either model implements feature priming.

2. Problem setup

The paper studies nonanticipating online square-loss regression with coordinatewise bounded inputs and a fixed sparse comparator, using past-data feature priming followed by a minimum-norm refit. Its lower bounds focus on the one-sparse comparator e1, while predictions may be clipped without increasing loss.

  • Online protocol: The learner computes coefficients from completed past history, observes the current input, predicts, and then receives its label.This is the standard nonanticipating interpretation of Warmuth and Amid’s past-data priming map.
  • Comparator: The comparator is zero-loss and the lower bounds use k = 1, S = {1}, uS = e1, and yt = xt,1.Labels are generated by a fixed sparse comparator, with the analysis specializing to the first coordinate.
  • Primed refit: Priming rescales historical design columns and performs a second minimum-norm fit using the resulting diagonal multiplier matrix Dt.Only multiplier magnitudes affect predictions: signed squaring and literal squaring are prediction-equivalent.
  • Loss handling: Clipping predictions to [−1, 1] cannot increase square loss because labels lie in [−1, 1].The empty-history prediction is zero, and the clipped prediction is defined as eyt = clip(byt).
  • Base primes: The three base primes include univariate LLS, which uses each feature’s past-data least-squares coefficient, and Pearson, which uses empirical correlation when both variances are positive.The supplied setup identifies these as proposals from Warmuth and Amid (2023, Sec. 2, p. 2).

3. Multivariate LLS: pt = X†

This section specifies the multivariate Moore–Penrose priming protocol and its Pearson-correlation totalization, including the conditions under which Pearson is defined and target preservation is required. It also fixes the prediction domain and adversarial-witness conventions used for the separation results.

  • Pearson totalization: Pearson correlation is undefined for histories of length at most one or zero empirical variance, so finite totalizations assign deterministic past-only fallback values.The totalization agrees with Pearson whenever Pearson is defined.
  • Pearson totalization: The Pearson lower bounds hold for every finite totalization, while the rank upper bound requires target preservation.Target preservation means the filled target prime is nonzero whenever the past label vector is not identically zero.
  • Loss and regret: Because the one-sparse comparator e1 has zero loss on the constructions, regret equals learner loss, analyzed through a clipped prediction-loss quantity.The clipped version is written as Rclip.
  • Adversarial conventions: The input constraint is x_t ∈ [−1, 1]^d, without an ℓ2-norm bound unless explicitly stated.Adversarial sequences may depend on the rule and horizon but are fixed before online play unless a witness is stated to be shared.
  • Adversarial conventions: Unit-power separation uses rule-specific witnesses, whereas powered separation uses one common fixed-exponent witness shared pathwise by all three rules’ selectors.The shared-witness convention applies only when explicitly stated.

3. A nuisance-interpolation obstruction

The three prime rules share a nuisance-interpolation obstruction: when nuisance features cheaply interpolate the history, the minimum-norm refit underweights the target coordinate. The resulting missing target weight forces clipped loss on one of two possible target signs.

  • Common obstruction: Cheap nuisance interpolation makes the minimum-norm refit place little weight on the truly predictive coordinate, despite interpolating all past labels.The obstruction is geometric and does not depend on how the three prime rules assign weights.
  • Clipped-loss consequence: An arbitrary nuisance contribution cannot make both target signs simultaneously accurate, even after clipping.The two-sign argument lower-bounds the average loss by the square of the missing target weight.
  • Scalar obstruction: When the transformed history label lies in the nuisance-column span, the second-stage fit’s target weight is governed by the prime-weighted nuisance interpolation cost π_1^2κ.Here κ is defined from the minimum-norm nuisance representation of the history label.
  • Clipped-loss consequence: One of the two target signs incurs average clipped loss at least (1 + π_1^2κ)^-2.The two legal examples use x_σ = (σ, h), labels y_σ = σ, and σ ∈ {−1, 1}.

4. Hadamard instantiations of the obstruction

Hadamard constructions expose a shared nuisance-interpolation obstruction: the nuisance coordinates fit the labels while the priming rules underweight the target. This yields sparse-regret separations for all three rules, including fixed powered variants and selectors.

  • Hadamard nuisance cost: Hadamard nuisance coordinates interpolate arbitrary signed labels, with the rules differing only in the prime-weighted cost of that interpolant.For powered univariate, multivariate, and Pearson rules, the nuisance squared-norm cost is bounded by r^(2α)/N.
  • Unit-power separation: At unit power, each prime predictor admits a deterministic realizable sparse-regret lower bound against the zero-loss comparator e1.The Pearson construction is uniform over every finite totalization when T ≥4; the comparator has zero cumulative loss.
  • Sparse-logarithmic failure: None of the three unit-power rules admits a universal sparse-logarithmic regret guarantee under the past-only protocol.The failure already occurs for k = 1, and Pearson’s conclusion is uniform over every finite totalization; raw predictions inherit the failure.
  • Shared powered witness: A single deterministic witness defeats all three powered rules and every three-rule selector for each fixed α ≥1.The sequence is independent of the prime rule, selector, Pearson totalization, and internal randomness; its powered exponent remains fixed throughout.
  • Powered-rate consequence: Because d = Θ(T^(2α)), the shared construction rules out the sparse-logarithmic benchmark for every fixed α ≥1, including α = 2.The argument does not cover procedures that tune the exponent online or externally correct the primed prediction.

5. Rank controls loss and the univariate frontier

History-interpolating predictors incur loss only when examples add new row-space directions, yielding a rank-dependent upper bound. For powered univariate priming, a triangular construction matches this dependence, establishing a tight Θ_α(min{T, d}) frontier while the multivariate and Pearson frontiers remain open.

  • Rank controls loss: The rank bound applies to powered univariate and multivariate priming, plus powered Pearson priming under any target-preserving totalization.For sequences realizable by e_1, the required history interpolation holds for all fixed α ≥ 1.
  • Rank controls loss: At most rank(X_1:T) rounds can produce positive loss, and clipping bounds each round’s squared loss by four.Thus regret is at most 4r when all inputs lie in an r-dimensional subspace, independently of the horizon.
  • Univariate frontier: Together, the rank upper bound and triangular lower bound establish clipped worst-case regret Θ_α(min{T, d}) for powered univariate priming under coordinatewise bounded and Euclidean-normalized inputs.The matching lower bound uses one new direction on each loss-producing round.
  • Univariate frontier: For every d and T, powered univariate priming has regret at least c_α min{d, T} on a rational sequence realizable with zero loss by e_1.Here c_α is the smaller of 1/8 and (9/16)(5/8)^(4α−4).
  • Univariate frontier: At unit power, the same construction gives the sharper lower bound 1 + floor(m/2), where m = min{d, T}.A Euclidean-normalized variant with ||x_t||_2 ≤ 1 retains regret at least c_αm/4.
  • Univariate frontier: Matching worst-case dependence on (T, d) remains open for multivariate and target-preserving Pearson priming.The rank theorem covers both rule families, but does not provide matching lower bounds.

6. Ridge changes the failure mode, not the rate

Ridge regularization changes nuisance-driven underweighting into a choice between nuisance interpolation and label underfitting, without restoring the target mass suppressed by cheap nuisance interpolants. The paper proves ridge-robust lower bounds for powered univariate priming and all three rules, including adaptive or randomized past-only schedules.

  • Ridge mechanism: Ridge cannot restore target mass already suppressed by a cheap nuisance interpolant, so increasing regularization changes the failure mechanism rather than eliminating it.For small λ, nuisance-driven Moore–Penrose prediction persists; for large λ, predictions approach zero and underfit label one.
  • Univariate frontier: 1 + ⌊min{T, d}/2⌋ is the unit-power lower bound for the fixed rational triangular sequence under every finite nonnegative ridge schedule.The schedule may be randomized or selected after observing x_t.
  • Three-rule separation: T ≥ 32T/81 holds for each powered prime rule against a deterministic past-only ridge policy on a paired-Hadamard sequence.Under independent Rademacher query signs, the same expectation bound covers randomized policies and pre-input switchers or convex mixtures of the three ridge-regularized rules.
  • Assumptions: The univariate theorem permits the ridge value to depend on the current input, whereas the common three-rule theorem is distributional and requires the ridge value fixed before the current target sign.This distinguishes the assumptions behind the two ridge-robust results.

7. The obstruction in frozen language-model representations

Diagnostics on frozen language-model activations reproduce the paper’s obstruction: increasing nuisance dimension lowers target mass, raises normalized regret, and makes cheap nuisance-only certificates common. With 2,047 nuisance neurons, normalized regret is substantially higher than in the target-only setting for all three priming rules.

  • Experimental diagnostic: Frozen Qwen2.5-7B-Instruct MLP activations test the mechanism using six selected target neurons per layer, with each target’s label equal to its activation and nuisance neurons as alternatives.The diagnostic uses layers 6, 13, and 20 from Alpaca instruction records, and the target coordinate has zero comparator loss.
  • Observed obstruction: Increasing nuisance dimension raises normalized regret, lowers target mass, and makes cheap nuisance-only certificates common.This pattern is reported in the registered Qwen3.8 dimension scan.
  • Observed obstruction: 0.029 target-only median normalized regret is observed for all three rules across six fixed targets.The target-only condition provides the baseline for the dimension scan.
  • Observed obstruction: 1.238, 0.303, and 0.587 normalized regret result for univariate, multivariate, and Pearson priming with 2,047 real nuisance neurons.The 2,048-coordinate design includes one target and 2,047 nuisance neurons.

8. Related work

This section situates the paper’s negative sparse-logarithmic result within prior work on feature priming, sparse regret, adaptive geometry, and symmetry-based lower bounds. It also distinguishes one-stage priming from alternative reweighting and refitting approaches that may still succeed.

  • Feature priming: Warmuth and Amid’s Open Problem 1 asks whether univariate, Pearson, or multivariate LLS priming admits a competitive regret bound; this paper answers the uniform sparse-logarithmic interpretation negatively.The comparison target is O(k log(n/k)) regret for averages of k bounded features, while dimension-dependent guarantees remain possible.
  • Sparse regret and adaptive geometry: Sparse-regret benchmarks reflect the contrast between coordinatewise methods that exploit few-coordinate comparators and ridge or least-squares methods with norm- and dimension-dependent guarantees.Exponentiated-gradient methods and truncated exponential weighting provide deterministic sparsity regret bounds for online regression.
  • Batch sparse recovery: Batch sparse recovery offers alternatives including ℓ1 regularization, constrained selectors, greedy recovery, and iteratively reweighted least squares.Sparse solutions can also result from implicit bias in reparameterized least-squares problems under additional design and optimization conditions.
  • Rotation-invariance and symmetry lower bounds: The paper’s symmetry perspective builds on classical distinctions between coordinate-sensitive and rotation-invariant methods and on geometric analyses of interpolating-solution selection.The closest geometric predecessor is Warmuth et al.’s Hadamard separation, which gives a sample-efficiency lower bound for gradient-trained networks.
  • Reweighting beyond one-stage priming: Negative results for the three one-stage rules do not rule out other reweighting schemes, including mirror-descent reparameterizations, LLS-primed ridge estimators, and recursive reweighting-refitting methods.Warmuth et al. establish statistical upper bounds for an LLS-primed estimator followed by ridge regression, while linear recursive feature machines reduce to iteratively reweighted least squares in the linear setting.

9. Scope and limitations

The study is limited to three fixed-power one-stage rules with standard second-stage ridge regularization, while several alternative procedures and sharper frontiers remain outside scope. Its constructions respect Euclidean constraints, but key multivariate and Pearson separations and broader experimental interpretations remain open.

  • Analytical scope: The analysis covers three one-stage rules at fixed α ≥1 with standard ridge regularization of the transformed second-stage coefficient.Penalties on the transformed-back coefficient, regularized first-stage priming, iterative or alternative-prime procedures, and augmented selectors are excluded.
  • Witness limitations: The shared Hadamard witness uses d = Θα(T^2α), which is not claimed sharp, while the selector guarantee applies only to the three rules at one common fixed power.Selectors may mix either the rules’ coefficients or their clipped predictions.
  • Open frontiers: The powered-univariate frontier is Θα(min{T, d}), but the unit-power multivariate and Pearson frontiers retain a d–d gap.The rank-adaptive guarantee is ensured for Pearson by target preservation; more generally, the exact condition is interpolation by the transformed historical design.
  • Geometric and experimental limits: The half-scaled triangular family satisfies ∥xt∥2, ∥e1∥2 ≤1, so its exact frontier survives both Euclidean constraints.Normalized multivariate and Pearson separations remain open.
  • Experimental scope: The frozen-activation experiments test downstream priming maps on synthetic one-neuron labels inside two real representations, not Qwen generation, natural semantic labels, or internal Transformer updates.These experiments therefore do not establish that a Transformer implements the studied online procedures internally.

10. Conclusion … D.2. Exact equivalence on paired histories

Under the past-only Moore–Penrose protocol, cheap nuisance interpolation suppresses the predictive coordinate, ruling out uniform sparse-logarithmic regret for all three feature-priming rules. Hadamard and paired constructions establish matching lower bounds, while rank-based upper bounds and powered-univariate constructions characterize the remaining frontier.

  • 10. Conclusion: Cheap nuisance interpolation yields an exact target-weight identity that drives clipped regret for all three one-stage priming rules.The learned target weight is controlled by the least transformed cost of interpolating the history without the target.
  • Appendix C. Proof of the unit-power sparse-regret separation: Ω(min{T, √d}) regret follows from Hadamard features against a zero-loss one-sparse comparator.The construction keeps the target mass small and uses a two-sign argument to force prediction loss.
  • 10. Conclusion: 4 rank(X1:T) upper-bounds regret for every clipped history-interpolating predictor, because errors require a new row-space direction.A Euclidean-normalized triangular sequence matches this dependence for powered univariate priming.
  • C.2.2. OFFLINE SIGN COMPILATION: The offline sign compiler fixes an algorithm-dependent but oblivious sequence before interaction, while the comparator e1 incurs zero loss.At each prefix, it chooses between two legal target signs using the larger clipped loss.
  • Appendix B. Common algebraic and geometric tools: The Moore–Penrose refit is a weighted minimum-norm interpolant, with zero-prime coordinates fixed at zero.This equivalence supplies the common algebraic basis for the univariate, multivariate, and Pearson constructions.
  • B.2. Hadamard interpolation: Hadamard interpolation provides nuisance-only certificates that make the target coordinate unnecessary in the transformed refit.The certificate is the central geometric mechanism behind the multivariate and univariate target-mass bounds.
  • C.4.2. THE TOTALIZATION-UNIFORM CONSTRUCTION: 9/16 loss is forced on each Pearson query, followed by zero-loss recovery, uniformly over finite past-only Pearson totalizations.Paired histories keep all relevant correlations defined and restore the paired state after each recovery.
  • D.2. Exact equivalence on paired histories: On paired histories, the three powered refits are identical for every common α ≥1, enabling one shared two-sign witness against selectors and mixtures.The shared coefficient vector, not merely its target coordinate, coincides on every nonempty paired history.

D.3. Oblivious compilation and selector robustness … Appendix F. Proof of the powered-univariate exact frontier

The paper compiles one oblivious Hadamard sequence that forces substantial clipped regret for every three-rule selector, while proving a rank-controlled upper bound from exact interpolation. Positive-loss rounds consume new row-space directions, yielding regret bounded by the data rank.

  • D.3. Oblivious compilation and selector robustness: 49M/64 clipped regret is forced against every three-rule selector by one deterministic paired sign string, uniformly over selector randomness and Pearson totalizations.The construction uses a finite greedy recursion and exact opposite pairs under both mixture semantics.
  • D.3. Oblivious compilation and selector robustness: Identical powered coefficient vectors make all selector outputs coincide on charged queries, covering convex mixtures and switchers even when weights depend on inputs or random tapes.The common prediction also makes the result valid under the second mixture semantics.
  • D.3. Oblivious compilation and selector robustness: 49/64 expected query loss per paired query persists for independent random signs, and remains valid after averaging over any selector random-tape law.Conditioning on the completed history and random tape reduces each query to the two-sign average.
  • D.3. Oblivious compilation and selector robustness: Ω(min{T,√d}) regret follows against the zero-loss one-sparse comparator e1, contradicting uniform O(k log(ed/k)) regret already at k = 1.Hadamard rows are sign-valued, labels equal the first coordinate, and the unsigned and signed power conventions also cover literal squaring at α = 2.
  • Appendix E. Proof of the rank upper bound: Each positive clipped-loss round introduces a new row-space direction when the second-stage fit interpolates historical labels.A positive-loss round requires xt outside rowspan(X<t), increasing rank by one.
  • E.1. Rank spending and interpolation: 4 rank(X1:T) bounds the squared clipped loss under realizable interpolation, because each positive-loss round contributes at most four.Both clipped predictions and labels lie in [−1, 1].
  • Appendix F. Proof of the powered-univariate exact frontier: rank(X1:T) ≤ min{T, d} gives the generic data-rank upper bound for the powered univariate and multivariate rules, with Pearson covered under its target-prime condition.The powered rules interpolate y = Xe1; Pearson does so when its target prime is nonzero, equivalently under the stated target-preserving convention.

F.1. A linear-dimensional triangular construction … G.3. Hadamard ridge certificates for all three rules

The triangular construction establishes linear regret for powered univariate priming while remaining valid under Euclidean normalization and arbitrary nonnegative ridge schedules. Hadamard certificates extend the nuisance-interpolation obstruction to all three powered rules, including randomized mixtures.

  • F.1. A linear-dimensional triangular construction: The active triangular design is nonsingular, and every active prefix is linearly independent, so each round adds one row-space direction.The leading-prefix determinant is (−1)^(t−1)t.
  • F.1. A linear-dimensional triangular construction: Half-scaling preserves powered-univariate coefficients, bounds every input norm by one, and retains at least one quarter of each active clipped loss.The resulting normalized worst-case order is Θ_α(min{T,d}).
  • G.1. A resolvent form of target mass: The resolvent formulation shows ridge target mass remains nonnegative, bounded below one, and extends continuously to the Moore–Penrose endpoint.This formalizes the target-mass obstruction when nuisance columns interpolate the labels.
  • G.2. The triangular sequence for every ridge schedule: For the triangular sequence, every ridge value shrinks the Moore–Penrose target contribution by ρ_t(λ) = 1/(1 + λ/λ_c(t)), without removing the linear lower bound.The normalized construction retains (c_α/4) min{T,d} uniformly over all nonnegative ridge values and history-dependent schedules.
  • G.3. Hadamard ridge certificates for all three rules: On completed-pair Hadamard histories, each powered univariate, Pearson, and multivariate rule admits a nuisance-only transformed coefficient that certifies small target mass.The certificate is uniform over finite Pearson totalizations.
  • G.3. Hadamard ridge certificates for all three rules: Random Rademacher query signs yield the same obstruction for all three rules, randomized past-only ridge schedules, and pre-input mixtures, with conditional expected query loss at least 64/81.The deterministic witness does not cover current-input-dependent ridge choices; the common statement is distributional.

Appendix H. Frozen-activation experiment details

Frozen Qwen activation experiments reproduce the feature-priming mechanism: nuisance interpolation increases regret while reducing target weight, despite a zero-loss one-sparse comparator. The prespecified recovery criterion passes across layers and all three rules, with the same diagnostic replicated across nuisance widths and model generations.

  • Representation and target selection: The protocol uses post-gating Qwen2.5-7B-Instruct activations, percentile-scaled and clipped coordinates, disjoint data pools, and eligibility filters for target selection.Activations come from layers 6, 13, and 20; responses are unused.
  • Online protocol and metrics: Strict-past predictions are clipped to [−1, 1], labels equal target activations, and the fixed one-hot comparator has zero loss.Normalized regret is defined as cumulative loss divided by the target activation power.
  • Recovery result: 16 targets across all three layers satisfy the complete mechanism criterion, while every compiled target exceeds the regret threshold for all three rules.Median regrets are 1.181, 0.355, and 0.641; the comparator error is zero and the largest historical residual is 2.367 × 10−13.
  • Fresh dimension–horizon diagnostic: All 18 fresh targets pass the prespecified T = 48 width comparison, with median regret rising by 0.619 as nuisance width increases from 16 to 2,048.The target-bootstrap 95% interval is [0.541, 0.672].
  • Cross-generation replication: On compiled orders, target-only median regret is 0.029 for each rule, whereas adding real nuisance coordinates raises medians to 1.238, 0.303, and 0.587.Independently row-permuting nuisance coordinates yields medians 0.799, 0.306, and 0.555.
  • Mechanism diagnostic: Across nuisance-width diagnostics, regret rises, target weight falls, and nuisance-only interpolation becomes exact; permuted and Rademacher controls reproduce the regret trend.The figure summarizes 18 targets in panels A–C and six fixed control targets in panel D.
Loading 2608.17573v1…