Gradient-free algorithm for saddle point problems under overparametrization
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911903458000896 |
|---|---|
| author | Statkevich, Ekaterina Bondar, Sofiya Dvinskikh, Darina Gasnikov, Alexander Lobanov, Aleksandr |
| author_facet | Statkevich, Ekaterina Bondar, Sofiya Dvinskikh, Darina Gasnikov, Alexander Lobanov, Aleksandr |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_02308 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Gradient-free algorithm for saddle point problems under overparametrization Statkevich, Ekaterina Bondar, Sofiya Dvinskikh, Darina Gasnikov, Alexander Lobanov, Aleksandr Optimization and Control 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. |
| title | Gradient-free algorithm for saddle point problems under overparametrization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2406.02308 |