Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint

Abstract

The ${\ell }_0$-constrained empirical risk minimization (${\ell }_0$-ERM) is a promising tool for high-dimensional statistical estimation. The existing analysis of ${\ell }_0$-ERM estimator is mostly on parameter estimation and support recovery consistency. From the perspective of statistical learning, another fundamental question is how well the ${\ell }_0$-ERM estimator would perform on unseen samples. The answer to this question is important for understanding the learnability of such a non-convex (and also NP-hard) M-estimator but still relatively under explored. In this paper, we investigate this problem and develop a generalization theory for ${\ell }_0$-ERM. We establish, in both white-box and black-box statistical regimes, a set of generalization gap and excess risk bounds for ${\ell }_0$-ERM to characterize its sparse prediction and optimization capability. Our theory mainly reveals three findings: 1) tighter generalization bounds can be attained by ${\ell }_0$-ERM than those of ${\ell }_2$-ERM if the risk function is (with high probability) restricted strongly convex; 2) tighter uniform generalization bounds can be established for ${\ell }_0$-ERM than the conventional dense ERM; and 3) sparsity level invariant bounds can be established by imposing additional strong-signal conditions to ensure the stability of ${\ell }_0$-ERM. In light of these results, we further provide generalization guarantees for the Iterative Hard Thresholding (IHT) algorithm which serves as one of the most popular greedy pursuit methods for approximately solving ${\ell }_0$-ERM. Numerical evidence is provided to confirm our theoretical predictions when implied to sparsity-constrained linear regression and logistic regression models.

References in corpus (12)

• Nearly unbiased variable selection under minimax concave penalty
• Nonconcave penalized likelihood with a diverging number of parameters
• High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity
• Strong oracle optimality of folded concave penalized estimation
• Optimization for deep learning: theory and algorithms
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Training Skinny Deep Neural Networks with Iterative Hard Thresholding Methods
• Data-Dependent Stability of Stochastic Gradient Descent
• Structured Sparsity and Generalization
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• Assumptionless consistency of the Lasso
• High Dimensional Classification through ${\ell }_0$-Penalized Empirical Risk Minimization