Non-smooth non-convex optimization problems are ubiquitous in image processing and machine learning. In recent years, significant progress was made by exploiting special problem structures, which led to many new algorithms, commonly referred to as splitting methods. By specializing to certain structures, however, a natural way to approach minimization problems was neglected: the sequential minimization of model functions. In smooth optimization, model functions are usually Taylor approximations of the objective; gradient descent, for example, minimizes the linearization plus a proximity term. In non-smooth optimization, there are also "Taylor-like" models, which, however, are not unique.
The key is the approximation quality of the model function fx̄ around a point x̄, which is controlled by a growth function ω:
|f(x) − fx̄(x)| ≤ ω(|x − x̄|) for all x.
Algorithms that look different, such as gradient descent, forward–backward splitting, or ProxDescent, obey the same growth function. This suggests that many of their properties are due to the growth function rather than the specific model. The goal of this project was the development of a unifying approach to non-smooth optimization algorithms based on sequentially minimizing model functions, in order to transfer results from one algorithm to another, to reduce their analysis to the essential mathematical structures, to provide new convergence guarantees, and to develop new algorithms for new applications.
Funded by the German Research Foundation (DFG Grant OC 150/1-1), January 2019 – June 2022. PhD student funded by the project: Mahesh Chandra Mukkamala.
Objectives
- A practical algorithm based on model functions and general proximity measures with convergence guarantees.
- Accelerated (inertial) variants of the framework.
- Convergence of the full sequence of iterates.
Results
The project resulted in a flexible algorithmic framework that unifies many known algorithms, is efficiently implementable, can be accelerated, and comes with the best convergence guarantees that can be expected in the general non-smooth non-convex setting. Bregman distances, which replace the Euclidean distance in the proximity term, turned out to add significant generality. All results are part of our research on the unification of non-smooth optimization algorithms and on inertial algorithms.
A unifying framework of model functions
This work lays the foundation of the project: a flexible algorithm that sequentially minimizes model functions together with a Bregman proximity measure, complemented by an Armijo-like line search. It unifies algorithms such as forward–backward splitting, ProxDescent, and several majorization–minimization methods, and it provides convergence guarantees for problems that could not be solved by any other algorithm before, for example, without a Lipschitz continuous gradient.
We transferred the idea of model functions to Frank–Wolfe type algorithms by replacing the proximity measure with a compact convex constraint set. This leads to new algorithms for non-smooth non-convex problems, for example, of Gauss–Newton type, and to hybrid schemes that combine a Frank–Wolfe oracle for one block of variables with a proximal oracle for another.
Using the Kurdyka–Lojasiewicz inequality, we proved convergence of the full sequence of iterates to a stationary point while maintaining the flexibility of the model functions, and we even allow for non-convex model functions. The MAP property generalizes relative smoothness (L-smad) to non-smooth composite problems, and the resulting algorithm Model BPG avoids line search.
Bregman distances for matrix factorization and deep linear networks
The recent theory of Bregman proximal gradient (BPG) methods for objectives without a Lipschitz continuous gradient requires Bregman distances that are adapted to the problem. We developed such distances for two important applications, which enable non-alternating algorithms with convergence guarantees.
For matrix factorization, a novel Bregman distance allows for closed-form update steps of non-alternating schemes, such as BPG and its inertial variant CoCaIn BPG, with convergence of the whole sequence to a stationary point.
For training deep linear neural networks, we developed Bregman distances that lead to strong convergence guarantees, closed-form updates, and a closed-form expression for the inertial parameter of CoCaIn BPG, without diminishing step sizes or line search.
Acceleration
Adaptive FISTA optimizes the extrapolation parameter by a line search. This establishes a close connection between accelerated (extrapolated) algorithms and quasi-Newton methods: with a certain optimized extrapolation step, the SR1 quasi-Newton method is recovered.
The convex–concave inertial (CoCaIn) backtracking strategy locally searches for tight upper and lower bounds of the objective to achieve maximal progress in each iteration, thereby adapting to the local convexity of the objective. It yields the first global convergence result for an inertial algorithm with Bregman distances to a stationary point for Kurdyka–Lojasiewicz functions and shows state-of-the-art performance on problems from machine learning and computer vision.
