Gradient-free algorithm for saddle point problems under overparametrization

This paper focuses on solving a stochastic saddle point problem (SPP) under an overparameterized regime for the case, when the gradient computation is impractical. As an intermediate step, we generalize Same-sample Stochastic Extra-gradient algorithm (Gorbunov et al., 2022) to a biased oracle and es...

Full description

Saved in:
Bibliographic Details
Published in:Chaos, solitons and fractals solitons and fractals, 2024-08, Vol.185, p.115048, Article 115048
Main Authors: Statkevich, Ekaterina, Bondar, Sofiya, Dvinskikh, Darina, Gasnikov, Alexander, Lobanov, Aleksandr
Format: Article
Language:English
Subjects:
Bounded noise
Gradient-free oracle
Overparametrization
Saddle point problem
Stochastic algorithm
Citations: Items that this one cites
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 stochastic saddle point problem (SPP) under an overparameterized regime for the case, when the gradient computation is impractical. As an intermediate step, we generalize Same-sample Stochastic Extra-gradient algorithm (Gorbunov et al., 2022) to a biased oracle and estimate novel convergence rates. As the result of the paper we introduce an algorithm, which uses gradient approximation instead of a gradient oracle. We also conduct an analysis to find the maximum admissible level of adversarial noise and the optimal number of iterations at which our algorithm can guarantee achieving the desired accuracy. •Generalized the S-SEG algorithm to a biased oracle.•Specified the result with Uniform Sampling and Importance Sampling based algorithm.•Proposed Zero-Order Same-sample Stochastic Extragradient algorithm for SPP.•Corroborated our theoretical results with experimental testing.•Compared our algorithm with several other algorithms, used for the solution of SPP
ISSN:0960-0779
1873-2887
DOI:10.1016/j.chaos.2024.115048