Gradient-Free Algorithms for Solving Stochastic Saddle Optimization Problems with the Polyak–Łojasiewicz Condition

This paper focuses on solving a subclass of stochastic nonconvex-nonconcave black box optimization problems with a saddle point that satisfy the Polyak–Łojasiewicz (PL) condition. To solve this problem, we provide the first (to our best knowledge) gradient-free algorithm. The proposed approach is ba...

Full description

Saved in:
Bibliographic Details
Published in:Programming and computer software 2023-12, Vol.49 (6), p.535-547
Main Authors: Sadykov, S. I., Lobanov, A. V., Raigorodskii, A. M.
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Artificial Intelligence
Bias
Computer Science
Machine learning
Mathematical analysis
Operating Systems
Optimization
Saddle points
Software Engineering
Software Engineering/Programming and Operating Systems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper focuses on solving a subclass of stochastic nonconvex-nonconcave black box optimization problems with a saddle point that satisfy the Polyak–Łojasiewicz (PL) condition. To solve this problem, we provide the first (to our best knowledge) gradient-free algorithm. The proposed approach is based on applying a gradient approximation (kernel approximation) to an oracle-biased stochastic gradient descent algorithm. We present theoretical estimates that guarantee its global linear rate of convergence to the desired accuracy. The theoretical results are checked on a model example by comparison with an algorithm using Gaussian approximation.
ISSN:0361-7688
1608-3261
DOI:10.1134/S0361768823060063