Most models for solving practical problems in computer vision, machine learning and the natural sciences depend on parameters, and estimating these parameters automatically from data is often a tremendous challenge. Formally, such parameter learning problems are bilevel optimization problems: the parameters are the variables of an upper level problem, whose objective evaluates the solution of a parameter-dependent lower level problem, for example, a variational model. In computer vision and machine learning, these problems are particularly demanding: the data and the parameter space are high-dimensional, and the lower level problems are naturally non-smooth.
The goal of this project was the development of a theoretical and practical framework for solving such bilevel problems with gradient-based methods. The key ingredient is the derivative of the solution mapping of the lower level problem with respect to the parameters. Since implicit differentiation requires second-order information that is prohibitively expensive in high dimensions, the project focused on an efficient alternative: the solution mapping is approximated by an iterative algorithm, and its derivative by the derivative of the algorithm, which is computed by automatic differentiation (AD).
Funded by the German Research Foundation (DFG Grant OC 150/4-1), October 2020 – September 2024. PhD student funded by the project: Sheheryar Mehmood.
Objectives
- Characterize non-smooth lower level problems that can be solved by an iterative algorithm with a smooth update mapping.
- Prove the convergence of the derivatives of such algorithms with respect to the parameters to the derivative of the solution mapping.
- Identify settings in which the solution mapping of a non-smooth lower level problem is differentiable in a suitable sense.
- Develop an efficient algorithmic framework for computing these derivatives, in particular with low memory requirements.
Results
The project established a convergence theory for automatic differentiation of optimization algorithms, from smooth problems to the non-smooth setting of partly smooth functions, together with memory-efficient variants. All results are part of our research on bilevel optimization and automatic differentiation.
For smooth parametric problems, we proved that the derivatives obtained by AD of an optimization algorithm converge to the derivative of the solution mapping given by the implicit function theorem, and we showed that the convergence speed of the algorithm and that of the derivative sequence are closely linked. In particular, accelerated algorithms also accelerate the convergence of the derivatives.
As a first step towards the non-smooth setting, we studied the differentiability of the value function of a parametric optimization problem through the lens of convex duality. The resulting dual gradient estimator computes the derivative of the value function efficiently for a large class of non-smooth problems that are relevant in computer vision and machine learning, by solving primal–dual optimization problems.
To characterize non-smooth problems that admit algorithms with smooth update mappings, we investigated the class of partly smooth functions. Such functions are smooth along a manifold and non-smooth in the normal directions, and algorithms like the proximal gradient method identify this manifold after finitely many iterations. Exploiting this structure, we transferred the results for the smooth setting to the partly smooth setting: AD of the proximal gradient method and of an accelerated variant converges to the derivative of the solution mapping. Moreover, Fixed-Point Automatic Differentiation (FPAD) reduces the memory consumption of reverse mode AD and converges faster.
Many algorithms have a time-varying update rule, for example, due to varying step sizes or momentum parameters. We provided convergence (rate) guarantees for AD of such time-varying iterative processes, including proximal gradient descent with variable step sizes and FISTA for partly smooth problems. This completes the theory developed in the project: the convergence rate of the algorithm is reflected in its derivative iterates.
Preliminary work
The project builds on our earlier approach of replacing a non-smooth lower level problem by an algorithm with differentiable update mappings:
P. Ochs, R. Ranftl, T. Brox, T. Pock
Bilevel Optimization with Nonsmooth Lower Level Problems
In J.-F. Aujol, M. Nikolova, N. Papadakis (Eds.): International Conference on Scale Space and Variational Methods in Computer Vision (SSVM). Lecture Notes in Computer Science, Vol. 9087, 654-665, Springer, 2015. Best Paper Award PDF
