# Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables

arXiv: https://arxiv.org/abs/2010.02280 · HTML: https://mlsanity.com/paper/2010.02280/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Oct 2020.

## Built on by (most cited first, 2 of 2)

- [Smooth Monotone Stochastic Variational Inequalities and Saddle Point Problems: A Survey](https://mlsanity.com/paper/2208.13592/) (2022)
- [Algorithm for Constrained Markov Decision Process with Linear Convergence](https://mlsanity.com/paper/2206.01666/) (2022)

## Abstract (arXiv)

The article is devoted to the development of algorithmic methods ensuring efficient complexity bounds for strongly convex-concave saddle point problems in the case when one of the groups of variables is high-dimensional, and the other is relatively low-dimensional (up to a hundred). The proposed technique is based on reducing problems of this type to a problem of minimizing a convex (maximizing a concave) functional in one of the variables, for which it is possible to find an approximate gradient at an arbitrary point with the required accuracy using an auxiliary optimization subproblem with another variable. In this case, the ellipsoid method is used for low-dimensional problems (if necessary, with an inexact δ-subgradient), and accelerated gradient methods are used for high-dimensional problems. For the case of a very small dimension of one of the groups of variables (up to 5), an approach based on a new version of the multidimensional analog of the Yu. E. Nesterov's method on the square (multidimensional dichotomy) is proposed with the possibility of using inexact values of the gradient of the objective functional.