Inertial Algorithms for Non-smooth Non-convex Optimization

We extended the Heavy-ball method from smooth unconstrained optimization to a class of non-smooth non-convex problems: the sum of a continuously differentiable function with Lipschitz continuous gradient and a non-smooth non-convex extended-valued function with a simple proximal mapping. The algorithm was termed iPiano. We proved global subsequential convergence of the algorithm to a stationary point and, for objective functions that satisfy the Kurdyka--Lojasiewicz inequality, convergence of the whole sequence of iterates. This was the first global convergence result for an inertial algorithm for non-smooth non-convex optimization problems. The Kurdyka--Lojasiewicz inequality is a mild assumption that is satisfied by most functions in practical applications. iPiano has shown state-of-the-art performance for several problems from image processing.

Complementing the global analysis, we studied the local convergence of the Heavy-ball method and iPiano for the class of prox-regular functions. Locally, iPiano is equivalent to inertial alternating/averaged proximal minimization/projection methods, which allowed us to transfer the convergence results, including convergence rates, to these algorithms. Key is a formula for prox-regular functions that expresses the gradient of the Moreau envelope using the proximal mapping, which is well known in the convex setting.

We proved an abstract convergence theorem for Kurdyka--Lojasiewicz functions that unifies several earlier ones. The flexibility that is crucial for inertial methods comes from a descent property with respect to a function that may change along the iterations (instead of the objective itself), a generic distance measure, and relative errors with respect to combinations of distance terms. As an application, we derived a block coordinate and variable metric variant of iPiano. See also our research on the unification of non-smooth optimization algorithms.

Building on this line of work, we introduce an abstract descent scheme that guarantees convergence of the full sequence of iterates to a stationary point for Kurdyka--Lojasiewicz functions and, in addition, allows the update step to be computed inexactly, which is crucial when the proximal mapping has no closed-form solution. Based on this framework, we propose two inertial algorithms: i2Piano, an inexact variant of iPiano that exploits large steps by adapting a local Lipschitz constant, and iPila, an inertial line-search method that enforces descent only on a merit function instead of the objective, which even allows it to escape from local minimizers. Both algorithms inherit the full convergence guarantees of the abstract scheme. Their benefits are demonstrated on image deblurring with impulse noise.

Backtracking finds a suitable step size by locally estimating a simple convex upper bound of the objective function. For inertial methods, this usually leads to very restrictive rules on the extrapolation parameter. We observed that the extrapolation parameter can be controlled by locally estimating also a simple concave lower bound of the objective. The resulting convex--concave inertial (CoCaIn) backtracking strategy adapts both parameters to the "local convexity" of the objective. We apply it to inertial Bregman proximal gradient methods (CoCaIn BPG), which do not require a Lipschitz continuous gradient, and prove the first global convergence result for an inertial algorithm with Bregman distances to a stationary point for Kurdyka--Lojasiewicz functions. The algorithm shows state-of-the-art performance on several problems from machine learning and computer vision.

Bregman proximal gradient methods require a Bregman distance that is adapted to the problem. For matrix factorization, we proposed a novel Bregman distance that allows for closed-form update steps. This enables non-alternating schemes, such as BPG and CoCaIn BPG, for which we prove convergence of the whole sequence to a stationary point. Unlike alternating minimization, they update all factors simultaneously, which avoids a bias towards one of the variables. In several experiments, the non-alternating schemes were superior in terms of speed and objective value at the limit point.

In the same spirit, we developed Bregman distances for training deep linear neural networks, whose loss function does not have a Lipschitz continuous gradient. This yields strong convergence guarantees for BPG and CoCaIn BPG, closed-form updates, and a closed-form expression for the inertial parameter of CoCaIn BPG. Unlike its Euclidean counterpart, BPG requires neither diminishing step sizes nor line search.

Instead of following a fixed rule, Adaptive FISTA locally optimizes the extrapolation parameter by an exact or inexact line search. Surprisingly, in some situations, the resulting method is equivalent to a proximal quasi-Newton method with an SR1 (identity minus rank-1) metric. Thanks to proximal calculus with respect to a rank-1 modified metric [BF12] S. Becker and J. Fadili: A Quasi-Newton Proximal Splitting Method. In Proceedings of the 25th International Conference on Neural Information Processing Systems (NIPS), 2618--2626, 2012. and its extension to proximal calculus for a rank-r modified metric, the update step can be computed efficiently, also for non-smooth non-convex additive composite problems. Convergence is proved in a general non-convex setting, which, as a byproduct, yields new convergence guarantees for proximal quasi-Newton methods.

We combine inertia and quasi-Newton metrics in a forward-backward splitting algorithm for monotone inclusion problems. While the inertial step is cheap, the bottleneck is the evaluation of the resolvent operator in the changed metric. We developed an efficient resolvent calculus for low-rank perturbed metrics, which accounts exactly for quasi-Newton metrics, and proved convergence, including linear rates when one of the operators is strongly monotone. As a special case, we obtain an inertial quasi-Newton primal-dual hybrid gradient method for saddle point problems, with favourable performance in image processing. This work is part of the project TRINOM-DS.

iPiasco is a forward-backward splitting algorithm with an inertial term for strongly convex problems given as the sum of a smooth and a non-smooth convex function. Using the strong convexity, we derived a worst-case linear convergence rate and proved that the algorithm is optimal. For certain problems, this rate is even better than the optimal worst-case rate for smooth strongly convex functions.

Fast Semi-Iterative (FSI) schemes accelerate basic iterative solvers, such as explicit diffusion schemes, Richardson iterations or projected gradient descent, by extrapolating with the previous iterate. The extrapolation parameters are derived from a connection between box filtering and explicit schemes for 1D homogeneous diffusion, and FSI schemes are closely related to the Heavy-ball method. Applications include anisotropic diffusion inpainting and non-smooth regularization.

Most acceleration strategies are generic and ignore specific information about the objective function. We equipped FSI schemes with an adaptive restart, which yields a theoretical convergence rate guarantee and state-of-the-art performance on a challenging image processing task.

We study non-convex optimization via second-order dynamics with a viscous damping and a geometric Hessian-driven damping. The Hessian-driven damping reduces the oscillations that purely viscously damped systems (such as the heavy-ball system) exhibit near minimizers, without requiring the Hessian to be computed explicitly. For an explicit and an implicit version of the Hessian-driven damping, we prove convergence of the gradient to zero and, for definable objective functions, convergence of the trajectory to a critical point including convergence rates. For Morse functions, the trajectory converges to a local minimizer for almost all initializations. All these properties carry over to the inertial algorithms that result from discretizing the dynamics.