Convex-Concave Interpolation and Application of PEP to the Bilinear-Coupled Saddle Point Problem

V. O. Krivchenko ; A. V. Gasnikov ; D. A. Kovalev

Russian journal of nonlinear dynamics, Tome 20 (2024) no. 5, pp. 875-893.

Résumé

In this paper we present interpolation conditions for several important convex-concave function classes: nonsmooth convex-concave functions, conditions for difference of strongly-convex functions in a form that contains oracle information exclusively and smooth convex-concave functions with a bilinear coupling term. Then we demonstrate how the performance estimation problem approach can be adapted to analyze the exact worst-case convergence behavior of first-order methods applied to composite bilinear-coupled min-max problems. Using the performance estimation problem approach, we estimate iteration complexities for several first-order fixed-step methods, Sim-GDA and Alt-GDA, which are applied to smooth convex-concave functions with a bilinear coupling term.

Détail

Keywords: saddle point, convex-concave functions, bilinear coupling, performance estimation problem
Mots-clés : interpolation conditions

Bibliographie

[1] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y., “Generative Adversarial Networks”, Commun. ACM, 63:11 (2020), 139–144 | DOI

[2] Li, S., Wu, Y., Cui, X., Dong, H., Fang, F., and Russell, S., “Robust Multi-Agent Reinforcement Learning via Minimax Deep Deterministic Policy Gradient”, Proc. AAAI Conf. on Artificial Intelligence, 33:01 (2019), 4213–4220 | DOI | MR

[3] Zhang, G., Bao, X., Lessard, L., and Grosse, R., “A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints”, J. Mach. Learn. Res., 22(103) (2021), 1–39 | MR

[4] Zhang, G., Wang, Y., Lessard, L., and Grosse, R., “Near-Optimal Local Convergence of Alternating Gradient Descent-Ascent for Minimax Optimization”, Proc. of the 25th Internat. Conf. on Artificial Intelligence and Statistics (PMLR, Valencia, Spain, Mar 2022), 7659–7679

[5] Lee, J., Cho, H., and Yun, C., , 2024, 76 pp. arXiv:2402.10475 [math.OC]

[6] Drori, Y. and Teboulle, M., “Performance of First-Order Methods for Smooth Convex Minimization: A Novel Approach”, Math. Program., 145:1–2 (2014), 451–482 | DOI | MR | Zbl

[7] Lessard, L., Recht, B., and Packard, A., “Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints”, SIAM J. Optim., 26:1 (2016), 57–95 | DOI | MR | Zbl

[8] Taylor, A., Van Scoy, B., and Lessard, L., “Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees”, Proc. of the 35th Internat. Conf. on Machine Learning (Stockholm, Sweden, Jul 2018), 4897–4906

[9] Rubbens, A., Bousselmi, N., Colla, S., and Hendrickx, J. M., “Interpolation Constraints for Computing Worst-Case Bounds in Performance Estimation Problems”, Proc. of the 62nd IEEE Conf. on Decision and Control (CDC, Marina Bay Sands, Singapore, Dec 2023), 3015–3022

[10] Taylor, A. B., Hendrickx, J. M., and Glineur, F., “Smooth Strongly Convex Interpolation and Exact Worst-Case Performance of First-Order Methods”, Math. Program., 161:1–2 (2017), 307–345 | DOI | MR | Zbl

[11] Kim, D. and Fessler, J. A., “Optimized First-Order Methods for Smooth Convex Minimization”, Math. Program., 159:1–2 (2016), 81–107 | DOI | MR | Zbl

[12] Zamani, M., Abbaszadehpeivasti, H., and de Klerk, E., “Convergence Rate Analysis of the Gradient Descent-Ascent Method for Convex-Concave Saddle-Point Problems”, Optim. Methods Softw., 39:5 (2024), 967–989 | DOI | MR | Zbl

[13] Dragomir, R. A., Taylor, A. B., d'Aspremont, A., and Bolte, J., “Optimal Complexity and Certification of Bregman First-Order Methods”, Math. Program., 194:1–2 (2022), 41–83 | DOI | MR | Zbl

[14] Rockafellar, R. T., “Characterization of the Subdifferentials of Convex Functions”, Pacific J. Math., 17:3 (1966), 497–510 | DOI | MR | Zbl

[15] Artstein-Avidan, S., Sadovsky, S., and Wyczesany, K., “A Rockafellar-Type Theorem for Non-Traditional Costs”, Adv. Math., 395 (2022), 108157, 22 pp. | DOI | MR | Zbl

[16] Bousselmi, N., Hendrickx, J. M., and Glineur, F., “Interpolation Conditions for Linear Operators and Applications to Performance Estimation Problems”, SIAM J. Optim., 34:3 (2024), 3033–3063 | DOI | MR | Zbl

[17] Rubbens, A. and Hendrickx, J. M., , 2024, 42 pp. arXiv:2405.08405 [math.OC]

[18] Zhang, Y. and Xiao, L., “Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization”, J. Mach. Learn. Res., 18:1 (2017), 2939–2980 | MR

[19] Du, S. S., Chen, J., Li, L., Xiao, L., and Zhou, D., “Stochastic Variance Reduction Methods for Policy Evaluation”, Proc. of the 34th Internat. Conf. on Machine Learning (ICML, Sydney, NSW, Australia, Aug 2017), 1049–1058

[20] Salim, A., Condat, L., Kovalev, D., and Richtárik, P., “An Optimal Algorithm for Strongly Convex Minimization under Affine Constraints”, Proc. of the 25th Internat. Conf. on Artificial Intelligence and Statistics (AISTATS, Valencia, Spain, Mar 2022), 4482–4498

[21] Kovalev, D., Gasnikov, A., and Richtárik, P., “Accelerated Primal-Dual Gradient Method for Smooth and Convex-Concave Saddle-Point Problems with Bilinear Coupling”, Proc. of the 36th Internat. Conf. on Neural Information Processing Systems (NIPS, New Orleans, La., USA, 2022), Art. 1579, 13 pp.

[22] Goujaud, B., Dieuleveut, A., and Taylor, A., “On Fundamental Proof Structures in First-Order Optimization”, Proc. of the 62nd IEEE Conf. on Decision and Control (CDC, Marina Bay Sands, Singapore, Dec 2023), 3023–3030 | MR