CIF: Small: Learning and estimation with rough non-convex objectives: Fundamental limits and efficient algorithms

信号处理、统计和机器学习中的大量问题需要最小化一个具有许多未知变量的代价函数。在一般情况下，这项任务在计算上是困难的，除非成本函数具有称为凸性的数学性质，这种情况在过去50年里吸引了大量的工作。另一方面，现代应用程序通常依赖于更复杂的非凸公式，这些公式使用简单的算法进行优化，这些算法不一定是最优的。这个项目探索的假设是，对于一大类非凸成本函数，人们可以在这些函数的典型实例中找到最优解，即使最坏的情况可能不可能优化。研究结果将影响到所有以非凸成本函数为特征的科学领域和现实世界的问题。本项目的目的是研究‘Mean-field’型成本函数的概率模型，即它们不具有潜在的低维结构。这种设置在高维统计和机器学习中非常常见：每个自由度都有可能与其他自由度相互作用(或不相互作用)。最近，通过开发新的算法来实现期望的优化目标，在特殊情况下建立了子层集的几何和可处理性之间的猜想联系。这些算法基于消息传递思想和自由能近似。该项目在更广泛的领域开发这些新方法，并调查它们适用的精确条件。此外，它还开发了潜在的替代方案和改进措施。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

A large number of problems in signal processing, statistics and machine learning require minimizing a cost function with many unknown variables. In a general setting, this task is computationally hard, unless the cost function has the mathematical property called convexity, a case that has attracted a large amount of work over the last fifty years. On the other hand, modern applications often rely on the more complex non-convex formulations, which are optimized using simple algorithms that are not necessarily optimal. This project explores the hypothesis that, for a broad class of non-convex cost functions, one can find optimal solutions in the typical instances of these functions, even if the worst case might be impossible to optimize. The outcomes will have impacts on all scientific fields and real-world problems that feature non-convex cost functions.This project aims at studying probabilistic models of cost functions that are of `mean-field' type, namely they do not have a latent low-dimensional structure. This setting is quite common in high-dimensional statistics and machine learning: Each degree of freedom is equally likely to interact (or not) with every other one. The conjectured connection between the geometry of sublevel sets and tractability was recently established in special cases by developing new algorithms that achieve the desired optimization goal. These algorithms are based on message passing ideas and free energy approximations. This project develops these new methods in a broader domain and investigates precise conditions for their applicability. Furthermore, it develops potential alternatives and improvements.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.