Collaborative Research: Connecting Submodularity and Restricted Strong Convexity

结构化估计问题出现在各种背景下，包括天文学，基因组学和计算机视觉。该项目旨在开发可以使用附加结构的方法，以便有效地估计统计模型，同时还使用该结构进行计算改进。本项目旨在将组合优化和统计估计的思想结合起来，以开发计算上易于处理的方法来执行结构化统计估计。本项目提供了一个综合程序来探索和连接组合优化和统计估计。现代统计学的挑战越来越依赖于对计算和统计问题的理解。许多现代统计估计问题依赖于施加额外的结构，以减少统计的复杂性，并提供可解释性。不幸的是，这些结构通常是组合的性质，并导致计算上具有挑战性的问题。并行地，组合优化社区已经在开发能够以计算高效的方式近似地解决这样的优化问题的算法方面投入了大量的努力。这个项目的重点是扩展组合优化中出现的想法，并将这些算法和想法与统计问题联系起来。该项目的研究方向被划分为三个主要方向：（a）基数约束优化及其在一般统计优化问题中的应用，（B）矩阵估计问题，包括低秩矩阵估计和半定规划问题，以及稀疏字典学习问题，（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.