Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates

Huibo Xu; Shi Fu; Qixin Zhang; Dacheng Tao

stat.MLAug 18, 2026

Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates

Authors: Huibo Xu, Shi Fu, Qixin Zhang, Dacheng Tao

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,\sqrt d\})$ clipped regret for each of the three unit-power rules against a zero-loss one-sparse comparator. For every fixed power $α\ge1$ , 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.

Explore similar work

Sep 22, 2026stat.ML

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the

d

-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is

O(\sqrt d)

in expectation for every time horizon, without knowledge of the horizon. The dependence on

d

is optimal up to a constant factor by the known

Ω(\sqrt d)

lower bound for horizons

T\ge d

. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the

O(\sqrt d)

regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.

Shinsaku Sakaue

Topic pending

Ask PDF

Aug 27, 2026cs.IT

Sharp Minimax Regret for Infinite-Memory Logistic Prediction

We determine the minimax cumulative log-loss regret of a finite-alphabet, exogenously driven source with genuinely infinite input memory: independent Rademacher inputs

(U_t)

are observed sequentially and the next binary mark has logit

\sum_{j\ge1}θ_jU_{t+1-j}

, the unknown coefficients obeying a summable envelope

|θ_j|\le r_j

\sum_jr_j\le B

. At horizon

T

, lag

j

can move the logit by at most

r_j

and is exercised in only

n_{T,j}=(T-j+1)_+

rounds, and the two limitations combine into the sum

Γ_T(r)=\sum_{j\le T}\log(1+n_{T,j}r_j^{2})

. One coordinate-localised Bayesian mixture achieves

R_T(r)\le CΓ_T(r)

for \emph{every} summable envelope with

C

universal. Our main result is a matching nonasymptotic converse for the canonical exponential and polynomial envelopes; its new ingredients are a modular finite-sample information bound for logistic experiments with an exogenous random design, and a conditioning estimate for the overlapping Toeplitz lag matrix obtained by exhibiting each off-diagonal Gram sum as a sum of independent Rademacher variables indexed by the edges of a forest, needing neither local asymptotic normality nor any spectral theorem for random Toeplitz matrices. So

Γ_T(r)

is the minimax regret scale here, giving

Θ(α^{-1}\log^{2}T)

for

r_j=Ae^{-αj}

and

Θ(T^{1/(2s)})

for

r_j=Aj^{-s}

s>1

--- the latter without the extra

(\log T)^{1-1/(2s)}

factor any window-truncation analysis pays. We also show memory decay cannot determine regret, and that a profile-scaled online Newton predictor attains

O_B(Γ_T(r))

in polynomial time per round.

Vaneet Aggarwal

Linear Regret Regret Minimax Finite-Sample Logistic Regression Infinite-Width Gaussian Limit

Ask PDF

Jul 12, 2026cs.LG

Bandit PCA with Minimax Optimal Regret

We study the bandit-feedback version of online principal component analysis (Bandit PCA): in each round

t = 1,\dots,T

, the adversary selects a

d \times d

symmetric gain matrix

G_t

with spectrum in

[0,1]

and rank at most

r

; the learner simultaneously selects a unit vector

w_t \in S^{d-1}

and receives the reward

w_t^\top G_t w_t

. The learner receives no other feedback, and aims to minimize the regret against the best unit vector in hindsight. This problem was introduced by Kotlowski and Neu (2019), who gave an algorithm with regret

O(d\sqrt{rT \log T})

and showed the lower bound of

Ω(r\sqrt{T/\log T})

. We improve upon both of these bounds and essentially bridge the gap between them, establishing the minimax regret of order

r\sqrt{dT}

up to polylogarithmic factors in

d

and

T

. The upper bound is attained by a novel algorithm, which combines online mirror descent on the spectrahedron of (real) density matrices with a multiscale exploration scheme in which the eigenspaces with different spectral magnitudes are updated at different rates. For the lower bound, we construct an adaptive adversary that refines a hidden large-reward subspace based on the learner's actions, in such a way that low regret is impossible without estimating the subspace; as a result, lower-bounding the regret reduces to studying the arising subspace estimation problem. Finally, we discuss connections of Bandit PCA with adaptive-measurement quantum tomography.

Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa Saha

Principal Component Analysis Regret Low-Rank Factorization

Ask PDF