# Solving smooth min-min and min-max problems by mixed oracle algorithms

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2021.

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

- [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)
- [Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization](https://mlsanity.com/paper/2501.03222/) (2025)
- [An Optimal Algorithm for Strongly Convex Min-min Optimization](https://mlsanity.com/paper/2212.14439/) (2022)

## Abstract (arXiv)

In this paper, we consider two types of problems that have some similarity in their structure, namely, min-min problems and min-max saddle-point problems. Our approach is based on considering the outer minimization problem as a minimization problem with inexact oracle. This inexact oracle is calculated via inexact solution of the inner problem, which is either minimization or a maximization problem. Our main assumptions are that the problem is smooth and the available oracle is mixed: it is only possible to evaluate the gradient w.r.t. the outer block of variables which corresponds to the outer minimization problem, whereas for the inner problem only zeroth-order oracle is available. To solve the inner problem we use accelerated gradient-free method with zeroth-order oracle. To solve the outer problem we use either inexact variant of Vaydya's cutting-plane method or a variant of accelerated gradient method. As a result, we propose a framework that leads to non-asymptotic complexity bounds for both min-min and min-max problems. Moreover, we estimate separately the number of first- and zeroth-order oracle calls which are sufficient to reach any desired accuracy.