Robust Accelerated Primal-Dual Methods for Computing Saddle Points
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913487130722304 |
|---|---|
| author | Zhang, Xuan Aybat, Necdet Serhat Gürbüzbalaban, Mert |
| author_facet | Zhang, Xuan Aybat, Necdet Serhat Gürbüzbalaban, Mert |
| contents | We consider strongly-convex-strongly-concave saddle point problems assuming we have access to unbiased stochastic estimates of the gradients. We propose a stochastic accelerated primal-dual (SAPD) algorithm and show that SAPD sequence, generated using constant primal-dual step sizes, linearly converges to a neighborhood of the unique saddle point. Interpreting the size of the neighborhood as a measure of robustness to gradient noise, we obtain explicit characterizations of robustness in terms of SAPD parameters and problem constants. Based on these characterizations, we develop computationally tractable techniques for optimizing the SAPD parameters, i.e., the primal and dual step sizes, and the momentum parameter, to achieve a desired trade-off between the convergence rate and robustness on the Pareto curve. This allows SAPD to enjoy fast convergence properties while being robust to noise as an accelerated method. SAPD admits convergence guarantees for the distance metric with a variance term optimal up to a logarithmic factor -which can be removed by employing a restarting strategy. We also discuss how convergence and robustness results extend to the convex-concave setting. Finally, we illustrate our framework on distributionally robust logistic regression problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_12743 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Robust Accelerated Primal-Dual Methods for Computing Saddle Points Zhang, Xuan Aybat, Necdet Serhat Gürbüzbalaban, Mert Optimization and Control We consider strongly-convex-strongly-concave saddle point problems assuming we have access to unbiased stochastic estimates of the gradients. We propose a stochastic accelerated primal-dual (SAPD) algorithm and show that SAPD sequence, generated using constant primal-dual step sizes, linearly converges to a neighborhood of the unique saddle point. Interpreting the size of the neighborhood as a measure of robustness to gradient noise, we obtain explicit characterizations of robustness in terms of SAPD parameters and problem constants. Based on these characterizations, we develop computationally tractable techniques for optimizing the SAPD parameters, i.e., the primal and dual step sizes, and the momentum parameter, to achieve a desired trade-off between the convergence rate and robustness on the Pareto curve. This allows SAPD to enjoy fast convergence properties while being robust to noise as an accelerated method. SAPD admits convergence guarantees for the distance metric with a variance term optimal up to a logarithmic factor -which can be removed by employing a restarting strategy. We also discuss how convergence and robustness results extend to the convex-concave setting. Finally, we illustrate our framework on distributionally robust logistic regression problem. |
| title | Robust Accelerated Primal-Dual Methods for Computing Saddle Points |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2111.12743 |