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.