Connections between structured estimation and weak submodularity
February 2 @ 11:00 am - 12:00 pm
Sahand Negahban (Yale University)
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.