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

CIF：小：具有粗略非凸目标的学习和估计：基本限制和高效算法

• 批准号: 2006489
• 负责人: Andrea Montanari
• 金额: $ 33万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-08-01 至 2023-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2006489&HistoricalAwards=false
• 关键词: CIF; Small; Learning; estimation; rough

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.

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

项目成果

High-Dimensional Projection Pursuit: Outer Bounds and Applications to Interpolation in Neural Networks

高维投影追踪：神经网络插值的外界和应用

• 发表时间: 2022
• 期刊: Proceedings of Machine Learning Research
• 作者: Kangjie Zhou, Andrea Montanari

Algorithmic thresholds in mean field spin glasses

平均场自旋玻璃的算法阈值

• 发表时间: 2021
• 期刊: The annals of probability
• 作者: Alaoui, AE;Montanari, A;Sellke, M
• 通讯作者: Sellke, M

Optimization of the Sherrington--Kirkpatrick Hamiltonian

Sherrington--Kirkpatrick 哈密顿量的优化

• DOI: 10.1137/20m132016x
• 发表时间: 2021
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Montanari, Andrea

Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization

• DOI: 10.1109/focs54457.2022.00038
• 发表时间: 2022-03
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: A. Alaoui;A. Montanari;Mark Sellke

An Information-Theoretic View of Stochastic Localization

• DOI: 10.1109/tit.2022.3180298
• 发表时间: 2021-09
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Ahmed El Alaoui;A. Montanari