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

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

ОПТИМАЛЬНОЕ РАЗДЕЛЕНИЕ ДАННЫХ В РАСПРЕДЕЛЕННОЙ ОПТИМИЗАЦИИ ДЛЯ МАШИННОГО ОБУЧЕНИЯ

Д. Медяков 1, *, Г. Молодцов 1, А. Безносиков 1, А. Гасников 1

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

* E-mail: mediakov.do@phystech.edu

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

Аннотация

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

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

  1. Verbraeken J., Wolting M., Katzy J., Kloppenburg J., Verbelen T., Rellermeyer J.S. “A survey on distributed machine learning,” Acm computing surveys (csur). 2020. T. 53. № 2. C. 1–33.

  2. Konečny J., McMahan H.B., Yu F.X., Richt’arik P., Suresh A.T., Bacon D. “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, 2016.

  3. Li T., Sahu A.K., Talwalkar A., Smith V. “Federated learning: Challenges, methods, and future directions,” IEEE signal processing magazine. 2020. T. 37. № 3. C. 50–60.

  4. Kairouz P., McMahan H.B., Avent B. et al., “Advances and open problems in federated learning,” Foundations and Trends® in Machine Learning. 2021. T. 14. № 1–2. C. 1–210.

  5. Ghosh A., Maity R.K., Mazumdar A., Ramchandran K. “Communication efficient distributed approximate Newton method,” в 2020 IEEE International Symposium on Information Theory (ISIT), IEEE, 2020. C. 2539–2544.

  6. Smith V., Forte S., Chenxin M., Tak’ač M., Jordan M.I., Jaggi M. “CoCoA: A general framework for communication-efficient distributed optimization,” Journal of Machine Learning Research. 2018. T. 18. C. 230.

  7. Gorbunov E., Burlachenko K.P., Li Z., Richt’arik P. “MARINA: Faster non-convex distributed learning with compression,” в International Conference on Machine Learning, PMLR, 2021. C. 3788–3798.

  8. Nesterov Y. et al. Lectures on convex optimization. Springer, 2018. T. 137.

  9. Arjevani Y., Shamir O. “Communication complexity of distributed convex learning and optimization,” Advances in neural information processing systems. 2015. T. 28.

  10. Shamir O., Srebro N., Zhang T. “Communication-efficient distributed optimization using an approximate newton-type method,” в International conference on machine learning, PMLR, 2014. C. 1000–1008.

  11. Matsushima S., Yun H., Zhang X., Vishwanathan S. “Distributed stochastic optimization of the regularized risk,” arXiv preprint arXiv:1406.4363, 2014.

  12. Tian Y., Scutari G., Cao T., Gasnikov A. “Acceleration in distributed optimization under similarity,” в International Conference on Artificial Intelligence and Statistics, PMLR, 2022. C. 5721–5756.

  13. Sun Y., Scutari G., Daneshmand A. “Distributed optimization based on gradient tracking revisited: Enhancing convergence rate via surrogation,” SIAM Journal on Optimization. 2022. T. 32. № 2. C. 354–385.

  14. Reddi S.J., Konečny J., Richt’arik P., P’ocz’os B., Smola A. “Aide: Fast and communication efficient distributed optimization,” arXiv preprint arXiv:1608.06879, 2016.

  15. Hendrikx H., Xiao L., Bubeck S., Bach F., Massoulie L. “Statistically preconditioned accelerated gradient method for distributed optimization,” в International conference on machine learning, PMLR, 2020. C. 4203–4227.

  16. Beznosikov A., Scutari G., Rogozin A., Gasnikov A. “Distributed saddle-point problems under data similarity,” Advances in Neural Information Processing Systems. 2021. T. 34. C. 8172–8184.

  17. Kovalev D., Beznosikov A., Borodich E., Gasnikov A., Scutari G. “Optimal gradient sliding and its application to optimal distributed optimization under similarity,” Advances in Neural Information Processing Systems. 2022. T. 35. C. 33 494–33 507.

  18. Polyak B.T. “Newton’s method and its use in optimization,” European Journal of Operational Research. 2007. T. 181. № 3. C. 1086–1096.

  19. Chang C.-C., Lin C.-J. “LIBSVM: a library for support vector machines,” ACM transactions on intelligent systems and technology (TIST). 2011. T. 2. № 3. C. 1–27.

  20. Kim D., Fessler J.A. “Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions,” Journal of optimization theory and applications. 2021. T. 188. № 1. C. 192–219.

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

Инструменты

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

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

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