Search papers, labs, and topics across Lattice.
This paper addresses the challenges of online generalized sparse regression by introducing a framework that eliminates the need for dynamic regularization parameter tuning while ensuring computational efficiency. The authors develop an efficient online hard-thresholding algorithm that allows for closed-form updates and requires minimal storage, achieving global convergence at optimal statistical rates under realistic assumptions. Numerical experiments reveal that their approach consistently outperforms existing state-of-the-art methods, highlighting the benefits of overparameterization in this context.
Overparameterization in online sparse regression can lead to significant improvements in computational efficiency and statistical performance, challenging traditional optimization paradigms.
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.
