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

CIF：小：驯服高维统计估计中的非凸性

• 批准号: 1907661
• 负责人: Yuxin Chen
• 金额: $ 50万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1907661&HistoricalAwards=false
• 关键词: CIF; Small; Taming; Nonconvexity; Dimensional

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.

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

项目成果

Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence

• DOI: 10.1137/21m1456789
• 发表时间: 2021-05
• 期刊: ArXiv
• 作者: Wenhao Zhan;Shicong Cen;Baihe Huang;Yuxin Chen;Jason D. Lee;Yuejie Chi

Inference and uncertainty quantification for noisy matrix completion

• DOI: 10.1073/pnas.1910053116
• 发表时间: 2019-11-12
• 期刊: PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA
• 影响因子: 11.1
• 作者: Chen, Yuxin;Fan, Jianqing;Yan, Yuling
• 通讯作者: Yan, Yuling

Uncertainty Quantification for Nonconvex Tensor Completion: Confidence Intervals, Heteroscedasticity and Optimality

• DOI: 10.1109/tit.2022.3205781
• 发表时间: 2020-06
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Changxiao Cai;H. Poor;Yuxin Chen

Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction

• 发表时间: 2019-09
• 期刊: J. Mach. Learn. Res.
• 作者: Boyue Li;Shicong Cen;Yuxin Chen;Yuejie Chi

Nonconvex Low-Rank Symmetric Tensor Completion from Noisy Data

• 发表时间: 2019-11
• 期刊: ArXiv
• 作者: Changxiao Cai;Gen Li;H. Poor;Yuxin Chen