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 的法定使命，并通过使用基金会的智力优势和更广泛的影响进行评估，被认为值得支持审查标准。

项目成果

Bridging convex and nonconvex optimization in robust PCA: Noise, outliers and missing data

在稳健的 PCA 中桥接凸优化和非凸优化：噪声、异常值和缺失数据

• DOI: 10.1214/21-aos2066
• 发表时间: 2021-10
• 期刊: The Annals of Statistics
• 作者: Chen, Yuxin;Fan, Jianqing;Ma, Cong;Yan, Yuling
• 通讯作者: Yan, Yuling

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

具有梯度跟踪和方差减少的网络中通信高效的分布式优化

• 发表时间: 2020-01
• 期刊: Journal of machine learning research
• 影响因子: 6
• 作者: Li, Boyue;Cen, Shicong;Chen, Yuxin;Chi, Yuejie
• 通讯作者: Chi, Yuejie

Nonconvex Low-Rank Symmetric Tensor Completion from Noisy Data

来自噪声数据的非凸低秩对称张量补全

• 发表时间: 2019-12
• 期刊: Advances in neural information processing systems
• 作者: Cai, Changxiao;Li, Gen;Poor, H. Vincent;Chen, Yuxin
• 通讯作者: Chen, Yuxin

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

非凸张量完成的不确定性量化：置信区间、异方差和最优性

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

Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality

非凸张量完成的不确定性量化：置信区间、异方差和最优性

• 发表时间: 2020-01
• 期刊: International Conference on Machine Learning
• 作者: Cai, Changxiao;Poor, H. Vincent;Chen, Yuxin
• 通讯作者: Chen, Yuxin