Collaborative Research: Connecting Submodularity and Restricted Strong Convexity

结构化估计问题出现在各种环境中，包括天文学、基因组学和计算机视觉。该项目旨在开发可以使用附加结构的方法，以便有效地估计统计模型，同时也使用该结构进行计算改进。这项工作旨在将组合优化和统计估计中的思想联系起来，以开发执行结构化统计估计的计算简便方法。本课题提供了一个探索组合优化与统计估计相结合的综合方案。现代统计挑战越来越依赖于对计算和统计问题的理解。许多现代统计估计问题依赖于强加额外的结构，以减少统计复杂性和提供可解释性。不幸的是，这些结构通常在本质上是组合的，并导致计算上具有挑战性的问题。与此同时，组合优化社区已经投入了大量的精力来开发能够以计算效率的方式近似解决此类优化问题的算法。这个项目的重点是扩展在组合优化中出现的想法，并将这些算法和想法与统计问题联系起来。本课题的研究方向由弱子模块化的概念统一为三个主要方向：(a)基数约束优化及其在一般统计优化问题中的应用；(b)矩阵估计问题，包括低秩矩阵估计和半定规划问题以及稀疏字典学习问题；(c)对弱子模块化的一般理论理解，并具体分析如何在该机制下开发适用于大规模数据集的算法。

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.