Generalized Dantzig Selector: Application to the k-support norm
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. Thereafter, non-asymptotic high-probability bounds are established on the estimation error, which rely on Gaussian widths of the unit norm ball and the error set. 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.
The paper introduces a generalization of the Dantzig selector, where the L1/Linfinity norm pair are replaced with an arbitrary norm R and its dual, along with supporting statistical theory and an inexact ADMM.  The authors also provide detailed derivations of both proximal operators and statistical theory for the special case where R is the k-support norm.This is very nicely written paper on an interesting subject.  My only critical comment is that its motivation, beyond generalization for its own sake, is unclear.  Why do we need a generalized Dantzig selector when there are already many papers on penalized loss methods?  This is an important question, but I admit not completely fair to the authors---they're not alone in avoiding this question.  Some ways to address this question include comparisons on real data and simulations, and/or commentary on the computational complexity and practical differences between applying this method and some other penalized regression method.If we ignore the question of motivation and accept that a generalization of the Dantzig selector is worthwhile, then I believe that this work presents a significant advance in a very clearly written paper.  Aside from the Dantzig selector, the auxiliary results on implementing the ADMM algorithm, including derivation of the proximal operator for the k-support norm, are worthwhile on their own.Minor comment:Inequality (27) of Theorem 4 is is contained in Lemma 3.3 of Gordon et al. (2007) which is an even stronger result.  I believe that a bound similar to inequality (28) could also be derived using the results of Gordon et al. (2007).Gordon, Y., Litvak, A. E., Mendelson, S., & Pajor, A. (2007). Gaussian averages of interpolated bodies and applications to approximate reconstruction. Journal of Approximation Theory, 149(1), 59–73. doi:10.1016/j.jat.2007.04.007