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 withnobservations,ppredictors, and an unknowns∗-sparse signal β∗∈ Rpcorrupted 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{i:β∗i̸=0}|β∗i| ≥ Cσ(logp/n)1/2, 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, 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.

In this paper, we focus our attention on the high-dimensional double sparse linear regression, that is, a combination of element-wise and group-wise sparsity. To address this problem, we propose an IHT-style (iterative hard thresholding) procedure that dynamically updates the threshold at each step. We establish the matching upper and lower bounds for parameter estimation, showing the optimality of our proposal in the minimax sense. More importantly, we introduce a fully adaptive optimal procedure designed to address unknown sparsity and noise levels. Our adaptive procedure demonstrates optimal statistical accuracy with fast convergence. Additionally, we elucidate the significance of the element-wise sparsity level $s_0$ as the trade-off between IHT and group IHT, underscoring the superior performance of our method over both. Leveraging the beta-min condition, we establish that our IHT-style procedure can attain the oracle estimation rate and achieve almost full recovery of the true support set at both the element level and group level. Finally, we demonstrate the superiority of our method by comparing it with several state-of-the-art algorithms on both synthetic and real-world datasets.

In this paper, we focus on the high-dimensional double sparse structures, where the parameter of interest simultaneously encourages group-wise and element-wise sparsity. By combining the Gilbert-Varshamov bound and its variants, we develop a novel lower bound technique for the metric entropy of the parameter space, specifically tailored for the double sparse structure over$\ell _{u}(\ell _{q})$-balls with$u,q \in [0,2$). We give lower bounds on the estimation error using an information-theoretic approach, leveraging the proposed technique and Fano’s inequality. To complement the lower bounds, we establish matching upper bounds through a direct analysis of constrained least-squares estimators and utilizing results from empirical processes. A significant discovery is that a phase transition phenomenon exists on the minimax rates for$u,q \in (0, 2)$. Furthermore, we extend the theoretical findings to the double sparse regression models and determine the minimax rates for estimation error. A novel Double Sparse Iterative Hard Thresholding (DSIHT) procedure is developed, with minimax optimality guaranteed. Finally, we demonstrate the superiority of the proposed method through numerical experiments.