Connections between structured estimation and weak submodularity

Abstract:  Many modern statistical estimation problems rely on imposing additional structure in order to reduce the statistical complexity and provide interpretability. Unfortunately, these structures often are combinatorial in nature and result in computationally challenging problems. In parallel, the combinatorial optimization community has placed significant effort in developing algorithms that can approximately solve such optimization problems in a computationally efficient manner. The focus of this talk is to expand upon ideas that arise in combinatorial optimization and connect those algorithms and ideas to statistical questions. We will discuss three main vignettes: Cardinality constrained optimization; low-rank matrix estimation problems; and greedy estimation of sparse fourier components.

Biography:  Professor Negahban is currently an Assistant Professor in the Department of Statistics at Yale University.  Prior to that he worked with Professor Devavrat Shah at MIT as a postdoc and Prof. Martin J. Wainwright at UC Berkeley as a graduate student.