mlsanityData to 14 Oct 2026

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

arXiv 2102.11386 ↗First posted 22 Feb 2021math.OC cs.LGcited by 7

Not on the map. Why?

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.

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

32 of 70 references.

References · 32

  1. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,739
  2. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 574
  3. 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 567
  4. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  5. 2016NIPS 2016 Tutorial: Generative Adversarial Networkscited by 285
  6. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  7. 2017Training GANs with Optimismcited by 217
  8. 2013Bayesian Optimization in a Billion Dimensions via Random Embeddingscited by 182
  9. 2016Variance-based regularization with convex objectivescited by 155
  10. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 148
  11. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  12. 2017Improving Exploration in Evolution Strategies for Deep Reinforcement Learning via a Population of Novelty-Seeking Agentscited by 107
20 more
  1. 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 101
  2. 2018Interaction Matters: A Note on Non-asymptotic Local Convergence of Generative Adversarial Networkscited by 68
  3. 2018Adversarially Robust Optimization with Gaussian Processescited by 62
  4. 2018Negative Momentum for Improved Game Dynamicscited by 60
  5. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  6. 2018On the Convergence and Robustness of Training GANs with Regularized Optimal Transportcited by 51
  7. 2020Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problemscited by 39
  8. 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
  9. 2015Stochastic Optimization Using a Trust-Region Method and Random Modelscited by 26
  10. 2019What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?cited by 20
  11. 2013Optimal Primal-Dual Methods for a Class of Saddle Point Problemscited by 19
  12. 2015Saddle-point dynamics: conditions for asymptotic stability of saddle pointscited by 18
  13. 2017An Online Learning Approach to Generative Adversarial Networkscited by 13
  14. 2019Convergence of Gradient Methods on Bilinear Zero-Sum Gamescited by 12
  15. 2019Min-Max Optimization without Gradients: Convergence and Applications to Adversarial MLcited by 9
  16. 2018A Subsampling Line-Search Method with Second-Order Resultscited by 8
  17. 2018A Stochastic Line Search Method with Convergence Rate Analysiscited by 5
  18. 2014Simple Complexity Analysis of Simplified Direct Searchcited by 4
  19. 2020Expected complexity analysis of stochastic direct-searchcited by 3
  20. 2019StoMADS: Stochastic blackbox optimization using probabilistic estimatescited by 2

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 1; 2023: 0; 2024: 1; 2025: 3.

7 papers.

  1. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  2. 2021On the Second-order Convergence Properties of Random Search Methodscited by 5
  3. 2025Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithmcited by 5
  4. 2024Minimisation of Polyak-Lojasewicz Functions Using Random Zeroth-Order Oraclescited by 4
  5. 2025Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problemscited by 3
  6. 2025Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oraclescited by 3
  7. 2022A Globally Convergent Evolutionary Strategy for Stochastic Constrained Optimization with Applications to Reinforcement Learningcited by 2