Cindy Rush (Columbia University)

Title: Algorithmic Analysis of SLOPE via Approximate Message Passing
Abstract: SLOPE is a relatively new convex optimization procedure for high-dimensional linear regression via the sorted L1 penalty: the larger the rank of the fitted coefficient, the larger the penalty. This non-separable penalty renders many existing techniques invalid or inconclusive in analyzing the SLOPE solution. In recent work, we use approximate message passing or AMP to provably solve the SLOPE problem in the regime of linear sparsity under Gaussian random designs. This algorithmic approach allows one to approximate the SLOPE solution via the much more amenable AMP iterates, and a consequence of this analysis is an asymptotically exact characterization of the SLOPE solution. Explicitly, we demonstrate that one can characterize the asymptotic dynamics of the AMP iterates by employing a recently developed state evolution analysis for non-separable penalties, thereby overcoming the difficulty caused by the sorted L1 penalty. We will further discuss how the exact asymptotic analysis allows one to analyze properties of the estimator like tradeoffs between Type I and Type II errors. This is joint work with Zhiqi Bu, Jason Klusowski, and Weijie Su.

Erik Waingarten (Stanford University)

Title: Fast Approximations for High Dimensional EMD
Abstract: The Earth Mover's Distance is a geometric min-cost matching problem. We receive two sets of s vectors in Σ^d which implicitly define a complete bipartite graph with edge costs given by distances. The task is to compute the minimum cost matching. We give a new analysis of an old algorithm, improving the approximation from O(log(s) log(d)) to Õ(log s). The plan is to give a broad overview of the problem and a sketch of the new analysis. This is joint work with Xi Chen, Rajesh Jayaram, and Amit Levi.