Newton-type methods with complexity guarantees for nonconvex data science

par M. Clément Royer

vendredi 12 mai 2023, 10:30 → 11:30 Europe/Paris

XR203 (XLIM)

Nonconvex optimization formulations are now commonly used in various areas of data science, from deep learning to matrix analysis and robust statistics. Many instances of that form come with a great deal of structure, that can be leveraged for optimization purposes. In particular, the solutions of these problems are often completely characterized by means of the first- and second-order derivatives. Consequently, the development of efficient optimization routines based on those derivatives represents an important area of research, wherein the theoretical efficiency of a method is measured by deriving complexity bounds. Such results quantify the effort required to reach an approximate solution, and are often used to compare optimization schemes. On the other hand, approaches that achieve the best theoretical results tend to depart from standard optimization frameworks, and may even by outperformed by textbook algorithms in practice.

In this talk, we revisit popular numerical optimization frameworks to equip them with complexity guarantees while maintaining their practical appeal, as evidenced on certain data science problems. We focus on Newton-type frameworks that we equip with the best-known complexity guarantees for nonconvex optimization. We first propose a generic method that hews close to the classical Newton-Conjugate gradient algorithm, and illustrate the practical impact of guaranteeing good complexity. We then propose a variant of our method tailored to specific nonconvex optimization landscapes, for which even stronger results can be derived. Finally, we will specialize our results to nonconvex formulations of data science tasks, such as those arising in phase retrieval and sparse signal recovery.