194. Local convergence of adaptively regularized tensor methods
Invited abstract in session TC-6: Structured nonsmooth optimization -- Part I, stream Nonsmooth and nonconvex optimization.
Tuesday, 14:00-16:00Room: B100/7013
Authors (first author is the speaker)
| 1. | Karl Welzel
|
| Mathematical Institute, University of Oxford | |
| 2. | Coralia Cartis
|
| Mathematical Institute, University of Oxford | |
| 3. | Raphael Hauser
|
| Oxford University Computing Laboratory, Oxford University | |
| 4. | Yang Liu
|
| Mathematical Institute, University of Oxford |
Abstract
Tensor methods are methods for unconstrained continuous optimization that can incorporate derivative information of up to order p > 2 by computing a step based on the pth-order Taylor expansion at each iteration. The most important among them are regularization-based tensor methods which have been shown to have optimal worst-case iteration complexity of finding an approximate minimizer. We are interested in how local convergence rates depend on the order of the Taylor expansion p. In the case of functions that are uniformly convex of order q (ones that around the minimizer x* grow like the distance to x* to the qth power) and a fixed regularization parameter, the answer is known: we get (p/(q-1))th-order local convergence of function values and gradient norms if p > q-1. In particular, when the Hessian is positive definite at the minimizer (q=2) we get pth-order convergence, but also when the Hessian is singular at x* (q>2) superlinear convergence (compared to Newton's linear convergence) is possible as long as enough derivatives are available. We extend these convergence results to locally uniformly convex functions and fully adaptive methods. We discuss how for p > 2 it becomes crucial to select the "right" minimizer of the regularized local model in each iteration to ensure all iterations are eventually successful. If the right minimizer is used, the (p/(q-1))th-order local convergence is preserved, otherwise the rate degrades but stays superlinear.
Keywords
- Second- and higher-order optimization
Status: accepted
Back to the list of papers