# Direct-Search for a Class of Stochastic Min-Max Problems

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 70 references that are in the map.
- First posted on arXiv 22 Feb 2021.

## Builds on (most cited first, 30 of 32)

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [NIPS 2016 Tutorial: Generative Adversarial Networks](https://mlsanity.com/paper/1701.00160/) (2016)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability](https://mlsanity.com/paper/1703.06182/) (2017)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agents](https://mlsanity.com/paper/1712.06560/) (2017)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networks](https://mlsanity.com/paper/1802.06132/) (2018)
- [Adversarially Robust Optimization with Gaussian Processes](https://mlsanity.com/paper/1810.10775/) (2018)
- [Negative Momentum for Improved Game Dynamics](https://mlsanity.com/paper/1807.04740/) (2018)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems](https://mlsanity.com/paper/2002.07919/) (2020)
- [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018)
- [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015)
- [What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?](https://mlsanity.com/paper/1902.00618/) (2019)
- [Optimal Primal-Dual Methods for a Class of Saddle Point Problems](https://mlsanity.com/paper/1309.5548/) (2013)
- [Saddle-point dynamics: conditions for asymptotic stability of saddle points](https://mlsanity.com/paper/1510.02145/) (2015)
- [An Online Learning Approach to Generative Adversarial Networks](https://mlsanity.com/paper/1706.03269/) (2017)
- [Convergence of Gradient Methods on Bilinear Zero-Sum Games](https://mlsanity.com/paper/1908.05699/) (2019)
- [Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML](https://mlsanity.com/paper/1909.13806/) (2019)
- [A Subsampling Line-Search Method with Second-Order Results](https://mlsanity.com/paper/1810.07211/) (2018)
- [A Stochastic Line Search Method with Convergence Rate Analysis](https://mlsanity.com/paper/1807.07994/) (2018)
- [Simple Complexity Analysis of Simplified Direct Search](https://mlsanity.com/paper/1410.0390/) (2014)

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

- [Faster Single-loop Algorithms for Minimax Optimization without Strong Concavity](https://mlsanity.com/paper/2112.05604/) (2021)
- [On the Second-order Convergence Properties of Random Search Methods](https://mlsanity.com/paper/2110.13265/) (2021)
- [Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm](https://mlsanity.com/paper/2504.07388/) (2025)
- [Minimisation of Polyak-Lojasewicz Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2405.09106/) (2024)
- [Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problems](https://mlsanity.com/paper/2504.03069/) (2025)
- [Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles](https://mlsanity.com/paper/2505.02281/) (2025)
- [A Globally Convergent Evolutionary Strategy for Stochastic Constrained Optimization with Applications to Reinforcement Learning](https://mlsanity.com/paper/2202.10464/) (2022)

## Abstract (arXiv)

Recent applications in machine learning have renewed the interest of the community in min-max optimization problems. While gradient-based optimization methods are widely used to solve such problems, there are however many scenarios where these techniques are not well-suited, or even not applicable when the gradient is not accessible. We investigate the use of direct-search methods that belong to a class of derivative-free techniques that only access the objective function through an oracle. In this work, we design a novel algorithm in the context of min-max saddle point games where one sequentially updates the min and the max player. We prove convergence of this algorithm under mild assumptions, where the objective of the max-player satisfies the Polyak-Lojasiewicz (PL) condition, while the min-player is characterized by a nonconvex objective. Our method only assumes dynamically adjusted accurate estimates of the oracle with a fixed probability. To the best of our knowledge, our analysis is the first one to address the convergence of a direct-search method for min-max objectives in a stochastic setting.