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

АДАПТИВНЫЕ МЕТОДЫ ДЛЯ ВАРИАЦИОННЫХ НЕРАВЕНСТВ С ОТНОСИТЕЛЬНО ГЛАДКИМИ И ОТНОСИТЕЛЬНО СИЛЬНО МОНОТОННЫМИ ОПЕРАТОРАМИ

Авторы: Аблаев С.С.¹^,2, Стонякин Ф.С.¹^,2, Алкуса М.С.¹^,3, Пасечнюк Д.А.¹^,4
Учреждения:
1. Московский физико-технический институт
2. Крымский федеральный университет им. В.И. Вернадского
3. Национальный исследовательский университет “Высшая школа экономики”
4. Исследовательский центр доверенного искусственного интеллекта ИСП РАН
Выпуск: № 6 (2023)
Страницы: 5-13
Раздел: АНАЛИЗ ДАННЫХ
URL: https://bakhtiniada.ru/0132-3474/article/view/148115
DOI: https://doi.org/10.31857/S013234742306002X
EDN: https://elibrary.ru/EIFITN
ID: 148115

Цитировать

Полный текст

Аннотация
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

Статья посвящена некоторым адаптивным методам для вариационных неравенств с относительно гладкими и относительно сильно монотонными операторами. Отталкиваясь от недавно предложенного проксимального варианта экстраградиентного метода для такого класса задач, мы детально исследуем метод с адаптивно подбираемыми значениями параметров. Доказана оценка скорости сходимости этого метода. Результат обобщен на класс вариационных неравенств с относительно сильно монотонными \(\delta \)-обобщенно гладкими операторами вариационного неравенства. Для задачи гребневой регрессии и вариационного неравенства, связанного с параллелепипедно-симплексными играми, выполнены численные эксперименты, демонстрирующие эффективность предложенной методики адаптивного подбора параметров в ходе реализации алгоритма.

Список литературы

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.