Estimating Double Sparse Structures Over ℓ_u(ℓ_q) -Balls: Minimax Rates and Phase Transition

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ell _{u}(\ell _{q})$ </tex-math></inline-formula>-balls with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$u,q \in [0,2$ </tex-math></inline-formula>). 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$u,q \in (0, 2)$ </tex-math></inline-formula>. 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.