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

数据科学问题的许多解决方案都是基于非凸优化的。最近令人惊讶的理论和经验结果表明，直接求解非凸问题可以产生计算效率高，精度高的算法。 这刺激了对各种结构化数据问题的非凸算法的分析工作的不断扩大。其中一类是鲁棒恢复问题，其目的是恢复损坏数据中的隐藏结构。虽然鲁棒性是数理统计中的经典主题，但对于高水平腐败具有保证准确性的计算效率方法尚未得到广泛研究。非凸最小化方法表明有可能获得有竞争力的速度和准确性，这样的问题，已经证明了PI和他的合作者对鲁棒子空间恢复的问题。研究工作的目的是进一步建立和扩展这样的保证，许多其他强大的恢复问题，其解决方案是现代应用问题的关键。应用包括从一组二维图像的三维重建的问题。PI和他的合作者旨在为真正具有挑战性的非凸恢复问题开发强大的理论和算法。这些恢复问题通常是NP-难的高度复杂的能源景观。然而，这些景观往往表现出特殊的结构，似乎允许在某些对抗性环境下恢复，并在某些生成模型下以高概率恢复。对于一些特殊的连续非凸集上的离群鲁棒优化问题，PI和他的合作者的目标是建立相应的非凸能量景观在某些一般条件下是“良好的”。这意味着，在这些条件下，可以应用在预先指定的点初始化的迭代方案，并保证其快速收敛到能量景观的全局最小值。在其他具有挑战性的离散设置中，观察到"多谷"景观。在这种情况下，特殊的结构和相变将被量化。PI和他的合作者计划应用他们的理论驱动的非凸优化解决方案，以解决几个应用科学问题，特别是在当前计算机视觉中从运动到结构的管道中出现的问题。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.