Georgia Institute of Technology College of Sciences

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.

The linear programming discriminant(LPD) estimator is used in sparse linear discriminant analysis for high dimensional classification problems. In this talk we will give a sufficient condition for the variable selection property of the LPD estimator and our result provides optimal bound on the requirement of sample size $n$ and magnitude of components of Bayes direction.

We present a framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning. The framework is based on defining a restricted class of algorithms, called statistical algorithms, that instead of directly accessing samples from the input distribution can only obtain an estimate of the expectation of any given function on the input distribution. Our definition captures many natural algorithms used in theory and practice, e.g., moment-based methods, local search, linear programming, MCMC and simulated annealing. Our techniques are inspired by the statistical query model of Kearns from learning theory, which addresses the complexity of PAC-learning. For specific well-known problems over distributions, we obtain lower bounds on the complexity of any statistical algorithm. These include an exponential lower bounds for moment maximization and a nearly optimal lower bound for detecting planted clique distributions when the planted clique has size n^{1/2-\delta} for any constant \delta > 0. Variants of the latter problem have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness. This is joint work with V. Feldman, E. Grigorescu, L. Reyzin and Y. Xiao.