PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Generalized Sparse Regression: How Does Overparametrization Help?

Shuoguang Yang, Qiang Sun

arXiv:2608.17466v1stat.MLcs.LGmath.ST

TL;DR

Online sparse regression lacks a practical approach that avoids dynamic regularization while remaining computationally efficient and statistically optimal. The paper proposes constrained generalized-sparsity regression with online hard thresholding for sparse linear regression and low-rank matrix sensing. Under realistic assumptions and a properly overparameterized projection set, the method converges globally at the optimal statistical rate while using efficient updates and summary-statistic storage.

  • Problem

    Online sparse regression must address dynamic regularization, storage and memory costs, real-time computation, and optimal guarantees under realistic assumptions.

  • Method

    The paper uses generalized-sparsity constraints and an online hard-thresholding algorithm for cardinality-constrained linear regression and rank-constrained matrix sensing.

  • Results

    The algorithm converges globally to the ground-truth coefficients at the optimal statistical rate under realistic assumptions, with an overparameterized projection set.

  • Takeaways & Limitations

    The constrained formulation eliminates dynamic regularization while retaining closed-form online updates and memory- and storage-efficient summary-statistic computation.

  • Takeaways & Limitations

    The per-round iteration number K and projection sparsity s are typically unavailable in real-world applications and may require cross-validation.

Abstract

from arXiv · show

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.

1 Introduction

The paper addresses the difficulty of extending sparse regression from offline to online settings by replacing dynamic regularization with constrained generalized sparsity and online hard thresholding. Under overparameterization and stated smoothness conditions, the method achieves optimal statistical performance with efficient updates and bounded storage.

  • Motivation: Online sparse regression must handle dynamic regularization, growing storage costs, real-time computation, and realistic statistical assumptions simultaneously.Dynamic tuning depends on unknown error distributions and sample size, while storing all past data costs O(t d1 d2).
  • Framework: The proposed constrained framework covers cardinality-constrained linear regression and rank-constrained matrix sensing using generalized sparsity.Here, generalized sparsity is measured by ||Θ||0 for vectors and rank(Θ) for matrices.
  • Algorithm: Online hard thresholding performs K thresholding steps per round instead of solving each subproblem exactly.The update projects gradient steps onto the generalized-sparsity constraint set.
  • Theory: With generalized sparse strong convexity and smoothness, an overparameterized projection set s > κ^2s* yields geometric convergence toward the ground-truth coefficients.The stated step size is η ≤ 1/L, where L is the sparse strong smoothness parameter.
  • Theory: For logarithmically large rounds, the algorithm reaches the optimal statistical error while using storage and memory independent of the number of rounds.The reported complexities are O(d2) for linear regression and O(d1^2 d2^2) for matrix sensing.
  • Contributions: The approach simultaneously removes dynamic regularization, supports closed-form updates, uses summary statistics, and provides optimal guarantees under realistic assumptions.The paper describes this as addressing all four major online-regression challenges.

2 Why Overparameterized Online Hard Thresholding Works

The paper motivates constrained online regression as a way to avoid dynamic regularization while retaining efficient updates and statistical guarantees. Overparameterized hard thresholding enlarges the projection set to handle correlated designs and enable convergence at realistic condition numbers.

  • Problem setup: Online generalized-sparsity regression uses sequential data to estimate a generalized-sparse coefficient matrix under cardinality or rank constraints.The setup covers linear regression when d2 = 1 and low-rank matrix regression otherwise.
  • Why online sparse regression is challenging: Regularized online regression is difficult because tuning changes over time, storing all data costs O(t d1 d2), and each update must support real-time computation.Regularized methods can also require repeated optimization rather than a fixed number of simple updates.
  • Why online regularized updates can fail: Few simple updates can fail because the moving objective requires sufficiently fast convergence, while approximate iterates may leave the cone-like set where restricted strong convexity holds.The exact solution remains in the cone under a suitable regularization condition, but approximate solutions can drift into a surrounding neighborhood.
  • Moving to online constrained regression: Constrained regression removes dynamic regularization but remains difficult because retaining all data is infeasible and cardinality-constrained regression is generally NP-hard.Summary statistics address storage, while algorithm design must address the computational hardness of the constrained problem.
  • Hard thresholding: For orthonormal designs, constrained least squares equals ordinary least squares followed by hard thresholding to retain the s* largest-magnitude entries.This closed-form characterization motivates iterative hard thresholding beyond orthonormal designs.
  • Overparameterization: The proposed method overparameterizes the projection set to s(κ, s*) ≥ s*, allowing extra features when condition numbers are large while keeping estimation error nearly unaffected.The projection size can be chosen larger as feature correlations increase, reducing the risk of missing true coefficients.
  • Convergence: The analysis establishes a recursive relation across online rounds that yields the final convergence result under the overparameterized projection scheme.The recursion follows from the projected updates with ηt,k ≤ 1/L.
  • Algorithmic guarantees: The resulting online algorithm uses fixed projection sparsity, summary statistics, and a few projected gradient steps, while allowing arbitrary sparse condition numbers.With ηt,k = 1/L, the required projection sparsity can be as small as s > κ^2s*; for κ = 1, this reduces to s > s*.

3 Global Convergence Analysis

The analysis establishes global convergence of online hard thresholding for sparse regression and low-rank matrix sensing under generalized sparse curvature conditions. Properly overparameterized projection sets and suitable step sizes yield geometric convergence to the ground truth at the optimal statistical rate.

  • Assumptions: The framework uses generalized sparse strong smoothness and convexity conditions to analyze online hard thresholding for sparse and low-rank problems.These conditions specialize to sparse strong smoothness and convexity for linear regression, and characterize the required curvature properties more generally.
  • Online sparse linear regression: For online sparse linear regression, the algorithm tracks a moving optimal sparse estimator while handling last-iterate convergence, changing losses, and metric mismatch.The target estimator changes after each incoming observation, so offline convergence arguments do not directly provide a recursive online guarantee.
  • Algorithmic analysis: The last hard-thresholding iterate has minimum loss among within-round iterates because the loss is non-increasing across thresholded gradient steps.This descent property holds for any projection sparsity level s≥1 under sparse smoothness.
  • Online sparse linear regression: With step size η≤1/L and projection sparsity s>s*/(η^2α^2), online hard thresholding converges geometrically to the ground-truth coefficients.The analysis requires sufficiently many hard-thresholding steps and an overparameterized projection set.
  • Online sparse linear regression: O(s*σ_x^2/(t+t0)) is achieved for sparse regression, matching the optimal offline statistical error under suitable projection sparsity.When η=1/L, the projection requirement reduces to s>κ^2s*; isotropic designs with κ=1 require only s>s*.
  • Online low-rank matrix sensing: For online rank-constrained matrix sensing, the sequence converges to the ground-truth coefficient matrix at rate O(s*σ_x^2/t) under analogous projection-rank conditions.The low-rank result parallels the sparse-regression convergence analysis.

4 No Batch Initialization

The paper extends online hard thresholding to settings without an initial batch by using a single-phase procedure. Early rounds require separate control because strong convexity may emerge only after enough observations, after which geometric contraction applies.

  • Motivation: The no-batch setting asks whether online hard thresholding can produce a solution after each observation without initialization data.This corresponds to setting t0=0 in the earlier formulation.
  • Algorithm: The single-phase algorithm follows the same hard-thresholding procedure but operates without an initial batch.The analysis denotes the data received through round t directly and computes the round-t solution online.
  • Assumptions: The analysis assumes generalized smoothness after receiving tw observations, although the exact threshold may be unknown in practice.For simplicity, the paper sets tw=t0.
  • Early rounds: Before strong convexity holds, hard-thresholding errors can propagate and amplify across early rounds, potentially producing poor early solutions.The paper separately bounds this initial phase before applying the post-threshold convergence result.
  • Post-threshold convergence: After t0 observations, strong convexity holds and the initial gap is geometrically discounted in subsequent rounds.The resulting corollary applies the same step-size and projection-size conditions used in the batch-initialized analysis.
  • Low-rank matrix sensing: The no-batch analysis also extends to rank-constrained matrix sensing under low-rank smoothness and strong convexity assumptions.Separate propositions and corollaries establish early-phase control and subsequent convergence for the matrix setting.

5 Numerical Experiments

Experiments evaluate online hard thresholding for sparse linear regression and low-rank matrix sensing across initialization, sparsity, correlation, and iteration settings. The results show convergence, robustness to initialization and correlation, and advantages over OS_LASSO in weak-signal settings.

  • Online Sparse Linear Regression: The experiments compare OHT and OS_LASSO using multiple hard-thresholding steps, initial batches, projection sparsity levels, and covariate designs.Sparse regression uses independent and Toeplitz correlation structures; OHT uses closed-form hard-thresholding gradient updates.
  • Online Sparse Linear Regression: When s≤30, OHT_K=5, OHT_K=10, and OHT_K=20 outperform OHT_K=1; for larger s, their performance is comparable or slightly better under Toeplitz designs.These observations are consistent with the requirement for sufficiently large projection sparsity and K for global convergence.
  • Online Sparse Linear Regression: OHT remains robust across initial batch sizes t0∈[20, 500], whereas its performance is reported as comparable throughout this range.Figure 2 evaluates 10^4 online rounds under independent and Toeplitz ρ=0.5 designs.
  • Online Sparse Linear Regression: Without an initial batch, OHT_K=5, OHT_K=10, and OHT_K=20 converge to Θ∗ for s=15 and s=30, while OHT_K=1 converges much more slowly.At t=10^4, a performance gap between OHT_K=1 and the larger-K variants remains evident.
  • Online Sparse Linear Regression: Algorithm 1 performs well at s=20 even when the sparse condition number κ=500 is large.The experiment suggests that the theorem’s dependence of projection sparsity on κ may not be tight.
  • Online Low-Rank Matrix Sensing: OHT outperforms OS_LASSO in weak-signal settings across covariate designs, especially with small initial batches.Under strong signals, OS_LASSO can identify the correct nonzero support using a small initial batch, narrowing the performance difference.
  • Online Low-Rank Matrix Sensing: For low-rank matrix sensing, OHT converges to Θ∗ for s=5 and s=15, with log-error slopes approximately −1 when K≥5.The observed slopes agree with the predicted O(s/(t+t0)) convergence rate; under-picking s=3 or 4 prevents convergence.

6 Conclusions

The paper proposes online hard thresholding for generalized sparse regression, targeting cardinality-constrained linear regression and low-rank matrix sensing. The method avoids dynamic regularization while using closed-form updates and summary statistics, and it achieves global convergence at the optimal statistical rate under realistic assumptions.

  • Contributions: The paper proposes an online hard-thresholding algorithm for cardinality-constrained linear regression and low-rank matrix sensing.These are the paper’s two generalized-sparsity-constrained problem classes.
  • Contributions: The algorithm avoids dynamic regularization, uses closed-form updates each round, and stores only summary statistics.These design choices target computational, memory, and storage efficiency.
  • Theoretical Guarantees: The algorithm converges globally to the ground-truth coefficients at the optimal statistical rate under realistic assumptions.The projection set must be properly overparameterized for the stated guarantee.
  • Limitations: A practical limitation is that the per-round iteration number K and projection sparsity s are typically unavailable in real-world applications.The paper suggests cross-validation on an initial batch or during early online rounds, and reports robustness when s is not under-picked.

Supplementary Material

The supplementary material contains additional numerical experiments and proofs for the paper’s main regression, matrix-sensing, and no-initial-batch results.

  • Organization: Appendix S.1 provides additional numerical experiments, while Appendices S.2–S.4 collect proofs for the main theoretical results.The proofs cover online sparse linear regression, online low-rank matrix sensing, and the no-initial-batch case.
  • Notation: The notation section introduces conventions for intersections involving spaces and orthogonal complements.The passage specifies notation for S1∩S2⊥ with a slight abuse of notation.

S.1 Additional Numerical Results

Additional experiments examine OHT under weak and strong signals, varying covariate correlation and initial batch size. OHT outperforms OS_LASSO in weak-signal settings, while the methods are comparable under strong signals when OS_LASSO identifies the correct support.

  • Experimental Setup: The supplementary experiments test OHT with s=50 and η=0.001 across weak-signal correlation designs and strong-signal independent designs.Weak-signal trials vary t0∈{100,500} and include independent and Toeplitz ρ=0.3, 0.5, 0.7 designs.
  • Weak Signal: OHT outperforms OS_LASSO_K=1 and OS_LASSO_K=20 in weak-signal settings for t0=100 and t0=500 across covariate designs.The supplementary figures report MSE against online learning rounds.
  • Strong Signal: Under strong signals, OS_LASSO and OHT have comparable performance because OS_LASSO identifies the correct nonzero support using a small initial batch.Subsequent updates remain restricted to that correctly identified support.
  • Conclusion: The additional numerical observations support OHT’s efficiency and robustness in weak-signal and small-initial-batch scenarios.These observations extend the main experiments across signal strengths and covariate correlations.

S.2.1 Proof of Proposition 3.1

The section presents empirical convergence diagnostics for online methods, including MSE comparisons across learning rounds and covariance-correlation settings.

  • Empirical convergence is assessed by plotting MSE against log t with a reference slope of −1.
  • The experiments compare OS_LASSO and OHT across multiple numbers of inner steps K.
  • Convergence is examined under weak-signal Toeplitz covariance with ρ=0.5 and ρ=0.7.
  • Figure 6 reports analogous convergence results for projection sparsity level s=15.

S.2.2 Proof of Lemma 3.2

This proof establishes an in-sample prediction-error bound for the cardinality-constrained estimator under the stated sparsity and regularity conditions.

  • The proof starts from the cardinality-constrained empirical-risk minimizer and uses its support-size relation to the true parameter.
  • The loss condition and expectation arguments convert the estimator’s error into a variance-dependent prediction-error bound.
  • The resulting bound scales as 8s*σ_x^2/[α^2(t0+t)].

S.2.3 Proof of Lemma 3.3

The section analyzes one hard-thresholding update for cardinality-constrained regression under a sparse restricted smoothness condition.

  • The update applies a hard-thresholding step after a gradient-based move on the online loss.
  • The analysis uses the (s,s)-SSS condition to control the loss change during the update.
  • The proof decomposes the objective change into two terms and bounds them separately.

S.2.4 Proof of Lemma 3.4

The section develops convergence arguments for sparse and low-rank hard-thresholding updates, combining descent, projection geometry, and statistical error bounds.

  • Sparse and low-rank descent: With step size η≤1/L, each inner update is shown to be nonincreasing in the online loss.
  • Sparse and low-rank descent: For cardinality constraints, overparameterized sparsity s>s*η^2/α^2 supports the contraction argument after K inner steps.
  • Sparse statistical recursion: The sparse statistical recursion contains a contraction term and a noise term proportional to 8sσ_x^2/[α^2(t0+t)].
  • Low-rank extension: For low-rank matrix sensing, the prediction-error bound has the form 8s*σ_X^2/[α^2(t0+t)].
  • Low-rank extension: The low-rank analysis transfers the sparse proof structure under LowRankSC and LowRankSS conditions, using rank(Θ−Θ*)≤2s.
  • Low-rank extension: The low-rank projection operator returns a rank-s approximation, and its relative-concavity analysis supports the convergence proof.
Loading 2608.17466v1…