On the Application of Danskin's Theorem to Derivative-Free Minimax Optimization

Abstract

Motivated by Danskin's theorem, gradient-based methods have been applied with empirical success to solve minimax problems that involve non-convex outer minimization and non-concave inner maximization. On the other hand, recent work has demonstrated that Evolution Strategies (ES) algorithms are stochastic gradient approximators that seek robust solutions. In this paper, we address black-box (gradient-free) minimax problems that have long been tackled in a coevolutionary setup. To this end and guaranteed by Danskin's theorem, we employ ES as a stochastic estimator for the descent direction. The proposed approach is validated on a collection of black-box minimax problems. Based on our experiments, our method's performance is comparable with its coevolutionary counterparts and favorable for high-dimensional problems. Its efficacy is demonstrated on a real-world application.

Submitted to LEGO 2018 (14th Int. Workshop on Global Optimization)

References in corpus (3)

• Towards Deep Learning Models Resistant to Adversarial Attacks
• Stochastic simultaneous optimistic optimization
• Adversarial Deep Learning for Robust Detection of Binary Encoded Malware

Cited by in corpus (5)

• Saddle Point Optimization with Approximate Minimization Oracle and its Application to Robust Berthing Control
• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities
• Saddle Point Optimization with Approximate Minimization Oracle
• Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function