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

Полный текст (PDF)

Аннотация

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

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

1. ВВЕДЕНИЕ

В статье рассматриваются задачи стохастической оптимизации

(1)
$\mathop {\min }\limits_{x \in Q \subseteq {{\mathbb{R}}^{d}}} f(x): = {{\mathbb{E}}_{\xi }}\left[ {f(x,\xi )} \right]$
и их седловые обобщения. При этом считается, что функция $f(x)$ – выпуклая, негладкая и имеет ограниченную константу Липшица. Также предполагается, что для наблюдения доступна реализация функции $f(x,\xi )$, но не ее градиент (по $x$) $\nabla f(x,\xi )$. Более того, в работе также рассматривается случай, когда эта реализация доступна с небольшим шумом неслучайной природы. Данная статья основывается на работе [1], в которой предложен оптимальный алгоритм (с точностью до логарифмических по размерности пространства множителей в оценках оракульных вызовов) решения задачи (1) сразу по трем критериям: 1) число оракульных вызовов (вычислений $f(x,\xi )$), 2) число последовательных итераций метода (на одной итерации можно вызывать оракул многократно), 3) максимально допустимый уровень (потенциально враждебного) шума, при котором все еще возможно достичь желаемой точности. В основе подхода [1] лежит довольно старая идея (см., например, [2]) замены исходной негладкой функции $f(x)$ ее сглаженной версией ${{f}_{\gamma }}(x) = {{\mathbb{E}}_{{\tilde {e}}}}\left[ {f(x + \gamma \tilde {e})} \right]$, где $\tilde {e}$ – равномерно распределенный случайный вектор на $B_{2}^{d}(1)$ – единичном евклидовом шаре с центром в нуле. Для сглаженной функции конечная аппроксимация (с шагом $\gamma $) производной по случайному направлению (выбранному равновероятно на единичной евклидовой сфере) будет несмещенной (рандомизированной) оценкой градиента, обладающей при использовании симметричной разностной аппроксимации хорошей дисперсией [3] – такой же, как если бы $f(x)$ была гладкой.

В другой работе [4] показано, что если использовать сглаживание не по евклидовому шару, а по шару в ${{l}_{1}}$-норме, то в определенных ситуациях можно улучшить оценки [1] на число оракульных вызовов на логарифмический множитель (по размерности пространства). Однако при этом в [4] не обсуждался вопрос о числе последовательных итераций и использовалась другая (более узкая) концепция враждебного шума, для которой вопрос о точных нижних оценках, насколько нам известно, по-прежнему остается открытым.

В настоящей статье показано, как можно в теории улучшить результаты работы [1] за счет схемы сглаживания из [4] (см. также работу [5], в которой данная схема сглаживания также предлагалась, но анализ был проведен менее точно). Как уже отмечалось выше, улучшения носят логарифмический масштаб. Отметим при этом, что проведенные в работе численные эксперименты не смогли явно уловить эффект такого улучшения оценок.

Другим важным направлением развития работы [1] стало обобщение всех результатов этой работы (и ее модификации со сглаживанием на шаре в ${{l}_{1}}$-норме) на распределенные алгоритмы в архитектуре федеративного обучения [6]. Отметим, что в федеративном обучении рассматриваются задачи типа (1), во-первых, гладкие, во-вторых, с полноградиентным (стохастическим) оракулом. Задача (1) решается независимо в каждом узле, потом узлы коммуницируют и вычисляют среднее (по узлам), затем снова начинают независимо решать задачу, стартуя с этого среднего. Через некоторое время узлы снова коммуницируют, считают среднее и процесс повторяется… В данной работе за счет использования схемы сглаживания (с введением дополнительной рандомизации) получается свести негладкую задачу стохастической оптимизации с безградиентным оракулом, к гладкой задаче стохастической оптимизации с оракулом, выдающим стохастический градиент, в котором стохастика формируется из изначальной стохастики, присущей исходной постановке задачи, и стохастике, возникшей при сглаживании (рандомизированной). Оказалось, что в существующей сейчас литературе практически отсутствуют методы федеративного обучения для негладких задач. По-видимому, это было связано с тем, что для негладких задач в общем случае невозможно осуществлять батч-параллелизацию (параллелизацию по $\xi $). Однако для безградиентного оракула батч-параллелизация возможна за счет появления дополнительной (рандомизированной) случайности в виде случайного направления [1]! Собственно за счет этого и удается перенести результаты работы [1] на архитектуру федеративного обучения. Насколько нам известно, результатам, полученным в данном направлении, сейчас нет конкурентов, поэтому здесь не приводится литературный обзор конкурирующих работ.

2. ОСНОВНОЙ ВКЛАД И СТРУКТУРА

Основной вклад статьи состоит в следующем.

• Приводим подробное описание двух схем сглаживания (параллельно): с ${{l}_{1}}$ и ${{l}_{2}}$-рандомизациями. Находим константу Липшица градиента ${{L}_{{{{f}_{\gamma }}}}}$ для ${{l}_{1}}$-рандомизации. Для явного описания оценки второго момента в ${{l}_{2}}$-рандомизации с двухточечной обратной связью находим констан-ту c, которая в исходной статье [3], из которой эта константа была взята, так и не была посчитана. Получаем оценку дисперсии (второго момента) для одноточечного случая ${{l}_{1}}$-рандомизации. Показываем, что ${{l}_{1}}$-рандомизация с одноточечным оракулом также превосходит ${{l}_{2}}$-рандомизацию с точностью до $\ln d$, как и с двухточечным оракулом.

• Получаем оптимальные верхние оценки скорости сходимости пробатченных алгоритмов первого порядка Minibatch SMP и Single-Machine SMP для решения задач оптимизации с седловой точкой в архитектуре федеративного обучения.

• Описываем технику генерирования безградиентных алгоритмов (решения седловых задач и задач выпуклой оптимизации), оптимальных по количеству коммуникационных раундов $N$, максимальному значению допустимого шума $\Delta $ и оракульной сложности $T$. Показываем, что одноточечные и двухточечные алгоритмы в архитектуре федеративного обучения, использующие ${{l}_{1}}$-рандомизацию, работают лучше алгоритмов, использующих ${{l}_{2}}$-рандомизацию, с точностью до логарифма в ${{l}_{1}}$-норме. Сравниваем одноточечные алгоритмы с двухточеными и показываем, что для решения с $\varepsilon $ точностью (по функции) одноточечные алгоритмы требуют в $O(d{\text{/}}{{\varepsilon }^{2}})$ больше обращений к оракулу, чем двухточечные. Анализируем работу алгоритма Minibatch Accelerated SGD, используя разные схемы сглаживания, на практическом эксперименте.

Структура статьи следующая: в разд. 3 и 4 представлено краткое введение в техники сглаживания и федеративное обучение соответственно. В п. 4.2 приводится главный результат работы. В разд. 5 приведены основные идеи доказательств теорем 1, 2. Численные эксперименты представлены в разд. 6.

3. СХЕМЫ СГЛАЖИВАНИЯ

Схема сглаживания позволяет создавать безградиентные методы решения негладких задач, модифицируя одноименные алгоритмы первого порядка, предназначенные для решения гладких задач. Впервые схема сглаживания была описана в книге [2], где представлена идея решения задач методами первого порядка, используя вместо стохастического оракула первого порядка безградиентный стохастический оракул, который получен через теорему Стокса. С тех пор уже придумали различные техники сглаживания, однако основная идея восходит от [2]. В данном разделе представим параллельно две схемы сглаживания: с ${{l}_{1}}$-рандомизацией [4, 5] и с ${{l}_{2}}$-рандомизацией [1], включающую стохастическую оптимизацию и смещенную оценку безградиентного оракула. Для этого рассматривается стохастическая негладкая выпуклая задача оптимизации

(2)
$\mathop {\min }\limits_{x \in Q \subseteq {{\mathbb{R}}^{d}}} \left\{ {f(x): = {{\mathbb{E}}_{\xi }}\left[ {f(x,\xi )} \right]} \right\},$
где $Q$ – выпуклое и компактное множество и $f(x,\xi )$ – выпуклая функция на множестве ${{Q}_{\gamma }}: = Q + B_{p}^{d}(\gamma )$. Здесь предполагается, что безградиентный оракул возвращает значение функции $f(x)$, возможно, с некоторым враждебным шумом $\delta (x)$: $\;{{f}_{\delta }}(x): = f(x) + \delta (x)$.

3.1. Обозначения и предположения

Обозначим через $\langle x,y\rangle : = \sum\nolimits_{i = 1}^d \,{{x}_{i}}{{y}_{i}}$ стандартное скалярное произведение $x,y \in {{\mathbb{R}}^{d}}$. Через ${{\left\| x \right\|}_{p}}: = {{\left( {\sum\nolimits_{i = 1}^d \,{\text{|}}{{x}_{i}}{\kern 1pt} {{{\text{|}}}^{p}}} \right)}^{{1/p}}}$ обозначаем ${{l}_{p}}$-норму ($p \geqslant 1$) в ${{\mathbb{R}}^{d}}$ и $B_{p}^{d}(r): = \left\{ {x \in \mathbb{R}:{{{\left\| x \right\|}}_{p}} \leqslant r} \right\}$, и определяют ${{l}_{p}}$-шар и ${{l}_{p}}$-сферу соответственно. Объем ${{l}_{p}}$-шара определяется через

$V(B_{p}^{d}(r)): = {{c}_{d}}{{r}^{d}} = \frac{{{{{\left( {2\Gamma \left( {\frac{1}{p} + 1} \right)} \right)}}^{d}}}}{{\Gamma \left( {\frac{d}{p} + 1} \right)}}{{r}^{d}},$
где $\Gamma ( \cdot )$ обозначает гамма-функцию. Для обозначения “расстояния” между начальной точкой ${{x}^{0}}$ и решением исходной задачи ${{x}_{*}}$ вводим $R: = \tilde {O}\left( {{{{\left\| {{{x}^{0}} - {{x}_{*}}} \right\|}}_{p}}} \right)$, где $\tilde {O}( \cdot )$ является $O( \cdot )$ с точностью до логарифма $\sqrt {\ln d} $.

Предположение 1 (липшицева непрерывная функция). Функция $f(x,\xi )$ и является $M$-липшицевой непрерывной функцией в ${{l}_{p}}$-норме, т.е. для всех $x,y \in Q$ имеем

$\left| {f(y,\xi ) - f(x,\xi )} \right| \leqslant M(\xi ){{\left\| {y - x} \right\|}_{p}}.$
Более того, существует положительная константа $M$, которая определяется следующим образом: $\mathbb{E}[{{M}^{2}}(\xi )] \leqslant {{M}^{2}}$. В частности, для $p = 2$ используем обозначение ${{M}_{2}}$ для константы Липшица.

Предположение 2 (ограниченность шума). Для всех $x \in Q$ выполняется $\left| {\delta (x)} \right| \leqslant \Delta $, где $\Delta $ – уровень неточности (шума).

Предположение 3. Для всех $x \in Q$ выполняется ${{\mathbb{E}}_{\xi }}[{\kern 1pt} {\text{|}}f(x,\xi ){\kern 1pt} {{{\text{|}}}^{2}}] \leqslant {{G}^{2}}$.

3.2. Гладкая аппроксимация

Поскольку задача (2) является негладкой, то вводим следующую гладкую аппроксимацию негладкой функции

(3)
${{f}_{\gamma }}(x): = {{\mathbb{E}}_{{\tilde {e}}}}\left[ {f(x + \gamma \tilde {e})} \right],$
где $\gamma > 0$, $\tilde {e}$ – случайный вектор, равномерно распределенный на $B_{p}^{d}(1)$ (далее ограничимся рассмотрением случаев $p = 1$ и $p = 2$). Здесь $f(x): = \mathbb{E}f(x,\xi )$.

Следующая лемма представляет совокупность свойств аппроксимации функции $f$ в зависимости от распределения вектора $\tilde {e}$. Основываясь на [1, 4, 7] и дополняя найденной константой Липшица градиента ${{L}_{{{{f}_{\gamma }}}}}$ в случае $p = 1$, выпишем свойства функции ${{f}_{\gamma }}$.

Лемма 1. Для всех $x,y \in Q$ c предположением 1 справедливо

$\tilde {e} \in RB_{1}^{d}(1)$ $\tilde {e} \in RB_{2}^{d}(1)$
$f(x) \leqslant {{f}_{\gamma }}(x) \leqslant f(x) + \frac{2}{{\sqrt d }}\gamma {{M}_{2}}$ $f(x) \leqslant {{f}_{\gamma }}(x) \leqslant f(x) + \gamma {{M}_{2}}$
${{f}_{\gamma }}$ – $M$-липшицева:
$\left| {{{f}_{\gamma }}(y) - {{f}_{\gamma }}(x)} \right| \leqslant M{{\left\| {y - x} \right\|}_{p}}$ $\left| {{{f}_{\gamma }}(y) - {{f}_{\gamma }}(x)} \right| \leqslant M{{\left\| {y - x} \right\|}_{p}}$
${{f}_{\gamma }}$имеет${{L}_{{{{f}_{\gamma }}}}}$-липшицевый градиент:
${{\left\| {\nabla {{f}_{\gamma }}(y) - \nabla {{f}_{\gamma }}(x)} \right\|}_{q}} \leqslant \underbrace {\frac{{dM}}{{2\gamma }}}_{{{L}_{{{{f}_{\gamma }}}}}}{{\left\| {y - x} \right\|}_{p}}$ ${{\left\| {\nabla {{f}_{\gamma }}(y) - \nabla {{f}_{\gamma }}(x)} \right\|}_{q}} \leqslant \underbrace {\frac{{\sqrt d M}}{\gamma }}_{{{L}_{{{{f}_{\gamma }}}}}}{{\left\| {y - x} \right\|}_{p}}$

где $q$ такой, что $1{\text{/}}p + 1{\text{/}}q = 1$.

Доказательство приведено в п. 5.1.

3.3. Рандомизация с двухточечной обратной связью

Аппроксимация градиента зашумленной функции ${{f}_{\gamma }}(x,\xi )$ из (3) может быть получена через две точки, близких к $x$. Для этого определим случайный вектор $e$, равномерно распределенный на $S_{p}^{d}(1)$. Тогда градиент может быть оценен следующей аппроксимацией.

• Оценка градиента для ${{l}_{1}}$-рандомизации ($e \in RS_{1}^{d}(1)$) [5] (см. также [4]):

(4)
$\nabla {{f}_{\gamma }}(x,\xi ,e) = \frac{d}{{2\gamma }}({{f}_{\delta }}(x + \gamma e,\xi ) - {{f}_{\delta }}(x - \gamma e,\xi ))\operatorname{sign} (e).$

• Оценка градиента для ${{l}_{2}}$-рандомизации ($e \in RS_{2}^{d}(1)$) [3]:

(5)
$\nabla {{f}_{\gamma }}(x,\xi ,e) = \frac{d}{{2\gamma }}({{f}_{\delta }}(x + \gamma e,\xi ) - {{f}_{\delta }}(x - \gamma e,\xi ))e.$

Для оценки градиента в (4) и (5) выбрана центральная конечно-разностная схема рандомизации, так как в работе [8] поясняется, что в гладком случае выгоднее оценивать градиент именно центральной конечно-разностной схемой (CFD), а не прямой конечно-разностной схемой (FFD). Отметим, что при $\Delta = 0$ оценки будут несмещенными, т.е. ${{E}_{{e,\xi }}}\left[ {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right] = \nabla {{f}_{\gamma }}(x)$.

Далее приведем свойства $\nabla {{f}_{\gamma }}(x,\xi ,e)$ для двух рандомизаций, используя известные результаты из [1, 3–5, 9, 10]. Во многих работах для ${{l}_{2}}$-рандомизации оценка второго момента записывается с точностью до константы $c$, поэтому в лемме 2 приводятся оценки второго момента для ${{l}_{1}}$ и ${{l}_{2}}$‑рандомизаций с уточнением константы $c$.

Лемма 2. Для всех $x \in Q$ с предположениями 1 и 2 имеем

i) $\nabla {{f}_{\gamma }}(x,\xi ,e)$ с ${{l}_{1}}$-рандомизации (4) имеет оценку дисперсии (второй момент):

${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant \kappa (p,d)\left( {M_{2}^{2} + \frac{{{{d}^{2}}{{\Delta }^{2}}}}{{12(1 + \sqrt 2 {{)}^{2}}{{\gamma }^{2}}}}} \right),$
где $1{\text{/}}p + 1{\text{/}}q = 1$ и

$\kappa (p,d) = 48(1 + \sqrt 2 {{)}^{2}}{{d}^{{2 - \frac{2}{p}}}}.$

Если $\Delta $ достаточно мала, то

(6)
${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant 2\kappa (p,d)M_{2}^{2}.$

ii) $\nabla {{f}_{\gamma }}(x,\xi ,e)$ с ${{l}_{2}}$-рандомизации (5) имеет оценку дисперсии (второй момент):

${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant \kappa (p,d)\left( {M_{2}^{2} + \frac{{{{d}^{2}}{{\Delta }^{2}}}}{{\sqrt 2 {{\gamma }^{2}}}}} \right),$
где $1{\text{/}}p + 1{\text{/}}q = 1$ и

$\kappa (p,d) = \sqrt 2 \min \left\{ {q,\ln d} \right\}{{d}^{{2 - \frac{2}{p}}}}.$

Если $\Delta $ достаточно мала, то

(7)
${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant 2\kappa (p,d)M_{2}^{2}.$

Доказательство приведено в п. 5.2.

3.4. Рандомизация с одноточечной обратной связью

Для случая когда двухточечная обратная связь недоступна, схемы сглаживания могут использовать одноточечную обратную связь через следующую несмещенную оценку.

• Оценка градиента для ${{l}_{1}}$-рандомизации ($e \in RS_{1}^{d}(1)$):

(8)
$\nabla {{f}_{\gamma }}(x,\xi ,e) = \frac{d}{\gamma }({{f}_{\delta }}(x + \gamma e,\xi ))\operatorname{sign} (e).$

• Оценка градиента для ${{l}_{2}}$-рандомизации ($e \in RS_{2}^{d}(1)$) [1]:

(9)
$\nabla {{f}_{\gamma }}(x,\xi ,e) = \frac{d}{\gamma }({{f}_{\delta }}(x + \gamma e,\xi ))e.$

Тогда свойства $\nabla {{f}_{\gamma }}(x,\xi ,e)$ для двух рандомизаций будут иметь следующий вид.

Лемма 3. Для всех $x \in Q$ с предположениями 2 и 3 имеем

i) $\nabla {{f}_{\gamma }}(x,\xi ,e)$ с ${{l}_{1}}$-рандомизации (8) имеет оценку дисперсии (второй момент):

${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant \kappa (p,d)\left( {\frac{{{{G}^{2}}}}{{{{\gamma }^{2}}}} + \frac{{{{\Delta }^{2}}}}{{{{\gamma }^{2}}}}} \right),$
где $1{\text{/}}p + 1{\text{/}}q = 1$ и

$\kappa (p,d) = {{d}^{{4 - \frac{2}{p}}}}.$

Если $\Delta $ достаточно мала, то

(10)
${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant 2\kappa (p,d)\frac{{{{G}^{2}}}}{{{{\gamma }^{2}}}}.$

ii) $\nabla {{f}_{\gamma }}(x,\xi ,e)$ с ${{l}_{2}}$-рандомизации (9) имеет оценку дисперсии (второй момент):

${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant \kappa (p,d)\left( {\frac{{{{G}^{2}}}}{{{{\gamma }^{2}}}} + \frac{{{{\Delta }^{2}}}}{{{{\gamma }^{2}}}}} \right),$
где $1{\text{/}}p + 1{\text{/}}q = 1$ и

$\kappa (p,d) = \min \left\{ {q,\ln d} \right\}{{d}^{{3 - \frac{2}{p}}}}.$

Если $\Delta $ достаточно мала, то

(11)
${{E}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant 2\kappa (p,d)\frac{{{{G}^{2}}}}{{{{\gamma }^{2}}}}.$

Доказательство приведено в п. 5.3.

3.5. Алгоритм сглаживания

Основываясь на выше представленных элементах, опишем общий подход, именуемый как схема сглаживания. Предположим, что у нас есть некоторый ускоренный пакетный алгоритм A$(L,{{\sigma }^{2}})$ архитектуры федеративного обучения, который решает задачу (2) с предположением, что $f$ является гладкой и удовлетворяет

${{\left\| {\nabla f(y) - \nabla f(x)} \right\|}_{q}} \leqslant L{{\left\| {y - x} \right\|}_{p}}\quad \forall x,y \in {{Q}_{\gamma }}$
и с помощью стохастического оракула первого порядка, который зависит от случайной величины $\eta $ и возвращает в точке $x$ смещенный стохастический градиент ${{\nabla }_{x}}{{f}_{\gamma }}(x,\eta )$
${{\mathbb{E}}_{\eta }}\left[ {\left\| {{{\nabla }_{x}}{{f}_{\gamma }}(x,\eta ) - \nabla f(x)} \right\|_{q}^{2}} \right] \leqslant {{\sigma }^{2}}.$
Тогда общий подход схемы сглаживания состоит в применении A$(L,{{\sigma }^{2}})$ к сглаженной задаче
(12)
$\mathop {\min }\limits_{x \in Q \subseteq {{\mathbb{R}}^{d}}} {{f}_{\gamma }}(x)$
для решения с $\varepsilon {\text{/}}2$ точностью c известными параметрами $\eta = e$, ${{\nabla }_{x}}{{f}_{\gamma }}(x,\eta ) = \nabla {{f}_{\gamma }}(x,\xi ,e)$, $L = {{L}_{{{{f}_{\gamma }}}}}$ и $\gamma $, представленная в следствии 1.

Следствие 1. Согласно лемме 1, чтобы получить $\varepsilon $-точность решения задачи (2), необходимо решить задачу (12) с $\varepsilon {\text{/}}2$-точностью со следующим параметром

Схема сглаживания с ${{l}_{1}}$-рандомизацией Схема сглаживания с ${{l}_{2}}$-рандомизацией
$\gamma = \frac{{\sqrt d \varepsilon }}{{4{{M}_{2}}}}$ $\gamma = \frac{\varepsilon }{{2{{M}_{2}}}}$

где $\varepsilon > 0$ является желаемой точностью решения задачи (2) с точки зрения субоптимальности: $\mathbb{E}[f({{x}^{N}}) - f({{x}_{*}})] \leqslant \varepsilon $.

Следствие 2. Согласно лемме 1, подставляя параметр $\gamma $ из следствия 1, имеем

Схема сглаживания с ${{l}_{1}}$-рандомизацией Схема сглаживания с ${{l}_{2}}$-рандомизацией
${{L}_{{{{f}_{\gamma }}}}} = \frac{{2\sqrt d M{{M}_{2}}}}{\varepsilon }$ ${{L}_{{{{f}_{\gamma }}}}} = \frac{{2\sqrt d M{{M}_{2}}}}{\varepsilon }$

Следствие 3. Согласно лемме 2 уравнения (6) и (7) для двухточечного оракула примут вид

Схема сглаживания с ${{l}_{1}}$-рандомизацией Схема сглаживания с ${{l}_{2}}$-рандомизацией
${{\sigma }^{2}} \leqslant 48(1 + \sqrt 2 {{)}^{2}}{{d}^{{2 - \frac{2}{p}}}}M_{2}^{2}$ ${{\sigma }^{2}} \leqslant 2\sqrt 2 \min \left\{ {q,\ln d} \right\}{{d}^{{2 - \frac{2}{p}}}}M_{2}^{2}$

если $\Delta $ достаточно мала.

Следствие 4. Согласно лемме 3 уравнения (10) и (11) для одноточечного оракула примут вид

Схема сглаживания с ${{l}_{1}}$-рандомизацией Схема сглаживания с ${{l}_{2}}$-рандомизацией
${{\sigma }^{2}} \leqslant 32{{d}^{{3 - \frac{2}{p}}}}\frac{{{{G}^{2}}M_{2}^{2}}}{{{{\varepsilon }^{2}}}}$ ${{\sigma }^{2}} \leqslant 8\min \left\{ {q,\ln d} \right\}{{d}^{{3 - \frac{2}{p}}}}\frac{{{{G}^{2}}M_{2}^{2}}}{{{{\varepsilon }^{2}}}}$

если $\Delta $ достаточно мала.

Замечание 1. Если вместо стохастической негладкой выпуклой задачи оптимизации (2) рассматривать стохастическую негладкую выпукло-вогнутую задачу с седловой точкой

$\mathop {\min }\limits_{x \in {{Q}_{x}} \subseteq {{\mathbb{R}}^{{{{d}_{x}}}}}} \mathop {\max }\limits_{y \in {{Q}_{y}} \subseteq {{\mathbb{R}}^{{{{d}_{y}}}}}} \left\{ {f(x,y): = \mathbb{E}\left[ {f(x,y,\xi )} \right]} \right\},$
то применяя схему сглаживания, описанную выше в данном разделе, отдельно к $x$ и $y$ переменным, получим те же результаты, что и для выпуклой оптимизации при соответствующих изменениях $f(x,\xi )$ на $f(z,\xi )$, где $z: = (x,y),z \in {{Q}_{z}}: = {{Q}_{x}} \times {{Q}_{y}}$, за исключением одного пункта в лемме 1:

• ($\tilde {e} \in RB_{1}^{d}(1)$) вместо

$f(x) \leqslant {{f}_{\gamma }}(x) \leqslant f(x) + \frac{2}{{\sqrt d }}\gamma {{M}_{2}}$
имеем

$f(x,y) - \frac{2}{{\sqrt d }}{{\gamma }_{y}}{{M}_{{2,y}}} \leqslant {{f}_{\gamma }}(x,y) \leqslant f(x,y) + \frac{2}{{\sqrt d }}{{\gamma }_{x}}{{M}_{{2,x}}};$

• ($\tilde {e} \in RB_{2}^{d}(1)$) вместо

$f(x) \leqslant {{f}_{\gamma }}(x) \leqslant f(x) + \gamma {{M}_{2}}$
имеем
$f(x,y) - {{\gamma }_{y}}{{M}_{{2,y}}} \leqslant {{f}_{\gamma }}(x,y) \leqslant f(x,y) + {{\gamma }_{x}}{{M}_{{2,x}}},$
где $\gamma = ({{\gamma }_{x}},{{\gamma }_{y}})$, а ${{M}_{{2,x}}}$ и ${{M}_{{2,y}}}$ – соответствующие константы Липшица в ${{l}_{2}}$-норме.

4. ФЕДЕРАТИВНОЕ ОБУЧЕНИЕ

Архитектура распределенного обучения выглядит следующим образом: между “компьютерами” распределяется набор данных, каждый компьютер делает одно локальное обновление (локальный шаг, например, шаг стохастического градиентного спуска), после чего происходит глобальное обновление (глобальный шаг, коммуникация всех компьютеров со всеми), далее цепочка локально-глобальных обновлений повторяется. Однако глобальное обновление, например при большом размере данных, тратит много вычислительных ресурсов, в отличие от локального обновления. Тогда вводится архитектура федеративного обучения, представленная на фиг. 1, где в гомогенном случае $B$ компьютеров делают параллельно $K$ локальных обновлений перед каждым коммуникационным раундом, общее число которых составляет $N$. Таким образом, $NK$ является общим числом итераций алгоритма, а $T = NKB$ является общим числом вызовов стохастического градиента.

Фиг. 1.

Архитектура федеративного обучения.

4.1. Оптимальные алгоритмы первого порядка

В данной статье остановимся и рассмотрим класс пробатченных ускоренных методов первого порядка, а именно Minibatch Accelerated SGD (Mb-Ac-SGD) и Single-Machine Accelerated SGD (SM-Ac-SGD) из [11], Local-AC-CA из [12] и FedAc из [13], результаты скорости сходимости которых представлены в табл. 1. В таблице были использованы следующие обозначения: $R$ есть ${{\left\| {{{x}^{0}} - {{x}_{*}}} \right\|}_{2}}$; $B$ – количество работающих компьютеров; $K$ – число локальных обновлений; $N$ – количество коммуникационных раундов; $L$ – гладкость.

Таблица 1.  

Результаты скорости сходимости

Алгоритм $\mathbb{E}\left[ {f( \cdot )} \right] - f{\kern 1pt} * \lesssim \ldots $ Ссылка
Mb-Ac-SGD $\frac{{L{{R}^{2}}}}{{{{N}^{2}}}} + \frac{{\sigma R}}{{\sqrt {BNK} }}$ (Woodworth и др., 2021) [11]
SM-Ac-SGD $\frac{{L{{R}^{2}}}}{{{{N}^{2}}{{K}^{2}}}} + \frac{{\sigma R}}{{\sqrt {NK} }}$ (Woodworth и др., 2021) [11]
Local-AC-CA $\frac{{L{{R}^{2}}}}{{{{N}^{2}}{{K}^{2}}}} + \frac{{\sigma R}}{{\sqrt {BNK} }}$ (Woodworth и др., 2020) [12]
FedAc $\frac{{L{{R}^{2}}}}{{{{N}^{2}}K}} + \frac{{\sigma R}}{{\sqrt {BNK} }} + \min \left\{ {\frac{{{{L}^{{1/3}}}{{\sigma }^{{2/3}}}{{R}^{{4/3}}}}}{{N{{K}^{{1/3}}}}},\frac{{{{L}^{{1/2}}}{{\sigma }^{{1/2}}}{{R}^{{3/2}}}}}{{N{{K}^{{1/4}}}}}} \right\}$ (Yuan, Ma, 2020) [13]
Mb-SMP $\max \left\{ {\frac{{L{{R}^{2}}}}{N},\frac{{\sigma R}}{{\sqrt {BNK} }}} \right\}$ Приложение A
SM-SMP $\max \left\{ {\frac{{L{{R}^{2}}}}{{NK}},\frac{{\sigma R}}{{\sqrt {NK} }}} \right\}$ Приложение A

Для квадратичной целевой функции было доказано, что $K > 1$ локальное обновление приводит к оптимальным оценкам скорости сходимости (алгоритм Local-AC-CA из [12]). Алгоритм F-edAc из [13] обобщает результаты статьи [12] на случай выпуклых функций.

Но уже в 2021 г. были получены оптимальные оценки скорости сходимости в статье [11]. В данной статье утверждается, что оптимальные оценки можно получить только в двух случаях. Первый случай (алгоритм Minibatch Accelerated SGD) предполагает, что каждый компьютер выполняет одно локальное обновление перед коммуникационном раундом. Второй случай (алгоритм Single-Machine Accelerated SGD) предполагает, что работает только один компьютер, который выполняет $NK$ обновлений. Несмотря на доказанные результаты статьи [11], на практике в общем случае выпуклых функций получается использовать $K > 1$ локальных шагов, незначительно теряя при этом в точности, однако существенно выигрывая в вычислительных ресурсах. Именно практические результаты позволяют ожидать в будущем позитивные теоретические результаты.

Существующие алгоритмы первого порядка для архитектуры федеративного обучения зачастую решают задачу выпуклой оптимизации. Что касается задач оптимизации с седловой точкой, то алгоритмы в архитектуре федеративного обучения на данный момент отсутствуют. В данной статье мы разработали и получили оптимальные оценки скорости сходимости пробатченных методов первого порядка Minibatch SMP (Mb-SMP) и Single-Machine SMP (SM-SMP) для решения задач оптимизации с седловой точкой, используя аналогичный подход, что и в выпуклой оптимизации [11]. Оценки сходимости для алгоритмов решения седловых задач также приведены в табл. 1. Подробное описание получения верхних оценок скорости сходимости для алгоритмов Minibatch SMP (Mb-SMP) и Single-Machine SMP (SM-SMP) приведено в приложении A .

4.2. Оптимальные алгоритмы нулевого порядка

Здесь представлен главный результат данной статьи, который заключается в объединении двух глобальных идей в области оптимизации, представленные в разд. 3 и п. 4.1. А именно решение стохастических негладких выпуклых/выпукло-вогнутых задач оптимизации безградиентными алгоритмами архитектуры федеративного обучения. Для разработки и применения безградиентных методов решения негладких задач предлагается выбрать метод первого порядка, используемый для решения гладких задач в архитектуре федеративного обучения. Далее необходимо модифицировать алгоритм выбранного метода путем замены вычисления стохастического градиента на безградиентную аппроксимацию с ${{l}_{1}}$ (4) или ${{l}_{2}}$ (5) рандомизацией. Полученный безградиентный алгоритм будет иметь одноименное название алгоритма первого порядка, однако он не будет требовать информацию о стохастическом градиенте.

Пусть под алгоритмом A$(L,{{\sigma }^{2}})$ будем понимать ускоренные пакетные алгоритмы решения задач выпуклой оптимизации: Minibatch и Single-Machine Accelerated SGD, Local-AC-CA и FedAc и ускоренные пакетные алгоритмы решения задач с седловой точкой: Minibatch SMP и Single‑-Machine SMP в архитектуре федеративного обучения. Тогда в теоремах 1, 2 предполагаем, что выполняется данное свойство: алгоритм A$(L,{{\sigma }^{2}})$ (со смещенным безградиентным оракулом $\nabla {{f}_{\gamma }}(x,\xi ,e)$) является надежным, если смещение из следствия 5 для ${{l}_{1}}$-рандомизации, из следст-вия 6 для ${{l}_{2}}$-рандомизации (рассмотренных в п. 5.4) не накапливается в течение итерации метода. То есть, если для A$(L,{{\sigma }^{2}})$ при $\Delta = 0$:

$E[{{f}_{\gamma }}({{x}^{N}}) - f({{x}_{*}})] \leqslant {{\Theta }_{A}}(N),$
тогда

• при $\Delta > 0$ и ${{d}^{{4 - \frac{2}{p}}}}{{\Delta }^{2}}{{\gamma }^{{ - 2}}} \lesssim \kappa (p,d)M_{2}^{2}$ из (6):

(13)
$E[{{f}_{\gamma }}({{x}^{N}}) - f({{x}_{*}})] \leqslant O\left( {{{\Theta }_{A}}(N) + d\Delta R{{\gamma }^{{ - 1}}}} \right);$

• при $\Delta > 0$ и ${{d}^{2}}{{\Delta }^{2}}{{\gamma }^{{ - 2}}} \lesssim dM_{2}^{2}$ из (7):

(14)
$E[{{f}_{\gamma }}({{x}^{N}}) - f({{x}_{*}})] \leqslant O\left( {{{\Theta }_{A}}(N) + \sqrt d \Delta R{{\gamma }^{{ - 1}}}} \right).$

Предположение о выполнении данного свойства базируется на статье [14], где был разработан анализ сходимости методов для смещенных стохастических оракулов. Поэтому в теоремах 1, 2 приводим результаты, предполагая, что можно по аналогии провести анализ сходимости методов федеративного обучения, рассмотренных в этой работе, для смещенных стохастических оракулов. Однако в доказательстве теорем 1, 2 будем рассматривать случай при $\Delta = 0$ и приводить оптимальные оценки параметров разработанных безградиентных алгоритмов.

Теорема 1. Схема сглаживания из разд. 3, применяемая к задаче (2), обеспечивает сходимость следующих двухточечных безградиентных алгоритмов: Minibatch и Single-Machine Accelerated SGD [11], Local-AC-CA [12] и FedAc [13]. Другими словами, для достижения $\varepsilon $ точности решения задачи (2) необходимо проделать $NK$ итераций с максимально допустимым уровнем шума $\Delta $ и общим числом вызова безградиентного оракула $T$ в соответствии с выбранным методом и схемой сглаживания:

• Minibatch Accelerated SGD

i) для ${{l}_{1}}$-рандомизации (4):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = O\left( {\frac{{{{d}^{{1/4}}}\sqrt {M{{M}_{2}}} R}}{\varepsilon }} \right);\quad K = 1;\quad B = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{KN{{\varepsilon }^{2}}}}} \right);$
$T = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} O\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ O\left( {\frac{{M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

ii) для ${{l}_{2}}$-рандомизации (5):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = O\left( {\frac{{{{d}^{{1/4}}}\sqrt {M{{M}_{2}}} R}}{\varepsilon }} \right);\quad K = 1;\quad B = O\left( {\frac{{\kappa (p,d)dM_{2}^{2}{{R}^{2}}}}{{KN{{\varepsilon }^{2}}}}} \right);$
$T = \tilde {O}\left( {\frac{{\kappa (p,d)dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} \tilde {O}\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ \tilde {O}\left( {\frac{{(\ln d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

• Single-Machine Accelerated SGD

i) для ${{l}_{1}}$-рандомизации (4):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right);\quad B = 1;$
$T = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} O\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ O\left( {\frac{{M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

ii) для ${{l}_{2}}$-рандомизации (5):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right);\quad B = 1;$
$T = \tilde {O}\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} \tilde {O}\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ \tilde {O}\left( {\frac{{(\ln d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

• Local-AC-SA

i) для ${{l}_{1}}$-рандомизации (4):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = O\left( {\frac{{{{d}^{{1/4}}}\sqrt {M{{M}_{2}}} R}}{\varepsilon }} \right);\quad B = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{KN{{\varepsilon }^{2}}}}} \right);$
$T = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} O\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ O\left( {\frac{{M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

ii) для ${{l}_{2}}$-рандомизации (5):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = O\left( {\frac{{{{d}^{{1/4}}}\sqrt {M{{M}_{2}}} R}}{\varepsilon }} \right);\quad B = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{KN{{\varepsilon }^{2}}}}} \right);$
$T = \tilde {O}\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} \tilde {O}\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ \tilde {O}\left( {\frac{{(\ln d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

• Federated Accelerated SGD (FedAc)

i) для ${{l}_{1}}$-рандомизации (4):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = O\left( {\frac{{{{d}^{{1/6}}}{{{(\kappa (p,d)M)}}^{{1/3}}}{{M}_{2}}{{R}^{{4/3}}}}}{{{{K}^{{1/3}}}{{\varepsilon }^{{4/3}}}}}} \right);\quad K = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{BN{{\varepsilon }^{2}}}}} \right);\quad B = 1;$
$T = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} O\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ O\left( {\frac{{M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

ii) для ${{l}_{2}}$-рандомизации (5):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = O\left( {\frac{{{{d}^{{1/2}}}{{{(\kappa (p,d)M)}}^{{1/3}}}{{M}_{2}}{{R}^{{4/3}}}}}{{{{K}^{{1/3}}}{{\varepsilon }^{{4/3}}}}}} \right);\quad K = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{BN{{\varepsilon }^{2}}}}} \right);\quad B = 1;$
$T = \tilde {O}\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} \tilde {O}\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ \tilde {O}\left( {\frac{{(\ln d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1. \hfill \\ \end{gathered} \right.$

Подробное доказательство теоремы 1 приведено в приложении B .

По результатам теоремы 1 стоит обратить внимание, что количество локальных обновлений $K > 1$ с использованием $B > 1$ компьютеров при оптимальных значениях $N$ и $T$ получилось только для одного алгоритма, а именно Local-AC-CA, который применяется для частного квадратичного случая. Это подтверждает, что в теории на данный момент существует только два оптимальных (по $\Delta $, $N$ и $T$) алгоритма: Minibatch и Single-Machine Accelerated SGD. В работе [13] показано, что на практике можно получить результат, в котором алгоритм совершает параллельно $K > 1$ локальных обновлений на каждых $B > 1$ компьютерах.

В теореме 2 также получены оптимальные оценки параметров, рассмотренных в п. 4.1 алгоритмов для решения стохастических негладких задач с седловой точкой, оптимальных по $\Delta $, N и T.

Теорема 2. Схема сглаживания из разд. 3, применяемая к седловой задаче (см. замечание 1), обеспечивает сходимость следующих двухточечных безградиентных алгоритмов: Minibatch SMP и Single-Machine SMP из приложения A . Другими словами, для достижения $\varepsilon $ точности решения седловой задачи (см. замечание 1) необходимо проделать $NK$ итераций с максимально допустимым уровнем шума $\Delta $ и общим числом вызова безградиентного оракула $T$ в соответствии с выбранным методом и схемой сглаживания:

• Minibatch SMP

i) для ${{l}_{1}}$-рандомизации (4):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = 1;\quad B = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right);$
$T = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} O\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ O\left( {\frac{{M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

ii) для ${{l}_{2}}$-рандомизации (5):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = 1;\quad B = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right);$
$T = \tilde {O}\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} \tilde {O}\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ \tilde {O}\left( {\frac{{(\ln d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

• Single-Machine SMP

i) для ${{l}_{1}}$-рандомизации (4):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right);\quad B = 1;$
$T = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} O\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ O\left( {\frac{{M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1; \hfill \\ \end{gathered} \right.$

ii) для ${{l}_{2}}$-рандомизации (5):

$\Delta = O\left( {\frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}} \right);$
$N = 1;\quad K = O\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right);\quad B = 1;$
$T = \tilde {O}\left( {\frac{{\kappa (p,d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right) = \left\{ \begin{gathered} \tilde {O}\left( {\frac{{dM_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 2, \hfill \\ \tilde {O}\left( {\frac{{(\ln d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right),\quad p = 1. \hfill \\ \end{gathered} \right.$

Подробное доказательство теоремы 2 приведено в приложении C .

По результатам теоремы 1 и теоремы 2 не трудно увидеть, что для всех алгоритмов оптимальное число вызовов безградиентного оракула в ${{l}_{1}}$-норме равняется $\tilde {O}\left( {\frac{{(\ln d)M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right)$ с ${{l}_{2}}$-рандомизацией, в то время как для ${{l}_{1}}$-рандомизации равняется $O\left( {\frac{{M_{2}^{2}{{R}^{2}}}}{{{{\varepsilon }^{2}}}}} \right)$, где $\varepsilon $ является точностью решения негладкой задачи. Данный результат подтверждает, что схема сглаживания с ${{l}_{1}}$-рандомизацией лучше работает в архитектуре федеративного обучения, чем схема сглаживания с ${{l}_{2}}$-рандомизацией. В разд. 6 проверим этот результат на практическом эксперименте.

Замечание 2. Для получения результатов теорем 1 и 2 использовалось предположение о доступности двухточечной обратной связи (см. п. 3.3). Если вместо двухточечной обратной связи использовать одноточечную (см. п. 3.4), то это приведет к такой же итерационной сложности (количеству коммуникационных раундов) $N$ и максимальному уровню неточности $\Delta $, однако оракульная сложность возрастет в $O\left( {d/{{\varepsilon }^{2}}} \right)$ раз. Данный случай подробно рассмотрен в приложении D .

Замечание 3. Стоит отметить, что идея объединения двух техник, а именно федеративного обучения со схемами сглаживания, не ограничивается рассмотренными алгоритмами первого порядка и может быть использована для решения негладких задач другими алгоритмами, используемыми в архитектуре федеративного обучения.

5. СХЕМЫ ДОКАЗАТЕЛЬСТВ

Приведем схемы для доказательств теоремы 1 и теоремы 2. Подробные доказательства этих теорем можно найти в приложении B, C . Здесь сфокусируемся на доказательстве леммы 1-3 и на нахождении оценки уровня неточности (враждебного шума).

5.1. Доказательство леммы 1

В данном п. рассмотрим неевклидовый случай, когда случайный вектор $\tilde {e}$ равномерно распределен на ${{l}_{1}}$-шаре. Доказательство евклидового случая можно найти в теореме 2.1 из [1].

Для всех $x,y \in Q$ верно следующее:

1) $f(x) \leqslant {{f}_{\gamma }}(x) \leqslant f(x) + \frac{2}{{\sqrt d }}\gamma {{M}_{2}}$;

2) ${{f}_{\gamma }}$ – $M$-липшицева:

$\left| {{{f}_{\gamma }}(y) - {{f}_{\gamma }}(x)} \right| \leqslant M{{\left\| {y - x} \right\|}_{p}},$

3) ${{f}_{\gamma }}$ имеет ${{L}_{{{{f}_{\gamma }}}}} = \frac{{dM}}{{2\gamma }}$-липшицевый градиент:

${{\left\| {\nabla {{f}_{\gamma }}(y) - \nabla {{f}_{\gamma }}(x)} \right\|}_{q}} \leqslant {{L}_{{{{f}_{\gamma }}}}}{{\left\| {y - x} \right\|}_{2}} \leqslant {{L}_{{{{f}_{\gamma }}}}}{{\left\| {y - x} \right\|}_{p}},$
где $q$ такой, что $1{\text{/}}p + 1{\text{/}}q = 1$.

Доказательство. Для первого неравенства первого свойства воспользуемся выпуклостью функции $f(x)$

${{f}_{\gamma }}(x) = {{\mathbb{E}}_{{\tilde {e}}}}\left[ {f(x + \gamma \tilde {e})} \right] \geqslant {{\mathbb{E}}_{{\tilde {e}}}}\left[ {f(x) + \langle \nabla f(x),\gamma \tilde {e}\rangle )} \right] = {{\mathbb{E}}_{{\tilde {e}}}}\left[ {f(x)} \right] = f(x).$

Для второго неравенства первого свойства, применяя лемму 1 из [4], имеем:

$\left| {{{f}_{\gamma }}(x) - f(x)} \right| = \left| {{{\mathbb{E}}_{{\tilde {e}}}}\left[ {f(x + \gamma \tilde {e})} \right] - f(x)} \right| \leqslant {{\mathbb{E}}_{{\tilde {e}}}}\left[ {\left| {f(x + \gamma \tilde {e}) - f(x)} \right|} \right] \leqslant \gamma {{M}_{2}}{{\mathbb{E}}_{{\tilde {e}}}}\left[ {{{{\left\| {\tilde {e}} \right\|}}_{2}}} \right] \leqslant \frac{2}{{\sqrt d }}\gamma {{M}_{2}},$
используя тот факт, что $f$ является ${{M}_{2}}$-липшицевой.

Для второго свойства:

$\begin{array}{*{20}{l}} {\left| {{{f}_{\gamma }}(y) - {{f}_{\gamma }}(x)} \right| = \left| {{{\mathbb{E}}_{{\tilde {e}}}}\left[ {f(y + \gamma \tilde {e}) - f(x + \gamma \tilde {e})} \right]} \right|}&{ \leqslant {{\mathbb{E}}_{{\tilde {e}}}}\left[ {\left| {f(y + \gamma \tilde {e}) - f(x + \gamma \tilde {e})} \right|} \right] \leqslant M{{{\left\| {y - x} \right\|}}_{p}}} \end{array}.$

И для третьего свойства, применяя лемму 11 из [15] имеем для любых $x,y \in Q$,

$\begin{gathered} {{\left\| {\nabla {{f}_{\gamma }}(y) - \nabla {{f}_{\gamma }}(x)} \right\|}_{q}} = {{\left\| {\int\limits_{B_{1}^{d}(\gamma )} {\kern 1pt} \nabla f(y + \tilde {e})\mu (\tilde {e})d\tilde {e} - \int\limits_{B_{1}^{d}(\gamma )} {\kern 1pt} \nabla f(x + \tilde {e})\mu (\tilde {e})d\tilde {e}} \right\|}_{q}} \leqslant \\ \leqslant {{\left\| {\int\limits_{{{Q}_{\gamma }}} {\kern 1pt} \nabla f(z)\mu (z - y)dz - \int\limits_{{{Q}_{\gamma }}} {\kern 1pt} \nabla f(z)\mu (z - x)dz} \right\|}_{q}} \leqslant M\underbrace {\int\limits_{{{Q}_{\gamma }}} \left| {\mu (z - y) - \mu (z - x)} \right|dz}_{{{I}_{1}}}, \\ \end{gathered} $
где второе неравенство следует из $z = x + \tilde {e}$ и $\mu (x) = \left\{ \begin{gathered} \frac{1}{{V(B_{1}^{d}(\gamma ))}},\quad x \in B_{1}^{d}(\gamma ), \hfill \\ 0\quad {\text{иначе}}. \hfill \\ \end{gathered} \right.$ Далее для оценки интеграла ${{I}_{1}}$ применим тот же подход, что и в доказательстве леммы 8 из [16] и рассмотрим случаи где ${{\left\| {y - x} \right\|}_{1}} > 2\gamma $ и ${{\left\| {y - x} \right\|}_{1}} \leqslant 2\gamma $.

Случай 1 (${{\left\| {y - x} \right\|}_{1}} > 2\gamma $). Для всех $\tilde {e}$ пусть ${{\left\| {\tilde {e} - x} \right\|}_{1}} \leqslant \gamma $, тогда имеем ${{\left\| {\tilde {e} - y} \right\|}_{1}} > \gamma \Rightarrow $ $\mu (\tilde {e} - y) = 0$, поэтому

$\int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = 1.$
Аналогично для всех $\tilde {e}$ пусть ${{\left\| {\tilde {e} - y} \right\|}_{1}} \leqslant \gamma $, тогда имеем $\mu (\tilde {e} - x) = 0$, поэтому
$\int\limits_{{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = 1.$
Следовательно,

$\int\limits_{{{Q}_{\gamma }}} \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = \int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} + \int\limits_{{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = 2.$

Поскольку $2 < \frac{{{{{\left\| {y - x} \right\|}}_{1}}}}{\gamma } \leqslant \frac{{{{d}^{{1 - 1/p}}}{{{\left\| {y - x} \right\|}}_{p}}}}{\gamma }$, учитывая тот факт, что для $p \in [1,2]$ выполнено ${{\left\| {y - x} \right\|}_{1}} \leqslant {{d}^{{1 - \frac{1}{p}}}}{{\left\| {y - x} \right\|}_{p}}$, тогда получим следующее неравенство:

$\int\limits_{{{Q}_{\gamma }}} \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} \leqslant \frac{{{{d}^{{1 - 1/p}}}{{{\left\| {y - x} \right\|}}_{p}}}}{\gamma }.$

Случай 2 (${{\left\| {y - x} \right\|}_{1}} \leqslant 2\gamma $). Разложим интеграл ${{I}_{1}}$ на 4 интеграла

$\begin{gathered} \int\limits_{{{Q}_{\gamma }}} \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = \\ \, = \int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma \;\& \;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} + \int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma \;\& \;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \geqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} + \\ \, + \int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \geqslant \gamma \;\& \;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} + \int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \geqslant \gamma \;\& \;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \geqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e}. \\ \end{gathered} $

Теперь рассмотрим каждый интеграл из разложения по отдельности.

1. Для первого и четвертого интегралов справедливо следующее:

$\mu (\tilde {e} - x) = \mu (\tilde {e} - y).$

Тогда, подставляя в первый интеграл, получим

(15)
$\int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma \;\& {{{\left\| {\tilde {e} - y} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = 0.$

Аналогично, подставляя в четвертый интеграл, получим

(16)
$\int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \geqslant \gamma \;\& {{{\left\| {\tilde {e} - y} \right\|}}_{1}} \geqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = 0.$

2. Когда ${{\left\| {\tilde {e} - x} \right\|}_{1}} \leqslant \gamma \;\& \;{{\left\| {\tilde {e} - y} \right\|}_{1}} \geqslant \gamma $ или ${{\left\| {\tilde {e} - x} \right\|}_{1}} \geqslant \gamma \;\& \;{{\left\| {\tilde {e} - y} \right\|}_{1}} \leqslant \gamma $, имеем

$\int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma \;\& \;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \geqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = \int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \geqslant \gamma \;\& \;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \leqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e},$
где $\mu (\tilde {e} - x)$ и $\mu (\tilde {e} - y)$ не пересекаются, поэтому, используя это и симметрию интегралов, и, определив множество $S = \left\{ {\tilde {e} \in {{\mathbb{R}}^{d}}\,{\text{|}}\,{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma \;{\text{и}}\;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \geqslant \gamma } \right\}$, получим сумму второго и третьего интегралов
(17)
$2\int\limits_{{{{\left\| {\tilde {e} - x} \right\|}}_{1}} \leqslant \gamma \;\& \;{{{\left\| {\tilde {e} - y} \right\|}}_{1}} \geqslant \gamma } \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = \frac{2}{{{{c}_{d}}{{\gamma }^{d}}}}{{V}_{S}},$
где ${{V}_{S}}$ – объем на множестве $S$.

Суммируя значения четырех интегралов (15)–(17), получим

(18)
$\int\limits_{{{Q}_{\gamma }}} \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} = \frac{2}{{{{c}_{d}}{{\gamma }^{d}}}}{{V}_{S}},$
где ${{V}_{S}}$ – объем на множестве $S$.

Теперь найдем верхнюю границу ${{V}_{S}}$ через ${{\left\| {y - x} \right\|}_{p}}$. Пусть ${{V}_{{{\text{cap}}}}}(r)$ – объем сферического колпака с расстоянием $r$ до центра ${{l}_{1}}$-сферы. Тогда

(19)
${{V}_{S}} = {{c}_{d}}{{\gamma }^{d}} - 2{{V}_{{{\text{cap}}}}}\left( {\frac{{{{{\left\| {y - x} \right\|}}_{p}}}}{4}} \right).$
Объем $d$-мерного сферического колпака ${{V}_{{{\text{cap}}}}}$ может быть вычислен через $(d - 1)$-мерную ${{l}_{1}}$-сферу следующим образом:
${{V}_{{{\text{cap}}}}}(r) = \int\limits_r^\gamma \,{{c}_{{d - 1}}}{{\left( {\gamma - \rho } \right)}^{{d - 1}}}d\rho \quad {\text{для}}\quad r \in [0,\gamma ],$
где ${{c}_{d}} = \frac{{{{2}^{d}}}}{{d!}}$, $d \geqslant 1$. Для $r \in [0,\gamma ]$ имеем
$\begin{gathered} V_{{{\text{cap}}}}^{'}(r) = - {{c}_{{d - 1}}}{{\left( {\gamma - r} \right)}^{{d - 1}}} \leqslant 0, \\ V_{{{\text{cap}}}}^{{''}}(r) = (d - 1){{c}_{{d - 1}}}{{(\gamma - r)}^{{d - 2}}} \geqslant 0, \\ \end{gathered} $
где $V_{{{\text{cap}}}}^{'},\;V_{{{\text{cap}}}}^{{''}}$ – первая и вторая производные по $r$ соответственно. Следовательно, ${{V}_{{{\text{cap}}}}}$ выпукла на $[0,\gamma ]$, и по определению субградиента имеем
${{V}_{{{\text{cap}}}}}(0) + V_{{{\text{cap}}}}^{'}(0)r \leqslant {{V}_{{{\text{cap}}}}}(r)\quad {\text{для}}\quad r \in [0,\gamma ].$
Так как ${{V}_{{{\text{cap}}}}}(0) = \frac{1}{2}{{c}_{d}}{{\gamma }^{d}}$ и $V_{{{\text{cap}}}}^{'}(0) = - {{c}_{{d - 1}}}{{\gamma }^{{d - 1}}}$, отсюда следует, что
(20)
$\frac{1}{2}{{c}_{d}}{{\gamma }^{d}} - {{c}_{{d - 1}}}{{\gamma }^{{d - 1}}} \leqslant {{V}_{{{\text{cap}}}}}(r)\quad {\text{для}}\quad r \in [0,\gamma ].$
Поскольку ${{\left\| {y - x} \right\|}_{1}}{\text{/}}2 \leqslant \gamma $ и отмечая, что ${{\left\| {y - x} \right\|}_{p}}{\text{/}}4 \leqslant {{\left\| {y - x} \right\|}_{p}}{\text{/}}2 \leqslant {{\left\| {y - x} \right\|}_{1}}{\text{/}}2$ выполняется для $p \in [1,2]$, можем задать $r = {{\left\| {y - x} \right\|}_{p}}{\text{/}}4 \leqslant \gamma $ и подставить в (20). Сделав это и используя (19), по-лучим
${{V}_{S}} = {{c}_{d}}{{\gamma }^{d}} - 2{{V}_{{{\text{cap}}}}}\left( {\frac{{{{{\left\| {y - x} \right\|}}_{p}}}}{4}} \right) \leqslant 2{{c}_{{d - 1}}}{{\gamma }^{{d - 1}}}\frac{{{{{\left\| {y - x} \right\|}}_{p}}}}{4}.$
Теперь, подставляя полученную оценку ${{V}_{S}}$ в (18), имеем
$\int\limits_{{{Q}_{\gamma }}} \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} \leqslant \frac{{{{c}_{{d - 1}}}}}{{{{c}_{d}}}}\frac{{{{{\left\| {y - x} \right\|}}_{p}}}}{\gamma }.$
Поскольку ${{c}_{d}} = \frac{{{{2}^{d}}}}{{d!}}$, можно увидеть, что
$\int\limits_{{{Q}_{\gamma }}} \left| {\mu (\tilde {e} - y) - \mu (\tilde {e} - x)} \right|d\tilde {e} \leqslant \frac{d}{{2\gamma }}{{\left\| {y - x} \right\|}_{p}}.$
Теперь, получив оценку для интеграла ${{I}_{1}}$, имеем, что

${{\left\| {\nabla {{f}_{\gamma }}(y) - \nabla {{f}_{\gamma }}(x)} \right\|}_{q}} \leqslant \frac{{dM}}{{2\gamma }}{{\left\| {y - x} \right\|}_{p}}.$

5.2. Доказательство леммы 2

В данном подразделе сосредоточимся на доказательство леммы 2 для ${{l}_{2}}$-рандомизации. Во многих работах, например в [1, 3, 9], оценка второго момента для безградиентной аппроксимации (5) приведена и доказана с точностью до некоторой числовой константы $c$. В данном доказательстве разберемся, чему же равна эта числовая константа $c$. А подробное доказательство леммы 2 для ${{l}_{1}}$-рандомизации приведено в лемме 4 [4].

Для всех $x \in Q$ с предположениями 1 и 2 $\nabla {{f}_{\gamma }}(x,\xi ,e)$ из (5) имеет нижнюю оценку (второй момент):

${{E}_{{\xi ,e}}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant \kappa (p,d)\left( {dM_{2}^{2} + \frac{{{{d}^{2}}{{\Delta }^{2}}}}{{\sqrt 2 {{\gamma }^{2}}}}} \right),$
где $1{\text{/}}p + 1{\text{/}}q = 1$ и

$\kappa (p,d) = \sqrt 2 \min \left\{ {q,\ln d} \right\}{{d}^{{2/q - 1}}}.$

Доказательство. Давайте рассмотрим

(21)
$\begin{gathered} {{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] = {{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| {\frac{d}{{2\gamma }}({{f}_{\delta }}(x + \gamma e,\xi ) - {{f}_{\delta }}(x - \gamma e,\xi ))e} \right\|_{q}^{2}} \right] = \\ = \frac{{{{d}^{2}}}}{{4{{\gamma }^{2}}}}{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {f(x + \gamma e,\xi ) + \delta (x + \gamma e) - f(x - \gamma e,\xi ) - \delta (x - \gamma e)} \right)}}^{2}}} \right] \leqslant \\ \leqslant \frac{{{{d}^{2}}}}{{2{{\gamma }^{2}}}}\left( {{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {f(x + \gamma e,\xi ) - f(x - \gamma e,\xi )} \right)}}^{2}}} \right] + {{\mathbb{E}}_{e}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {\delta (x + \gamma e) - \delta (x - \gamma e)} \right)}}^{2}}} \right]} \right), \\ \end{gathered} $
где использовался тот факт, что для всех $a,b,(a + b{{)}^{2}} \leqslant 2{{a}^{2}} + 2{{b}^{2}}$. Для первого слагаемого (21) выполняется следующее с произвольным параметром $\alpha $ с учетом симметричного распределения $e$
$\begin{gathered} \frac{{{{d}^{2}}}}{{2{{\gamma }^{2}}}}{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {f(x + \gamma e,\xi ) - f(x - \gamma e,\xi )} \right)}}^{2}}} \right] = \\ = \frac{{{{d}^{2}}}}{{2{{\gamma }^{2}}}}{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {(f(x + \gamma e,\xi ) - \alpha ) - (f(x - \gamma e,\xi ) - \alpha )} \right)}}^{2}}} \right] \leqslant \\ \end{gathered} $
(22)
$ \leqslant \frac{{{{d}^{2}}}}{{{{\gamma }^{2}}}}{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {f(x + \gamma e,\xi ) - \alpha } \right)}}^{2}} + {{{\left( {f(x - \gamma e,\xi ) - \alpha } \right)}}^{2}}} \right] = $
$\begin{gathered} = \frac{{{{d}^{2}}}}{{{{\gamma }^{2}}}}\left( {{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {f(x + \gamma e,\xi ) - \alpha } \right)}}^{2}}} \right] + {{\mathbb{E}}_{{\xi ,e}}}\left[ {{{{\left( {f(x - \gamma e,\xi ) - \alpha } \right)}}^{2}}} \right]} \right) = \\ = \frac{{2{{d}^{2}}}}{{{{\gamma }^{2}}}}{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {f(x + \gamma e,\xi ) - \alpha } \right)}}^{2}}} \right]. \\ \end{gathered} $
Применяя неравенство Коши–Шварца для (22) и используя $\sqrt {\mathbb{E}\left[ {\left\| e \right\|_{q}^{4}} \right]} \leqslant \kappa {\kern 1pt} '{\kern 1pt} (p,d)$, где $\kappa {\kern 1pt} '(p,d) = \min \left\{ {q,\ln d} \right\}{{d}^{{2/q - 1}}}$, получим
(23)
$\begin{gathered} \frac{{2{{d}^{2}}}}{{{{\gamma }^{2}}}}{{\mathbb{E}}_{{\xi ,e}}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {f(x + \gamma e,\xi ) - \alpha } \right)}}^{2}}} \right] \leqslant \frac{{2{{d}^{2}}}}{{{{\gamma }^{2}}}}{{\mathbb{E}}_{\xi }}\left[ {\sqrt {\mathbb{E}\left[ {\left\| e \right\|_{q}^{4}} \right]} \sqrt {{{\mathbb{E}}_{e}}\left[ {{{{\left( {f(x + \gamma e,\xi ) - \alpha } \right)}}^{4}}} \right]} } \right] \leqslant \\ \leqslant \frac{{2{{d}^{2}}\kappa {\kern 1pt} '{\kern 1pt} (p,d)}}{{{{\gamma }^{2}}}}{{\mathbb{E}}_{\xi }}\left[ {\sqrt {{{\mathbb{E}}_{e}}\left[ {{{{\left( {f(x + \gamma e,\xi ) - \alpha } \right)}}^{4}}} \right]} } \right]. \\ \end{gathered} $
Следующая лемма, которую рассмотрим, является уточнением леммы 9 [3] с указанием числовой константы $c$.

Лемма 4. Для любой функции $f(e)$, которая является $M$-липшицевой относительно ${{l}_{2}}$-нормы, имеет место, что если $e$ равномерно распределен на евклидовой сфере, тогда

$\sqrt {\mathbb{E}\left[ {{{{\left( {f(e) - \mathbb{E}\left[ {f(e)} \right]} \right)}}^{4}}} \right]} \leqslant \frac{{M_{2}^{2}}}{{\sqrt 2 d}}.$

Доказательство. Пусть неравенство концентрации меры, использующее математическое ожидание, имеет вид

$\Pr ({\kern 1pt} \left| {f - \mathbb{E}f} \right| > t) \leqslant K\exp ( - \eta {{t}^{2}}),$
где $K$ и $\eta $ – неизвестные параметры. Тогда, чтобы найти параметры $K$ и $\eta $, выпишем неравенство, использующую медиану функции, используя параметры $K$ и $\eta $ (так как в литературе, например в [10], обычно записывается неравенство концентрации меры на сфере, используя медиану функции ${{M}_{f}}$, а не математическое ожидание):
(24)
$\Pr {\kern 1pt} ({\kern 1pt} {\text{|}}f - {{M}_{f}}{\kern 1pt} {\text{|}} > t) \leqslant 2K\exp ( - \eta {{t}^{2}}{\text{/}}4) = 4\exp ( - d{{t}^{2}}{\text{/}}2M_{2}^{2}).$
Подставляя параметры $K = 2$ и $\eta = 2d{\text{/}}M_{2}^{2}$ из неравенства (24), запишем стандартный результат о концентрации липшицевых функций на евклидовой единичной сфере
$\Pr ({\kern 1pt} {\text{|}}f(e) - \mathbb{E}{\text{[}}f(e){\text{]|}} > t) \leqslant 2\exp ( - 2d{{t}^{2}}{\text{/}}M_{2}^{2}).$
Следовательно,
$\begin{gathered} \sqrt {\mathbb{E}\left[ {{{{\left( {f(e) - \mathbb{E}\left[ {f(e)} \right]} \right)}}^{4}}} \right]} = \sqrt {\int\limits_{t = 0}^\infty \Pr \left( {{{{\left( {f(e) - \mathbb{E}\left[ {f(e)} \right]} \right)}}^{4}} > t} \right)dt} = \\ = \sqrt {\int\limits_{t = 0}^\infty \Pr \left( {\left| {f(e) - \mathbb{E}\left[ {f(e)} \right]{\kern 1pt} } \right| > \sqrt[4]{t}} \right)dt} \leqslant \sqrt {\int\limits_{t = 0}^\infty 2\exp \left( { - \frac{{2d\sqrt t }}{{M_{2}^{2}}}} \right)dt} = \sqrt {2\frac{{M_{2}^{4}}}{{{{{(2d)}}^{2}}}}} , \\ \end{gathered} $
где в последнем шаге использовался факт, что $\int_{t = 0}^\infty {\exp ( - \sqrt x )dx} = 2$. Таким образом, найдена числовая константа $c = \frac{1}{{\sqrt 2 }}$ из леммы 9 [3].

Затем используем лемму 4 вместе с тем фактом, что $f(x + \gamma e,\xi )$ является $\gamma {{M}_{2}}(\xi )$-липшицевой относительно $e$ с точки зрения ${{l}_{2}}$-нормы. Таким образом, для (23) и $\alpha : = \mathbb{E}\left[ {f(x + \gamma e,\xi )} \right]$ выполняется

(25)
$\frac{{2{{d}^{2}}\kappa {\kern 1pt} '{\kern 1pt} (p,d)}}{{{{\gamma }^{2}}}}{{\mathbb{E}}_{\xi }}\left[ {\sqrt {{{\mathbb{E}}_{e}}\left[ {{{{\left( {f(x + \gamma e,\xi ) - \alpha } \right)}}^{4}}} \right]} } \right] \leqslant \frac{{2{{d}^{2}}\kappa {\kern 1pt} '{\kern 1pt} (p,d)}}{{{{\gamma }^{2}}}} \cdot \frac{{{{\gamma }^{2}}\mathbb{E}\left[ {M_{2}^{2}(\xi )} \right]}}{{\sqrt 2 d}} = \sqrt 2 \kappa {\kern 1pt} '{\kern 1pt} (p,d)dM_{2}^{2}.$
Для второго слагаемого (21) выполняется следующее:
(26)
$\frac{{{{d}^{2}}}}{{2{{\gamma }^{2}}}}{{\mathbb{E}}_{e}}\left[ {\left\| e \right\|_{q}^{2}{{{\left( {\delta (x + \gamma e) - \delta (x - \gamma e)} \right)}}^{2}}} \right] \leqslant \frac{{{{d}^{2}}{{\Delta }^{2}}}}{{{{\gamma }^{2}}}}{{\mathbb{E}}_{e}}\left[ {\left\| e \right\|_{q}^{2}} \right] \leqslant \frac{{\kappa '(p,d){{d}^{2}}{{\Delta }^{2}}}}{{{{\gamma }^{2}}}}.$
Подставляя (25) и (26) в неравенство (21) и занося коэффициент $\sqrt 2 $ в $\kappa {\kern 1pt} '(p,d)$, получим утверждение леммы 2 для ${{l}_{2}}$-рандомизации c $\kappa (p,d) = \sqrt 2 \kappa {\kern 1pt} '(p,d) = \sqrt 2 \min \left\{ {q,\ln d} \right\}{{d}^{{2/q - 1}}}$.

5.3. Доказательство леммы 3

Рассмотрим краткое доказательство леммы 3 для случая с ${{l}_{1}}$-рандомизацией. С евклидовым случаем можно познакомиться в следующих работах [1, 17].

Для всех $x \in Q$ с предположениями 2 и 3 $\nabla {{f}_{\gamma }}(x,\xi ,e)$ из (8) имеет нижнюю оценку (второй момент):

${{\mathbb{E}}_{e}}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] \leqslant \frac{{{{d}^{{4 - \frac{2}{p}}}}}}{{{{\gamma }^{2}}}}\left( {{{G}^{2}} + {{\Delta }^{2}}} \right),$
где $1{\text{/}}p + 1{\text{/}}q = 1$.

Доказательство. Доказательство этой леммы будет базироваться на доказательстве леммы 4 из [4]. Используя определение $\nabla {{f}_{\gamma }}(x,\xi ,e)$, получим

$\mathbb{E}\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] = \frac{{{{d}^{2}}}}{{{{\gamma }^{2}}}}\mathbb{E}\left[ {{{{(f(x + \gamma e) + \delta (x))}}^{2}}\left\| {\operatorname{sign} (e)} \right\|_{q}^{2}} \right] = \frac{{{{d}^{{4 - \frac{2}{p}}}}}}{{{{\gamma }^{2}}}}\mathbb{E}\left[ {{{{(f(x + \gamma e) + \delta (x))}}^{2}}} \right].$
Далее с предположениями 2 и 3 получим утверждение леммы:

$E\left[ {\left\| {\nabla {{f}_{\gamma }}(x,\xi ,e)} \right\|_{q}^{2}} \right] = \frac{{{{d}^{{4 - \frac{2}{p}}}}}}{{{{\gamma }^{2}}}}E\left[ {{{{(f(x + \gamma e) + \delta (x))}}^{2}}} \right] \leqslant \frac{{{{d}^{{4 - \frac{2}{p}}}}}}{{{{\gamma }^{2}}}}\left( {{{G}^{2}} + {{\Delta }^{2}}} \right).$

5.4. Оценки уровня неточности

Приведем необходимые леммы и следствия для нахождения двух оценок уровня неточности (враждебного шума): для ${{l}_{1}}$-рандомизация (4) и для ${{l}_{2}}$-рандомизация (5). Для этого воспользуемся известными результатами и теми же суждениями, что и в [18].

Лемма 5 (см. [4]). Функция ${{f}_{\gamma }}(x)$ дифференцируема со следующим градиентом с ${{l}_{1}}$-рандомизацией:

$\nabla {{f}_{\gamma }}(x) = {{\mathbb{E}}_{e}}\left[ {\frac{d}{\gamma }f(x + \gamma e)\operatorname{sign} (e)} \right].$

Лемма 6 (см. [19]). Функция ${{f}_{\gamma }}(x)$ дифференцируема со следующим градиентом с ${{l}_{2}}$-рандомизацией:

$\nabla {{f}_{\gamma }}(x) = {{\mathbb{E}}_{e}}\left[ {\frac{d}{\gamma }f(x + \gamma e)e} \right].$

Лемма 7 (см. [20]). Пусть вектор $e$ – случайный единичный вектор из евклидовой единичной сферы $\{ e:{{\left\| e \right\|}_{2}} = 1\} $. Тогда для всех $r \in {{\mathbb{R}}^{d}}$ следует

$\mathbb{E}[{\kern 1pt} {\text{|}}\langle e,r\rangle {\text{|}}{\kern 1pt} ] \leqslant \frac{{{{{\left\| r \right\|}}_{2}}}}{{\sqrt d }}.$

Лемма 8. Для $\nabla {{f}_{\gamma }}(x,\xi ,e)$ и $\nabla {{f}_{\gamma }}(x)$ с предположением 2, выполняется следующее:

${{\mathbb{E}}_{{\xi ,e}}}[\langle \nabla {{f}_{\gamma }}(x,\xi ,e),r\rangle ] \geqslant \langle \nabla {{f}_{\gamma }}(x),r\rangle - \frac{{d\Delta {{\mathbb{E}}_{e}}[{\kern 1pt} {\text{|}}{\kern 1pt} \langle {\text{sign}}(e),r\rangle {\kern 1pt} {\text{|}}{\kern 1pt} ]}}{\gamma },$
где $\nabla {{f}_{\gamma }}$ с ${{l}_{1}}$-рандомизацией;
${{\mathbb{E}}_{{\xi ,e}}}[\langle \nabla {{f}_{\gamma }}(x,\xi ,e),r\rangle ] \geqslant \langle \nabla {{f}_{\gamma }}(x),r\rangle - \frac{{d\Delta {{\mathbb{E}}_{e}}[{\kern 1pt} {\text{|}}{\kern 1pt} \langle e,r\rangle {\kern 1pt} {\text{|}}{\kern 1pt} ]}}{\gamma },$
где $\nabla {{f}_{\gamma }}$ с ${{l}_{2}}$-рандомизацией.

Доказательство. Рассмотрим следующие утверждения.

i) для ${{l}_{1}}$-рандомизации (4):

$\begin{gathered} \nabla {{f}_{\gamma }}(x,\xi ,e) = \frac{d}{{2\gamma }}({{f}_{\delta }}(x + \gamma e,\xi ) - {{f}_{\delta }}(x - \gamma e,\xi ))\operatorname{sign} (e) = \\ = \frac{d}{{2\gamma }}(f(x + \gamma e,\xi ) + \delta (x + \gamma e) - f(x - \gamma e,\xi ) - \delta (x - \gamma e))\operatorname{sign} (e) = \\ = \frac{d}{{2\gamma }}((f(x + \gamma e,\xi ) - f(x - \gamma e,\xi ))\operatorname{sign} (e) + (\delta (x + \gamma e) - \delta (x - \gamma e))\operatorname{sign} (e)). \\ \end{gathered} $

Из данного равенства следует

(27)
$\begin{gathered} {{\mathbb{E}}_{{\xi ,e}}}[\langle \nabla {{f}_{\gamma }}(x,\xi ,e),r\rangle ] = \frac{d}{{2\gamma }}{{E}_{{\xi ,e}}}[\langle (f(x + \gamma e,\xi ) - f(x - \gamma e,\xi ))\operatorname{sign} (e),r\rangle ] + \\ \, + \frac{d}{{2\gamma }}{{\mathbb{E}}_{e}}[\langle (\delta (x + \gamma e) - \delta (x - \gamma e))\operatorname{sign} (e),r\rangle ]. \\ \end{gathered} $

Применяя лемму 5 к первому слагаемому (27), получим

(28)
$\begin{gathered} \frac{d}{{2\gamma }}{{\mathbb{E}}_{{\xi ,e}}}[\langle (f(x + \gamma e,\xi ) - f(x - \gamma e,\xi ))\operatorname{sign} (e),r\rangle ] = \\ = \frac{d}{{2\gamma }}{{\mathbb{E}}_{{\xi ,e}}}[\langle f(x + \gamma e,\xi )\operatorname{sign} (e),r\rangle ] + \frac{d}{{2\gamma }}{{\mathbb{E}}_{{\xi ,e}}}[\langle f(x - \gamma e,\xi )\operatorname{sign} (e),r\rangle ] = \\ = \frac{d}{\gamma }{{\mathbb{E}}_{e}}\left[ {\langle {{\mathbb{E}}_{\xi }}\left[ {f(x + \gamma e,\xi )} \right]\operatorname{sign} (e),r\rangle } \right] = \frac{d}{\gamma }{{\mathbb{E}}_{e}}[\langle f(x + \gamma e)\operatorname{sign} (e),r\rangle ] = \langle \nabla {{f}_{\gamma }}(x),r\rangle . \\ \end{gathered} $

Для второго слагаемого (27) с учетом ${\text{|}}\delta (x){\kern 1pt} {\text{|}} \leqslant \Delta $ получим

(29)
$\frac{d}{\gamma }{{\mathbb{E}}_{e}}[\langle (\delta (x + \gamma e) - \delta (x - \gamma e))\operatorname{sign} (e),r\rangle ] \geqslant - \frac{d}{{2\gamma }}2\Delta {{\mathbb{E}}_{e}}[{\kern 1pt} {\text{|}}{\kern 1pt} \langle \operatorname{sign} (e),r\rangle {\kern 1pt} {\text{|}}{\kern 1pt} ] = - \frac{d}{\gamma }\Delta {{\mathbb{E}}_{e}}[{\kern 1pt} {\text{|}}{\kern 1pt} \langle \operatorname{sign} (e),r\rangle {\kern 1pt} {\text{|}}{\kern 1pt} ].$

Используя уравнения (28) и (29) для уравнения (27), получим утверждение леммы для ${{l}_{1}}$-рандомизации.

ii) для ${{l}_{2}}$-рандомизации (5):

$\begin{gathered} \nabla {{f}_{\gamma }}(x,\xi ,e) = \frac{d}{{2\gamma }}({{f}_{\delta }}(x + \gamma e,\xi ) - {{f}_{\delta }}(x - \gamma e,\xi ))e = \\ = \frac{d}{{2\gamma }}(f(x + \gamma e,\xi ) + \delta (x + \gamma e) - f(x - \gamma e,\xi ) - \delta (x - \gamma e))e = \\ = \frac{d}{{2\gamma }}((f(x + \gamma e,\xi ) - f(x - \gamma e,\xi ))e + (\delta (x + \gamma e) - \delta (x - \gamma e))e). \\ \end{gathered} $

Из данного равенства следует

(30)
$\begin{gathered} {{E}_{{\xi ,e}}}[\langle \nabla {{f}_{\gamma }}(x,\xi ,e),r\rangle ] = \frac{d}{{2\gamma }}{{\mathbb{E}}_{{\xi ,e}}}[\langle (f(x + \gamma e,\xi ) - f(x - \gamma e,\xi ))e,r\rangle ] + \\ \, + \frac{d}{{2\gamma }}{{\mathbb{E}}_{e}}[\langle (\delta (x + \gamma e) - \delta (x - \gamma e))e,r\rangle ]. \\ \end{gathered} $

Применяя лемму 6 к первому слагаемому (30), получим

(31)
$\begin{gathered} \frac{d}{{2\gamma }}{{\mathbb{E}}_{{\xi ,e}}}[\langle (f(x + \gamma e,\xi ) - f(x - \gamma e,\xi ))e,r\rangle ] = \\ = \frac{d}{{2\gamma }}{{\mathbb{E}}_{{\xi ,e}}}[\langle f(x + \gamma e,\xi )e,r\rangle ] + \frac{d}{{2\gamma }}{{\mathbb{E}}_{{\xi ,e}}}[\langle f(x - \gamma e,\xi )e,r\rangle ] = \\ = \frac{d}{\gamma }{{\mathbb{E}}_{e}}\left[ {\langle {{\mathbb{E}}_{\xi }}\left[ {f(x + \gamma e,\xi )} \right]e,r\rangle } \right] = \frac{d}{\gamma }{{\mathbb{E}}_{e}}[\langle f(x + \gamma e)e,r\rangle ] = \langle \nabla {{f}_{\gamma }}(x),r\rangle . \\ \end{gathered} $

Для второго слагаемого (30) с учетом ${\text{|}}\delta (x){\text{|}} \leqslant \Delta $ получим

(32)
$\frac{d}{\gamma }{{\mathbb{E}}_{e}}[\langle (\delta (x + \gamma e) - \delta (x - \gamma e))e,r\rangle ] \geqslant - \frac{d}{{2\gamma }}2\Delta {{\mathbb{E}}_{e}}[{\kern 1pt} {\text{|}}{\kern 1pt} \langle e,r\rangle {\kern 1pt} {\text{|}}{\kern 1pt} ] = - \frac{d}{\gamma }\Delta {{\mathbb{E}}_{e}}[{\kern 1pt} {\text{|}}{\kern 1pt} \langle e,r\rangle {\kern 1pt} {\text{|}}{\kern 1pt} ].$

Используя уравнения (31) и (32), для уравнения (30) получим утверждение леммы для ${{l}_{2}}$-рандомизации.

Следствие 5. Заметим, что вектор ${\text{sign}}(e) = \left( {{\text{sign}}({{e}_{1}}),...,{\text{sign}}({{e}_{d}})} \right)$ в ${{l}_{1}}$-норме при большой размерности пространства $d$ ведет себя схожим образом, как вектор из независимых радемахеровских случайных величин. Тогда из неравенства Хинчина следует $E[{\kern 1pt} {\text{|}}{\kern 1pt} \langle \operatorname{sign} (e),r\rangle {\kern 1pt} {\text{|}}{\kern 1pt} ] \leqslant {{\left\| r \right\|}_{2}}$, где $r \in {{\mathbb{R}}^{d}}$. Применяя данное неравенство к лемме 8, получим

${{\mathbb{E}}_{e}}\langle [\nabla {{f}_{\gamma }}(x,e)] - \nabla {{f}_{\gamma }}(x),r\rangle \lesssim \frac{{d\Delta {{{\left\| r \right\|}}_{2}}}}{\gamma }.$

Следствие 6. Применяя утверждение леммы 7 к лемме 8, получим то же неравенство, что и в работе [18] для всех $r \in {{\mathbb{R}}^{d}}$

${{\mathbb{E}}_{e}}\langle {\kern 1pt} [\nabla {{f}_{\gamma }}(x,e)] - \nabla {{f}_{\gamma }}(x),r\rangle \lesssim \frac{{\sqrt d \Delta {{{\left\| r \right\|}}_{2}}}}{\gamma }.$

Теперь рассмотрим, как получить оценки уровня неточности (шума).

Из (13) и (14), подставляя значение параметра $\gamma $ из следствия 1 ($\gamma = \frac{{\sqrt d \varepsilon }}{{4{{M}_{2}}}}$ для ${{l}_{1}}$-рандомизации, $\gamma = \frac{\varepsilon }{{2{{M}_{2}}}}$ для ${{l}_{2}}$-рандомизации) и $R = {{\left\| {{{x}^{0}} - {{x}_{*}}} \right\|}_{2}}$, получим ограничительные условия на уровень неточности (шума) для ${{l}_{1}}$ и ${{l}_{2}}$-рандомизаций:

Схема сглаживания с ${{l}_{1}}$-рандомизацией Схема сглаживания с ${{l}_{2}}$-рандомизацией
$\Delta \lesssim \frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}$ $\Delta \lesssim \frac{{{{\varepsilon }^{2}}}}{{\sqrt d {{M}_{2}}R}}$

Замечание 4. Стоит отметить, что результаты леммы 8 и следствий 5 и 6 для седловых задач такие же и доказываются аналогично. Следовательно, оценки уровня неточности для задачи с седловой точкой совпадают с оценками для выпуклой оптимизации. С целью избежания повторений будем ссылаться на это замечание как на результат получения оценок уровня неточности для седловых задач.

6. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ

Приведем численное сравнение двух техник сглаживания в архитектуре федеративного обучения. Рассматриваем стохастическую негладкую задачу оптимизации на множестве симплекса $Q = \left\{ {x \in {{\mathbb{R}}^{d}}:{{{\left\| x \right\|}}_{1}} = 1,x \geqslant 0} \right\}$ с функцией $f:{{\mathbb{R}}^{d}} \to \mathbb{R}$, определенную следующим образом:

$f(x) = \langle b,x\rangle + {{\left\| x \right\|}_{\infty }},$
где $b \in {{\mathbb{R}}^{d}}$ – случайный вектор, равномерно распределенный на отрезке $[0,1]$. В качестве метода оптимизации используется безградиентный двухточечный алгоритм Minibatch Accelerated SGD, рассмотренный в разд. 4. На фиг. 2 представлена зависимость ошибки $f(\bar {x})$ на последней итерации от изменения количества локальных вызовов безградиентного оракула $K{{ = 3}^{0}}{{,...,3}^{8}}$ при различном количестве машин $B = 8$ и $B = 32$, работающих параллельно, где $\bar {x} = \frac{1}{t}\sum\nolimits_{i = 1}^t \,{{x}_{i}}$, а $t$ – номер итерации. Количество итераций было выбрано $KN{{ = 3}^{8}}$. Чем больше $K$, тем меньше количество коммуникационных раундов $N$, обратное также верно. Уровень неточности $\Delta = 0$ (без враждебного шума), размерность задачи $d = 100$.

Фиг. 2.

Зависимость ошибки от числа машин $B$ и различных локальных обновлений $K$.

Не трудно заметить из фиг. 2, что при увеличении числа локальных обновлений $K$ (уменьшении раундов связи $N$), точность ухудшается (тем самым подтверждая теоретические результаты), однако не критично. То есть при решении практических задач, несмотря на теорию, можно брать число локальных обновлений $K \leqslant {{3}^{6}}$, чтобы получить достаточно хороший результат. Также стоит обратить внимание, что на практике схема сглаживания с ${{l}_{2}}$-рандомизацией не только не уступает схеме сглаживания с ${{l}_{1}}$-рандомизацией, но иногда и превосходит ее. Однако возникает интерес узнать, в каких случаях схема сглаживания с ${{l}_{1}}$-рандомизацией будет превосходить схему сглаживания с ${{l}_{2}}$-рандомизацией. Для этого рассмотрим два случая вычисления безградиентного оракула: с враждебным шумом и без враждебного шума. На фиг. 3 представлена зависимость ошибки $f(\bar {x})$ от количества итераций и уровня неточности (наличия враждебного шума) $\Delta = 0$ и $\Delta = 6 \times {{10}^{{ - 5}}}$. Число работающих параллельно машин выбрано $B = 8$. На каждой машине количество локальных вызовов безградиентного оракула равняется $K{{ = 3}^{2}}$, а количество коммуникационных раундов ${{3}^{6}}$. Таким образом, общее число итераций $NK{{ = 3}^{8}}$. Размерность задачи $d = 100$, количество запусков равняется 20.

Фиг. 3.

Зависимость ошибки от количества итераций при различных значениях уровня неточности при 20 запусках.

По фиг. 3 можно сделать вывод, что при добавления враждебного шума схема сглаживания с ${{l}_{1}}$ рандомизацией работает лучше, чем схема сглаживания с ${{l}_{2}}$-рандомизацией в архитектуре федеративного обучения.

7. ЗАКЛЮЧЕНИЕ

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

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

  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.

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

Инструменты

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

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

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