250. Complexity of Newton-type methods with quadratic regularization for nonlinear least squares
Invited abstract in session WB-8: Theoretical advances in nonconvex optimization, stream Large scale optimization: methods and algorithms.
Wednesday, 10:30-12:30Room: B100/7007
Authors (first author is the speaker)
| 1. | Iskander LEGHERABA
|
| 2. | Clément Royer
|
| LAMSADE, Université Paris Dauphine-PSL |
Abstract
Equipping globalized versions of Newton's method with complexity guarantees in a nonconvex setting has been a popular topic of research in recent years, motivated in part by the development of cubic regularization methods. In particular, quadratic regularization schemes can be adapted to achieve optimal iteration complexity bounds on general nonconvex problems.
In this talk, we describe a novel quadratic regularization approach where the quadratic subproblems are solved using a capped conjugate gradient technique. Such inexact steps lead to best-known operation and iteration complexity bounds, in both a first- and a second-order sense. By specializing our results to nonlinear least squares problems, we provide new complexity bounds that improve over existing results, through a reasoning that can be extended to other algorithms such as cubic regularization. We finally discuss the practical relevance of our approach on matrix least squares problems.
Keywords
- Complexity and efficiency of algorithms
- Second- and higher-order optimization
- Large-scale optimization
Status: accepted
Back to the list of papers