1. На главную
  2. Электронные версии
  3. Журнал вычислительной математики и математической физики
  4. T. 63, № 9, 2023

Журнал вычислительной математики и математической физики, 2023, T. 63, № 9, стр. 1458-1512

Безградиентные методы федеративного обучения с l1 и l2-рандомизацией для задач негладкой выпуклой стохастической оптимизации

Б. А. Альашкар 1, А. В. Гасников 1, 2, 3, Д. М. Двинских 4, А. В. Лобанов 1, 5, 6, *

1 НИУ МФТИ
141700 М.о., Долгопрудный, Институтский пер., 9, Россия

2 ИППИ РАН
127051 Москва, Б. Каретный пер., 19, стр. 1, Россия

3 КМЦ АГУ
385000 Республика Адыгея, Майкоп, ул. Первомайская, 208, Россия

4 НИУ ВШЭ
109028 Москва, Покровский б-р, 11, Россия

5 ИСП РАН
109004 Москва, ул. А. Солженицына, 25, Россия

6 МАИ (НИУ)
125993 Москва, Волоколамское шоссе, 4, Россия

* E-mail: lobbsasha@mail.ru

Поступила в редакцию 18.11.2022
После доработки 20.05.2023
Принята к публикации 29.05.2023

Аннотация

В статье исследуются негладкие задачи выпуклой стохастической оптимизации. С помощью техники сглаживания, базирующейся на замене значения функции в рассматриваемой точке усредненным значением функции по шару (в ${{l}_{1}}$-норме или ${{l}_{2}}$-норме) малого радиуса с центром в этой точке, исходная задача сводится к гладкой задаче (константа Липшица градиента которой обратно пропорционально радиусу шара). Важным свойством используемого сглаживания является возможность вычислять несмещенную оценку градиента сглаженной функции на основе только реализаций исходной функции. Полученную гладкую задачу стохастической оптимизации предлагается далее решать в распределенной архитектуре федеративного обучения (задача решается параллельно: узлы делают локальные шаги, например, стохастического градиентного спуска, потом коммуницируют – все со всеми, затем все это повторяется). Цель статьи – построить на базе современных достижений в области безградиентной негладкой оптимизации и в области федеративного обучения безградиентные методы решения задач негладкой стохастической оптимизации в архитектуре федеративного обучения. Библ. 22. Фиг. 3. Табл. 1.

Ключевые слова: безградиентные методы, методы с неточным оракулом, федеративное об-учение.

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

  1. The power of first-order smooth optimization for black-box non-smooth problems / A. Gasnikov et al. // arXiv preprint arXiv:2201.12289. 2022.

  2. Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. 1979.

  3. Shamir O. An optimal algorithm for bandit and zero-order convex optimization with twopoint feedback // The Journal of Machine Learning Research. 2017. T. 18. № 1. C. 1703–1713.

  4. A gradient estimator via L1-randomization for online zero-order optimization with two point feedback / A. Akhavan et al. // arXiv preprint arXiv:2205.13910. 2022.

  5. Gradient-free proximal methods with inexact oracle for convex stochastic nonsmooth optimization problems on the simplex / A.V. Gasnikov et al. // Automation and Remote Control. 2016. T. 77. № 11. C. 2018–2034.

  6. Advances and open problems in federated learning / P. Kairouz [и дp.] // Foundations and Trends® in Machine Learning. 2021. T. 14, № 1/2. C. 1–210.

  7. Optimal rates for zero-order convex optimization: The power of two function evaluations / J.C. Duchi et al. // IEEE 5. C. 2788–2806. Transactions on Information Theory. 2015. T. 61.

  8. Scheinberg K. Finite Difference Gradient Approximation: To Randomize or Not? // INFORMS Journal on Computing. 2022. T. 34. № 5. C. 2384–2388.

  9. Beznosikov A., Gorbunov E., Gasnikov A. Derivative-free method for composite optimization with applications to decentralized distributed optimization // IFAC-PapersOnLine. 2020. T. 53. № 2. C. 4038–4043.

  10. Ledoux M. The concentration of measure phenomenon// American Mathematical Soc., 2001.

  11. The min-max complexity of distributed stochastic convex optimization with intermittent communication / B.E. Woodworth et al. // Conference on Learning Theory. PMLR. 2021. C. 4386–4437.

  12. Is local SGD better than minibatch SGD? / B. Woodworth et al. // Internat. Conference on Machine Learning. PMLR. 2020. C. 10334–10343.

  13. Yuan H., Ma T. Federated accelerated stochastic gradient descent // Advances in Neural Information Processing Systems. 2020. T. 33. C. 5332–5344.

  14. Gorbunov E., Dvinskikh D., Gasnikov A. Optimal decentralized distributed algorithms for stochastic convex optimization // arXiv preprint arXiv:1911.07363. 2019.

  15. Duchi J.C., Bartlett P.L., Wainwright M.J. Randomized smoothing for stochastic optimization // SIAM Journal on Optimization. 2012. T. 22. № 2. C. 674–701.

  16. Yousefian F., Nedic’ A., Shanbhag U.V. On stochastic gradient and subgradient methods with adaptive steplength sequences // Automatica. 2012. T. 48. № 1. C. 56–67.

  17. Стохастическая онлайн оптимизация. Одноточечные и двухточечные нелинейные многорукие бандиты. Выпуклый и сильно выпуклый случаи / А.В. Гасников [и др.] // Автоматика и телемеханика. 2017. № 2. С. 36–49.

  18. Gradient-Free Optimization for Non-Smooth Minimax Problems with Maximum Value of Adversarial Noise / D. Dvinskikh et al. // arXiv preprint arXiv:2202.06114. 2022.

  19. Flaxman A.D., Kalai A.T., McMahan H.B. Online convex optimization in the bandit setting: gradient descent without a gradient // Proc. of the sixteenth annual ACMSIAM symposium on Discrete algorithms. 2005. C. 385–394.

  20. Dvurechensky P., Gorbunov E., Gasnikov A. An accelerated directional derivative method for smooth stochastic convex optimization // European Journal of Operational Research. 2021. T. 290. № 2. C. 601–621.

  21. Juditsky A., Nemirovski A., Tauvel C. Solving variational inequalities with stochastic mirrorprox algorithm // Stochastic Systems. 2011. T. 1. № 1. C. 17–58.

  22. Lan G. An optimal method for stochastic composite optimization // Math. Programming. 2012. T. 133. № 1. C. 365–397.

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

Инструменты

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

Журнал вычислительной математики и математической физики

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