Online Linearized LASSO

Shuoguang Yang, Yuhao Yan, Xiuneng Zhu, Qiang Sun

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$-error of our estimator decays to zero at the optimal order of $\tilde \mathcal{O}(\frac{s}{\sqrt{t}})$, where $s$ is the sparsity level, $t$ is the streaming sample size, and $\tilde \mathcal{O}(\cdot)$ hides logarithmic terms. Numerical experiments demonstrate the practical efficiency of our algorithm.

Introduction

In the era of big data, high-dimensional datasets where the number of features $p$ exceeds the number of observations $n$ are increasingly common. A fundamental assumption in analyzing such data is sparsity: only a small subset of features significantly influences the outcome. The LASSO (Least Absolute Shrinkage and Selection Operator) has become the standard tool for identifying these features. However, traditional LASSO is an "offline" method, requiring all data to be available simultaneously.

In many modern applications, such as high-frequency trading or real-time genomics, data arrives in a continuous stream. Applying offline LASSO to streaming data is computationally prohibitive due to increasing memory requirements and the need to re-solve complex optimization problems at every step. This paper introduces Online Linearized LASSO (OLin-LASSO), a memory-efficient framework designed for sparse regression in streaming environments.

The OLin-LASSO Framework

Transitioning LASSO to an online setting introduces three primary challenges:

  1. Memory Constraints: Storing all historical data leads to $O(pt)$ memory complexity, which is unsustainable for long-running streams.
  2. Dynamic Regularization: The regularization parameter $\lambda$ must be adaptively tuned as the sample size $t$ grows.
  3. Restricted Strong Convexity (RSC): Theoretical guarantees for LASSO typically rely on the RSC condition. In online settings, ensuring this condition holds for the loss function at every single time step is difficult.

OLin-LASSO addresses these issues through a linearized loss function. The algorithm utilizes a small initial "burn-in" batch of size $t_0$ to establish the necessary curvature (the quadratic part of the loss). For all subsequent streaming data, the algorithm employs a linear approximation based on the current coefficient estimates.

By fixing the quadratic component to the initial batch, the RSC condition only needs to be satisfied once. This allows the algorithm to refine estimates using new data without requiring every new data point to meet stringent geometric criteria. Furthermore, OLin-LASSO only stores summary statistics, resulting in a memory complexity of $O(pt_0 + p^2)$, which is independent of the total number of streaming rounds $T$.

Theoretical and Empirical Results

The authors prove that OLin-LASSO achieves the minimax optimal $\ell_2$-error convergence rate of $\tilde{O}(s/\sqrt{t})$. Notably, this method removes the "minimal signal strength" requirement common in previous online sparse methods, which often assumed that important variables must have large coefficients to be detectable.

Numerical Experiments

The performance of OLin-LASSO was evaluated using synthetic datasets with Toeplitz correlation structures ($\rho = 0.5$) and various noise distributions. The experiments compared OLin-LASSO against OS-LASSO, a popular two-stage online method.

Convergence of squared $\ell_2$-error over online rounds $t$ for OLin-LASSO compared to OS-LASSO baselines.

As shown in the figure above, OLin-LASSO exhibits consistent convergence as the number of online rounds increases, whereas OS-LASSO baselines tend to plateau. This demonstrates the superior statistical efficiency of the linearized approach in long-running streams.

Impact of initial batch size $t_0$ on final estimation error.

Furthermore, OLin-LASSO proves to be significantly more robust to the choice of the initial batch size. While OS-LASSO requires a relatively large $t_0$ to achieve low error, OLin-LASSO maintains high accuracy even with a small initial sample, highlighting its practical utility in data-scarce starts.

Conclusion

OLin-LASSO provides a robust and memory-efficient solution for high-dimensional sparse regression on streaming data. By decoupling the curvature requirement from the streaming updates, it achieves optimal convergence rates under relaxed assumptions. Future research may explore adaptive methods for determining the optimal initial batch size $t_0$ without prior knowledge of sparsity levels or data condition numbers.

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$-error of our estimator decays to zero at the optimal order of $\tilde \mathcal{O}(\frac{s}{\sqrt{t}})$, where $s$ is the sparsity level, $t$ is the streaming sample size, and $\tilde \mathcal{O}(\cdot)$ hides logarithmic terms. Numerical experiments demonstrate the practical efficiency of our algorithm.
BibTeX
@inproceedings{yang2023online,
  author = {Shuoguang Yang and Yuhao Yan and Xiuneng Zhu and Qiang Sun},
  title = {{Online Linearized LASSO}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=XmFN5LqynG},
}
Figure