Collaborative Research: Connecting Submodularity and Restricted Strong Convexity

点击翻译按钮获取中文摘要

Structured estimation problems arise in a variety of contexts including astronomy, genomics, and computer vision. This project aims to develop methods that can use the additional structure in order to estimate statistical models effectively, while also using the structure for computational improvements. This work seeks to connect ideas in combinatorial optimization and statistical estimation to develop computationally tractable methods for performing structured statistical estimation.This project provides an integrated program to explore and connect combinatorial optimization and statistical estimation. Modern statistical challenges have become increasingly dependent on understanding both the computational and statistical issues. 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 project is to expand upon ideas that arise in combinatorial optimization and connect those algorithms and ideas to statistical questions. The research directions of this project are split into three main thrusts unified by the concept of weak submodularity: (a) cardinality constrained optimization and its applications to general statistical optimization problems; (b) matrix estimation problems including low-rank matrix estimation and semi-definite programming problems as well as problems in sparse dictionary learning; and (c) a general theoretical understanding of weak submodularity and specifically analyzing how to develop algorithms in this regime that work well for large-scale datasets.