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

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

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.