Relax-and-Sparsify Approximation Algorithms for Sparse Ridge Regression
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
| (14) |
| Algorithm 3 | Algorithm 4 | Greedy | Randomized | DIHT | Beam Search | |
| 0.134 | 0.104 | 0.007 | 0.369 | 0.064 | 0.424 | |
| 0.231 | 0.086 | 0.012 | 0.457 | 0.077 | 0.356 | |
| 2.799 | 0.089 | 0.017 | 0.545 | 0.097 | 0.390 |
| Dataset | Algorithm 3 | Algorithm 4 | Greedy | Randomized | DIHT | Beam Search |
| Breast Cancer | 97.114 | 0.505 | 0.033 | 1.005 | 0.187 | 0.541 |
| Lung Cancer | 215.449 | 0.878 | 0.067 | 1.572 | 0.340 | 0.780 |
| AML | 384.638 | 0.685 | 0.093 | 1.613 | 0.369 | 0.842 |
| Riboflavin | 6.314 | 0.478 | 0.027 | 0.848 | 0.155 | 0.476 |
| Leukemia | 23.533 | 0.247 | 0.026 | 0.829 | 0.133 | 0.443 |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Algorithm 2 | Algorithm 3 | Algorithm 4 | Greedy | Randomized | DIHT | Beam Search | |||||||||||
| Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | ||||
| 20 | - | - | 5.612 | 0.059 | 7.466 | 0.030 | 32.092 | 0.001 | 12.380 | 0.108 | 6.912 | 0.048 | 12.813 | 0.054 | |||
| 30 | - | - | 2.178 | 0.065 | 3.028 | 0.032 | 18.823 | 0.001 | 4.999 | 0.123 | 2.870 | 0.021 | 6.244 | 0.078 | |||
| 40 | - | - | 1.070 | 0.050 | 1.369 | 0.027 | 10.531 | 0.002 | 1.990 | 0.104 | 1.256 | 0.022 | 3.386 | 0.101 | |||
| 50 | - | - | 0.623 | 0.062 | 0.788 | 0.031 | 8.140 | 0.002 | 1.546 | 0.119 | 0.702 | 0.022 | 2.629 | 0.132 | |||
| 60 | - | - | 0.381 | 0.061 | 0.470 | 0.034 | 4.782 | 0.002 | 0.921 | 0.119 | 0.515 | 0.027 | 1.258 | 0.156 | |||
| Algorithm 2 | Algorithm 3 | Algorithm 4 | Greedy | Randomized | DIHT | Beam Search | |||||||||||
| Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | ||||
| 20 | - | - | 28.251 | 0.249 | 31.242 | 0.022 | 54.221 | 0.001 | 64.410 | 0.127 | 46.618 | 0.025 | 31.983 | 0.058 | |||
| 30 | - | - | 12.656 | 0.283 | 14.248 | 0.024 | 44.099 | 0.002 | 29.113 | 0.137 | 22.323 | 0.029 | 19.742 | 0.087 | |||
| 40 | - | - | 5.466 | 0.197 | 6.983 | 0.026 | 31.808 | 0.002 | 15.452 | 0.133 | 9.711 | 0.029 | 14.766 | 0.120 | |||
| 50 | - | - | 3.771 | 0.255 | 4.030 | 0.024 | 23.284 | 0.003 | 7.660 | 0.132 | 6.353 | 0.029 | 10.234 | 0.146 | |||
| 60 | - | - | 2.406 | 0.188 | 2.211 | 0.026 | 17.881 | 0.003 | 4.693 | 0.139 | 3.092 | 0.028 | 7.688 | 0.176 | |||
| Algorithm 2 | Algorithm 3 | Algorithm 4 | Greedy | Randomized | DIHT | Beam Search | |||||||||||
| Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | Avg. Gap | Avg. Time | ||||
| 20 | - | - | 47.095 | 1.843 | 52.120 | 0.017 | 69.529 | 0.002 | 130.949 | 0.167 | 86.689 | 0.031 | 47.393 | 0.058 | |||
| 30 | - | - | 27.880 | 4.292 | 30.984 | 0.020 | 51.137 | 0.003 | 75.290 | 0.169 | 54.805 | 0.031 | 33.681 | 0.095 | |||
| 40 | - | - | 15.204 | 5.431 | 19.632 | 0.021 | 45.616 | 0.004 | 44.510 | 0.190 | 29.024 | 0.030 | 27.969 | 0.229 | |||
| 50 | - | - | 8.654 | 3.455 | 9.879 | 0.023 | 33.994 | 0.004 | 20.883 | 0.160 | 16.499 | 0.031 | 21.866 | 0.135 | |||
| 60 | - | - | 6.257 | 3.031 | 7.237 | 0.022 | 27.294 | 0.005 | 16.141 | 0.156 | 11.220 | 0.032 | 15.504 | 0.192 | |||
| Dataset | Algorithm 2 | Algorithm 3 | Algorithm 4 | Greedy | Randomized | DIHT | Beam Search | |||||||||||
| Gap | Time | Gap | Time | Gap | Time | Gap | Time | Gap | Time | Gap | Time | Gap | Time | |||||
| Breast Cancer ( ) | 20 | 1 | 68 | - | - | 48.923 | 72.758 | 69.535 | 0.540 | 88.918 | 0.011 | 146.942 | 1.147 | 80.137 | 0.242 | 52.709 | 0.123 | |
| 30 | 5 | 72 | - | - | 28.983 | 417.290 | 36.155 | 0.932 | 72.178 | 0.014 | 82.095 | 0.919 | 53.605 | 0.183 | 38.756 | 0.199 | ||
| 40 | 16 | 68 | - | - | 22.449 | 70.364 | 20.117 | 0.941 | 57.329 | 0.018 | 65.396 | 0.922 | 36.776 | 0.190 | 33.170 | 0.305 | ||
| 50 | 25 | 68 | - | - | 15.083 | 110.645 | 13.372 | 0.925 | 51.779 | 0.024 | 35.141 | 0.869 | 35.870 | 0.179 | 30.446 | 0.387 | ||
| 60 | 33 | 71 | - | - | 10.110 | 114.122 | 12.642 | 0.929 | 44.194 | 0.029 | 19.358 | 1.144 | 14.553 | 0.174 | 22.985 | 0.441 | ||
Ridge Regression
Ridge regression uses an L2 penalty to stabilize least-squares prediction, especially with many, correlated, or noisy features.
See all 36 papers