199. Convergence rates of regularized quasi-Newton methods without strong convexity
Invited abstract in session MB-3: First-order methods in modern optimization (Part I), stream Large scale optimization: methods and algorithms.
Monday, 10:30-12:30Room: B100/4011
Authors (first author is the speaker)
| 1. | Shida Wang
|
| 2. | Jalal Fadili
|
| GREYC CNRS UMR 6072, ENSICAEN | |
| 3. | Peter Ochs
|
| Saarland University |
Abstract
In this paper, we study convergence rates of the cubic regularized proximal quasi-Newton method (Cubic SR1) for solving non-smooth additive composite problems that satisfy the so-called Kurdyka-Lojasiewicz (KL) property with respect to some desingularization function rather than strong convexity. After a number of iterations, Cubic SR1 exhibits non-asymptotic explicit super-linear convergence rates if the exponent of KL property is beyond 1/2. For the special case, i.e. functions which satisfy Lojasiewicz inequality (PL), the rate becomes global and non-asymptotic. This work presents, for the first time, non-asymptotic explicit convergence rates of regularized (proximal) SR1 quasi-Newton methods applied to non-convex non-smooth problems with KL property. Actually, the rates are novel even in the smooth non-convex case. Notably, we achieve this without employing line search or trust region strategies, without assuming the Dennis-Mor´e condition, and without assuming strong convexity. Furthermore, for convex problems, we focus on a more tractable gradient regularized
quasi-Newton method (Gradient SR1) which can achieve results similar to those obtained with cubic regularization.
Keywords
- Second- and higher-order optimization
- Non-smooth optimization
- Large-scale optimization
Status: accepted
Back to the list of papers