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

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

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

Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization

• DOI: 10.1287/opre.2021.2151
• 发表时间: 2020-07
• 期刊: ArXiv
• 作者: Shicong Cen;Chen Cheng;Yuxin Chen;Yuting Wei;Yuejie Chi