math.OCNov 15, 2026

Relax-and-Sparsify Approximation Algorithms for Sparse Ridge Regression

Authors: Shixuan Yi, Yongchun Li

Organizations: School of Data Science, The Chinese University of Hong Kong, Shenzhen

Abstract

This paper studies sparse ridge regression in the low-rank, high-dimensional setting that often arises when data collection is expensive. By exploiting the low-rank structure, we develop approximation algorithms within a relax-and-sparsify framework: solve a convex relaxation and then sparsify its solution to satisfy the original sparsity constraint. Specifically, we establish a tight rank-dependent sparsity bound for the convex relaxation by decomposing its support into two parts. This decomposition in turn motivates two approximation strategies, parameter reduction and binary redistribution, each exploiting a different part. Experiments on synthetic and real datasets show that the binary redistribution algorithms outperform the benchmarks in most instances.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Jun 26, 2023

Efficient Cross-Validation for Sparse Linear Regression

Given a high-dimensional covariate matrix and a response vector, ridge-regularized sparse linear regression selects a subset of features that explains the relationship between covariates and the response in an interpretable manner. To choose hyperparameters that control the sparsity level and amount of regularization, practitioners commonly use k-fold cross-validation. However, cross-validation substantially increases the computational cost of sparse regression as it requires solving many mixed-integer optimization problems (MIOs) for each hyperparameter combination. To address this computational burden, we derive computationally tractable relaxations of the k-fold cross-validation loss, facilitating hyperparameter selection while solving 5050--80%80\% fewer MIOs in practice. Our computational results demonstrate, across eleven real-world UCI datasets, that exact MIO-based cross-validation can be competitive with mature software packages such as glmnet and L0Learn.
Oct 7, 2026

D-SLR: The Disjoint Row-Sparse plus Low-Rank Decomposition

Compressing a matrix for reconstruction still defaults to the truncated SVD, approximating the data with a single low-rank structure. It is common to reduce the residual further by adding an overlapping row-sparse component, but methods that solve this joint problem often require iterative solvers and tuning of regularization parameters. We propose the Disjoint Row-Sparse plus Low-Rank (D-SLR) decomposition, a closed-form drop-in for the truncated SVD that improves or exactly matches it. D-SLR restricts rows to either being stored verbatim or approximated by the low-rank fit, never both. Under squared error this restriction costs nothing: the joint optimum is attainable disjointly with fewer parameters at every non-trivial rank and stored row count (shape). With zero stored rows D-SLR reduces to the truncated SVD, so it never does worse at equal cost. The algorithm scores the entire error-versus-parameters tradeoff, and the solution is chosen afterwards by a supplied error target or parameter count, or by a selection rule. The grid and solution together cost three SVDs, with no tuning or regularization. We derive an assumption-free, a-posteriori lower bound on the error at every shape, giving each solution a computable certificate on the potential gain of any other choice of rank and stored rows. Experiments on synthetic and real data (LLM embedding tables, network traffic, hyperspectral images) confirm the gains and quantify the certificate.
Jul 7, 2026

The Regularization Parameter: Sparse Precision Matrix Estimation

Sparse precision matrix estimation provides an interpretable and computationally efficient framework for modeling conditional dependencies in high-dimensional, low-sample-size data. A recurring challenge is appropriately selecting the regularization parameter that controls estimator sparsity and strikes a balance between underfitting and overfitting. We propose a closed-form, matrix-valued regularization parameter derived from the sampling distribution of the first-order optimality conditions of the ℓ1\ell_1-regularized Gaussian maximum-likelihood estimator. By prescribing the probability that each nonzero entry of the estimator satisfies its optimality condition under resampling, we eliminate the need for cross-validation. The resulting regularization parameter is shown to attain asymptotic scaling properties that, under standard conditions, provide consistency and sparsistency of the estimator. On synthetic Gaussian and non-Gaussian datasets, as well as real-world gene microarray and neuroimaging applications, the proposed approach achieves estimation accuracy comparable to cross-validation, delivers superior support recovery, and reduces runtime by several orders of magnitude.