Theory-Driven Solutions to Robust and Non-Convex Data Science Problems

University Of Minnesota-Twin Cities, Minneapolis MN

Investigators

Abstract

Many solutions to data science problems are based on non-convex optimization. Recent surprising theoretical and empirical results have shown that directly solving non-convex problems can yield computationally efficient, high-accuracy algorithms. This has spurred the expanding body of work on the analysis of non-convex algorithms for a variety of structured data problems. One class of these is robust recovery problems, which aim to recover a hidden structure in corrupted data. While robustness is a classical theme in mathematical statistics, computationally efficient methods with guaranteed accuracy for high levels of corruption have not been widely studied. Non-convex minimization methods indicate the potential to obtain competitive speed and accuracy for such problems, as was already demonstrated by the PI and his collaborators on the problem of robust subspace recovery. The research work aims to further establish and extend such guarantees to many other robust recovery problems whose solutions are crucial for modern applied problems. Applications include the problem of three-dimensional reconstruction from a set of two-dimensional images. The PI and his collaborators aim to develop robust theory and algorithms for truly challenging non-convex recovery problems. These recovery problems are typically NP-hard with highly complex energy landscapes. However, these landscapes often exhibit special structure that seems to allow for recovery under certain adversarial settings and recovery with high probability under certain generative models. For some of the problems of outlier-robust optimization over special, continuous non-convex sets, the PI and his collaborators aim to establish that the corresponding non-convex energy landscapes are "well-tempered" under some generic conditions. This implies that, under these conditions, one may apply an iterative scheme initialized at a pre-specified point and guarantee its fast convergence to the global minimum of the energy landscape. In other challenging discrete settings, "multi-valley" landscapes are observed. In this case, special structures and phase transitions will be quantified. The PI and his collaborators plan to apply their theory-driven, non-convex optimization solutions in order to solve several applied scientific problems, in particular, problems that arise in the current pipeline of structure from motion in computer vision. 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.