Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low

References

• Aarts EH, Lenstra JK (1997) Local Search in Combinatorial Optimization (Princeton University Press, Princeton, NJ).Google Scholar
• Amini A, Kamilov US, Unser M (2012) The analog formulation of sparsity implies infinite divisibility and rules out Bernoulli-Gaussian priors. Proc. 2012 IEEE Inform. Theory Workshop (IEEE, Piscataway, NJ), 682–686.Google Scholar
• Atamturk A, Gomez A (2019) Rank-one convexification for sparse regression. Preprint, submitted January 29, https://arxiv.org/abs/1901.10334.Google Scholar
• Bartlett PL, Mendelson S, Neeman J (2012) ℓ1-regularized linear regression: Persistence and oracle inequalities. Probab. Theory Related Fields 154(1–2):193–224.Crossref, Google Scholar
• Bellec PC, Lecué G, Tsybakov AB (2018) Slope meets Lasso: Improved oracle bounds and optimality. Ann. Statist. 46(6B):3603–3642.Crossref, Google Scholar
• Belloni A, Chernozhukov V (2013) Least squares after model selection in high-dimensional sparse models. Bernoulli 19(2):521–547.Crossref, Google Scholar
• Belloni A, Chernozhukov V, Wang L (2014) Pivotal estimation via square-root Lasso in nonparametric regression. Ann. Statist. 42(2):757–788.Crossref, Google Scholar
• Bertsimas D, Weismantel R (2005) Optimization over Integers (Dynamic Ideas, Belmont, MA).Google Scholar
• Bertsimas D, King A, Mazumder R (2016) Best subset selection via a modern optimization lens. Ann. Statist. 44(2):813–852.Crossref, Google Scholar
• Bhadra A, Datta J, Li Y, Polson NG, Willard B (2019) Prediction risk for the horseshoe regression. J. Machine Learning Res. 20(1):2882–2920.Google Scholar
• Bickel P, Ritov Y, Tsybakov A (2009) Simultaneous analysis of Lasso and Dantzig selector. Ann. Statist. 37:1705–1732.Crossref, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Breiman L (1996) Heuristics of instability and stabilization in model selection. Ann. Statist. 24(6):2350–2383.Crossref, Google Scholar
• Bühlmann P, van-de-Geer S (2011) Statistics for High-Dimensional Data (Springer, Berlin).Crossref, Google Scholar
• Carvalho CM, Polson NG, Scott JG (2010) The horseshoe estimator for sparse signals. Biometrika 97(2):465–480.Crossref, Google Scholar
• Comminges L, Dalalyan AS (2012) Tight conditions for consistency of variable selection in the context of high dimensionality. Ann. Statist. 40(5):2667–2696.Crossref, Google Scholar
• Dalalyan AS, Hebiri M, Lederer J (2017) On the prediction performance of the Lasso. Bernoulli 23(1):552–581.Crossref, Google Scholar
• Fan Y, Lv J (2013) Asymptotic properties for combined L1 and concave regularization. Biometrika 101(1):57–70.Crossref, Google Scholar
• Frank I, Friedman J (1993) A statistical view of some chemometrics regression tools (with discussion). Technometrics 35(2):109–148.Crossref, Google Scholar
• Gamarnik D, Zadik I (2017) High dimensional regression with binary coefficients. estimating squared error and a phase transition. Proc. 2017 Conf. Learning Theory, PMLR 65:948–953.Google Scholar
• Greenshtein E (2006) Best subset selection, persistence in high-dimensional statistical learning and optimization under ℓ1 constraint. Ann. Statist. 34(5):2367–2386.Crossref, Google Scholar
• Greenshtein E, Ritov Y (2004) Persistence in high-dimensional linear predictor selection and the virtue of overparametrization. Bernoulli 10:971–988.Crossref, Google Scholar
• Hastie T, Tibshirani R, Tibshirani R (2020) Best subset, forward stepwise or Lasso? Analysis and recommendations based on extensive comparisons. Statist. Sci. 35(4):579–592.Google Scholar
• Hastie T, Mazumder R, Lee JD, Zadeh R (2015) Matrix completion and low-rank SVD via fast alternating least squares. J. Machine Learning Res. 16:3367–3402.Google Scholar
• Hazimeh H, Mazumder R (2020) Fast best subset selection: Coordinate descent and local combinatorial optimization algorithms. Oper. Res. 68(5):1517–1537.Google Scholar
• Hazimeh H, Mazumder R, Radchenko P (2021a) Grouped variable selection with discrete optimization: Computational and statistical perspectives. Ann. Statist. Preprint, submitted April 14, https://arxiv.org/abs/2104.07084.Google Scholar
• Hazimeh H, Mazumder R, Saab A (2021b) Sparse regression at scale: Branch-and-bound rooted in first-order optimization. Math. Programming, 1–42.Google Scholar
• Hoerl AE, Kennard R (1970) Ridge regression: Biased estimation for nonorthogonal problems. Technometrics 12:55–67.Crossref, Google Scholar
• Huang J, Breheny P, Lee S, Ma S, Zhang C (2016) The Mnet method for variable selection. Statist. Sinica 26:903–923.Google Scholar
• James W, Stein C (1961) Estimation with quadratic loss. Proc. Fourth Berkeley Sympos. Math. Statist. Probab., vol. 1 (University of California Press, Berkeley, CA), 361–379.Google Scholar
• Koltchinskii V, Lounici K, Tsybakov A (2011) Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. Ann. Statist. 39(5):2302–2329.Crossref, Google Scholar
• Koren Y, Bell R, Volinsky C (2009) Matrix factorization techniques for recommender systems. Comput. 42(8):30–37.Crossref, Google Scholar
• Lecué G, Mendelson S (2017) Sparse recovery under weak moment assumptions. J. Eur. Math. Soc. 19(3):881–904.Crossref, Google Scholar
• Linderoth JT, Lodi A (2010) MILP software. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (Wiley, New York).Google Scholar
• Liu Y, Wu Y (2007) Variable selection via a combination of the L0 and L1 penalties. J. Comput. Graphical Statist. 16(4):782–798.Crossref, Google Scholar
• Lounici K, Pontil M, Tsybakov A, Geer S (2011) Oracle inequalities and optimal inference under group sparsity. Ann. Statist. 39(4):2164–2204.Crossref, Google Scholar
• Martin R, Tang Y (2020) Empirical priors for prediction in sparse high-dimensional linear regression. J. Machine Learning Res. 21(144):1–30.Google Scholar
• Martin R, Mess R, Walker SG (2017) Empirical Bayes posterior concentration in sparse high-dimensional linear models. Bernoulli 23(3):1822–1847.Crossref, Google Scholar
• Mazumder R, Radchenko P (2017) The discrete Dantzig selector: Estimating sparse linear models via mixed integer linear optimization. IEEE Trans. Inform. Theory 63(5):3053–3075.Google Scholar
• Meinshausen N (2007) Relaxed Lasso. Comput. Statist. Data Anal. 52(1):374–393.Crossref, Google Scholar
• Miller A (2002) Subset Selection in Regression (CRC Press, Boca Raton, FL).Crossref, Google Scholar
• Mitchell TJ, Beauchamp JJ (1988) Bayesian variable selection in linear regression. J. Amer. Statist. Assoc. 83(404):1023–1032.Crossref, Google Scholar
• Mladenović N, Hansen P (1997) Variable neighborhood search. Comput. Oper. Res. 24(11):1097–1100.Crossref, Google Scholar
• Natarajan B (1995) Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2):227–234.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1999) Integer Programming and Combinatorial Optimization (Wiley, New York).Google Scholar
• Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course (Springer, Boston).Crossref, Google Scholar
• Nesterov Y (2013) Gradient methods for minimizing composite functions. Math. Programming 140(1):125–161.Crossref, Google Scholar
• Polson NG, Sun L (2019) Bayesian ℓ0-regularized least squares. Appl. Stochastic Models Bus. Indust. 35(3):717–731.Crossref, Google Scholar
• Raskutti G, Wainwright M, Yu B (2011) Minimax rates of estimation for high-dimensional linear regression over-balls. IEEE Trans. Inform. Theory 57(10):6976–6994.Crossref, Google Scholar
• Rigollet P, Tsybakov A (2011) Exponential screening and optimal rates of sparse estimation. Ann. Statist. 39(2):731–771.Crossref, Google Scholar
• Rocková V, George EI (2018) The spike-and-slab Lasso. J. Amer. Statist. Assoc. 113(521):431–444.Crossref, Google Scholar
• Soussen C, Idier J, Brie D, Duan J (2011) From Bernoulli–Gaussian deconvolution to sparse signal restoration. IEEE Trans. Signal Processing 59(10):4572–4584.Crossref, Google Scholar
• Sun T, Zhang C-H (2012) Scaled sparse linear regression. Biometrika 99(4):879–898.Crossref, Google Scholar
• Tibshirani R (1996) Regression shrinkage and selection via the lasso. J. Royal Statist. Soc. B 58:267–288.Crossref, Google Scholar
• Verzelen N (2012) Minimax risks for sparse regressions: Ultra-high dimensional phenomenons. Electron. J. Statist. 6:38–90.Crossref, Google Scholar
• Vielma JP, Dunning I, Huchette J, Lubin M (2017) Extended formulations in mixed integer conic quadratic programming. Math. Program. Comput. 9:369–418.Crossref, Google Scholar
• Wainwright MJ (2009) Sharp thresholds for high-dimensional and noisy recovery of sparsity using ℓ1-constrained quadratic programming. IEEE Trans. Inform. Theory 55(5):2183–2202.Crossref, Google Scholar
• Weng H, Feng Y, Qiao X (2019) Regularization after retention in ultrahigh dimensional linear regression models. Statist. Sinica 29(1):387–407.Google Scholar
• Zhang C-H, Zhang T (2012) A general theory of concave regularization for high-dimensional sparse estimation problems. Statist. Sci. 27(4):576–593.Crossref, Google Scholar
• Zhang Y, Wainwright MJ, Jordan MI (2017) Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators. Electron. J. Statist. 11(1):752–799.Crossref, Google Scholar
• Zou H, Hastie T (2005) Regularization and variable selection via the elastic net. J. Royal Statist. Soc. B 67(2):301–320.Crossref, Google Scholar
• Zou H, Zhang HH (2009) On the adaptive elastic-net with a diverging number of parameters. Ann. Statist. 37(4):1733–1751.Crossref, Google Scholar