Stability and Risk Bounds of Iterative Hard Thresholding

DOI10.1109/TIT.2022.3170434MaRDI QIDQ6195697zbMATH OpenOpenAlexWikidataFDO

Authors Xiao-Tong Yuan, Ping Li

Publication date 14 March 2024

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.09413

zbMATH Keywords

Iterative Hard Thresholding (IHT)risk boundssparsitystatistical learning

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Stochastic programming (90C15) Nonconvex programming, global optimization (90C26) Applications of mathematical programming (90C90)

Abstract: In this paper, we analyze the generalization performance of the Iterative Hard Thresholding (IHT) algorithm widely used for sparse recovery problems. The parameter estimation and sparsity recovery consistency of IHT has long been known in compressed sensing. From the perspective of statistical learning, another fundamental question is how well the IHT estimation would predict on unseen data. This paper makes progress towards answering this open question by introducing a novel sparse generalization theory for IHT under the notion of algorithmic stability. Our theory reveals that: 1) under natural conditions on the empirical risk function over $n$ samples of dimension $p$, IHT with sparsity level $k$ enjoys an $mathcalildeO(n^{-1/2}sqrtklog(n)log(p))$ rate of convergence in sparse excess risk; 2) a tighter $mathcalildeO(n^{-1/2}sqrtlog(n))$ bound can be established by imposing an additional iteration stability condition on a hypothetical IHT procedure invoked to the population risk; and 3) a fast rate of order $mathcalildeOleft(n^{-1}k(lo{g}^3(n)+log(p))ight)$ can be derived for strongly convex risk function under proper strong-signal conditions. The results have been substantialized to sparse linear regression and sparse logistic regression models to demonstrate the applicability of our theory. Preliminary numerical evidence is provided to confirm our theoretical predictions.

This page was built for publication: Stability and Risk Bounds of Iterative Hard Thresholding

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