Streaming Sparse Linear Regression

Shuoguang Yang, Yuhao Yan, Xiuneng Zhu, Qiang Sun

TL;DR

This paper introduces "Online Linearized LASSO" (OLin-LASSO), a novel framework for sparse linear regression on streaming data. It achieves memory efficiency and theoretical guarantees by using a linearized loss function and relaxing strict convexity requirements, outperforming existing methods in simulations, especially with limited initial data.

What Problem Does This Paper Address?

Traditional sparse linear regression methods (like LASSO) assume all data is available upfront (offline). However, in many real-world scenarios, data arrives sequentially (streaming). Existing methods for online sparse regression face significant challenges:

  • Memory and Storage: Storing all past data to re-compute estimates is infeasible for large datasets.
  • Dynamic Regularization: The regularization parameter needs careful tuning as more data arrives, which is complex in an online setting.
  • Restrictive Assumptions: Many online methods require strong convexity conditions that are hard to satisfy consistently for all incoming data points.

This paper aims to bridge this gap by developing an efficient and theoretically sound online sparse linear regression method that overcomes these limitations.

Methods

The core of the proposed "Online Linearized LASSO" (OLin-LASSO) framework lies in its novel loss function and algorithmic approach:

  • Novel Loss Function: Instead of using the full loss on all past data, OLin-LASSO uses a combination of:
  • A squared loss on an initial batch of data ($t_0$). This provides the necessary curvature for the optimization problem.
  • A linearized loss for subsequent data points. This approximation is based on the current best estimate and avoids recomputing the full loss, making it memory efficient.
  • Memory Efficiency: The framework achieves a fixed memory complexity of $O(t_0p + p^2)$, which is independent of the total number of online rounds ($t$). This is a significant improvement over methods that require storing all data.
  • Relaxed Convexity Assumptions: The Restricted Strong Convexity (RSC) condition, crucial for theoretical guarantees, is only required to hold for the initial batch's squared loss, not for every incoming data point. This makes the method more practical.
  • Iterative Optimization: The algorithm iteratively updates the coefficient estimate $\beta_t$ by solving a $\ell_1$-regularized optimization problem at each round $t$, using the previous estimate $\beta_{t-1}$ to linearize the loss.

Datasets

Not discussed in the paper. The experiments use synthetically generated data.

Key Insights and Ideas

  • Linearization is Key for Online Efficiency: Approximating the loss function with a linear term for streaming data is a powerful technique to reduce computational and memory burdens without sacrificing too much accuracy.
  • Initial Batch as a "Curvature Anchor": The initial batch's squared loss acts as a stable "anchor" providing the essential curvature for the optimization problem, allowing subsequent data to be handled more efficiently.
  • RSC Relaxation is Practical: Requiring RSC only on the initial batch, rather than all incoming data, significantly broadens the applicability of online sparse regression methods.
  • Optimal Convergence Rate Achieved: The theoretical analysis shows that the proposed method achieves the optimal $\tilde{O}(\sqrt{s/t})$ convergence rate for the $\ell_2$-norm error, matching theoretical lower bounds.

Key Results

  • Theoretical Guarantees: The paper provides theoretical guarantees for the $\ell_1$ and $\ell_2$ norm estimation errors, showing they decay at the optimal rate of $\tilde{O}(\sqrt{s/t})$, where $s$ is the sparsity level and $t$ is the number of streaming samples.
  • Memory Complexity: The algorithm has a memory complexity of $O(t_0p + p^2)$, independent of the total number of online rounds $t$.
  • Numerical Performance: Experiments demonstrate that OLin-LASSO outperforms existing online sparse regression methods (specifically OS-LASSO) in terms of Mean Squared Error (MSE), especially when the initial batch size ($t_0$) is small.
  • Robustness: The algorithm shows superior performance across various covariate correlation designs and signal strengths (weak vs. strong signals).

Limitations and Future Work

  • Initial Batch Size Requirement: The framework requires an initial batch of a certain size ($t_0 \geq (96sc/k)^2 \log(p^2/\delta)$) to ensure convergence. The parameters $s$ (sparsity) and $k$ (condition number) are unknown in practice.
  • Open Problem: The authors pose an open problem: can problem-independent algorithms be developed that avoid the need for such primitives (like $t_0$ size and knowledge of $s, k$) while maintaining comparable theoretical performance?

Summary updated

Abstract

Sparse regression has been a popular approach to perform variable selection and enhance the prediction accuracy and interpretability of the resulting statistical model. Existing approaches focus on offline regularized regression, while the online scenario has rarely been studied. In this paper, we propose a novel online sparse linear regression framework for analyzing streaming data when data points arrive sequentially. Our proposed method is memory efficient and requires less stringent restricted strong convexity assumptions. Theoretically, we show that with a properly chosen regularization parameter, the $\ell_2$-norm statistical error of our estimator diminishes to zero in the optimal order of $\tilde{O}({\sqrt{s/t}})$, where $s$ is the sparsity level, $t$ is the streaming sample size, and $\tilde{O}(\cdot)$ hides logarithmic terms. Numerical experiments demonstrate the practical efficiency of our algorithm.
BibTeX
@inproceedings{yang2023streaming,
  author = {Shuoguang Yang and Yuhao Yan and Xiuneng Zhu and Qiang Sun},
  title = {{Streaming Sparse Linear Regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=XmFN5LqynG},
}

Loading related content...

Figure