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 C(3,S) while the right panel depicts the region where Θtappr−Θ∗ may fall.
Figure 2: Online sparse linear regression under weak signal setup for t0∈[20,500] and t=10000 online learning rounds for independent and Toeplitz ρ=0.5 covariate designs.
Figure 3: Online sparse linear regression under weak signal setup for projection sparsity level s∈[15,100] , t0=100 , and T=104 online rounds, under independent and Toeplitz ρ=0.5 covariate correlation designs.
Figure 4: Online sparse linear regression under weak signal setup without the initial batch under projection sparsity level s∈{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 ∥ΘT−Θ∗∥22 for t0=100 and T=104 under projection sparsity levels s=14,15,20,25,30,40 and [Λi,i,1≤i≤p]=[500,100,10,8,⋯,1,1,⋯,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 ∥ΘT−Θ∗∥F2 for t0=100 and T=104 under projection rank levels s=3,4,5,10,15,20 .
Figure 5: Online low-rank matrix sensing for t0=100 and T=10000 online learning rounds with projection sparsity level s=5 .
Figure 6: Online low-rank matrix sensing for t0=100 and T=10000 online learning rounds with projection sparsity level s=15 .
Figure 7: Online low-rank matrix sensing without the initial batch ( t0=0 ) and T=2000 online learning rounds with projection rank levels s∈{5,15} .
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure S.1: Empirical convergence of MSE ∥Θt−Θ∗∥F2 against online learning round t under weak signal setup and independent covariate correlation
Figure S.2: Empirical convergence of MSE ∥Θt−Θ∗∥F2 against online learning round t and weak signal setup with Toeplitz ρ=0.3 covariate correlation
Figure S.3: Empirical convergence of MSE ∥Θt−Θ∗∥F2 against online learning round t under weak signal setup and Toeplitz ρ=0.5 covariate correlation
Figure S.4: Empirical convergence of MSE ∥Θt−Θ∗∥F2 against online learning round t under weak signal setup and Toeplitz ρ=0.7 covariate correlation
Figure S.5: Empirical convergence of MSE ∥Θt−Θ∗∥F2 against online learning round t under strong signal setup and independent covariate correlation
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 ℓ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.
Shixiang Liu, Zhifan Li, Hanming Yang +1
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
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 b0≥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.
Xiaofeng Cao, Junfan Li, Langzhang Liang +2
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
Online high-dimensional regression requires algorithms that can update sequentially while preserving structural sparsity. We propose Adaptive Iterative Hard Thresholding (AIHT), an online sparse-regression framework that alternates stochastic subgradient updates with adaptively scheduled hard-thresholding steps. The key idea is to separate support discovery from local refinement: early in the learning process, AIHT delays thresholding so that weak but informative coordinates have time to accumulate signal, while later it increases the projection frequency to stabilize the sparse estimator and exploit local curvature. We develop the theory for high-dimensional online quantile regression, a challenging setting in which the loss is nonsmooth and the data may exhibit heterogeneity or heavy-tailed noise. Under restricted curvature and gradient-leakage conditions, AIHT remains in an inflated sparse cone, exhibits a two-phase convergence behavior, and attains logarithmic regret for the sliding-window objective. Simulations for online quantile regression, together with threshold-scheduling ablations, support the proposed mechanism and illustrate its advantage over standard online sparse-learning baselines.