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

Publication date 20 January 2020

Abstract: The

e l l_{0}

-constrained empirical risk minimization (

e l l_{0}

-ERM) is a promising tool for high-dimensional statistical estimation. The existing analysis of

e l l_{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

e l l_{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

e l l_{0}

-ERM. We establish, in both white-box and black-box statistical regimes, a set of generalization gap and excess risk bounds for

e l l_{0}

-ERM to characterize its sparse prediction and optimization capability. Our theory mainly reveals three findings: 1) tighter generalization bounds can be attained by

e l l_{0}

-ERM than those of

e l l_{2}

-ERM if the risk function is (with high probability) restricted strongly convex; 2) tighter uniform generalization bounds can be established for

e l l_{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

e l l_{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

e l l_{0}

-ERM. Numerical evidence is provided to confirm our theoretical predictions when implied to sparsity-constrained linear regression and logistic regression models.

This page was built for publication: Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333184)