Minimax Rates for High-dimensional Double Sparse Structure over \ell_u(\ell_q)-balls

arXiv2207.11888MaRDI QIDQ6405893FDOQ6405893

Authors: Z. F. Li, Yanhang Zhang, Jianxing Yin 

Publication date: 24 July 2022

Abstract: 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. Combining Gilbert-Varshamov bound and its variants, we develop a novel lower bound technique for the metric entropy of the parameter space, which is well suited for the double sparse structure over $el{l}_q$-balls for $qin[0,1]$. We prove the lower bounds on estimation error in an information theoretical manner, which is based on our proposed lower bound technique and Fano's inequality. The matching upper bounds are also established, whose proof follows from a direct analysis of the constrained least-squares estimators and results on empirical processes. Moreover, we extend the results over $el{l}_q$-balls into the double sparse regression model and establish its minimax rate on the estimation error. Finally, we develop the DSIHT (Double Sparse Iterative Hard Thresholding) algorithm and show its optimality in the minimax sense for solving the double sparse linear regression.

This page was built for publication: Minimax Rates for High-dimensional Double Sparse Structure over $\ell_u(\ell_q)$-balls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405893)