Online Generalized Sparse Regression: How Does Overparametrization Help?

Shuoguang Yang; Qiang Sun

stat.MLAug 18, 2026

Online Generalized Sparse Regression: How Does Overparametrization Help?

Authors: Shuoguang Yang, Qiang Sun

Organizations: HKUST · University of Toronto and MBZUAI

Abstract

Regularized sparse regression has been extensively studied in the offline setting, but online formulation remains relatively under-explored. This gap stems from four key challenges: (i) the infeasibility of dynamically updating the regularization parameter in every online round, (ii) managing storage and memory complexity, (iii) enabling real-time computation via closed-form updates rather than solving full optimization problems at each round, and (iv) achieving optimal statistical guarantees under realistic assumptions. In this paper, we propose an online generalized-sparsity-constrained regression framework, focusing on online cardinality-constrained linear regression and low-rank matrix sensing. Unlike online regularized regression, our constrained formulation eliminates the need for dynamic parameter tuning. We introduce an efficient online hard-thresholding algorithm that performs closed-form updates and requires storing only summary statistics, making it computationally, memory, and storage efficient. Despite the inherent nonconvexity and combinatorial nature of the formulation, our algorithm achieves global convergence at the optimal statistical rate under realistic assumptions, provided that the projection set is properly overparameterized. Numerical experiments demonstrate that our method consistently outperforms state-of-the-art alternatives.

Figures & tables

Figure 1: The left panel shows the cone-like set $\mathcal{C}(3,{\mathcal{S}})$ while the right panel depicts the region where $\widehat{\Theta}_{t}^{\scriptstyle\textrm{appr}}-\Theta^{*}$ may fall.

Figure 2: Online sparse linear regression under weak signal setup for

t_{0}\in[20,500]

and

t=10000

online learning rounds for independent and Toeplitz

\rho=0.5

covariate designs.

Figure 3: Online sparse linear regression under weak signal setup for projection sparsity level

s\in[15,100]

t_{0}=100

, and

T=10^{4}

online rounds, under independent and Toeplitz

\rho=0.5

covariate correlation designs.

Figure 4: Online sparse linear regression under weak signal setup without the initial batch under projection sparsity level

s\in\{15,30\}

MSE	$s=14$	$s=15$	$s=20$	$s=25$	$s=30$	$s=40$
OHT_K=1	0.519131	0.529622	0.376415	0.239696	0.138760	0.126439
OHT_K=5	0.115403	0.070367	0.011384	0.007039	0.010385	0.012848
OHT_K=10	0.070169	0.046840	0.007254	0.009965	0.011081	0.013396
OHT_K=20	0.046217	0.009727	0.007280	0.008915	0.011370	0.014919

Table 1: Empirical last-iterate MSE

\|\Theta_{T}-\Theta^{*}\|_{2}^{2}

for

t_{0}=100

and

T=10^{4}

under projection sparsity levels

s=14,15,20,25,30,40

and

[\Lambda_{i,i},1\leq i\leq p]=[500,100,10,8,\cdots,1,1,\cdots,1]

MSE	$s=3$	$s=4$	$s=5$	$s=10$	$s=15$	$s=20$
OHT_K=1	10.8453	5.6856	0.0546	0.1265	0.1848	0.2395
OHT_K=5	10.8447	5.6460	0.0508	0.1357	0.1968	0.2499
OHT_K=10	10.8367	5.6276	0.0503	0.1367	0.1958	0.2451
OHT_K=20	10.8299	5.2613	0.0499	0.1350	0.1990	0.2516

Table 2: Empirical last-iterate MSE

\|\Theta_{T}-\Theta^{*}\|_{\mathrm{F}}^{2}

for

t_{0}=100

and

T=10^{4}

under projection rank levels

s=3,4,5,10,15,20

Figure 5: Online low-rank matrix sensing for

t_{0}=100

and

T=10000

online learning rounds with projection sparsity level

s=5

Figure 6: Online low-rank matrix sensing for

t_{0}=100

and

T=10000

online learning rounds with projection sparsity level

s=15

Figure 7: Online low-rank matrix sensing without the initial batch (

t_{0}=0

) and

T=2000

online learning rounds with projection rank levels

s\in\{5,15\}

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure S.1: Empirical convergence of MSE

\|\Theta_{t}-\Theta^{*}\|_{\mathrm{F}}^{2}

against online learning round

t

under weak signal setup and independent covariate correlation

Figure S.2: Empirical convergence of MSE

\|\Theta_{t}-\Theta^{*}\|_{\mathrm{F}}^{2}

against online learning round

t

and weak signal setup with Toeplitz

\rho=0.3

covariate correlation

Figure S.3: Empirical convergence of MSE

\|\Theta_{t}-\Theta^{*}\|_{\mathrm{F}}^{2}

against online learning round

t

under weak signal setup and Toeplitz

\rho=0.5

covariate correlation

Figure S.4: Empirical convergence of MSE

\|\Theta_{t}-\Theta^{*}\|_{\mathrm{F}}^{2}

against online learning round

t

under weak signal setup and Toeplitz

\rho=0.7

covariate correlation

Figure S.5: Empirical convergence of MSE

\|\Theta_{t}-\Theta^{*}\|_{\mathrm{F}}^{2}

against online learning round

t

under strong signal setup and independent covariate correlation

Explore similar work

High-dimensional online learning via asynchronous decomposition: Non-divergent results, dynamic regularization, and beyond
Mar 21, 2026Shixiang Liu, Zhifan Li, Hanming Yang +1Statistical Learning Theory Streaming Algorithms
School of Statistics, Renmin University of China · School of Statistics and Mathematics, Zhongnan University of Economics and Law · Institute of Statistics and Big Data, Renmin University of China +1
New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression
Oct 8, 2026Xiaofeng Cao, Junfan Li, Langzhang Liang +2Linear Regression Minimax Regret
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 +2
Adaptive Iterative Hard Thresholding for Online High-dimensional Quantile Regression
Jun 26, 2026Zitian Zhou, Nan LinSparse Recovery Quantile Regression
Washington University in St. Louis

Mar 21, 2026J/K move · Enter open · S save

High-dimensional online learning via asynchronous decomposition: Non-divergent results, dynamic regularization, and beyond

Shixiang Liu, Zhifan Li, Hanming Yang, Jianxin Yin

School of Statistics, Renmin University of China · School of Statistics and Mathematics, Zhongnan University of Economics and Law · Institute of Statistics and Big Data, Renmin University of China+1

Statistical Learning Theory Streaming Algorithms Sparse Recovery

Open paper AskPDF arXiv

Existing high-dimensional online learning methods often face the challenge that their error bounds, or per-batch sample sizes, diverge as the number of data batches increases. To address this issue, we propose an asynchronous decomposition framework that leverages summary statistics to construct a surrogate score function for current-batch learning. This framework is implemented via a dynamic-regularized iterative hard thresholding algorithm, providing a computationally and memory-efficient solution for sparse online optimization. We provide a unified theoretical analysis that accounts for both the streaming computational error and statistical accuracy, establishing that our estimator maintains non-divergent error bounds and

\ell_0

sparsity across all batches. Furthermore, the proposed estimator adaptively achieves additional gains as batches accumulate, attaining the oracle accuracy as if the entire historical dataset were accessible and the true support were known. These theoretical properties are further illustrated through an example of the generalized linear model.

Abstract

Explore similar work

High-dimensional online learning via asynchronous decomposition: Non-divergent results, dynamic regularization, and beyond

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

Adaptive Iterative Hard Thresholding for Online High-dimensional Quantile Regression