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

Xiaofeng Cao; Junfan Li; Langzhang Liang; Mingwei Xu; Xiao Zhang

cs.LGOct 8, 2026

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

Authors: Xiaofeng Cao, Junfan Li, Langzhang Liang, Mingwei Xu, Xiao Zhang

Organizations: School of Computer Science and Technology, Tongji University, Shanghai, China · School of Computing and Artificial Intelligence, Shanghai University of Finance and Economics, Shanghai, China · AI3 Institute, Fudan University and Shanghai Innovation Institute · School of Artificial Intelligence, Jilin University, Changchun, China · Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China

Abstract

We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only $b$ out of $d$ attributes per instance for prediction and $b_0\geq 0$ additional attributes after prediction, which was proved to be NP-hard. Previous work focused on designing computationally efficient algorithms under regularity assumptions, but did not characterize its information theoretic complexity. In this work, we give the first lower bound on the minimax regret of OSLR and design algorithms with better upper bounds without regularity assumptions. We characterize how minimax regret scales with problem-dependent parameters, capturing the information theoretic complexity of OSLR.

Figures & tables

$(d,b,b_{0})$ -OSLR	Upper Bound	Lower Bound
$b_{0}\geq 2$	$O\left(\sqrt{\frac{(d-b)(d-b-1)}{b_{0}(b_{0}-1)}}\sqrt{T\ln{N}}\right)$ (Ours)	$\Omega\left(\frac{1}{\sqrt{b}}\sqrt{\frac{dT}{b+b_{0}}}\right)$ (Ours)
	$O\left(\frac{d^{2}}{b^{2}_{0}}\sqrt{T\ln{N}}\right)$ [ 6 ]
$b_{0}\in\{0,1\}$	$O(\sqrt{NT}\ln{T})$ (Ours)
	$O\left(N^{\frac{1-q}{3-2q}}T^{\frac{2-q}{3-2q}}\right),q\in(0,1)$ [ 10 ]

Table 1: Regret Lower Bound and Upper Bounds for

(d,b,b_{0})

-OSLR.

N=\binom{d}{b}

Explore similar work

Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates
Aug 18, 2026Huibo Xu, Shi Fu, Qixin Zhang +1Linear Regression Statistical Learning Theory
Nanyang Technological University, Singapore
Lower Bounds for Linear-Oracle Online Learning
Sep 29, 2026Mohit SinhaOnline Convex Optimization Information-Theoretic Lower Bounds
Sharp Minimax Regret for Infinite-Memory Logistic Prediction
Aug 27, 2026Vaneet AggarwalLogistic Regression Bayesian Mixture Models
Purdue University

Aug 18, 2026, stat.MLJ/K move · Enter open · S save

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

Huibo Xu, Shi Fu, Qixin Zhang, Dacheng Tao

Nanyang Technological University, Singapore

Linear Regression Statistical Learning Theory

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Lower Bounds for Linear-Oracle Online Learning

Sharp Minimax Regret for Infinite-Memory Logistic Prediction