Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems

Mohammad Khalafi, Digvijay Boob
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:16250-16270, 2023.

Abstract

We investigate a primal-dual (PD) method for the saddle point problem (SPP) that uses a linear approximation of the primal function instead of the standard proximal step, resulting in a linearized PD (LPD) method. For convex-strongly concave SPP, we observe that the LPD method has a suboptimal dependence on the Lipschitz constant of the primal function. To fix this issue, we combine features of Accelerated Gradient Descent with the LPD method resulting in a single-loop Accelerated Linearized Primal-Dual (ALPD) method. ALPD method achieves the optimal gradient complexity when the SPP has a semi-linear coupling function. We also present an inexact ALPD method for SPPs with a general nonlinear coupling function that maintains the optimal gradient evaluations of the primal parts and significantly improves the gradient evaluations of the coupling term compared to the ALPD method. We verify our findings with numerical experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-khalafi23a, title = {Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems}, author = {Khalafi, Mohammad and Boob, Digvijay}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {16250--16270}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/khalafi23a/khalafi23a.pdf}, url = {https://proceedings.mlr.press/v202/khalafi23a.html}, abstract = {We investigate a primal-dual (PD) method for the saddle point problem (SPP) that uses a linear approximation of the primal function instead of the standard proximal step, resulting in a linearized PD (LPD) method. For convex-strongly concave SPP, we observe that the LPD method has a suboptimal dependence on the Lipschitz constant of the primal function. To fix this issue, we combine features of Accelerated Gradient Descent with the LPD method resulting in a single-loop Accelerated Linearized Primal-Dual (ALPD) method. ALPD method achieves the optimal gradient complexity when the SPP has a semi-linear coupling function. We also present an inexact ALPD method for SPPs with a general nonlinear coupling function that maintains the optimal gradient evaluations of the primal parts and significantly improves the gradient evaluations of the coupling term compared to the ALPD method. We verify our findings with numerical experiments.} }
Endnote
%0 Conference Paper %T Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems %A Mohammad Khalafi %A Digvijay Boob %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-khalafi23a %I PMLR %P 16250--16270 %U https://proceedings.mlr.press/v202/khalafi23a.html %V 202 %X We investigate a primal-dual (PD) method for the saddle point problem (SPP) that uses a linear approximation of the primal function instead of the standard proximal step, resulting in a linearized PD (LPD) method. For convex-strongly concave SPP, we observe that the LPD method has a suboptimal dependence on the Lipschitz constant of the primal function. To fix this issue, we combine features of Accelerated Gradient Descent with the LPD method resulting in a single-loop Accelerated Linearized Primal-Dual (ALPD) method. ALPD method achieves the optimal gradient complexity when the SPP has a semi-linear coupling function. We also present an inexact ALPD method for SPPs with a general nonlinear coupling function that maintains the optimal gradient evaluations of the primal parts and significantly improves the gradient evaluations of the coupling term compared to the ALPD method. We verify our findings with numerical experiments.
APA
Khalafi, M. & Boob, D.. (2023). Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:16250-16270 Available from https://proceedings.mlr.press/v202/khalafi23a.html.

Related Material