Seminar Series: Clément Royer, University of Wisconsin-Madison | Industrial and Systems Engineering

Tuesday, March 26 at 4:00pm to 5:00pm

Mohler Laboratory, 453
200 W Packer Ave., Bethlehem, PA 18015

Title: Nonconvex optimization via Newton-CG methods with complexity guarantees

Abstract      

There has been a recent surge of interest for finding local minima of nonconvex functions, mostly due to the outbreak of such instances in data science. In this context, the focus is on developing algorithms that possess good worst-case complexity properties. However, those guarantees often differ regarding the quantities of interest (number of iterations, evaluations or arithmetic calculations) and their nature (deterministic or high-probability results), thereby making it difficult to compare various strategies. In addition, endowing an algorithm with a complexity analysis is sometimes done in a theoretical fashion, and this can be detrimental to the practical use of such a method.

In this talk, we consider a classical approach in large-scale optimization, where the (linear) conjugate gradient algorithm is incorporated in a Newton-type method. We first present a simple instance of this scheme, for which complexity bounds can be derived: those are optimal within a large class of second-order methods. We then propose new variants that compare favorably to recently proposed algorithms based on accelerated gradient in terms of computational cost. To this end, we revisit the convergence theory of the conjugate gradient algorithm when applied to a nonconvex quadratic function. We also leverage randomized linear algebra techniques to obtain second-order complexity results at a reasonable expense. By incorporating these tools within our Newton-type framework, we are able to match the guarantees of recently proposed algorithms based on accelerated gradient. Finally, we describe several features of our implementation of our strategies, and illustrate their performance on a benchmark of nonconvex problems.

Bio sketch

Clément Royer is a postdoctoral research associate at the Wisconsin Institute for Discovery, a research institute at the University of Wisconsin-Madison, which he joined in November 2016. A native of Southwestern France, Clément received his Ph.D. in Applied Mathematics from the University of Toulouse, France, as well as his Master and Engineer degrees in Computer Science and Applied Mathematics.

His research interests revolve around continuous optimization and its applications, particularly in data science and complex systems. He currently focuses on introducing randomness within otherwise deterministic optimization schemes, and on analyzing the worst-case complexity behavior of optimization algorithms.