mlsanityData to 7 Oct 2026

Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning

arXiv 1810.02060 ↗First posted 4 Oct 2018math.OC cs.LGcited by 62

Not on the map. Why?

Abstract (arXiv)

Min-max problems have broad applications in machine learning, including learning with non-decomposable loss and learning with robustness to data distribution. Convex-concave min-max problem is an active topic of research with efficient algorithms and sound theoretical foundations developed. However, it remains a challenge to design provably efficient algorithms for non-convex min-max problems with or without smoothness. In this paper, we study a family of non-convex min-max problems, whose objective function is weakly convex in the variables of minimization and is concave in the variables of maximization. We propose a proximally guided stochastic subgradient method and a proximally guided stochastic variance-reduced method for the non-smooth and smooth instances, respectively, in this family of problems. We analyze the time complexities of the proposed methods for finding a nearly stationary point of the outer minimization problem corresponding to the min-max problem.

Key facts. Cited by 62 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 18; 2023: 11; 2024: 12; 2025: 4; 2026: 8.

62 papers.

Sort:

By area:

  1. 2021Provably Faster Algorithms for Bilevel Optimizationcited by 106
  2. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  3. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  4. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  5. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  6. 2022Differentially Private SGDA for Minimax Problemscited by 23
  7. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  8. 2022Stochastic Constrained DRO with a Complexity Independent of Sample Sizecited by 16
  9. 2022Large-scale Optimization of Partial AUC in a Range of False Positive Ratescited by 15
  10. 2024Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimizationcited by 15
  11. 2025Wasserstein Convergence of Score-based Generative Models under Semiconvexity and Discontinuous Gradientscited by 15
  12. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
38 more
  1. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  2. 2021AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimizationcited by 13
  3. 2022Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysiscited by 12
  4. 2023Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimizationcited by 11
  5. 2021Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problemscited by 10
  6. 2022Zeroth-Order Alternating Gradient Descent Ascent Algorithms for a Class of Nonconvex-Nonconcave Minimax Problemscited by 10
  7. 2023Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimizationcited by 10
  8. 2022MaxMatch: Semi-Supervised Learning with Worst-Case Consistencycited by 9
  9. 2021Minimax Optimization with Smooth Algorithmic Adversariescited by 8
  10. 2021Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domaincited by 8
  11. 2023A first-order augmented Lagrangian method for constrained minimax optimizationcited by 8
  12. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  13. 2024On the Generalization Ability of Unsupervised Pretrainingcited by 8
  14. 2021Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemscited by 7
  15. 2022Tight Analysis of Extra-gradient and Optimistic Gradient Methods For Nonconvex Minimax Problemscited by 7
  16. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 6
  17. 2022An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimizationcited by 6
  18. 2023Decentralized gradient descent maximization method for composite nonconvex strongly-concave minimax problemscited by 6
  19. 2021Improved Robustness and Safety for Pre-Adaptation of Meta Reinforcement Learning with Prior Regularizationcited by 4
  20. 2023Efficient Stochastic Approximation of Minimax Excess Risk Optimizationcited by 4
  21. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  22. 2023f-FERM: A Scalable Framework for Robust Fair Empirical Risk Minimizationcited by 4
  23. 2024Single-Loop Stochastic Algorithms for Difference of Max-Structured Weakly Convex Functionscited by 4
  24. 2024Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimizationcited by 3
  25. 2024A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problemscited by 3
  26. 2022A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programmingcited by 2
  27. 2024Two trust region type algorithms for solving nonconvex-strongly concave minimax problemscited by 2
  28. 2024Causal Invariance Learning via Efficient Nonconvex Optimizationcited by 2
  29. 2023Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithmscited by 1
  30. 2023An accelerated first-order regularized momentum descent ascent algorithm for stochastic nonconvex-concave minimax problemscited by 1
  31. 2024Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimizationcited by 1
  32. 2024Stochastic Compositional Minimax Optimization with Provable Convergence Guaranteescited by 1
  33. 2025Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximizationcited by 1
  34. 2025EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimizationcited by 1
  35. 2026Differentially Private Non-convex Distributionally Robust Optimizationcited by 1
  36. 2026Single-Loop Stochastic Projected Damped Extragradient Methods for Stochastic Nonconvex--(Strongly) Concave Minimax Optimizationcited by 1
  37. 2022ScaLA: Accelerating Adaptation of Pre-Trained Transformer-Based Language Models via Efficient Large-Batch Adversarial Noisecited by 0
  38. 2022SAGDA: Achieving O(ε-2) Communication Complexity in Federated Min-Max Learningcited by 0

50 most cited of 62 All 62 (JSON)