1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 514, № 2, 2023

Доклады Российской академии наук. Математика, информатика, процессы управления, 2023, T. 514, № 2, стр. 158-168

МИНИМАКСНАЯ ОПТИМИЗАЦИЯ НА МЕДЛЕННО МЕНЯЮЩИХСЯ ГРАФАХ

Н. Ч. Нгуен 1, *, А. Рогозин 1, **, Д. Метелев 1, ***, А. Гасников 1, 2, 3, 4, ****

1 Московский физико-технический институт (государственный университет)
Долгопрудный, Россия

2 Институт проблем передачи информации имени А.А. Харкевича Российской академии наук
Москва, Россия

3 Кавказский математический центр Адыгейского государственного университета
Майкоп, Республика Адыгея, Россия

4 Институт системного программирования им. В.П. Иванникова Российской академии наук (ИСП РАН)
Москва, Россия

* E-mail: ngnhtrg@phystech.edu
** E-mail: aleksandr.rogozin@phystech.edu
*** E-mail: metelev.ds@phystech.edu
**** E-mail: gasnikov@yandex.ru

Поступила в редакцию 03.09.2023
После доработки 08.09.2023
Принята к публикации 15.10.2023

Аннотация

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

Ключевые слова: седловая задача, децентрализованная оптимизация, меняющийся граф, экстраградиентный метод

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

  1. Bazerque J.A., Giannakis G.B. Distributed spectrum sensing for cognitive radio networks by exploiting sparsity. IEEE Transactions on Signal Processing. 2009. V. 58. № 3. P. 1847–1862.

  2. Beznosikov A., Rogozin A., Kovalev D., Gasnikov A. Near-optimal decentralized algorithms for saddle point problems over time-varying networks. In International Conference on Optimization and Applications, pages 246–257. Springer, 2021.

  3. Beznosikov A., Samokhin V., Gasnikov A. Distributed saddle-point problems: Lower bounds, near-optimal and robust algorithms. arXiv preprint arXiv:2010.13112, 2020.

  4. Beznosikov A., Samokhin V., Gasnikov A. Distributed saddle-point problems: Lower bounds, optimal algorithms and federated gans. arXiv preprint arXiv:2010.13112, 2021.

  5. Forero P.A., Cano A., Giannakis G.B. Consensus-based distributed support vector machines. Journal of Machine Learning Research. 2010. V. 11. № 5.

  6. Gan L., Topcu U., Low S.H. Optimal decentralized protocol for electric vehicle charging. IEEE Transactions on Power Systems. 2012. V. 28. № 2. P. 940–951.

  7. Kovalev D., Beznosikov A., Sadiev A., Persiianov M., Richt’arik P., Gasnikov A. Optimal algorithms for decentralized stochastic variational inequalities. Advances in Neural Information Processing Systems. 2022. V. 35. P. 31073–31088.

  8. Kovalev D., Gasanov E., Gasnikov A., Richtarik P. Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. Advances in Neural Information Processing Systems. 2021. V. 34.

  9. Kovalev D., Salim A., Richt’arik P. Optimal and practical algorithms for smooth and strongly convex decentralized optimization. Advances in Neural Information Processing Systems. 2020. V. 33.

  10. Kovalev D., Shulgin E., Richt’arik P., Rogozin A., Gasnikov A. Adom: Accelerated decentralized optimization method for time-varying networks. arXiv preprint arXiv:2102.09234, 2021.

  11. Metelev D., Beznosikov A., Rogozin A., Gasnikov A., Proskurnikov A. Decentralized optimization over slowly time-varying graphs: Algorithms and lower bounds. arXiv preprint arXiv:2307.12562, 2023.

  12. Metelev D., Rogozin A., Kovalev D., Gasnikov A. Is consensus acceleration possible in decentralized optimization over slowly time-varying networks? In International Conference on Machine Learning. PMLR, 2023. P. 24532–24554.

  13. Nedic A. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine. 2020. V. 37. № 3. P. 92–101.

  14. Nedi’c A., Olshevsky A., Uribe C.A. Fast convergence rates for distributed non-bayesian learning. IEEE Transactions on Automatic Control. 2017. V. 62. № 11. P. 5538–5553.

  15. Nedic A., Ozdaglar A. Cooperative distributed multi-agent optimization. Convex optimization in signal processing and communications. 2010. V. 340.

  16. Rabbat M., Nowak R. Distributed optimization in sensor networks. In Proceedings of the 3rd international symposium on Information processing in sensor networks. 2004. P. 20–27.

  17. Ram S.S., Veeravalli V.V., Nedic A. Distributed non-autonomous power control through distributed convex optimization. In IEEE INFOCOM 2009, IEEE, 2009. P. 3001–3005.

  18. Ren W., Beard R.W. Distributed consensus in multi-vehicle cooperative control, V. 27. Springer, 2008.

  19. Scaman K., Bach F., Bubeck S., Lee Y.T., Massouli’e L. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, JMLR. org, 2017. P. 3027–3036.

  20. Zhang J., Hong M., Zhang S. On lower iteration complexity bounds for the saddle point problems. arXiv preprint arXiv:1912.07481, 2019.

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

Инструменты

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

Доклады Российской академии наук. Математика, информатика, процессы управления

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