Abstract:

Optimisation and saddle point problems, where the minimisation is accompanied by an inner maximisation, are well-known to be successfully treated by methods from monotone inclusion andvariational inequality theory. In this context we are particularly interested in first order methods thatare full splitting. This means that only gradient information for smooth functions and proximal evaluations of simple convex nonsmooth functions are used. Furthermore we require that the algorithms do not include convoluted inner loops but evaluate the involved operators separately.
We do this on three different conceptual levels: (i) monotone inclusions that are most general and
include (ii) variational inequalities that already contain more structure and include (iii) minimax/saddle
point problems that arise from game theory or in the context of determining primal-dual pairs of
optimal solutions of constrained convex optimisation problems. We propose full splitting, first order
solution methods, establish asymptotic convergence of the algorithm and prove convergence rates in
the case of variational inequalities and minimax problems.
To empirically validate all considered methods we provide simple, conceptual problems that showcase
the convergence behaviour of the proposed methods. This is complemented by more complex
experiments covering relevant real-world machine learning applications (for example in Digital
Humanities), treating, among other things, Generative Adversarial Nets (GANs) and Multikernel
Support Vector Machines. GANs have proven to be a powerful class of generative models that are
notoriously hard to optimise by conventional training methods, but can be cast as a minimax problem
and observably benefit from employing more principled algorithms established for this type of
problem.