Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization

Abstract

Saddle-point optimization problems are an important class of optimization problems with applications to game theory, multi-agent reinforcement learning and machine learning. A majority of the rich literature available for saddle-point optimization has focused on the offline setting. In this paper, we study nonstationary versions of stochastic, smooth, strongly-convex and strongly-concave saddle-point optimization problem, in both online (or first-order) and multi-point bandit (or zeroth-order) settings. We first propose natural notions of regret for such nonstationary saddle-point optimization problems. We then analyze extragradient and Frank-Wolfe algorithms, for the unconstrained and constrained settings respectively, for the above class of nonstationary saddle-point optimization problems. We establish sub-linear regret bounds on the proposed notions of regret in both the online and bandit setting.

References in corpus (13)

• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Fast Convergence of Regularized Learning in Games
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Online Forecasting of Total-Variation-bounded Sequences
• The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
• Competing Against Equilibria in Zero-Sum Games with Evolving Payoffs
• Online Nonparametric Regression with General Loss Functions
• Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• Chasing Convex Bodies with Linear Competitive Ratio

Cited by in corpus (6)

• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Non-stationary Online Regression
• Efficient Projection-Free Algorithms for Saddle Point Problems
• New First-Order Algorithms for Stochastic Variational Inequalities
• Proximal Point Method for Online Saddle Point Problem