mlsanityData to 7 Oct 2026

Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization

arXiv 2106.09082 ↗First posted 16 Jun 2021math.OC cs.LGcited by 18

Not on the map. Why?

Abstract (arXiv)

Min-max optimization is emerging as a key framework for analyzing problems of robustness to strategically and adversarially generated data. We propose a random reshuffling-based gradient free Optimistic Gradient Descent-Ascent algorithm for solving convex-concave min-max problems with finite sum structure. We prove that the algorithm enjoys the same convergence rate as that of zeroth-order algorithms for convex minimization problems. We further specialize the algorithm to solve distributionally robust, decision-dependent learning problems, where gradient information is not readily available. Through illustrative simulations, we observe that our proposed approach learns models that are simultaneously robust against adversarial distribution shifts and strategic decisions from the data sources, and outperforms existing methods from the strategic classification literature.

Key facts. Cited by 18 papers in the map (data through 7 Oct 2026). Builds on 32 of its 82 references that are in the map. First posted on arXiv 16 Jun 2021.

Builds on

32 of 82 references.

References · 32

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  3. 2018Black-box Adversarial Attacks with Limited Queries and Informationcited by 499
  4. 2020Performative Predictioncited by 318
  5. 2017Certified Defenses for Data Poisoning Attackscited by 288
  6. 2015Strategic Classificationcited by 256
  7. 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 160
  8. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  9. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  10. 2018AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networkscited by 137
  11. 2017Strategic Classification from Revealed Preferencescited by 126
  12. 2015Distributionally Robust Logistic Regressioncited by 124
20 more
  1. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  2. 2021Outside the Echo Chamber: Optimizing the Performative Riskcited by 95
  3. 2019NATTACK: Learning the Distributions of Adversarial Examples for an Improved Black-Box Attack on Deep Neural Networkscited by 94
  4. 2020Stochastic Optimization for Performative Predictioncited by 92
  5. 2020Performative Prediction in a Stateful Worldcited by 90
  6. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 78
  7. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  8. 2020Stochastic optimization with decision-dependent distributionscited by 65
  9. 2019How Good is SGD with Random Shuffling?cited by 63
  10. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
  11. 2020Closing the convergence gap of SGD without replacementcited by 56
  12. 2018Bandit learning in concave N-person gamescited by 32
  13. 2019Optimal Decision Making Under Strategic Behaviorcited by 20
  14. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  15. 2016Frank-Wolfe Algorithms for Saddle Point Problemscited by 18
  16. 2020Learning to Play Sequential Games versus Unknown Opponentscited by 18
  17. 2015A Practical Guide to Robust Optimizationcited by 16
  18. 2019Min-Max Optimization without Gradients: Convergence and Applications to Adversarial MLcited by 9
  19. 2020Gradient-Free Methods for Saddle-Point Problemcited by 8
  20. 2020Zeroth-Order Algorithms for Smooth Saddle-Point Problemscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 6; 2024: 3; 2025: 2; 2026: 1.

18 papers.

Sort:

  1. 2022Regret Minimization with Performative Feedbackcited by 40
  2. 2023Performative Prediction with Neural Networkscited by 33
  3. 2023Causal Strategic Classification: A Tale of Two Shiftscited by 30
  4. 2023Plug-in Performative Optimizationcited by 20
  5. 2022Strategic Classification with Graph Neural Networkscited by 14
  6. 2023Performative Recommendation: Diversifying Content via Strategic Incentivescited by 12
  7. 2023Performative Prediction with Bandit Feedback: Learning through Reparameterizationcited by 11
  8. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  9. 2021Model Transferability With Responsive Decision Subjectscited by 9
  10. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  11. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7
  12. 2024Parameter-Free Algorithms for Performative Regret Minimization under Decision-Dependent Distributionscited by 2
6 more
  1. 2024Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimizationcited by 1
  2. 2025A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Gamescited by 1
  3. 2025EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimizationcited by 1
  4. 2023Follower Agnostic Methods for Stackelberg Gamescited by 0
  5. 2024How to Boost Any Loss Functioncited by 0
  6. 2026Zeroth-Order Stackelberg Control in Combinatorial Congestion Gamescited by 0