Rethinking Hard Thresholding Pursuit: Full Adaptation and Sharp Estimation

2025/01/05 by Zhang, Yanhang, Li, Zhifan, Liu, Shixiang +2 · 1 citation
#FOS: Mathematics #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.2501.02554

Abstract

Hard Thresholding Pursuit (HTP) has aroused increasing attention for its robust theoretical guarantees and impressive numerical performance in non-convex optimization. In this paper, we introduce a novel tuning-free procedure, named Full-Adaptive HTP (FAHTP), that simultaneously adapts to both the unknown sparsity and signal strength of the underlying model. We provide an in-depth analysis of the iterative thresholding dynamics of FAHTP, offering refined theoretical insights. In specific, under the beta-min condition min_{i ∈ S^*}|\boldsymbolβ^*_i| ≥ Cσ(log p/n)^1/2, we show that the FAHTP achieves oracle estimation rate σ(s^*/n)^1/2, 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, our method 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.

Cited by

• Sparse Polyak: an adaptive step size rule for high-dimensional M-estimation

Related

• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• Modified Hard Thresholding Pursuit with Regularization Assisted Support Identification
• Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime
• Sparse Convex Optimization via Adaptively Regularized Hard Thresholding
• Scaled minimax optimality in high-dimensional linear regression: A non-convex algorithmic regularization approach