CIF: Small: Taming Nonconvexity in High-Dimensional Statistical Estimation

当今科学和工程中的许多应用都需要对海量数据集进行有效的信息处理，以便提取关键信息和可操作的见解，以便进行可靠的决策。然而，即使拥有云计算的巨大能力，传统的统计算法在计算上也不可能处理和分析每天产生的海量数据。这种挑战的核心是“非凸性”的数学概念，它渗透到当代信息处理任务中。由于数据采集机制的高度复杂性，经典的统计估计器通常需要求解高度非凸的优化问题。目前的理论预测，在最坏的情况下，这样的任务可能很难解决，但像梯度下降这样的简单迭代算法每天都会被使用数千次来解决高度非凸的问题，并取得了显著的经验成功。理论和实践之间的巨大鸿沟需要弥合，这个项目的目标是通过开发新的理论来做到这一点，以便更好地解释和预测非凸优化算法的性能。这一新理论的影响将通过建立对非凸性的基本理解而感受到，并将提出新的方法来解决一些具有非凸性特征的困难的实际问题。本研究项目计划通过研究能够实现高效统计估计的低复杂性非凸优化方法来解决这些紧迫的挑战。其主要目标是通过统计和优化的新组合来揭开简单优化算法的不合理有效性的神秘面纱，提供对指导科学发现具有直接价值的可扩展的统计估计解决方案。具体地说，本研究项目的目标有四个：(1)理解为什么随机初始化足以解决重要的非凸统计问题；(2)理解为什么简单的优化算法即使在没有复杂的正则化的情况下也能保证工作；(3)研究如何在样本匮乏的情况下减少优化算法的不受欢迎的可变性；以及(4)研究简单谱方法的有效性和优点。该项目将开发的算法和技术将大大增强信号处理能力，超越最先进的方法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Many of today's applications in science and engineering require the efficient information processing of massive data sets in order to extract critical information and actionable insights for reliable decision making. Yet, even with the enormous power of cloud computing, it is computationally infeasible for classical statistical algorithms to process and analyze the massive amount of data generated daily. At the core of such challenges is the mathematical concept of 'non-convexity', that permeates contemporary information processing tasks. Due to the highly complex nature of data acquisition mechanisms, classical statistical estimators often require the solution of highly non-convex optimization problems. Current theory predicts that such tasks can be daunting to solve in the worst-case, yet simple iterative algorithms like gradient descent are used thousands of times every day to solve highly non-convex problems with remarkable empirical success. This huge gap between theory and practice needs to be bridged, and the goal of this project is to do so by developing new theory that better explains and predicts the performance of non-convex optimization algorithms. The impact of this new theory will be felt by virtue of creating a foundational understanding of non-convexity and will suggest novel ways to tackle some of the hard practical problems that feature non-convexity as well.This research project plans to address these pressing challenges by investigating low-complexity non-convex optimization methods that enable efficient statistical estimation. The main goal is to demystify the unreasonable effectiveness of simple optimization algorithms through a novel combination of ideas from statistics and optimization, offering scalable statistical estimation solutions that are of immediate value to guide scientific discovery. In particular, the objective of this research project is four-fold: (1) Understand why random initialization suffices for solving important non-convex statistical problems; (2) Understand why simple optimization algorithms are guaranteed to work even without sophisticated regularization; (3) Investigate how to reduce the undesired variability of optimization algorithms in the sample-starved regime; and (4) Study the effectiveness and benefits of simple spectral methods. The algorithms and techniques to be developed in this project will significantly enhance signal processing capabilities beyond the state-of-the-art methods.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.