Solving strongly convex-concave composite saddle point problems with a small dimension of one of the variables

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

Algorithmic methods are developed that guarantee efficient complexity estimates for strongly convex-concave saddle-point problems in the case when one group of variables has a high dimension, while another has a rather low dimension (up to 100). These methods are based on reducing problems of this type to the minimization (maximization) problem for a convex (concave) functional with respect to one of the variables such that an approximate value of the gradient at an arbitrary point can be obtained with the required accuracy using an auxiliary optimization subproblem with respect to the other variable. It is proposed to use the ellipsoid method and Vaidya's method for low-dimensional problems and accelerated gradient methods with inexact information about the gradient or subgradient for high-dimensional problems. In the case when one group of variables, ranging over a hypercube, has a very low dimension (up to five), another proposed approach to strongly convex-concave saddle-point problems is rather efficient. This approach is based on a new version of a multidimensional analogue of Nesterov's method on a square (the multidimensional dichotomy method) with the possibility to use inexact values of the gradient of the objective functional.

作者简介

Mohammad Alkousa

Moscow Institute of Physics and Technology (National Research University)

Email: mohammad.alkousa@phystech.edu

Alexander Gasnikov

Moscow Institute of Physics and Technology (National Research University); Ivannikov Institute for System Programming of the RAS; Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute); Caucasus Mathematical Center, Adyghe State University

Email: gasnikov@yandex.ru
Doctor of physico-mathematical sciences, Associate professor

Egor Gladin

Humboldt University

Email: mohammad.alkousa@phystech.edu

Ilya Kuruzov

Moscow Institute of Physics and Technology (National Research University)

Email: mohammad.alkousa@phystech.edu

Dmitry Pasechnyuk

Moscow Institute of Physics and Technology (National Research University)

Email: pasechniuk.da@phystech.edu
without scientific degree, no status

Fedor Stonyakin

Moscow Institute of Physics and Technology (National Research University); V. I. Vernadsky Crimean Federal University

编辑信件的主要联系方式.
Email: fedyor@mail.ru

Candidate of physico-mathematical sciences, Associate professor

参考

  1. М. С. Алкуса, А. В. Гасников, Д. М. Двинских, Д. А. Ковалев, Ф. С. Стонякин, “Ускоренные методы для седловых задач”, Ж. вычисл. матем. и матем. физ., 60:11 (2020), 1843–1866
  2. W. Azizian, I. Mitliagkas, S. Lacoste-Julien, G. Gidel, “A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games”, Proceedings of the twenty third international conference on artificial intelligence and statistics, Proceedings of Machine Learning Research (PMLR), 108, 2020, 2863–2873
  3. А. В. Гасников, П. Е. Двуреченский, Ю. Е. Нестеров, “Стохастические градиентные методы с неточным оракулом”, Труды МФТИ, 8:1 (2016), 41–91
  4. А. В. Гасников, Д. М. Двинских, П. Е. Двуреченский, Д. И. Камзолов, В. В. Матюхин, Д. А. Пасечнюк, Н. К. Тупица, А. В. Чернов, “Ускоренный метаалгоритм для задач выпуклой оптимизации”, Ж. вычисл. матем. и матем. физ., 61:1 (2021), 20–31
  5. Le Thi Khanh Hien, Renbo Zhao, W. B. Haskell, An inexact primal-dual framework for large-scale non-bilinear saddle point problem
  6. Guanghui Lan, First-order and stochastic optimization methods for machine learning, Springer Ser. Data Sci., Springer, Cham, 2020, xiii+582 pp.
  7. Tianyi Lin, Chi Jin, M. I. Jordan, “Near-optimal algorithms for minimax optimization”, Proceedings of thirty third conference on learning theory, Proceedings of Machine Learning Research (PMLR), 125, 2020, 2738–2779
  8. I. Usmanova, M. Kamgarpour, A. Krause, K. Levy, “Fast projection onto convex smooth constraints”, Proceedings of the 38th international conference on machine learning, Proceedings of Machine Learning Research (PMLR), 139, 2021, 10476–10486
  9. А. В. Гасников, Современные численные методы оптимизации. Метод универсального градиентного спуска, 2-е испр. изд., МЦНМО, М., 2021, 272 с.
  10. B. Cox, A. Juditsky, A. Nemirovski, “Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators”, J. Optim. Theory Appl., 172:2 (2017), 402–435
  11. Yu. Nesterov, “Excessive gap technique in nonsmooth convex minimization”, SIAM J. Optim., 16:1 (2005), 235–249
  12. Junyu Zhang, Mingyi Hong, Shuzhong Zhang, “On lower iteration complexity bounds for the convex concave saddle point problems”, Math. Program., 194:1-2, Ser. A (2022), 901–935
  13. Yuanhao Wang, Jian Li, “Improved algorithms for convex-concave minimax optimization”, NIPS 2020, Adv. Neural Inf. Process. Syst., 33, MIT Press, Cambridge, MA, 2020, 11 pp.
  14. A. Nemirovski, S. Onn, U. G. Rothblum, “Accuracy certificates for computational problems with convex structure”, Math. Oper. Res., 35:1 (2010), 52–78
  15. A. Nemirovski, Information-based complexity of convex programming, Lecture notes, 1995, 268 pp.
  16. Д. А. Пасечнюк, Ф. С. Стонякин, “Об одном методе минимизации выпуклой липшицевой функции двух переменных на квадрате”, Компьютерные исследования и моделирование, 11:3 (2019), 379–395
  17. Б. Т. Поляк, Введение в оптимизацию, Наука, М., 1983, 384 с.
  18. O. Devolder, F. Glineur, Yu. Nesterov, “First-order methods of smooth convex optimization with inexact oracle”, Math. Program., 146:1-2, Ser. A (2014), 37–75
  19. P. M. Vaidya, “A new algorithm for minimizing convex functions over convex sets”, Math. Program., 73:3, Ser. A (1996), 291–341
  20. S. Bubeck, “Convex optimization: algorithms and complexity”, Found. Trends Mach. Learn., 8:3-4 (2015), 231–357
  21. E. Gladin, A. Sadiev, A. Gasnikov, P. Dvurechensky, A. Beznosikov, M. Alkousa, “Solving smooth min-min and min-max problems by mixed oracle algorithms”, MOTOR 2021: Mathematical optimization theory and operations research–recent trends, Commun. Comput. Inf. Sci., 1476, Springer, Cham, 2021, 19–40
  22. А. В. Гасников, Ю. Е. Нестеров, “Универсальный метод для задач стохастической композитной оптимизации”, Ж. вычисл. матем. и матем. физ., 58:1 (2018), 52–69
  23. J. M. Danskin, “The theory of Max-Min, with applications”, SIAM J. Appl. Math., 14:4 (1966), 641–664
  24. O. Devolder, Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization, PhD thesis, UCL, CORE, Louvain-la-Neuve, 2013, vii+309 pp.
  25. O. Devolder, F. Glineur, Yu. Nesterov, First-order methods with inexact oracle: the strongly convex case, CORE Discussion Papers, no. 2013/16, 2013, 35 pp.
  26. Н. З. Шор, Методы минимизации недифференцируемых функций и их приложения, Наукова думка, Киев, 1979, 199 с.
  27. Исходный код экспериментов на GitHub
  28. P. Bernhard, A. Rapaport, “On a theorem of Danskin with an application to a theorem of von Neumann–Sion”, Nonlinear Anal., 24:8 (1995), 1163–1181

补充文件

附件文件
动作
1. JATS XML
下载

版权所有 © Alkousa M.S., Gasnikov A.V., Gladin E.L., Kuruzov I.A., Pasechnyuk D.A., Stonyakin F.S., 2023

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».