Adaptive Methods or Variational Inequalities with Relatively Smooth and Reletively Strongly Monotone Operators

S. S. Ablaev; Аблаев С. С.; F. S. Stonyakin; Стонякин Ф. С.; M. S. Alkousa; Алкуса М. С.; D. A. Pasechnyk; Пасечнюк Д. А.

doi:10.31857/S013234742306002X

Adaptive Methods or Variational Inequalities with Relatively Smooth and Reletively Strongly Monotone Operators

Authors: Ablaev S.S.¹^,2, Stonyakin F.S.¹^,2, Alkousa M.S.¹^,3, Pasechnyk D.A.¹^,4
Affiliations:
1. Moscow Institute of Physics and Technology
2. Vernadsky Crimean Federal University
3. National Research University “Higher School of Economics”
4. Trusted Artificial Intelligence Research Center of ISP RAS
Issue: No 6 (2023)
Pages: 5-13
Section: DATA ANALYSIS
URL: https://rjmseer.com/0132-3474/article/view/675725
DOI: https://doi.org/10.31857/S013234742306002X
EDN: https://elibrary.ru/EIFITN
ID: 675725

Cite item

Full Text

Open Access
Restricted Access

Access granted
Restricted Access

Subscription Access

Abstract

The article is devoted to some adaptive methods for variational inequalities with relatively smooth and relatively strongly monotone operators. Based on the recently proposed proximal version of the extragradient method for this class of problems, we study in detail the method with adaptively selected parameter values. An estimate for the rate of convergence of this method is proved. The result is generalized to a class of variational inequalities with relatively strongly monotone δ-generalized smooth variational inequality operators. For the problem of ridge regression and variational inequality associated with box-simplex games, numerical experiments were performed demonstrating the effectiveness of the proposed method of adaptive selection of parameters during the running of the algorithm.

References

Stonyakin F., Tyurin A., Gasnikov A., Dvurechensky P., Agafonov A., Dvinskikh D., Alkousa M., Pasechnyuk D., Artamonov S., Piskunova V. Inexact Relative Smoothness and Strong Convexity for Optimization and Variational Inequalities by Inexact Model // Optim. Methods and Software. 2021. V. 36. № 6. P. 1155–1201.
Cohen M.B., Sidford A., Tian K. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. arXiv preprint https://arxiv.org/pdf/2011.06572.pdf (2020).
Titov A.A., Ablaev S.S., Stonyakin F.S., Alkousa M.S., Gasnikov A. Some Adaptive First-Order Methods for Variational Inequalities with Relatively Strongly Monotone Operators and Generalized Smoothness. In: Olenev N., Evtushenko Y., Jaćimović M., Khachay M., Malkova V., Pospelov I. (eds) Optimization and Applications. OPTIMA 2022. Lecture Notes in Computer Science, vol 13781. Springer, Cham, 2022.
Bauschke H.H., Bolte J., Teboulle M. A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications // Mathematics of Operations Research. 2017. V. 42 (1.2). P. 330–348.
Lu H., Freund R.M., Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications // SIAM Journal on Optimization. 2018. V. 28 (1.1). P. 333–354.
Hendrikx H., Xiao L., Bubeck S., Bach F., Massoulie L. Statistically preconditioned accelerated gradient method for distributed optimization. In International conference on machine learning, 4203–4227. PMLR, 2020.
Tian Y., Scutari G., Cao T., Gasnikov A. Acceleration in Distributed Optimization under Similarity. Proceedings of The 25th International Conference on Artificial Intelligence and Statistics // PMLR. 2022. V. 151. P. 5721–5756.
Jin Y., Sidford A., Tian K. Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods. In Conference on Learning Theory, 4362–4415. PMLR, 2022.