mlsanityData to 14 Oct 2026

Exploiting hidden structures in non-convex games for convergence to Nash equilibrium

arXiv 2312.16609 ↗First posted 27 Dec 2023cs.GT cs.LGcited by 3

Not on the map. Why?

Abstract (arXiv)

A wide array of modern machine learning applications - from adversarial models to multi-agent reinforcement learning - can be formulated as non-cooperative games whose Nash equilibria represent the system's desired operational states. Despite having a highly non-convex loss landscape, many cases of interest possess a latent convex structure that could potentially be leveraged to yield convergence to equilibrium. Driven by this observation, our paper proposes a flexible first-order method that successfully exploits such "hidden structures" and achieves convergence under minimal assumptions for the transformation connecting the players' control variables to the game's latent, convex-structured layer. The proposed method - which we call preconditioned hidden gradient descent (PHGD) - hinges on a judiciously chosen gradient preconditioning scheme related to natural gradient methods. Importantly, we make no separability assumptions for the game's hidden structure, and we provide explicit convergence rate guarantees for both deterministic and stochastic environments.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 18 of its 48 references that are in the map. First posted on arXiv 27 Dec 2023.

Builds on

18 of 48 references.

References · 18

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2017Robust Adversarial Reinforcement Learningcited by 451
  3. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 131
  4. 2019On the convergence of single-call stochastic extra-gradient methodscited by 89
  5. 2020The Complexity of Constrained Min-Max Optimizationcited by 82
  6. 2016Learning in games with continuous action sets and unknown payoff functionscited by 81
  7. 2019Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networkscited by 76
  8. 2020The limits of min-max optimization algorithms: convergence to spurious non-critical setscited by 50
  9. 2022Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planningcited by 48
  10. 2018Bandit learning in concave N-person gamescited by 35
  11. 2021Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertisingcited by 31
  12. 2022A unified stochastic approximation framework for learning in gamescited by 23
6 more
  1. 2018Multi-agent online learning in time-varying gamescited by 17
  2. 2020On the Impossibility of Global Convergence in Multi-Loss Optimizationcited by 16
  3. 2019Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Gamescited by 15
  4. 2021Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascentcited by 8
  5. 2016Distributed stochastic optimization via matrix exponential learningcited by 6
  6. 2020A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Netscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 0; 2026: 1.

3 papers.

  1. 2024Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problemcited by 5
  2. 2024Solving Hidden Monotone Variational Inequalities with Surrogate Lossescited by 1
  3. 2026Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedbackcited by 0