Randomized Primal-Dual Methods with Adaptive Step Sizes

Erfan Yazdandoost Hamedani, Afrooz Jalilzadeh, Necdet S. Aybat
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:11185-11212, 2023.

Abstract

In this paper we propose a class of randomized primal-dual methods incorporating line search to contend with large-scale saddle point (SP) problems defined by a convex-concave function $\mathcal L(\mathbf{x},y) = \sum_{i=1}^M f_i(x_i)+\Phi(\mathbf{x},y)-h(y)$. We analyze the convergence rate of the proposed method under mere convexity and strong convexity assumptions of $\mathcal L$ in $\mathbf{x}$-variable. In particular, assuming $\nabla_y\Phi(\cdot,\cdot)$ is Lipschitz and $\nabla_{\mathbf{x}}\Phi(\cdot,y)$ is coordinate-wise Lipschitz for any fixed $y$, the ergodic sequence generated by the algorithm achieves the $\mathcal O(M/k)$ convergence rate in the expected primal-dual gap. Furthermore, assuming that $\mathcal L(\cdot,y)$ is strongly convex for any $y$, and that $\Phi(\mathbf{x},\cdot)$ is affine for any $\mathbf{x}$, the scheme enjoys a faster rate of $\mathcal O(M/k^2)$ in terms of primal solution suboptimality. We implemented the proposed algorithmic framework to solve kernel matrix learning problem, and tested it against other state-of-the-art first-order methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-yazdandoost-hamedani23a, title = {Randomized Primal-Dual Methods with Adaptive Step Sizes}, author = {Yazdandoost Hamedani, Erfan and Jalilzadeh, Afrooz and Aybat, Necdet S.}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {11185--11212}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/yazdandoost-hamedani23a/yazdandoost-hamedani23a.pdf}, url = {https://proceedings.mlr.press/v206/yazdandoost-hamedani23a.html}, abstract = {In this paper we propose a class of randomized primal-dual methods incorporating line search to contend with large-scale saddle point (SP) problems defined by a convex-concave function $\mathcal L(\mathbf{x},y) = \sum_{i=1}^M f_i(x_i)+\Phi(\mathbf{x},y)-h(y)$. We analyze the convergence rate of the proposed method under mere convexity and strong convexity assumptions of $\mathcal L$ in $\mathbf{x}$-variable. In particular, assuming $\nabla_y\Phi(\cdot,\cdot)$ is Lipschitz and $\nabla_{\mathbf{x}}\Phi(\cdot,y)$ is coordinate-wise Lipschitz for any fixed $y$, the ergodic sequence generated by the algorithm achieves the $\mathcal O(M/k)$ convergence rate in the expected primal-dual gap. Furthermore, assuming that $\mathcal L(\cdot,y)$ is strongly convex for any $y$, and that $\Phi(\mathbf{x},\cdot)$ is affine for any $\mathbf{x}$, the scheme enjoys a faster rate of $\mathcal O(M/k^2)$ in terms of primal solution suboptimality. We implemented the proposed algorithmic framework to solve kernel matrix learning problem, and tested it against other state-of-the-art first-order methods.} }
Endnote
%0 Conference Paper %T Randomized Primal-Dual Methods with Adaptive Step Sizes %A Erfan Yazdandoost Hamedani %A Afrooz Jalilzadeh %A Necdet S. Aybat %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-yazdandoost-hamedani23a %I PMLR %P 11185--11212 %U https://proceedings.mlr.press/v206/yazdandoost-hamedani23a.html %V 206 %X In this paper we propose a class of randomized primal-dual methods incorporating line search to contend with large-scale saddle point (SP) problems defined by a convex-concave function $\mathcal L(\mathbf{x},y) = \sum_{i=1}^M f_i(x_i)+\Phi(\mathbf{x},y)-h(y)$. We analyze the convergence rate of the proposed method under mere convexity and strong convexity assumptions of $\mathcal L$ in $\mathbf{x}$-variable. In particular, assuming $\nabla_y\Phi(\cdot,\cdot)$ is Lipschitz and $\nabla_{\mathbf{x}}\Phi(\cdot,y)$ is coordinate-wise Lipschitz for any fixed $y$, the ergodic sequence generated by the algorithm achieves the $\mathcal O(M/k)$ convergence rate in the expected primal-dual gap. Furthermore, assuming that $\mathcal L(\cdot,y)$ is strongly convex for any $y$, and that $\Phi(\mathbf{x},\cdot)$ is affine for any $\mathbf{x}$, the scheme enjoys a faster rate of $\mathcal O(M/k^2)$ in terms of primal solution suboptimality. We implemented the proposed algorithmic framework to solve kernel matrix learning problem, and tested it against other state-of-the-art first-order methods.
APA
Yazdandoost Hamedani, E., Jalilzadeh, A. & Aybat, N.S.. (2023). Randomized Primal-Dual Methods with Adaptive Step Sizes. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:11185-11212 Available from https://proceedings.mlr.press/v206/yazdandoost-hamedani23a.html.

Related Material