Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem

DOI10.1007/978-3-030-58657-7_11MaRDI QIDQ4965105zbMATH OpenOpenAlexFDO

Authors Aleksandr Beznosikov, Abdurakhmon Sadiev, Alexander V. Gasnikov

Publication date 25 February 2021

Published in Mathematical Optimization Theory and Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.05913

zbMATH Keywords

saddle-point problemstochastic optimizationzeroth-order optimization

Mathematics Subject Classification ID

Stochastic programming (90C15) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

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 $fracnlogn$ 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.

Recommendations

• Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
• Stochastic intermediate gradient method for convex problems with stochastic inexact oracle
• Accelerated stochastic algorithms for convex-concave saddle-point problems
• Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact
• Stochastic intermediate gradient method for convex optimization problems
• Stochastic generalized gradient method for nonconvex nonsmooth stochastic optimization
• An accelerated method for derivative-free smooth stochastic convex optimization
• Universal intermediate gradient method for convex problems with inexact oracle
• Gradient-free two-point methods for solving stochastic nonsmooth convex optimization problems with small non-random noises
• Stochastic Successive Convex Approximation for Non-Convex Constrained Stochastic Optimization

Cites work

• Accelerated gradient-free optimization methods with a non-Euclidean proximal operator
• Accelerated methods for saddle-point problem
• An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback
• Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Optimal Rates for Zero-Order Convex Optimization: The Power of Two Function Evaluations
• Random gradient-free minimization of convex functions
• Reinforcement learning. An introduction
• Stochastic online optimization. Single-point and multi-point non-linear multi-armed bandits. Convex and strongly-convex case

Cited in

(17)

• Noisy zeroth-order optimization for non-smooth saddle point problems
• One-point gradient-free methods for smooth and non-smooth saddle-point problems
• Improved exploitation of higher order smoothness in derivative-free optimization
• An accelerated method for derivative-free smooth stochastic convex optimization
• Accelerated stochastic algorithms for convex-concave saddle-point problems
• Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex
• Gradient-free methods for non-smooth convex stochastic optimization with heavy-tailed noise on convex compact
• Zeroth-order single-loop algorithms for nonconvex-linear minimax problems
• Accelerated gradient methods with absolute and relative noise in the gradient
• Stochastic Saddle Point Problems with Decision-Dependent Distributions
• Recent theoretical advances in decentralized distributed convex optimization
• Derivative-free alternating projection algorithms for general nonconvex-concave minimax problems
• General procedure to provide high-probability guarantees for stochastic saddle point problems
• Stochastic adversarial noise in the ``black box optimization problem
• Gradient norm regularization second-order algorithms for solving nonconvex-strongly concave minimax problems
• Accelerated zero-order SGD under high-order smoothness and overparameterized regime
• Stochastic intermediate gradient method for convex problems with stochastic inexact oracle

This page was built for publication: Gradient-Free Methods with Inexact Oracle for Convex-Concave Stochastic Saddle-Point Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4965105)