Gradient-free algorithm for saddle point problems under overparametrization
Ekaterina Statkevich,
Sofiya Bondar,
Darina Dvinskikh,
Alexander Gasnikov and
Aleksandr Lobanov
Chaos, Solitons & Fractals, 2024, vol. 185, issue C
Abstract:
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.
Keywords: Saddle point problem; Gradient-free oracle; Stochastic algorithm; Bounded noise; Overparametrization (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077924006003
Full text for ScienceDirect subscribers only
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:185:y:2024:i:c:s0960077924006003
DOI: 10.1016/j.chaos.2024.115048
Access Statistics for this article
Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros
More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().