Gradient-Free Methods for Saddle-Point Problem

Abstract

In the paper, we generalize the approach Gasnikov et. al, 2017, which allows to solve (stochastic) convex optimization problems with an inexact gradient-free oracle, to the convex-concave saddle-point problem. The proposed approach works, at least, like the best existing approaches. But for a special set-up (simplex type constraints and closeness of Lipschitz constants in 1 and 2 norms) our approach reduces $\frac{n}{\log n}$ times the required number of oracle calls (function calculations). Our method uses a stochastic approximation of the gradient via finite differences. In this case, the function must be specified not only on the optimization set itself, but in a certain neighbourhood of it. In the second part of the paper, we analyze the case when such an assumption cannot be made, we propose a general approach on how to modernize the method to solve this problem, and also we apply this approach to particular cases of some classical sets.

Appears in: Communications in Computer and Information Science book series (CCIS,volume 1275). Minor modifications (typos) with respect to the CCIS version. 26 pages, 1 algorithm, 5 figures, 3 tables

References in corpus (1)

• Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization

Cited by in corpus (5)

• Solving smooth min-min and min-max problems by mixed oracle algorithms
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• Gradient-free algorithm for saddle point problems under overparametrization
• Linearly Convergent Gradient-Free Methods for Minimization of Parabolic Approximation
• General Procedure to Provide High-Probability Guarantees for Stochastic Saddle Point Problems