May 12

3:30 pm

## Inference in High-Dimensional Settings: Trade-offs Between Computational and Statistical Efficiency

### Martin Wainwright

Seminar

University of California, Berkeley - Department of Statistics

Many problems in contemporary scientific and engineering applications have a high-dimensional nature, meaning that the model dimension is comparable to or larger than the sample size. This talk considers questions of two types concerning high-dimensional inference. First, given a practical (polynomial-time) algorithm, what are the statistical limitations of its performance? Second, how do such practical limitations compare to information-theoretic bounds, which apply to the performance of any algorithm regardless of its computational complexity?

We analyze these issues in high-dimensional versions of two canonical inference problems: (a) subset selection in linear regression; and (b) model selection in discrete Markov random fields. We begin analyzing simple polynomial-time methods based on convex relaxations:

L1 constrained quadratic programming (Lasso) for sparse regression, and L1-regularized logistic regression for graphical model selection. We provide conditions on the sample size n that controls the success/failure of these methods as a function of the problem size p, and the sparsity index k. Using information-theoretic methods, we prove that these algorithms are order-optimal in certain regimes (meaning that no other algorithm can perform substantially better), but sub-optimal in others.

Based on joint works with John Lafferty, Kannan Ramchandran, Pradeep Ravikumar, Prasad Santhanam, Wei Wang.