Collaborative Research: Tractable Non-Convex Optimization

New York University, New York NY

Investigators

Abstract

Practitioners in most fields of science and engineering invest a substantial amount of time developing appropriate mathematical models for the complex questions they set out to answer. A model is deemed appropriate for a given task if it meets two potentially conflicting criteria simultaneously. On the one hand, it must be sufficiently faithful to reality (and as such, sufficiently complex) so as to capture the essential properties of the object of study. On the other hand, the model must be simple enough that it can be practically used to answer relevant questions. This second requirement is computational in nature. In effect, the modeler aims to reduce a particular question to a mathematical problem known to be practically solvable, or tractable. For the most part, tractability ensures that the problem can be solved using known algorithms, and as a result the status quo has been that problems that are not tractable should be avoided for applications. Yet, scores of problems in science and engineering are most naturally modeled within a framework that has been previously determined to be non-tractable. This research project aims to develop theory and algorithms to identify and solve non-convex optimization problems, typically regarded as non-tractable. The goal is to provide practitioners with an extended modeling toolbox, allowing them to capture key aspects of our complex reality. This project targets optimization problems that are tractable despite non-convexity. This can come about in a number of ways. The non-convexity may be structurally benign, in that the problem actually does not have local optima at all. This project explores such structural effects in the context of Burer-Monteiro relaxations. Alternatively, the problem may present numerous local optima in some instances, yet present only good quality ones on instances of the problem encountered in practice. This motivates the analysis of non-convex optimization problems in a non-adversarial setting, in many cases more relevant to practice than classical adversarial analyses. This project investigates some model problems of this nature. Here too, salvation can come in different forms: It is possible that when data is good enough (for example, if the signal to noise ratio is sufficient), local optima cannot exist; or, it is possible to initialize the algorithms close enough to the global optimum so that convergence to it is assured; or, even local optima are satisfactory to answer the underlying question. This project explores such situations through applications in community detection in large networks and through phase synchronization, as model problems for understanding challenges in a more general class of problems including, but not limited to, electron cryomicroscopy from structural biology and simultaneous localization and mapping in robotics. A common feature of many tractable non-convex optimization is that they are naturally posed on smooth nonlinear spaces called Riemannian manifolds. As a result, important algorithmic aspects of this project involve developing theory, algorithms, and software for optimization on Riemannian manifolds.