175. Randomized trust-region method for non-convex mimimization
Invited abstract in session TB-10: First order methods: new perspectives for machine learning , stream Large scale optimization: methods and algorithms.
Tuesday, 10:30-12:30Room: B100/8011
Authors (first author is the speaker)
| 1. | Radu-Alexandru Dragomir
|
| Telecom Paris |
Abstract
We study second-order trust-region algorithms, with subproblem solvers based on the conjugate gradient method, for non-convex optimization.
In this context, a desirable property is that the algorithm avoids saddle points and converges to a local minimizer. We introduce a trust-region method that (i) satisfies this property, (ii) has efficient complexity for large-scale problems, and (iii) is as close as possible to the version used in practice.
Our scheme is based on the Steihaug-Toint truncated conjugate gradient (tCG) method, with two key modifications: a random perturbation of the initial point and a supplementary gradient step when the iterates reach the trust-region boundary.
We provide theoretical guarantees for functions with isolated critical points. Our key assumption, the mu-Morse property, is a bound on the magnitude of the Hessian eigenvalues at critical points.
Keywords
- Large-scale optimization
- Second- and higher-order optimization
- Complexity and efficiency of algorithms
Status: accepted
Back to the list of papers