Rethinking Hard Thresholding Pursuit: Full Adaptation and Sharp Estimation

Hard Thresholding Pursuit (HTP) has aroused increasing attention for its robust theoretical guarantees and impressive numerical performance in non-convex optimization. This paper consider a high-dimensional linear regression model with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> observations, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> predictors, and an unknown <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">s</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup>-sparse signal β<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup> ∈ R<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">^p</i> corrupted by noise of magnitude σ.We introduce a novel tuning-free procedure, namely Full-Adaptive HTP (FAHTP), that simultaneously adapts to both the unknown sparsity and signal strength of the underlying model. Our theoretical analysis rigorously characterizes the iterative thresholding dynamics of FAHTP, offering refined theoretical insights. In specific, under the beta-min condition min<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">{<i>i</i>:β^∗<i>_i</i> ̸=0}</sub> |β<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">_i</i> | ≥ Cσ(log <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i>/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>)<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2</sup>, FAHTP achieves oracle estimation rate σ(s<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup>/<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>)<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2</sup>, highlighting its theoretical superiority over convex competitors such as LASSO and SLOPE, and recovers the true support set exactly. More importantly, even without the beta-min condition, FAHTP achieves a tighter error bound than the classical minimax rate with high probability. The comprehensive numerical experiments substantiate our theoretical findings, underscoring the effectiveness and robustness of the proposed FAHTP.