Gradient-free Federated Learning Methods with l1 and l2-randomization for Non-smooth Convex Stochastic Optimization Problems

B. A. Alashqar; Альашкар Б. А.; A. V. Gasnikov; Гасников А. В.; D. M. Dvinskikh; Двинских Д. М.; A. V. Lobanov; Лобанов А. В.

doi:10.31857/S0044466923090028

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

Авторы: Альашкар Б.А.¹, Гасников А.В.²^,3^,4, Двинских Д.М.⁵, Лобанов А.В.¹^,6^,7
Учреждения:
1. НИУ МФТИ
2. Московский физико-технический институт
3. Институт проблем передачи информации РАН
4. Кавказский математический центр Адыгейского гос. университета
5. НИУ ВШЭ
6. ИСП РАН
7. МАИ (НИУ)
Выпуск: Том 63, № 9 (2023)
Страницы: 1458-1512
Раздел: ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
URL: https://ogarev-online.ru/0044-4669/article/view/136192
DOI: https://doi.org/10.31857/S0044466923090028
EDN: https://elibrary.ru/MLJEUH
ID: 136192

Цитировать

Полный текст

Открытый доступ
Доступ закрыт

Доступ предоставлен
Доступ закрыт

Только для подписчиков

Аннотация
Об авторах
Список литературы
Дополнительные файлы
Статистика

Аннотация

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

Ключевые слова

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

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

The power of first-order smooth optimization for black-box non-smooth problems / A. Gasnikov et al. // arXiv preprint arXiv:2201.12289. 2022.
Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оптимизации. 1979.
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.
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.
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.
Advances and open problems in federated learning / P. Kairouz [и дp.] // Foundations and Trends® in Machine Learning. 2021. T. 14, № 1/2. C. 1–210.
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.
Scheinberg K. Finite Difference Gradient Approximation: To Randomize or Not? // INFORMS Journal on Computing. 2022. T. 34. № 5. C. 2384–2388.
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.
Ledoux M. The concentration of measure phenomenon// American Mathematical Soc., 2001.
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.
Is local SGD better than minibatch SGD? / B. Woodworth et al. // Internat. Conference on Machine Learning. PMLR. 2020. C. 10334–10343.
Yuan H., Ma T. Federated accelerated stochastic gradient descent // Advances in Neural Information Processing Systems. 2020. T. 33. C. 5332–5344.
Gorbunov E., Dvinskikh D., Gasnikov A. Optimal decentralized distributed algorithms for stochastic convex optimization // arXiv preprint arXiv:1911.07363. 2019.
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.
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.
Стохастическая онлайн оптимизация. Одноточечные и двухточечные нелинейные многорукие бандиты. Выпуклый и сильно выпуклый случаи / А.В. Гасников [и др.] // Автоматика и телемеханика. 2017. № 2. С. 36–49.
Gradient-Free Optimization for Non-Smooth Minimax Problems with Maximum Value of Adversarial Noise / D. Dvinskikh et al. // arXiv preprint arXiv:2202.06114. 2022.
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.
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.
Juditsky A., Nemirovski A., Tauvel C. Solving variational inequalities with stochastic mirrorprox algorithm // Stochastic Systems. 2011. T. 1. № 1. C. 17–58.
Lan G. An optimal method for stochastic composite optimization // Math. Programming. 2012. T. 133. № 1. C. 365–397.