论文标题
高维双重稀疏结构$ \ ell_u（\ ell_q）$ - 球的最小值
Minimax Rates for High-dimensional Double Sparse Structure over $\ell_u(\ell_q)$-balls
论文作者
论文摘要
在本文中，我们着重于高维双稀疏结构，其中感兴趣的参数同时鼓励每组的小组稀疏性和元素的稀疏性。通过结合Gilbert-Varshamov Bounds及其变体，我们为参数空间的度量熵开发了一种新颖的下限技术，该技术专门针对$ \ ell_u（\ ell_q）$ - 带有$ u，Q \ in [0,1] $的双稀疏结构（\ ell_u（\ ell_q）$ - 球量身定制。我们利用信息理论方法证明了估计误差的下限，利用了我们提出的下限技术和Fano的不平等。为了补充下限，我们通过直接分析受约束最小二乘估计器的直接分析建立匹配的上限，并利用经验过程的结果。 A significant finding of our study is the discovery of a phase transition phenomenon in the minimax rates for $u,q \in (0, 1]$. Furthermore, we extend the theoretical results to the double sparse regression model and determine its minimax rate for estimation error. To tackle double sparse linear regression, we develop the DSIHT (Double Sparse Iterative Hard Thresholding) algorithm, demonstrating its optimality in the最小值，我们通过数值实验证明了我们方法的优越性。
In this paper, we focus on the high-dimensional double sparse structure, where the parameter of interest simultaneously encourages group-wise sparsity and element-wise sparsity in each group. 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,1]$. We prove lower bounds on the estimation error using an information-theoretic approach, leveraging our proposed lower bound 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 utilize results from empirical processes. A significant finding of our study is the discovery of a phase transition phenomenon in the minimax rates for $u,q \in (0, 1]$. Furthermore, we extend the theoretical results to the double sparse regression model and determine its minimax rate for estimation error. To tackle double sparse linear regression, we develop the DSIHT (Double Sparse Iterative Hard Thresholding) algorithm, demonstrating its optimality in the minimax sense. Finally, we demonstrate the superiority of our method through numerical experiments.
