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

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

## 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 (most cited first, 18 of 18)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learning](https://mlsanity.com/paper/2206.15378/) (2022)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [The Complexity of Constrained Min-Max Optimization](https://mlsanity.com/paper/2009.09623/) (2020)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks](https://mlsanity.com/paper/1905.10961/) (2019)
- [The limits of min-max optimization algorithms: convergence to spurious non-critical sets](https://mlsanity.com/paper/2006.09065/) (2020)
- [Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning](https://mlsanity.com/paper/2210.05492/) (2022)
- [Bandit learning in concave N-person games](https://mlsanity.com/paper/1810.01925/) (2018)
- [Neural Auction: End-to-End Learning of Auction Mechanisms for E-Commerce Advertising](https://mlsanity.com/paper/2106.03593/) (2021)
- [A unified stochastic approximation framework for learning in games](https://mlsanity.com/paper/2206.03922/) (2022)
- [Multi-agent online learning in time-varying games](https://mlsanity.com/paper/1809.03066/) (2018)
- [On the Impossibility of Global Convergence in Multi-Loss Optimization](https://mlsanity.com/paper/2005.12649/) (2020)
- [Poincar'e Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games](https://mlsanity.com/paper/1910.13010/) (2019)
- [Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent](https://mlsanity.com/paper/2101.05248/) (2021)
- [Distributed stochastic optimization via matrix exponential learning](https://mlsanity.com/paper/1606.01190/) (2016)
- [A Limited-Capacity Minimax Theorem for Non-Convex Games or: How I Learned to Stop Worrying about Mixed-Nash and Love Neural Nets](https://mlsanity.com/paper/2002.05820/) (2020)

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

- [Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem](https://mlsanity.com/paper/2410.05673/) (2024)
- [Solving Hidden Monotone Variational Inequalities with Surrogate Losses](https://mlsanity.com/paper/2411.05228/) (2024)
- [Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback](https://mlsanity.com/paper/2605.26373/) (2026)

## 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.