1. На главную
  2. Электронные версии
  3. Программирование
  4. № 6, 2023

Программирование, 2023, № 6, стр. 5-13

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

С. С. Аблаев a, b, *, Ф. С. Стонякин a, b, **, М. С. Алкуса a, c, ***, Д. А. Пасечнюк a, d, ****

a Московский физико-технический институт
141701 г. Долгопрудный, Институтский пер., 9, Россия

b Крымский федеральный университет им. В.И. Вернадского
295007 г. Симферополь, проспект академика Вернадского, 4, Россия

c Национальный исследовательский университет “Высшая школа экономики”
101000 г. Москва, ул. Мясницкая, д. 20, Россия

d Исследовательский центр доверенного искусственного интеллекта ИСП РАН
109004 г. Москва, ул. Александра Солженицына, 25, Россия

* E-mail: seydamet.ablaev@yandex.ru
** E-mail: fedyor@mail.ru
*** E-mail: mohammad.alkousa@phystech.edu
**** E-mail: dmivilensky1@gmail.com

Поступила в редакцию 13.06.2023
После доработки 15.07.2023
Принята к публикации 20.07.2023

Аннотация

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

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

  1. 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.

  2. 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).

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Программирование

Архивы выпусков Информация о журнале Отправить рукопись в журнал