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

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

Source-linked AI summary

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

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

arXiv:2610.11551v1Oct 8, 2026cs.LG

TL;DR

Online sparse linear regression’s minimax-regret complexity was unknown without regularity assumptions. This paper establishes a lower bound and develops upper-bound algorithms, presenting a first characterization of its information-theoretic complexity.

Problem
Without regularity assumptions, the minimax regret of (d, b, b0)-OSLR remained unknown, while prior work provided only upper bounds.
Source: §1 · p. 2
Method
The paper establishes a minimax-regret lower bound and proposes separate algorithms for b0 ≥ 2 and b0 ≤ 1, relating OSLR to online sparse linear learning.
Source: §1.1 · p. 3, §3 · p. 5
Results
The paper proves a minimax-regret lower bound for all b0 ≥ 0 with b0 < d − b and provides upper-bound algorithms for the cases b0 ≥ 2 and b0 ≤ 1.
Source: §1.1 · p. 3
Takeaways & Limitations
The work provides the first characterization of OSLR’s information-theoretic complexity, although its lower and upper bounds have gaps in problem-dependent constants.
Source: §1.1 · p. 3
For b0 = 1, Algorithm 2 does not use the additional attributes and may be suboptimal.
Source: §6 · p. 13

Abstract

from arXiv · show

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.

1 Introduction

Online sparse linear regression restricts which attributes a learner can inspect, reflecting constraints such as test costs and privacy. The paper establishes a minimax lower bound and develops upper bounds without regularity assumptions, while reducing its lower-bound analysis to identifying useful attributes under restricted observations.

1 Introduction

Earlier work addressed computational efficiency under regularity assumptions, but minimax regret without those assumptions remained unexplored; OSLR is also NP-hard.In OSLR, the learner uses at most b of d attributes to predict and may observe b0 additional attributes afterward.Source: §1 · p. 2

1.1 Main Results

The paper gives a minimax lower bound for b0 ≥ 0 when b0 < d − b, then proposes separate algorithms for b0 ≥ 2 and b0 ≤ 1.The bounds share an optimal T-dependent factor but differ in problem-dependent parameters.Source: §1.1 · p. 3

1.2 Technical Challenges

The lower-bound analysis reduces OSLR to identifying optimal attributes under restricted observations, using virtual parameters optimal for the attributes observed each round.The analysis first decouples the instance and outcome, then the observation choices and model parameters.Source: §1.2 · pp. 3–4

2 Problem Setting

The section sets notation for bounded instances, indexed vectors and matrices, and support sets. It also defines the Bregman divergence used in the paper.

2 Problem Setting

Instances are drawn from X, the set of vectors in R^d whose Euclidean norm is at most X.The output is bounded by |y_t| ≤ Y.Source: §2 · p. 4
For a support S, a[S] selects the vector coordinates indexed by S, while A[S,S] selects the corresponding rows and columns..Source: §2 · p. 4
B_ψ(·,·) denotes the Bregman divergence for a convex function ψ on a convex set Ω.Source: §2 · p. 4
Supp(w) denotes the indices of the nonzero coordinates of w.Source: §2 · p. 4

3 Lower Bound on the Minimax Regret

The section establishes a minimax-regret lower bound for OSLR and reduces its analysis to an equivalent partial-information learning problem. It states that the bound extends from deterministic to stochastic algorithms.

3 Lower Bound on the Minimax Regret

For any d > b0 + b ≥ b ≥ 1, the cited passage reports that regret of any algorithm for (d, b, b0)-OSLR satisfies a bound, but its value is not shown.Source: §3 · p. 4
The section says the T-dependent order is optimal in both additional-observation regimes, while problem-dependent constants remain a focus of the upper-bound improvements.The supplied passages do not preserve the full lower-bound expression or the specific order in T.Source: §3 · p. 4
The proof reduces OSLR to OSLL, an equivalent partial-information online learning problem with the same regret.This lets the authors analyze the lower bound through OSLL.Source: §3 · p. 5
The deterministic-algorithm lower bound also holds for stochastic algorithms.Source: §3 · p. 9

4 A Better Algorithm for (d, b, b0)-OSLR with b0 ≥2

For b0 ≥ 2, Algorithm 1 learns over candidate supports and their linear models using estimates built from partial observations. Its regret bound improves on the cited prior algorithm’s bound by a factor O(d/b0).

4 A Better Algorithm for (d, b, b0)-OSLR with b0 ≥2

Algorithm 1 simultaneously learns a distribution over N candidate supports and a linear model for each support.It samples a model according to that distribution and predicts using the selected support’s attributes.Source: §4 · p. 9
The algorithm estimates losses and gradients for unselected models using covariance and instance estimators based on the observed attributes.The estimators are stated to be unbiased for the instance and its covariance matrix.Source: §4 · p. 10

The expected regret of Algorithm 1 satisfies

The regret bound improves on the cited prior algorithm’s bound by a factor O(d/b0).The comparison is reported for the b0 ≥ 2 case.Source: The expected regret of Algorithm 1… · p. 11
The estimators use observed attributes from the selected support, and the regret bound depends on (d − b)(d − b − 1) rather than d².Source: The expected regret of Algorithm 1… · p. 11

5 A Better Algorithm for (d, b, b0)-OSLR with b0 ≤1

For b0 ≤ 1, Algorithm 2 uses CORRAL to manage a distribution over candidate supports and addresses the difficulty of controlling small action probabilities. Its stated regret is optimal up to a logarithmic factor, which the authors note can be removed with a better black-box algorithm.

5 A Better Algorithm for (d, b, b0)-OSLR with b0 ≤1

When b0 = 1, selecting among candidate supports is a bandit problem, and importance-weighted gradient variance can grow as action probabilities approach zero.CORRAL is used to update the probabilities so a negative term can offset accumulated gradient variances.Source: §5 · p. 12

The expected regret of Algorithm 2 satisfies

O(NT ln T) regret is reported for Algorithm 2, optimal up to O(ln T) relative to the lower bound.Source: The expected regret of Algorithm 2… · p. 13
The authors say the O(ln T) factor can be removed using a better black-box algorithm; they use CORRAL for simplicity.Source: The expected regret of Algorithm 2… · p. 13

6 Discussion

The discussion identifies stronger lower bounds and improved algorithms as directions for future work. It conjectures that the O(1/sqrt(b)) factor can be removed and notes that the b0 = 1 case may be suboptimal.

The authors identify proving a stronger lower bound as a future research direction.Source: §6 · p. 13
They conjecture that the O(1/sqrt(b)) factor can be removed.Source: §6 · p. 13
They did not design a customized algorithm for b0 = 1, and Algorithm 2 may be suboptimal because it does not use the additional attributes.Source: §6 · p. 13
They propose designing better algorithms for b0 ≥ 2, b0 = 1, and b0 = 0.Source: §6 · p. 13

Appendix

The appendix presents mathematical tools and update properties used in the subsequent OMD analyses, including a Bregman divergence, an optimality condition, update solutions, and a technical lemma.

A 1. Bregman Divergence

For the specified quadratic ψ_t, the appendix gives the Bregman divergence as a squared distance scaled by λ_t.Source: A 1. Bregman Divergence · p. 15

A 2. First Optimality Condition

The first optimality condition concerns a minimizer of a convex differentiable function over a convex domain.Source: A 2. First Optimality Condition · p. 15
The OMD update is rewritten, differentiated with respect to p_{t+1}, and analyzed using the first optimality condition.Source: A 2. First Optimality Condition · p. 15

A 3. Solutions of OMD

The OMD solutions use Lagrange multipliers; p_{t+1} can be solved by binary search, and the update for w_{t+1,i} is obtained from the multiplier method.Source: A 3. Solutions of OMD · p. 16

A 4. Technical Lemma

A technical lemma introduces q under the estimator condition in (8), and the appendix proceeds to analyze the second-order central moment.Source: A 4. Technical Lemma · pp. 16–17

B. Proof of Theorem 2

The proof of Theorem 2 reduces its regret analysis by relating a sparse competitor to one of the sets S_i and decomposing the regret into two terms.

For any w′ in W_b, the proof states that there is a w in W and an index i in [N] with the specified relationship.Source: B. Proof of Theorem 2 · p. 18
It assumes without loss of generality that the support of w′ is contained in S_i.Source: B. Proof of Theorem 2 · p. 18
The proof decomposes the regret into R1 and R2, then analyzes those terms separately.Source: B. Proof of Theorem 2 · p. 18

B 1. Analyzing R1

This subsection analyzes Ξ1,1 using a log-form update and an exponential inequality under a bound on the estimated costs.

The subsection gives an upper bound on Ξ1,1.Source: B 1. Analyzing R1 · p. 19
The update is expressed as ln p̃_{t+1,i} = ln(p_{t,i}) − ηc̃_{t,i}.Source: B 1. Analyzing R1 · p. 19
The analysis uses exp(−x) ≤ 1 − x + x^2 for x in [−1, 1] and assumes η max |c̃_{t,i}| ≤ 1.Source: B 1. Analyzing R1 · p. 20

B 2. Analyzing R2

The R2 analysis follows the R1 analysis and invokes Lemma 2 in its expectation and inequality steps; the section then combines the expected upper bounds for R1 and R2.

The R2 analysis is described as similar to the analysis of R1.Source: B 2. Analyzing R2 · p. 20
Lemma 2 is cited for the last inequality in the analysis.Source: B 2. Analyzing R2 · p. 21
The section combines the upper bounds on E[R1] and E[R2].Source: B 2. Analyzing R2 · p. 21

C. Proof of Theorem 3

The proof bounds R1 using CORRAL's regret guarantee and then turns to R2 before concluding.

C. Proof of Theorem 3

CORRAL's regret guarantee is used to upper-bound R1.Source: C. Proof of Theorem 3 · p. 21
Lemma 3 states a condition on the maximum c value and that ρT,i follows Algorithm 3.Source: C. Proof of Theorem 3 · p. 21
After bounding R1, the proof turns to analyzing R2.Source: C. Proof of Theorem 3 · p. 22
The proof concludes after the R2 analysis.Source: C. Proof of Theorem 3 · p. 22