Saddle Point Optimization with Approximate Minimization Oracle

Abstract

A major approach to saddle point optimization ${\min }_x{\max }_{y}f(x,y)$ is a gradient based approach as is popularized by generative adversarial networks (GANs). In contrast, we analyze an alternative approach relying only on an oracle that solves a minimization problem approximately. Our approach locates approximate solutions $x^{\prime }$ and $y^{\prime }$ to ${\min }_{x^{\prime }}f(x^{\prime },y)$ and ${\max }_{y^{\prime }}f(x,y^{\prime })$ at a given point $(x,y)$ and updates $(x,y)$ toward these approximate solutions $(x^{\prime },y^{\prime })$ with a learning rate $\eta$. On locally strong convex--concave smooth functions, we derive conditions on $\eta$ to exhibit linear convergence to a local saddle point, which reveals a possible shortcoming of recently developed robust adversarial reinforcement learning algorithms. We develop a heuristic approach to adapt $\eta$ derivative-free and implement zero-order and first-order minimization algorithms. Numerical experiments are conducted to show the tightness of the theoretical results as well as the usefulness of the $\eta$ adaptation mechanism.

Accepted for GECCO 2021

References in corpus (10)

• Robust Adversarial Reinforcement Learning
• The Numerics of GANs
• Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods
• Gradient descent GAN optimization is locally stable
• Adversarially Robust Optimization with Gaussian Processes
• The Implicit and the Inverse Function theorems: easy proofs
• Local Saddle Point Optimization: A Curvature Exploitation Approach
• Frank-Wolfe Algorithms for Saddle Point Problems
• On the Application of Danskin's Theorem to Derivative-Free Minimax Optimization
• Drift Theory in Continuous Search Spaces: Expected Hitting Time of the (1+1)-ES with 1/5 Success Rule

Cited by in corpus (2)

• On Neural Network Identification for Low-Speed Ship Maneuvering Model
• Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control