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

Cornell University, Ithaca NY

Investigators

Abstract

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.