Generalized Dantzig Selector: Application to the k-support norm

Abstract

We propose a Generalized Dantzig Selector (GDS) for linear models, in which any norm encoding the parameter structure can be leveraged for estimation. We investigate both computational and statistical aspects of the GDS. Based on conjugate proximal operator, a flexible inexact ADMM framework is designed for solving GDS, and non-asymptotic high-probability bounds are established on the estimation error, which rely on Gaussian width of unit norm ball and suitable set encompassing estimation error. Further, we consider a non-trivial example of the GDS using $k$-support norm. We derive an efficient method to compute the proximal operator for $k$-support norm since existing methods are inapplicable in this setting. For statistical analysis, we provide upper bounds for the Gaussian widths needed in the GDS analysis, yielding the first statistical recovery guarantee for estimation with the $k$-support norm. The experimental results confirm our theoretical analysis.

Updates to bound

References in corpus (4)

• Simultaneous analysis of Lasso and Dantzig selector
• Bregman Alternating Direction Method of Multipliers
• Estimation with Norm Regularization
• New Perspectives on k-Support and Cluster Norms

Cited by in corpus (4)

• Theory-guided Data Science: A New Paradigm for Scientific Discovery from Data
• The Dantzig selector: Recovery of Signal via ${\ell }_1-\alpha {\ell }_2$ Minimization
• Fast Saddle-Point Algorithm for Generalized Dantzig Selector and FDR Control with the Ordered l1-Norm
• New Computational and Statistical Aspects of Regularized Regression with Application to Rare Feature Selection and Aggregation