Project Details
Projekt Print View

Unification of Smooth and Non-smooth Non-convex Optimization Algorithms

Subject Area Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
Mathematics
Term from 2018 to 2022
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 397569761
 
Final Report Year 2022

Final Report Abstract

The goal of the project was the development of an abstract algorithmic framework that unifies several algorithms and convergence guarantees that are important for applications in image processing, computer vision and machine learning. High expectations were imposed on the framework to yield highly efficient, easily implementable, flexible algorithms that can be accelerated with state-of-the-art convergence guarantees in the general setting of non-smooth non-convex optimization. The key idea is the observation that simple algorithmic schemes such as Gradient Descent, Newton’s Method or the Conditional Gradient method essentially rely on sequential minimization of simple surrogates to the objective function. Due to smoothness, mostly, these surrogates are constructed based on Taylor expansion and a distance term that controls the progress of the algorithm to achieve convergence guarantees. In the non-smooth setting, similar Taylor-like model functions can be constructed and efficiently used for updating within algorithms, however these models are not unique anymore. We contributed to the understanding of the actual flexibility of such a framework in the non-smooth setting. Moreover, significant additional generality could be added by formulating an appropriate class of distance functions: Bregman distances. We directly implemented the most recent algorithmic results for Bregman distances in our framework leading to direct (non-alternating) solution strategies to matrix factorization and deep linear neural network problems, which was beyond the initial goals. Also regarding the incorporation of acceleration within the abstract model function framework, we contributed beyond our initial expectations by developing a state-of-the-art convex-concave inertial backtracking strategy, that (in the non-convex setting) is able to adapt to local convexity of the objective function. This development satisfied the high expectations for a practical algorithmic framework in the non-smooth non-convex setting, which we could eventually complement with the best possible convergence guarantees in this challenging setup by proving that the iterates generated by the algorithm converge to a stationary point. In summary, we neglected a small part of our initial plan to make achievements of the overall framework that go beyond the expectations of the project.

Publications

 
 

Additional Information

Textvergrößerung und Kontrastanpassung