CRII: CIF: Limits and Robustness of Nonconvex Low-Rank Estimation

CRII：CIF：非凸低秩估计的局限性和鲁棒性

• 批准号: 1657420
• 负责人: Yudong Chen
• 金额: $ 17.5万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-02-15 至 2020-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1657420&HistoricalAwards=false
• 关键词: CRII; CIF; Limits; Robustness; Nonconvex

The objective of this research is to significantly broaden the algorithms and theory for nonconvex low-rank estimation. Low-rank estimation problems are ubiquitous in science and engineering. Recently developed nonconvex methods promise great computational gains on large-scale datasets, but the algorithmic and theoretical foundation has not yet reached the same level of maturity as their convex counterpart. This research attacks this deficit in two research thrusts: pushing the limits of nonconvex methods for greater flexibility through a unified theoretical framework, and developing new algorithms robust to data corruption. To achieve greater flexibility and generality for the nonconvex approach, the investigator develops a new unifying paradigm that explains when and why nonconvex methods succeed. This is accomplished by a novel reinterpretation of various nonconvex methods through a two-step procedure. This flexible framework unifies several existing algorithms including gradient descent and alternating minimization, and opens the door for designing new algorithms. Theoretically this unified view allows for a decoupling of the statistical and optimization analysis. The investigator will explore the consequences of this approach by (a) providing a simpler and modular analysis of the convergence and statistical properties of existing algorithms, (b) studying the global behaviors of nonconvex methods and the role of initialization, and (c) designing new algorithms that are more efficient and general. The second thrust of this project studies the robustness of nonconvex methods. To protect against arbitrary corruption in data, the investigator designs new robust nonconvex formulations by viewing corruption as a superimposed structure and leveraging sparsity in the optimization objectives. This result will be further expanded through the use of nonsmooth nonconvex formulations and a complete rethinking of existing analytic techniques.

本研究的目的是显着拓宽非凸低秩估计的算法和理论。低秩估计问题在科学和工程中普遍存在。最近开发的非凸方法在大规模数据集上有很大的计算增益，但其算法和理论基础尚未达到与凸方法相同的成熟程度。本研究在两个研究方向上解决了这一缺陷：通过统一的理论框架推动非凸方法的极限以获得更大的灵活性，并开发对数据损坏具有鲁棒性的新算法。为了实现更大的灵活性和通用性的非凸方法，调查员开发了一个新的统一的范式，解释了何时以及为什么非凸方法成功。这是通过一个新的重新解释各种非凸方法，通过两个步骤的过程。这个灵活的框架统一了几个现有的算法，包括梯度下降和交替最小化，并打开了大门，设计新的算法。从理论上讲，这种统一的观点允许统计和优化分析的解耦。研究者将通过以下方式探索这种方法的后果：（a）对现有算法的收敛性和统计特性提供更简单和模块化的分析;（B）研究非凸方法的全局行为和初始化的作用;以及（c）设计更有效和更通用的新算法。这个项目的第二个重点是研究非凸方法的鲁棒性。为了防止数据中的任意腐败，调查员设计了新的强大的非凸公式，将腐败视为叠加结构，并利用稀疏性的优化目标。这一结果将进一步扩大通过使用非光滑非凸公式和现有的分析技术的一个完整的反思。

项目成果

Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly

通过 SDP 鲁棒地实现随机块模型中的贝叶斯错误率

• 发表时间: 2019
• 期刊: 32nd Annual Conference on Learning Theory
• 作者: Fei, Yingjie;Chen, Yudong
• 通讯作者: Chen, Yudong

Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression

二元线性回归混合的 EM 算法的全局收敛性

• 发表时间: 2019
• 期刊: 32nd Annual Conference on Learning Theory
• 作者: Kwon, Jeongyeol;Qian, Wei;Caramanis, Constantine;Chen, Yudong;Davis, Damek
• 通讯作者: Davis, Damek

Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning

• 发表时间: 2018-06
• 作者: Dong Yin;Yudong Chen;K. Ramchandran;P. Bartlett

Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly

通过 SDP 稳健地实现同步和块模型中的贝叶斯错误率

• DOI: 10.1109/tit.2020.2966438
• 发表时间: 2020
• 期刊: IEEE Transactions on Information Theory
• 影响因子: 2.5
• 作者: Fei, Yingjie;Chen, Yudong
• 通讯作者: Chen, Yudong

Global Convergence of Least Squares EM for Demixing Two Log-Concave Densities

用于分解两个对数凹密度的最小二乘EM的全局收敛性

• 发表时间: 2019
• 期刊: 33rd Conference on Neural Information Processing Systems (NeurIPS 2019
• 作者: Qian, Wei;Zhang, Yuqian;Chen, Yudong
• 通讯作者: Chen, Yudong