Title: A surprising connection between single-linkage, graphical lasso, sparse PCA, and other L1 penalized estimators
Authors: Vincent Vu - The Ohio State University (United States) [presenting]
Abstract: Statistical sufficiency formalizes the notion of data reduction. In the decision theoretic interpretation, once a model is chosen all inferences should be based on a sufficient statistic. However, suppose we start with a set of methods that share a sufficient statistic rather than a specific model. Is it possible to reduce the data beyond the statistic and yet still be able to compute all of the methods? We will present some progress towards a theory of ``computational sufficiency'' and show that strong reductions can be made for large classes of penalized M-estimators by exploiting hidden symmetries in the underlying optimization problems. These reductions can (1) enable efficient computation and (2) reveal hidden connections between seemingly disparate methods. As a main example, we will show how the theory provides a surprising answer to the following question: ``What do the Graphical Lasso, sparse PCA, single-linkage clustering, and L1 penalized Ising model selection all have in common?''