PC Seminar: Using Approximate Message Passing to Analyze the Performance of High-dimensional Statistical Estimators

Abstract: Approximate message passing (AMP) is a class of e_cient algorithms that have been used for signal recovery in a number of statistics and engineering appli- cations. In this talk, we discuss how AMP can also be used a theoretical tool for characterizing the performance of such estimators in high dimensions. As a particular example, we will consider sorted L1 regularization, which has been incorporated into many methods for solving high-dimensional statistical estima- tion problems, including the SLOPE estimator in linear regression. We study how this regularization technique improves variable selection by characterizing the optimal SLOPE trade-o_ between measures of type I and type II error. Our proofs are based on a novel technique that reduces a variational calculus problem to a class of in_nite-dimensional convex optimization problems along with results from AMP theory. With SLOPE being a particular example, we discuss these results in the context of a general program for systematically de- riving exact expressions for the asymptotic risk of estimators that are solutions to a broad class of convex optimization problems via AMP. Collaborators on this work include Zhiqi Bu, Oliver Feng, Jason Klusowski, Richard Samworth, Weijie Su, Ramji Venkataramanan, Ruijia Wu.

This is a seminar in our seminar series on Probability and Combinatorics (PC).