An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function
- Author(s)
- Radu Ioan Bot, Ernö Robert Csetnek, Michael Sedlmayer
- Abstract
In this work we aim to solve a convex-concave saddle point problem, where the convex-concave coupling function is smooth in one variable and nonsmooth in the other and not assumed to be linear in either. The problem is augmented by a nonsmooth regulariser in the smooth component. We propose and investigate a novel algorithm under the name of OGAProx, consisting of an optimistic gradient ascent step in the smooth variable coupled with a proximal step of the regulariser, and which is alternated with a proximal step in the nonsmooth component of the coupling function. We consider the situations convex-concave, convex-strongly concave and strongly convex-strongly concave related to the saddle point problem under investigation. Regarding iterates we obtain (weak) convergence, a convergence rate of order O(1/K ) and linear convergence like O(𝜃^K ) with 𝜃 < 1, respectively. In terms of function values we obtain ergodic convergence rates of order O(1/K), O(1/K^2) and O(𝜃^K) with 𝜃 < 1, respectively. We validate our theoretical considerations on a nonsmooth-linear saddle point problem, the training of multi kernel support vector machines and a classification problem incorporating minimax group fairness.
- Organisation(s)
- Department of Mathematics, Research Network Data Science
- Journal
- Computational Optimization and Applications
- Volume
- 86
- Pages
- 925 - 966
- No. of pages
- 42
- ISSN
- 0926-6003
- DOI
- https://doi.org/10.1007/s10589-022-00378-8
- Publication date
- 2021
- Peer reviewed
- Yes
- Austrian Fields of Science 2012
- 101016 Optimisation
- Keywords
- ASJC Scopus subject areas
- Computational Mathematics, Control and Optimization, Applied Mathematics
- Portal url
- https://ucris.univie.ac.at/portal/en/publications/an-accelerated-minimax-algorithm-for-convexconcave-saddle-point-problems-with-nonsmooth-coupling-function(44b4f6c4-9b6f-47db-8350-d393f53def7b).html