EFFICIENCY BOUNDS FOR ALGORITHMS WITH BREGMAN DIVERGENCE
Abstract
In this paper, variants of extrapolation from the past algorithm and operator extrapolation algorithm with Bregman divergence for solving variational inequalities with monotone and Lipschitz-continuous operators, which act in a finite-dimensional real linear space, are investigated. Main results: efficiency bounds for the gap function.
References
Semenov V. V. Variational inequalities: theory and algorithms. Kyiv: "Kyiv University", 2021. 167 p.
Nemirovski A. Prox-method with rate of convergence O(1/T) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. on Optim. 2004. Vol. 15. P. 229–251.
Beck A. First-Order Methods in Optimization. Philadelphia: Society for Industrial and Applied Mathematics, 2017. 479 p.
Vishnoi N. K. Algorithms for Convex Optimization. Cambridge: Cambridge University Press, 2021. 340 p.
Juditsky A., Nemirovski A., Tauvel C. Solving variational inequalities with Stochastic Mirror-Prox algorithm. Stochastic Systems. 2011. Vol. 1. No. 1. P. 17–58.
Allen-Zhu Z., Orecchia L. Linear coupling: An ultimate unification of gradient and mirror descent. arXiv preprint arXiv:1407.1537. 2014.
Semenov V. V. A variant of mirror descent method for solving variational inequalities. In: Polyakova, L. N. (ed.) Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of V. F. Demyanov). IEEE, 2017. P. 281–284.
Semenov V. V. A Version of the Mirror descent Method to Solve Variational Inequalities. Cybernetics and Systems Analysis. 2017. Vol. 53. P. 234–243.
Nomirovskii D. A., Rublyov V. V., Semenov V. V. Convergence of Two-Stage Method with Bregman Divergence for Solving Variational Inequalities. Cybernetics and Systems Analysis. 2019. Vol. 55. P. 359–368.
Chabak L., Semenov V., Vedel Y. A New Non-Euclidean Proximal Method for Equilibrium Problems. In: Chertov O., Mylovanov T., Kondratenko Y., Kacprzyk J., Kreinovich V., Stefanuk V. (eds) Recent Developments in Data Science and Intelligent Analysis of Information. ICDSIAI 2018. Advances in Intelligent Systems and Computing, vol. 836. Springer, Cham, 2019. P. 50–58.
Semenov V., Kharkov O. Operator extrapolation method for variational irregularities in Banach spaces. Physico-mathematical modeling and information technology. 2023. No. 37. pp. 118–122.
Cohen M. B., Sidford A., Tian K. Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. arXiv preprint arXiv: 2011.06572. 2021.
Semenov V. V., Denisov S. V., Siryk D. S., Kharkov O. S. Convergence of the extrapolation method from the past and the operator extrapolation method. International Scientific Technical Journal "Problems of control and informatics". 2021. Volume 66. No. 3. pp. 58–72.
