One-Point Gradient-Free Methods for Smooth and Non-Smooth Saddle-Point Problems

Abstract

In this paper, we analyze gradient-free methods with one-point feedback for stochastic saddle point problems ${\min }_x{\max }_y\phi (x,y)$. For non-smooth and smooth cases, we present analysis in a general geometric setup with arbitrary Bregman divergence. For problems with higher-order smoothness, the analysis is carried out only in the Euclidean case. The estimates we have obtained repeat the best currently known estimates of gradient-free methods with one-point feedback for problems of imagining a convex or strongly convex function. The paper uses three main approaches to recovering the gradient through finite differences: standard with a random direction, as well as its modifications with kernels and residual feedback. We also provide experiments to compare these approaches for the matrix game.

arXiv admin note: text overlap with arXiv:2005.05913

References in corpus (4)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Derivative-Free Method For Composite Optimization With Applications To Decentralized Distributed Optimization
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• One-Point Gradient-Free Methods for Smooth and Non-Smooth Saddle-Point Problems

Cited by in corpus (1)

• One-Point Gradient-Free Methods for Smooth and Non-Smooth Saddle-Point Problems