# Efficient Regret Minimization in Non-Convex Games

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2017.

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

- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods](https://mlsanity.com/paper/2207.02829/) (2022)
- [Non-convex online learning via algorithmic equivalence](https://mlsanity.com/paper/2205.15235/) (2022)
- [Non-Convex Bilevel Optimization with Time-Varying Objective Functions](https://mlsanity.com/paper/2308.03811/) (2023)
- [In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before An Ongoing Trajectory Terminates](https://mlsanity.com/paper/2410.15612/) (2024)
- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)
- [Playing Large Games with Oracles and AI Debate](https://mlsanity.com/paper/2312.04792/) (2023)
- [Dynamic Regret Analysis for Online Meta-Learning](https://mlsanity.com/paper/2109.14375/) (2021)
- [Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems](https://mlsanity.com/paper/2302.12320/) (2023)
- [Online Decision-Focused Learning](https://mlsanity.com/paper/2505.13564/) (2025)
- [Future Gradient Descent for Adapting the Temporal Shifting Data Distribution in Online Recommendation Systems](https://mlsanity.com/paper/2209.01143/) (2022)
- [Provable Length Generalization in Sequence Prediction via Spectral Filtering](https://mlsanity.com/paper/2411.01035/) (2024)
- [Distributed Online Non-convex Optimization with Composite Regret](https://mlsanity.com/paper/2209.10105/) (2022)
- [Online Nonconvex Bilevel Optimization with Bregman Divergences](https://mlsanity.com/paper/2409.10470/) (2024)
- [Personalized Federated Learning for Cellular VR: Online Learning and Dynamic Caching](https://mlsanity.com/paper/2501.11745/) (2025)
- [Robust Multimodal Learning via Entropy-Gated Contrastive Fusion](https://mlsanity.com/paper/2505.15417/) (2025)
- [Convergence of Regret Matching in Potential Games and Constrained Optimization](https://mlsanity.com/paper/2510.17067/) (2025)
- [Non-Stationary Functional Bilevel Optimization](https://mlsanity.com/paper/2601.15363/) (2026)
- [A Gradient-based Approach for Online Robust Deep Neural Network Training with Noisy Labels](https://mlsanity.com/paper/2306.05046/) (2023)
- [Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization](https://mlsanity.com/paper/2602.06457/) (2026)
- [Multi-task Federated Edge Learning (MtFEEL) in Wireless Networks](https://mlsanity.com/paper/2108.02517/) (2021)
- [Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting](https://mlsanity.com/paper/2310.06081/) (2023)
- [Online Non-convex Optimization with Long-term Non-convex Constraints](https://mlsanity.com/paper/2311.02426/) (2023)
- [Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret](https://mlsanity.com/paper/2409.15680/) (2024)
- [Event-Driven Online Vertical Federated Learning](https://mlsanity.com/paper/2506.14911/) (2025)
- [Fully First-Order Algorithms for Online Bilevel Optimization](https://mlsanity.com/paper/2602.11665/) (2026)
- [Online Optimization of Difference-of-Convex Compositions with Smooth Mappings](https://mlsanity.com/paper/2607.19553/) (2026)

## Abstract (arXiv)

We consider regret minimization in repeated games with non-convex loss functions. Minimizing the standard notion of regret is computationally intractable. Thus, we define a natural notion of regret which permits efficient optimization and generalizes offline guarantees for convergence to an approximate local optimum. We give gradient-based methods that achieve optimal regret, which in turn guarantee convergence to equilibrium in this framework.