A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2019
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909810688000000 |
|---|---|
| author | Hamedani, Erfan Yazdandoost Jalilzadeh, Afrooz Aybat, Necdet Serhat |
| author_facet | Hamedani, Erfan Yazdandoost Jalilzadeh, Afrooz Aybat, Necdet Serhat |
| contents | We consider (stochastic) convex-concave saddle point (SP) problems with high-dimensional decision variables, arising in various applications including machine learning problems. To contend with the challenges in computing full gradients, we employ a randomized block-coordinate primal-dual scheme in which randomly selected primal and dual blocks of variables are updated. We consider both deterministic and stochastic settings, where deterministic partial gradients and their randomly sampled estimates are used, respectively, at each iteration. We investigate the convergence of the proposed method under different blocking strategies and provide the corresponding complexity results. While the best-known computational complexity result for computing a saddle point with $\varepsilon$ primal-dual gap for deterministic primal-dual methods using full gradients is $\mathcal O(\max\{m,n\}^2/\varepsilon)$, where $m$ and $n$ denote the dimensions of primal and dual variables, respectively, we show that our proposed randomized block-coordinate method achieves an improved complexity of $\mathcal O(mn/\varepsilon)$ assuming a coordinate-friendly structure on the problem. Moreover, for the stochastic setting where a mini-batch sample gradient is utilized, we show a computational complexity of $\tilde{\mathcal{O}}(m^2n^2/\varepsilon^2)$ through acceleration. Finally, almost sure convergence of the iterate sequence to a saddle point is established. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1907_03886 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems Hamedani, Erfan Yazdandoost Jalilzadeh, Afrooz Aybat, Necdet Serhat Optimization and Control We consider (stochastic) convex-concave saddle point (SP) problems with high-dimensional decision variables, arising in various applications including machine learning problems. To contend with the challenges in computing full gradients, we employ a randomized block-coordinate primal-dual scheme in which randomly selected primal and dual blocks of variables are updated. We consider both deterministic and stochastic settings, where deterministic partial gradients and their randomly sampled estimates are used, respectively, at each iteration. We investigate the convergence of the proposed method under different blocking strategies and provide the corresponding complexity results. While the best-known computational complexity result for computing a saddle point with $\varepsilon$ primal-dual gap for deterministic primal-dual methods using full gradients is $\mathcal O(\max\{m,n\}^2/\varepsilon)$, where $m$ and $n$ denote the dimensions of primal and dual variables, respectively, we show that our proposed randomized block-coordinate method achieves an improved complexity of $\mathcal O(mn/\varepsilon)$ assuming a coordinate-friendly structure on the problem. Moreover, for the stochastic setting where a mini-batch sample gradient is utilized, we show a computational complexity of $\tilde{\mathcal{O}}(m^2n^2/\varepsilon^2)$ through acceleration. Finally, almost sure convergence of the iterate sequence to a saddle point is established. |
| title | A Randomized Block-Coordinate Primal-Dual Method for Large-scale Stochastic Saddle Point Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/1907.03886 |