New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression

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.

Can a constant number of linear minimizations per round improve on the $T^{3/4}$ regret rate of online Frank-Wolfe on general convex sets? Weibel et al. conjectured that fixed-coefficient methods cannot. We prove their conjecture and extend the lower bound to every deterministic learner in an oracle-only model. The learner receives an initial feasible point and a diameter bound, and must remain feasible on every domain consistent with its oracle replies. For $T$ rounds, at most $b$ calls between decisions, diameter bound $D$, and gradient norm bound $L$, we construct an instance in dimension $d=2b(T-1)+1$ with regret at least $2^{-1/4}LDb^{-1/4}T^{3/4}$. The adversary fixes the domain, initial point, deterministic tie rule and linear losses before play. The vertices form a path on which every point available before a decision has zero current loss, while the final vertex has negative loss on every round. For constant $b$, the result matches the known upper rate for dimension-independent guarantees. For one-call fixed schedules with a nonzero coefficient on the newest gradient, a second construction gives regret at least $3LDT^{3/4}/4$ with unique minimizers at every issued query. Exact-arithmetic certificates for the tuned schedule of Weibel et al. closely match their finite-horizon numerical worst cases, with unique oracle replies.

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.