Efficient Regret Minimization in Non-Convex Games

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.

• Publication year

  2017

• Venue

  International Conference on Machine Learning

• Publication date

  2017-07-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1708.00075
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Generative Adversarial Networks

  2021cited by this paper
• Accelerated Methods for Non-Convex Optimization

  2016cited by this paper
• Unrolled Generative Adversarial Networks

  2016cited by this paper
• Connecting Generative Adversarial Networks and Actor-Critic Methods

  2016cited by this paper
• Variance Reduction for Faster Non-Convex Optimization

  2016cited by this paper
• Second-Order Stochastic Optimization for Machine Learning in Linear Time

  2016cited by this paper
• Finding approximate local minima faster than gradient descent

  2016cited by this paper
• Finding Approximate Local Minima for Nonconvex Optimization in Linear Time

  2016cited by this paper
• Introduction to Online Convex Optimization

  2016cited by this paper
• Convergence rates of sub-sampled Newton methods

  2015cited by this paper
• Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming

  2013cited by this paper
• The Multiplicative Weights Update Method: a Meta-Algorithm and Applications

  2012cited by this paper
• Online Learning and Online Convex Optimization

  2012cited by this paper
• Adaptive Subgradient Methods for Online Learning and Stochastic Optimization

  2011cited by this paper
• Computational Equivalence of Fixed Points and No Regret Algorithms, and Convergence to Equilibria

  2007cited by this paper
• Prediction, learning, and games

  2006cited by this paper
• Cubic regularization of Newton method and its global performance

  2006cited by this paper
• From External to Internal Regret

  2005cited by this paper
• Online Convex Programming and Generalized Infinitesimal Gradient Ascent

  2003cited by this paper
• A simple adaptive procedure leading to correlated equilibrium

  2000cited by this paper
• A decision-theoretic generalization of on-line learning and an application to boosting

  1997cited by this paper
• Universal Portfolios

  1996cited by this paper
• Aggregating strategies

  1990cited by this paper

• Non-Stationary Functional Bilevel Optimization

  2026cites this paper
• An online forecasting-based fine-tuning pipeline for time-series anomaly prediction.

  2026cites this paper
• Fully First-Order Algorithms for Online Bilevel Optimization

  2026cites this paper
• Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization

  2026influential citation
• Probabilistic electric load forecasting via adaptive online learning and multi-objective optimization: A NA-TP forecasting approach

  2026cites this paper
• Robust Multimodal Learning via Entropy-Gated Contrastive Fusion

  2025cites this paper
• Nesterov Accelerated Gradient Tracking With Adam for Distributed Online Optimization

  2025cites this paper
• Online Non-Convex Non-Cooperative Cluster-Based Games With Byzantine Resiliency in Decentralized Multi-Agent Systems

  2025cites this paper
• Momentum-Based Distributed Disturbance Feedback Optimization of Heterogeneous Multiagent Systems: A Timescale Separation Approach

  2025cites this paper
• Online Decision-Focused Learning

  2025cites this paper
• Distributed Online Optimization Of Consensus-Based Adaptive Gradients Over Time-Varying Networks

  2025influential citation
• Decentralized non-convex online optimization with adaptive momentum estimation and quantized communication

  2025cites this paper
• Personalized Federated Learning for Cellular VR: Online Learning and Dynamic Caching

  2025cites this paper
• Privacy-Preserving Distributed Online Mirror Descent for Nonconvex Optimization

  2025cites this paper
• Convergence of Regret Matching in Potential Games and Constrained Optimization

  2025influential citation
• Event-Driven Online Vertical Federated Learning

  2025influential citation
• First-order (coarse) correlated equilibria in non-concave games

  2024cites this paper
• Online Non-convex Learning in Dynamic Environments

  2024influential citation
• Online Distributed Stochastic Gradient Algorithm for Nonconvex Optimization With Compressed Communication

  2024influential citation
• Adaptive Passive-Aggressive Framework for Online Regression with Side Information

  2024cites this paper
• A Hybrid Federated Learning Architecture With Online Learning and Model Compression

  2024cites this paper
• In-Trajectory Inverse Reinforcement Learning: Learn Incrementally Before an Ongoing Trajectory Terminates

  2024influential citation
• Provable Length Generalization in Sequence Prediction via Spectral Filtering

  2024influential citation
• In-Trajectory Inverse Reinforcement Learning: Learn Incrementally From An Ongoing Trajectory

  2024influential citation
• Distributed Online Bandit Nonconvex Optimization with One-Point Residual Feedback via Dynamic Regret

  2024cites this paper
• Online Nonconvex Bilevel Optimization with Bregman Divergences

  2024influential citation
• Online Policy Optimization in Unknown Nonlinear Systems

  2024cites this paper
• Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization

  2023cites this paper
• Online Distributed Seeking for First-Order Nash Equilibria of Nonconvex Noncooperative Games With Multiple Clusters

  2023cites this paper
• Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion

  2023cites this paper
• Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems

  2023cites this paper
• A Gradient-based Approach for Online Robust Deep Neural Network Training with Noisy Labels

  2023cites this paper
• Online Min-max Problems with Non-convexity and Non-stationarity

  2023influential citation
• Non-Convex Bilevel Optimization with Time-Varying Objective Functions

  2023influential citation
• Online Nonconvex Optimization with Limited Instantaneous Oracle Feedback

  2023influential citation
• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting

  2023cites this paper
• Learning Multi-agent Behaviors from Distributed and Streaming Demonstrations

  2023influential citation
• Time-Variation in Online Nonconvex Optimization Enables Escaping From Spurious Local Minima

  2023cites this paper
• Game-Theoretic Mixed $H_{2}/H_{\infty}$ Control with Sparsity Constraint for Multi-Agent Control Systems

  2023cites this paper
• Playing Large Games with Oracles and AI Debate

  2023cites this paper
• Online Non-convex Optimization with Long-term Non-convex Constraints

  2023cites this paper
• Online Min-max Optimization: Nonconvexity, Nonstationarity, and Dynamic Regret

  2022influential citation
• Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods

  2022influential citation
• Imbalanced fault diagnosis of rolling bearing using a deep gradient improved generative adversarial network

  2022cites this paper
• Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations

  2022cites this paper
• Online Adaptive Controller Selection in Time-Varying Systems: No-Regret via Contractive Perturbations

  2022cites this paper
• Exploitability Minimization in Games and Beyond

  2022cites this paper
• Distributed Online Non-convex Optimization with Composite Regret

  2022cites this paper
• Regrets of proximal method of multipliers for online non-convex optimization with long term constraints

  2022cites this paper
• Stochastic Zeroth-Order Optimization under Nonstationarity and Nonconvexity

  2022influential citation
• Non-convex online learning via algorithmic equivalence

  2022cites this paper
• CycleGAN-Based Singing/Humming to Instrument Conversion Technique

  2022cites this paper
• Future Gradient Descent for Adapting the Temporal Shifting Data Distribution in Online Recommendation Systems

  2022influential citation
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature

  2021cites this paper
• Diminishing Regret for Online Nonconvex Optimization

  2021cites this paper
• Memory Efficient Online Meta Learning

  2021cites this paper
• Zeroth-Order Non-Convex Learning via Hierarchical Dual Averaging

  2021cites this paper
• Multi-task Federated Edge Learning (MtFEEL) in Wireless Networks

  2021cites this paper
• Dynamic Regret Analysis for Online Meta-Learning

  2021cites this paper
• Drinking From a Firehose: Continual Learning With Web-Scale Natural Language

  2020cites this paper
• SGLB: Stochastic Gradient Langevin Boosting

  2020cites this paper
• On the Absence of Spurious Local Trajectories in Online Nonconvex Optimization

  2020cites this paper
• Second-Order Online Nonconvex Optimization

  2020cites this paper
• Correlated Adversarial Imitation Learning

  2020cites this paper
• Non-stationary neural network for stock return prediction

  2020cites this paper
• RNN-based Online Learning: An Efficient First-Order Optimization Algorithm with a Convergence Guarantee

  2020cites this paper
• Time-varying neural network for stock return prediction

  2020cites this paper
• Achieving Online Regression Performance of LSTMs With Simple RNNs

  2020cites this paper
• Online non-convex learning for river pollution source identification

  2020cites this paper
• Follow the Neurally-Perturbed Leader for Adversarial Training

  2020cites this paper
• A Second-order Equilibrium in Nonconvex-Nonconcave Min-max Optimization: Existence and Algorithm

  2020cites this paper
• A Hitting Time Analysis of Non-convex Optimization with Time-Varying Revelations

  2020cites this paper
• Regret minimization in stochastic non-convex learning via a proximal-gradient approach

  2020influential citation
• Online non-convex optimization with imperfect feedback

  2020cites this paper
• Adaptive Gradient Tracking In Stochastic Optimization

  2020cites this paper
• Game-Theoretic Mixed H2/H∞ Control with Sparsity Constraint for Multi-agent Networked Control Systems

  2019influential citation
• Dual Averaging Method for Online Graph-structured Sparsity

  2019influential citation
• Online Convex Optimization in Changing Environments and its Application to Resource Allocation

  2019cites this paper
• Stabilizing Generative Adversarial Networks: A Survey

  2019cites this paper
• No-Regret Non-Convex Online Meta-Learning

  2019influential citation
• Distributed Bandit Online Convex Optimization With Time-Varying Coupled Inequality Constraints

  2019cites this paper
• Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization

  2019cites this paper
• Online Adaptive Principal Component Analysis and Its extensions

  2019cites this paper
• Online Non-Convex Learning: Following the Perturbed Leader is Optimal

  2019cites this paper
• Time-Smoothed Gradients for Online Forecasting

  2019influential citation
• Escaping Spurious Local Minimum Trajectories in Online Time-varying Nonconvex Optimization

  2019cites this paper
• Online Meta-Learning on Non-convex Setting

  2019cites this paper
• Dynamic Local Regret for Non-convex Online Forecasting

  2019influential citation
• No-Regret Learning in Unknown Games with Correlated Payoffs

  2019cites this paper
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization

  2019cites this paper
• Absence of Spurious Local Trajectories in Time-Varying Optimization: A Control-Theoretic Perspective

  2019cites this paper
• Online Active Learning of Reject Option Classifiers

  2019cites this paper
• A Variational Inequality Perspective on Generative Adversarial Networks

  2018cites this paper
• Online Continuous Submodular Maximization

  2018influential citation
• Efficient Online Hyperparameter Learning for Traffic Flow Prediction

  2018influential citation
• Efficient Online Hyperparameter Optimization for Kernel Ridge Regression with Applications to Traffic Time Series Prediction

  2018cites this paper
• A Local Regret in Nonconvex Online Learning

  2018cites this paper
• Learning in Non-convex Games with an Optimization Oracle

  2018cites this paper
• Convergence Problems with Generative Adversarial Networks (GANs)

  2018cites this paper
• Beyond Local Nash Equilibria for Adversarial Networks

  2018cites this paper