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

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

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

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

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

EDN: ANULIA
DOI: 10.31857/S2686954323601665

Аннотация

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

1. ВСТУПЛЕНИЕ

1.1. Распределенная оптимизация

Рассматривается задача оптимизации следующего вида:

(1)

$\mathop {\min }\limits_{x \in {{\mathbb{R}}^{d}}} f(x) = \frac{1}{n}\sum\limits_{i = 1}^n {{f}_{i}}(x),$

где $x \in {{\mathbb{R}}^{d}}$ содержит параметры статистической модели для обучения, n – количество устройств/узлов в сети, а f_i – эмпирическая функция потерь на i-м устройстве, т.е. f_i(x) = $\frac{1}{{{{b}_{i}}}}\sum\limits_{j = 1}^{{{b}_{i}}} {l(x,z_{i}^{j})} $, с $z_{i}^{1}, \ldots ,z_{i}^{{{{b}_{i}}}}$ – набором выборок ${{b}_{i}}$, принадлежащих i-му устройству, и $l(x,z_{i}^{j})$ измеряет несоответствие между параметром x и образцом $z_{i}^{j}$. Это формулировка задачи распределенной оптимизации. В настоящее время есть несколько причин сделать такую постановку задачи.

Чтобы достичь наилучших результатов в современных оптимизационных задачах в машинном обучении, исследователи и практики сталкиваются с различными вызовами. Иметь дело с современными моделями машинного обучения остается чрезвычайно сложной задачей, в первую очередь потому, что модели обучаются на все более объемных выборках данных. Наличие обучающей выборки большого объема в наборе данных повышает устойчивость и обобщаемость полученной модели. В этом случае данные обычно обрабатываются с использованием сети устройств, т.е. собираются распределенным образом и хранятся в крайних узлах сети, например, как при классическом кластеризационном [1] и федеративном [2–4] обучении.

Для решения задачи (1) было предложено несколько методов решения. Стандартный подход предполагает чередование локальных вычислений на краевых устройствах (узлах $i = 2, \ldots ,n$) с коммуникациями с сервером (i = 1), который поддерживает и обновляет актуальную копию оптимизационных переменных, в конечном итоге формируя окончательную оценку решения. При распределенном обучении сложных моделей проблемным местом часто становятся коммуникационные расходы между устройствами в сети. Такая проблема обусловливает необходимость разработки более эффективных методов распределенного обучения, некоторые из которых были описаны в [2, 5–7].

1.2. Распределенная оптимизация в условиях схожести данных

Сегодня в машинном обучении модно использовать методы, основанные на идее инерционного моментума. Одним из путей решения распределенной оптимизационной задачи является применение ускорения Нестерова [8], которое представляет собой оптимальный метод для гладких нераспределенных оптимизационных задач. Для распределенных сетей он может быть применен следующим образом. На каждой итерации локально вычисляется градиент и результаты отправляются на сервер. Он, в свою очередь, усредняет полученные градиенты и делает шаг метода. Тогда количество коммуникаций будет равно количеству итераций. В этом случае получаются оптимальные оценки для локальных вычислений – $\sqrt \kappa ,\kappa = L{\text{/}}\mu $, где L и $\mu $ – константы гладкости и сильной выпуклости целевой функции f. В случае, когда $\kappa $ мала, такой подход вполне приемлем. Однако для плохо обусловленных функций с большой $\kappa $ полиномиальная зависимость от $\kappa $ может оказаться неудовлетворительной из-за высокой стоимости коммуникаций. Это часто имеет место для многих задач Минимизации Эмпирического Риска (МЭР), когда оптимальный параметр регуляризации для тестового прогнозирования очень мал.

Для дальнейшего решения пробелемы стоимости коммуникаций можно использовать дополнительную структуру, обычно встречающуюся в задачах МЭР, известную как схожесть данных [9–11]. Ее можно определить как разность градиентов функций, т.е. ${\text{||}}\nabla {{f}_{i}}(x) - \nabla {{f}_{j}}(x){\text{||}} < \delta \forall x$. Но такой подход не является “естественным”, так как если задача не ограниченна, то такая $\delta $ не может существовать. Рассмотрим, например, квадратичную постановку: $\nexists \delta :{\text{||}}({{A}_{i}}\, - \,{{A}_{j}})x{\text{||}}\, < \,\delta $, если $x \to \infty $. Поэтому сфокусируемся на другом подходе, а именно, на подобии Гессианнов. В частности, для всех $x$ из рассматриваемой области и всех $i \ne j; i,j \in $ ∈ {1, ..., n}, разность между матрицами Гессиана локальных потерь, обозначаемая ${\text{||}}{{\nabla }^{2}}{{f}_{i}}(x) - {{\nabla }^{2}}{{f}_{j}}(x){\text{||}}$, ограничена $\delta $, где $\delta > 0$ измеряет степень сходства. При таком предположении можно оценить $\delta \sim \mathcal{O}(1{\text{/}}\sqrt N )$, где $N$ – размер выборки на одно устройство [9]. Впервые такой подход был исследован в [10]. После этого в [9] были доказаны нижние оценки для этой задачи, где затраты на коммуникации пропорциональны $\sqrt {\delta \mu } $. Затем долгое время исследователи пытались найти методы, позволяющие достичь этих оценок. В частности, были получены такие алгоритмы, как [12–16]. В 2022 г. удалось получить оптимальный метод, который описан в [17].

1.3. Различные затраты на коммуникации и локальные вычисления

Во всех вышеперечисленных работах авторы выдвигали предположение о том, что коммуникации обходятся значительно дороже локальных вычислений. Более того, в целом в работах по распределенной оптимизации, не только в области схожести Гессианов, делалось такое предположение. Данный вопрос будет рассмотрен с другой стороны, уходя от фиксированных больших коммуникаций и сделав 2 предположения:

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

2. Отношение коммуникационных затрат к локальному времени вычислений – величина переменная, которая может быть либо $ \ll {\kern 1pt} 1$, либо $ \gg {\kern 1pt} 1$, либо даже $ \sim {\kern 1pt} 1$.

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

Можно ли найти такое распределение данных между устройствами в сети, чтобы сократить реальное время работы оптимального алгоритма [17] при любых коммуникационных затратах и времени локальных вычислений?

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

3. Стоимости связи и мощности устройств задаются как случайные величины, затем на длительное время запускается работа сети и измеряются их математическое ожидание и дисперсия. Поскольку распределение данных по устройствам зависит от постоянных времени связи и мощности устройств, то в реальности оптимальное распределение будет отличаться из-за шума.

Поэтому в связи с этим предположением возникает вопрос об измерении погрешности времени работы программы при оптимальном распределении данных.

1.4. Вклад

В целом наш вклад заключается в следующем:

• Обобщение модели вычислений. Строится общая модель времени вычислений в сетях при распределенной оптимизации. Модель основана на оптимальном алгоритме [17] и учитывает разницу в мощностях устройств при различных затратах на связь.

• Всеобъемлющий анализ. Особое внимание уделяеется частным случаям и полученным в них результатам. Рассматривается случай, когда коммуникации слишком дорогие, а также случай дешевых коммуникаций (не настолько дорогих, чтобы связь занимала больше времени, чем обработка всех данных одним устройством). Более того, результаты получаются не только с учетом разницы во временных затратах, но и при рассмотрении различных оценок $\delta $.

• Различные техники получения решения. Получаются результаты в различных случаях, в том числе для различных оценок $\delta $. Также используются следующие методы: формула Кардано, верхние оценки в предельных случаях и нахождение нуля функции простейшими численными методами.

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

• Эксперименты. На основе проведенных экспериментов было получено подтверждение того, что с выведенным распределением решение выбранной задачи занимает меньшее время. Кроме того, соответствующие эксперименты были дополнены шумом в сети.

2. ПОСТАНОВКА ЗАДАЧИ

На данном этапе остановимся на первых двух предположениях из Секции 1.3. Для достижения меньшей коммуникационной и локально-градиентной сложности обратимся к алгоритму 2 из [17]. Для этого необходимо представить функцию в виде суммы гладкой выпуклой функции f₁ и гладкой потенциально невыпуклой функции $f - {{f}_{1}}$. Тогда алгоритм будет переписан в следующем более общем виде:

Алгоритм 1. Accelerated Extragradient

1: Input: ${{x}^{0}} = x_{f}^{0} \in {{\mathbb{R}}^{d}}$

2: Parameters: $\tau \in (0,1)$, $\eta ,\theta ,\alpha > 0$, $K \in \{ 1,2, \ldots \} $

3: for $k = 0,1,2, \ldots ,K - 1$ do

4: $x_{g}^{k} = \tau {{x}^{k}} + (1 - \tau )x_{f}^{k}$

5: $x_{f}^{{k + 1}} \approx \arg \mathop {\min }\limits_{x \in {{\mathbb{R}}^{d}}} [A_{\theta }^{k}(x): = \langle \nabla (f - {{f}_{1}})(x_{g}^{k}),x - x_{g}^{k}\rangle + \frac{1}{{2\theta }}{\text{||}}x - x_{g}^{k}{\text{|}}{{{\text{|}}}^{2}} + {{f}_{1}}(x)]$

6: ${{x}^{{k + 1}}} = {{x}^{k}} + \eta \alpha (x_{f}^{{k + 1}} - {{x}^{k}}) - \eta \nabla f(x_{f}^{{k + 1}})$

7: end for

8: Output: x^K

Нам необходимо проанализировать работу этого алгоритма, а именно, выяснить, сколько операций выполняет этот алгоритм за итерацию. В строке 5, при решении подзадачи argmin, на устройствах выполняется одно локальное вычисление для вычисления ${{f}_{i}}(x_{g}^{k})$, затем одна коммуникация для передачи этих результатов и дополнительные вычисления на сервере для нахождения решения $x_{f}^{{k + 1}}$. Затем, в строке 6, выполняются одно локальное вычисление и одна коммуникация. Получается выражение для общего времени работы алгоритма. Введем следующие обозначения: ${{\tau }_{i}}$ – время одного локального вычисления на i-м устройстве, $K$ – количество итераций, ${{\tau }_{{comm}}}$ – время одной коммуникации, ${{k}_{{some}}}$ – дополнительные вычисления центрального узла, $n$ – количество узлов в сети. С учетом этого общее время работы алгоритма можно записать в виде:

$\begin{gathered} {{T}_{{sum}}} = 2 \cdot \max ({{\tau }_{1}},{{\tau }_{2}}, \ldots ,{{\tau }_{n}}) \cdot K + \\ \, + 2 \cdot K \cdot {{\tau }_{{comm}}} + {{\tau }_{1}} \cdot {{k}_{{some}}}. \\ \end{gathered} $

Наша задача – минимизировать время ${{T}_{{sum}}}$. С учетом утверждения (1) и вида функций ${{f}_{i}}$ представим время ${{\tau }_{i}}$ в виде ${{\tau }_{i}} = \tau _{i}^{{loc}} \cdot {{b}_{i}}$, где $\tau _{i}^{{loc}}$ – мощность, т.е. время, затрачиваемое i-м устройством на обработку единицы информации, поступающей на его вход, а ${{b}_{i}}$ – размер набора данных, поступающего на i-е устройство. ${{b}_{i}}$ должно удовлетворять следующим ограничениям: $\sum\limits_{i = 1}^n {{{b}_{i}} = N} $, где $N$ – размер всего набора данных, $\delta = \frac{L}{{\sqrt {{{b}_{i}}} }}$ или $\delta = \frac{L}{{{{b}_{i}}}}$ [15].

В итоге была получена следующая задача минимизации:

$\begin{gathered} \mathop {\min }\limits_{\sum\limits_{i = 1}^n {{b}_{i}} = N;\delta = \frac{L}{{b_{1}^{\gamma }}}} \text{[}2\, \cdot \,\max (\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}},\tau _{2}^{{loc}}\, \cdot \,{{b}_{2}}, \ldots ,\tau _{n}^{{loc}}\, \cdot \,{{b}_{n}})\, \cdot \,K\, + \\ \, + 2 \cdot K \cdot {{\tau }_{{comm}}} + {{\tau }_{1}} \cdot {{k}_{{some}}}],\quad \gamma \in \left\{ {\frac{1}{2},1} \right\}. \\ \end{gathered} $ (2)

3. КАК РЕШИТЬ (2)

3.1. Первичная задача минимизации

В [17] представлены оценки K и k_some, а именно: 2 · K = $\mathcal{O}\left( {\max \left\{ {1,\sqrt {\frac{\delta }{\mu }} } \right\}\log \left( {\frac{1}{\varepsilon }} \right)} \right)$, k_some = = $\mathcal{O}\left( {\max \left\{ {1,\sqrt {\frac{L}{\delta }} ,\sqrt {\frac{\delta }{\mu }} ,\sqrt {\frac{L}{\mu }} } \right\}\log \left( {\frac{1}{\varepsilon }} \right)} \right)$.

В таком случае (2) принимает вид:

(3)

$\begin{gathered} \mathop {\min }\limits_{\sum\limits_{i = 1}^n {{b}_{i}} = N;\delta = \frac{L}{{b_{1}^{\gamma }}}} \left[ {\mathop {(\max (\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}},\tau _{2}^{{loc}}\, \cdot \,{{b}_{2}}, \ldots ,\tau _{n}^{{loc}}\, \cdot \,{{b}_{n}})}\limits_{_{{_{{}}}}} } \right.\, + \,{{\tau }_{{comm}}})\, \times \\ \times \,\mathcal{O}\left( {\max \left\{ {1,\sqrt {\frac{\delta }{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right\}} \right) + \\ + \, \tau _{1}^{{loc}}\, \cdot \,{{b}_{1}}\, \cdot \,\mathcal{O}{\kern 1pt} \left. {\left( {\max \left[ {1,\sqrt {\frac{L}{\delta }} ,\sqrt {\frac{\delta }{\mu }} ,\sqrt {\frac{L}{\mu }} } \right]{\text{log}}\left( {\frac{1}{\varepsilon }} \right)} \right)} \right], \\ \gamma \, \in \,\left\{ {\frac{1}{2},1} \right\}. \\ \end{gathered} $

3.2. Вспомогательная задача

Рассматриваем следующую вспомогательную задачу:

(4)

$\mathop {\min }\limits_{\sum\limits_{i = 2}^n {{b}_{i}} = N} [\max (\tau _{2}^{{loc}} \cdot {{b}_{2}},\tau _{3}^{{loc}} \cdot {{b}_{3}}, \ldots ,\tau _{n}^{{loc}} \cdot {{b}_{n}})].$

Лемма 1. Решением задачи (4) является $\overleftarrow b \, = \,{{({{b}_{2}},{{b}_{3}}, \ldots ,{{b}_{n}})}^{T}}$, такой что $\tau _{2}^{{loc}} \cdot {{b}_{2}}\, = \,\tau _{3}^{{loc}} \cdot {{b}_{3}}$ = ... = = $\tau _{n}^{{loc}} \cdot {{b}_{n}}$.

Доказательство. Не умаляя общности, примем фиксированные значения $\tau _{2}^{{loc}}\, \leqslant \,\tau _{3}^{{loc}}\, \leqslant \, \ldots \, \leqslant \,\tau _{n}^{{loc}}$. Затем произвольно выберем ${{b}_{2}} \geqslant {{b}_{3}} \geqslant \ldots \geqslant {{b}_{n}}$. Это действительно так, иначе имела бы место ситуация, когда $\exists i \ne j{\text{:}}$ $i,j \in \{ 2, \ldots ,n\} {\text{:}}$ $\max (\tau _{i}^{{loc}} \cdot {{b}_{i}},\tau _{j}^{{loc}}$ · b_j) > > $\max (\tau _{i}^{{loc}} \cdot {{b}_{j}},\tau _{j}^{{loc}} \cdot {{b}_{i}})$, и, следовательно, распределение было бы неоптимальным.

Главная цель – минимизировать функцию $g(\overleftarrow b )$ = = $\max (\tau _{2}^{{loc}}\, \cdot \,{{b}_{2}},\tau _{3}^{{loc}}\, \cdot \,{{b}_{3}}, \ldots ,\tau _{n}^{{loc}}\, \cdot \,{{b}_{n}})$. Предположим, что существует такое распределение, что $\exists i\, \in \,\{ 2, \ldots ,n\} $ : $g({{\overleftarrow b }^{0}})$ = $\tau _{i}^{{loc}} \cdot b_{i}^{0}$ является минимумом, и $\forall j\,:\,j\, \geqslant \,2$, $j\, \ne \,i$ ↪ $\tau _{i}^{{loc}} \cdot b_{i}^{0} > \tau _{j}^{{loc}} \cdot b_{j}^{0}$. Из этого следует, что $b_{i}^{0} > \frac{{\tau _{j}^{{loc}}}}{{\tau _{i}^{{loc}}}}b_{j}^{0} > \frac{{\tau _{{{{j}_{1}}}}^{{loc}}}}{{\tau _{i}^{{loc}}}}b_{{{{j}_{1}}}}^{0} > \ldots > \frac{{\tau _{{{{j}_{k}}}}^{{loc}}}}{{\tau _{i}^{{loc}}}}b_{{{{j}_{k}}}}^{0}$.

Далее, учитывая $\sum\limits_{i = 2}^n {{{b}_{i}} = N} $ ↪ $b_{i}^{0} + \frac{{\tau _{j}^{{loc}}}}{{\tau _{i}^{{loc}}}}b_{j}^{0}$ + + $\frac{{\tau _{{{{j}_{1}}}}^{{loc}}}}{{\tau _{i}^{{loc}}}}b_{{{{j}_{1}}}}^{0}\, + \, \ldots \, + \,\frac{{\tau _{{{{j}_{k}}}}^{{loc}}}}{{\tau _{i}^{{loc}}}}b_{{{{j}_{k}}}}^{0}$ > N, получаем $b_{i}^{0}$ > > . Затем рассмотрим b_i = = , ${{b}_{j}} = \frac{{\tau _{i}^{{loc}}}}{{\tau _{j}^{{loc}}}} \cdot {{b}_{i}}$ $\forall j \in \{ 2, \ldots ,n\} $. Такое распределение дает минимум $g(\overleftarrow b )$ = $\tau _{i}^{{loc}} \cdot {{b}_{i}}$ = = $\tau _{j}^{{loc}} \cdot {{b}_{j}}$ $\forall j \in \{ 2, \ldots ,n\} $, и $g(\overleftarrow b ) < g({{\overleftarrow b }^{0}})$. Это противоречит предположению о минимальности. Таким образом, для распределения, минимизирующего функцию $g(\overleftarrow b )\, = \,\max (\tau _{2}^{{loc}}\, \cdot \,{{b}_{2}},\tau _{3}^{{loc}}\, \cdot \,{{b}_{3}}, \ldots ,\tau _{n}^{{loc}}\, \cdot \,{{b}_{n}})$, справедливо $\tau _{2}^{{loc}} \cdot {{b}_{2}} = \tau _{3}^{{loc}} \cdot {{b}_{3}} = \ldots = \tau _{n}^{{loc}} \cdot {{b}_{n}}$.

Вернемся к задаче (3). Помимо минимального выражения, уже изученного в (4), в задаче (3) имеются дополнительные члены. δ в (3) зависит от величины b₁, но не зависит от ${{b}_{i}},i = \overline {2,n} $. Отсюда и из леммы 1 следует, что в исходной задаче (3) обмен данными между 2-м, 3-м и последующими устройствами должен быть пропорциональным. Таким образом, задача (3) сводится к новой задаче с дополнительными ограничениями:

(5)

$\begin{gathered} \mathop {\min }\limits_{\substack{ \sum\limits_{i = 1}^n {{b}_{i}} = N;\delta = \frac{L}{{b_{1}^{\gamma }}}; \\ \tau _{2}^{{loc}} \cdot {{b}_{2}} = \ldots = \tau _{n}^{{loc}} \cdot {{b}_{n}} } } \left[ {(\max (\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}},\tau _{2}^{{loc}}\, \cdot \,{{b}_{2}}, \ldots ,\tau _{n}^{{loc}}\, \cdot \,{{b}_{n}}){{ + }_{{_{{_{{_{{_{{_{{_{{_{{_{{_{{}}}}}}}}}}}}}}}}}}}}}} \right. \\ + \,{{\tau }_{{comm}}}) \cdot \mathcal{O}\left( {\max \left\{ {1,\sqrt {\frac{\delta }{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right\}} \right) + \\ \, + \tau _{1}^{{loc}} \cdot {{b}_{1}} \cdot \left. {\mathcal{O}\left( {\max \left\{ {1,\sqrt {\frac{L}{\delta }} ,\sqrt {\frac{\delta }{\mu }} ,\sqrt {\frac{L}{\mu }} } \right\}\log \left( {\frac{1}{\varepsilon }} \right)} \right)} \right], \\ \gamma \in \left\{ {\frac{1}{2},1} \right\}. \\ \end{gathered} $

3.3. Определим окончательную задачу минимизации

Из леммы 1 следует, что ${{b}_{i}} \cdot \tau _{i}^{{loc}} = {\text{const}}$ $\forall i\, \in \,\overline {2,n} $. Таким образом,

$\begin{gathered} N - {{b}_{1}} = \sum\limits_{i = 2}^n {{b}_{i}} = \sum\limits_{i = 2}^n \frac{{\tau _{2}^{{loc}} \cdot {{b}_{2}}}}{{\tau _{i}^{{loc}}}} = \\ \, = \tau _{2}^{{loc}} \cdot {{b}_{2}} \cdot \sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}} \Rightarrow {{b}_{2}} = \frac{{N - {{b}_{1}}}}{{\tau _{2}^{{loc}}}}{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}}. \\ \end{gathered} $

Как уже говорилось ранее, рассматривается случай $\delta = \frac{L}{{{{b}_{1}}}}$ и case of $\delta = \frac{L}{{\sqrt {{{b}_{1}}} }}$.

3.3.1. Случай $\delta = \frac{L}{{{{b}_{1}}}}$. Здесь выполняются следующие соотношения:

$\gamma = 1, \quad \mu \leqslant \delta \leqslant L \Rightarrow \left( {\begin{array}{*{20}{c}} {2 \cdot K = \mathcal{O}\left( {\sqrt {\frac{L}{{\mu {{b}_{1}}}}} \log \left( {\frac{1}{\varepsilon }} \right)} \right)} \\ {{{k}_{{some}}} = \mathcal{O}\left( {\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right)} \end{array}} \right.{\kern 1pt} .$

Подставив эти оценки в (5), задача примет следующий вид:

$\begin{gathered} \mathop {\min }\limits_{\sum\limits_{i = 1}^n {{b}_{i}} = N} \left[ {\mathop {(\max \{ \tau _{1}^{{loc}} \cdot {{b}_{1}},\tau _{2}^{{loc}} \cdot {{b}_{2}}\} }\limits_{_{{_{{_{{}}}}}}} } \right. + {{\tau }_{{comm}}}) \\ \left. {\, \times \,\mathcal{O}\left( {\sqrt {\frac{L}{{\mu {{b}_{1}}}}} \log \left( {\frac{1}{\varepsilon }} \right)} \right) + \tau _{1}^{{loc}} \cdot {{b}_{1}} \cdot \mathcal{O}\left( {\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right)} \right]. \\ \end{gathered} $

В результате, оставив в функции единственную переменную b₁, осуществляется переход к окончательному виду задачи минимизации:

(6)

$\begin{gathered} \mathop {\min }\limits_{0 < {{b}_{1}} \leqslant N} \left[ {\left( {\max \left\{ {\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}}; (N\, - \,{{b}_{1}})\, \cdot \,{{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}} \right\}\, + \,{{\tau }_{{comm}}}} \right)} \right. \times \\ \times \,\mathcal{O}\left( {\sqrt {\frac{L}{{\mu {{b}_{1}}}}} \log \left( {\frac{1}{\varepsilon }} \right)} \right) + \tau _{1}^{{loc}} \cdot {{b}_{1}} \cdot \left. {\mathcal{O}\left( {\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right)} \right]. \\ \end{gathered} $

Исследуем эту задачу далее. Для этого найдем точку, в которой выражения под максимумом совпадают.

$\begin{gathered} b_{1}^{0} \cdot \left( {\tau _{1}^{{loc}} + {{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}} \right) = N{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} \Rightarrow \\ \, \Rightarrow b_{1}^{0} = \frac{{N{{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}}{{\tau _{1}^{{loc}} + {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}}. \\ \end{gathered} $

Таким образом, получились два полуинтервала, на каждом из которых можно сформулировать свою задачу минимизации:

$\left( {\begin{array}{*{20}{l}} \begin{gathered} (a) 0\, < \,{{b}_{1}}\, \leqslant \,b_{1}^{0}\, \Rightarrow \,\max \left\{ {\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}}; (N\, - \,{{b}_{1}}) \cdot {{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}} \right\}\, = \hfill \\ = (N - {{b}_{1}}) \cdot {{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} \hfill \\ \end{gathered} \\ \begin{gathered} (b) b_{1}^{0} < {{b}_{1}} \leqslant N \Rightarrow \hfill \\ \Rightarrow \max \left\{ {\tau _{1}^{{loc}} \cdot {{b}_{1}}; (N - {{b}_{1}}) \cdot {{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}} \right\} = \tau _{1}^{{loc}} \cdot {{b}_{1}} \hfill \\ \end{gathered} \end{array}} \right.{\kern 1pt} .$

Строим функции одной переменной ${{\mathcal{F}}_{1}}({{b}_{1}})$, ${{\mathcal{F}}_{2}}({{b}_{1}})$ на соответствующих полуинтервалах, которые необходимо минимизировать в соответствии с задачей (6).

$\left( {\begin{array}{*{20}{l}} \begin{gathered} (a)\,:\,{{\mathcal{F}}_{1}}({{b}_{1}})\, = \,\left[ {N{{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}\, + \,{{\tau }_{{comm}}}} \right] \cdot {{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)b_{1}^{{ - \frac{1}{2}}} - \hfill \\ - \,\,{{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}}b_{1}^{{\frac{1}{2}}} + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{b}_{1}} \hfill \\ \end{gathered} \\ \begin{gathered} (b)\,:\,{{\mathcal{F}}_{2}}({{b}_{1}})\, = \,{{\tau }_{{comm}}}\, \cdot \,{{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)b_{1}^{{ - \frac{1}{2}}}\, + \hfill \\ + \,{{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)\tau _{1}^{{loc}}b_{1}^{{\frac{1}{2}}}\, + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{b}_{1}} \hfill \\ \end{gathered} \end{array}} \right.{\kern 1pt} .$

Кроме того, сразу же найдем их производные для дальнейшего анализа.

$\left( \begin{gathered} (a): \;\mathcal{F}_{1}^{'}({{b}_{1}}) = - \frac{1}{2}{{c}_{1}}b_{1}^{{ - \frac{3}{2}}}\left[ {N{{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}} + {{\tau }_{{comm}}}} \right] \times \hfill \\ \times \,\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) - \frac{1}{2}{{c}_{1}}b_{1}^{{ - \frac{1}{2}}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} + \hfill \\ \, + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) \hfill \\ (b):\; \mathcal{F}_{2}^{'}({{b}_{1}}) = - \frac{1}{2}{{c}_{1}}b_{1}^{{ - \frac{3}{2}}}{{\tau }_{{comm}}} \cdot \sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) + \hfill \\ + \frac{1}{2}{{c}_{1}}b_{1}^{{ - \frac{1}{2}}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)_{1}^{{loc}} + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) \hfill \\ \end{gathered} \right.{\kern 1pt} .$

3.3.2. Случай $\delta = \frac{L}{{\sqrt {{{b}_{1}}} }}$. Здесь будем действовать аналогично предыдущему пункту. Сначала представим необходимые в данном случае соотношения.

$\begin{gathered} \gamma = \frac{1}{2}, \\ \mu \leqslant \delta \leqslant L \Rightarrow \left\{ \begin{gathered} 2 \cdot K = \mathcal{O}\left( {\sqrt {\frac{L}{{\mu \sqrt {{{b}_{1}}} }}} \log \left( {\frac{1}{\varepsilon }} \right)} \right) \hfill \\ {{k}_{{some}}} = \mathcal{O}\left( {\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right) \hfill \\ \end{gathered} \right.. \\ \end{gathered} $

Подставляя эти соотношения в (5), получаем:

$\begin{gathered} \mathop {\min }\limits_{\sum\limits_{i = 1}^n {{b}_{i}} = N} \left[ {(\max \{ \tau _{1}^{{loc}} \cdot {{b}_{1}},\tau _{2}^{{loc}} \cdot {{b}_{2}}\} + {{\tau }_{{comm}}}){{ \times }_{{_{{_{{_{{_{{_{{_{{_{{_{{_{{}}}}}}}}}}}}}}}}}}}}}} \right. \\ \left. { \times \,\mathcal{O}\left( {\sqrt {\frac{L}{{\mu \sqrt {{{b}_{1}}} }}} \log \left( {\frac{1}{\varepsilon }} \right)} \right) + \tau _{1}^{{loc}} \cdot {{b}_{1}} \cdot \mathcal{O}\left( {\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right)} \right]. \\ \end{gathered} $

Снова избавившись от всех переменных, кроме b₁, запишем окончательную задачу минимизации в этом случае:

(7)

$\begin{gathered} \mathop {\min }\limits_{0 < {{b}_{1}} \leqslant N} \left[ {\left( {{\text{max}}\left\{ {\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}}; (N\, - \,{{b}_{1}})\, \cdot \,{{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}} \right\}\, + \,{{\tau }_{{comm}}}} \right)} \right. \times \\ \left. {\, \times \mathcal{O}\left( {\sqrt {\frac{L}{{\mu \sqrt {{{b}_{1}}} }}} \log \left( {\frac{1}{\varepsilon }} \right)} \right) + \tau _{1}^{{loc}} \cdot {{b}_{1}} \cdot \mathcal{O}\left( {\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \right)} \right]. \\ \end{gathered} $

Аналогично выбираем точку $b_{1}^{0}$, она оказывается такой же, как и в предыдущем пункте. После этого можно получить два полуинтервала, на каждом из которых можно сформулировать свою задачу минимизации:

$\left( {\begin{array}{*{20}{l}} \begin{gathered} (a)\;0\, < \,{{b}_{1}}\, \leqslant \,b_{1}^{0}\, \Rightarrow \,\max \left\{ {\tau _{1}^{{loc}} \cdot {{b}_{1}}; (N\, - \,{{b}_{1}}) \cdot {{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}} \right\}\, = \hfill \\ = (N - {{b}_{1}}) \cdot {{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} \hfill \\ \end{gathered} \\ \begin{gathered} (b)\;b_{1}^{0}\, < \,{{b}_{1}}\, \leqslant \,N\, \Rightarrow \hfill \\ \Rightarrow \,{\text{max}}\left\{ {\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}}; (N\, - \,{{b}_{1}})\, \cdot \,{{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}} \right\}\, = \,\tau _{1}^{{loc}}\, \cdot \,{{b}_{1}} \hfill \\ \end{gathered} \end{array}} \right.{\kern 1pt} .$

Мы строим функции одной переменной ${{\mathcal{F}}_{1}}({{b}_{1}})$, ${{\mathcal{F}}_{2}}({{b}_{1}})$ на соответствующих полуинтервалах, которые необходимо минимизировать в соответствии с задачей (7).

$\left( {\begin{array}{*{20}{l}} \begin{gathered} (a){\kern 1pt} :\;{{\mathcal{F}}_{1}}({{b}_{1}})\, = \,\left[ {N{{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}\, + \,{{\tau }_{{comm}}}} \right]\, \cdot \,{{c}_{1}}\sqrt {\frac{L}{\mu }} {\text{log}}\left( {\frac{1}{\varepsilon }} \right)b_{1}^{{ - \frac{1}{4}}}\, - \hfill \\ - \,{{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}}b_{1}^{{\frac{3}{4}}} + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{b}_{1}} \hfill \\ \end{gathered} \\ \begin{gathered} (b){\kern 1pt} :\;{{\mathcal{F}}_{2}}({{b}_{1}}) = {{\tau }_{{comm}}} \cdot {{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)b_{1}^{{ - \frac{1}{4}}} + \hfill \\ + \,{{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)\tau _{1}^{{loc}}b_{1}^{{\frac{3}{4}}} + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{b}_{1}} \hfill \\ \end{gathered} \end{array}} \right.{\kern 1pt} .$

Кроме того, сразу же найдем их производные для дальнейшего анализа.

$\left( {\begin{array}{*{20}{l}} \begin{gathered} (a){\kern 1pt} :\;\mathcal{F}_{1}^{'}({{b}_{1}})\, = \hfill \\ = \, - {\kern 1pt} \frac{1}{4}{{c}_{1}}b_{1}^{{ - \frac{5}{4}}}\left[ {N{{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}}\, + \,{{\tau }_{{comm}}}} \right]\, \cdot \,\sqrt {\frac{L}{\mu }} {\text{log}}\left( {\frac{1}{\varepsilon }} \right)\, - \hfill \\ - \,\frac{3}{4}{{c}_{1}}b_{1}^{{ - \frac{1}{4}}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) \hfill \\ \end{gathered} \\ \begin{gathered} (b){\kern 1pt} :\;\mathcal{F}_{2}^{'}({{b}_{1}})\, = \, - \frac{1}{4}{{c}_{1}}b_{1}^{{ - \frac{5}{4}}}{{\tau }_{{comm}}} \cdot \sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) + \hfill \\ + \frac{3}{4}{{c}_{1}}b_{1}^{{ - \frac{1}{4}}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)\tau _{1}^{{loc}} + \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) \hfill \\ \end{gathered} \end{array}} \right.{\kern 1pt} .$

3.4. Финальное решение

3.4.1. Случай $\delta = \frac{L}{{{{b}_{1}}}}$. Наша цель – найти минимум уже полученных функций ${{\mathcal{F}}_{1}}({{b}_{1}}),\;{{\mathcal{F}}_{2}}({{b}_{1}})$. Для этого будем искать нули $\mathcal{F}_{1}^{'}({{b}_{1}}),\;\mathcal{F}_{2}^{'}({{b}_{1}})$. Здесь получаем кубическое уравнение. Для его решения можно воспользоваться формулой Кардано.

Рассмотрим уравнение $a{{x}^{{ - \frac{1}{2}}}} + b{{x}^{{ - \frac{3}{2}}}} + c = 0$, где в случае $(a){\kern 1pt} :\;0 < {{b}_{1}} \leqslant b_{1}^{0}$ и $(b){\kern 1pt} :\;b_{1}^{0} < {{b}_{1}} \leqslant N$ получаем:

$\left( {\begin{array}{*{20}{l}} \begin{gathered} (a){\kern 1pt} :\;a = \frac{1}{2}{{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right){{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}};\quad b = - \frac{1}{2}{{c}_{1}}\left[ {N\sum\limits_{i = 2}^n {{{\frac{1}{{\tau _{i}^{{loc}}}}}}^{{ - 1}}} + {{\tau }_{{comm}}}} \right] \cdot \sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right); \hfill \\ c = \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right) \hfill \\ \end{gathered} \\ {(b){\kern 1pt} :\;a = \frac{1}{2}{{c}_{1}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)\tau _{1}^{{loc}};\quad b = - \frac{1}{2}{{c}_{1}}{{\tau }_{{comm}}} \cdot \sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right);\quad c = \tau _{1}^{{loc}} \cdot {{c}_{2}}\sqrt {\frac{L}{\mu }} \log \left( {\frac{1}{\varepsilon }} \right)} \end{array}} \right.{\kern 1pt} .$

Тогда при условии, что

$\begin{gathered} N \geqslant \frac{{{{a}^{2}}}}{{3{{c}^{2}}}} + \frac{{\sqrt[3]{{2{{a}^{6}} + 3\sqrt 3 \sqrt {4{{a}^{3}}{{b}^{3}}{{c}^{6}} + 27{{b}^{4}}{{c}^{8}}} + 18{{a}^{3}}b{{c}^{2}} + 27{{b}^{2}}{{c}^{4}}}}}}{{3\sqrt[3]{2}{{c}^{2}}}} - \\ \, - \frac{{\sqrt[3]{2}( - {{a}^{4}} - 6ab{{c}^{2}})}}{{3{{c}^{2}}\sqrt[3]{{2{{a}^{6}} + 3\sqrt 3 \sqrt {4{{a}^{3}}{{b}^{3}}{{c}^{6}} + 27{{b}^{4}}{{c}^{8}}} + 18{{a}^{3}}b{{c}^{2}} + 27{{b}^{2}}{{c}^{4}}}}}}, \\ \end{gathered} $

получаем решение:

$\begin{gathered} x = \frac{{{{a}^{2}}}}{{3{{c}^{2}}}} + \frac{{\sqrt[3]{{2{{a}^{6}} + 3\sqrt 3 \sqrt {4{{a}^{3}}{{b}^{3}}{{c}^{6}} + 27{{b}^{4}}{{c}^{8}}} + 18{{a}^{3}}b{{c}^{2}} + 27{{b}^{2}}{{c}^{4}}}}}}{{3\sqrt[3]{2}{{c}^{2}}}} - \\ \, - \frac{{\sqrt[3]{2}( - {{a}^{4}} - 6ab{{c}^{2}})}}{{3{{c}^{2}}\sqrt[3]{{2{{a}^{6}} + 3\sqrt 3 \sqrt {4{{a}^{3}}{{b}^{3}}{{c}^{6}} + 27{{b}^{4}}{{c}^{8}}} + 18{{a}^{3}}b{{c}^{2}} + 27{{b}^{2}}{{c}^{4}}}}}}. \\ \end{gathered} $

Отсюда тривиально следует искомое решение. Поскольку на каждом из полуинтервалов получили одно значение b₁, которое является минимумом функции на нем, то, выбрав из них то, на котором функция меньше, получим оптимальное значение b₁.

3.4.2. Случай $ \delta = \frac{L}{{\sqrt {{{b}_{1}}} }}$. Поступить аналогично предыдущему параграфу не получается, так как выписать решение этих уравнений в аналитическом виде не представляется возможным из-за их степеней. Поэтому рассмотрим следующие предельные реализации:

1. $\forall i$ ↪ ${{\tau }_{{comm}}} \ll \tau _{i}^{{loc}}$;

2. $\forall i$ ↪ ${{\tau }_{{comm}}} \gg \tau _{i}^{{loc}}$, $\forall i \ne j$ ↪ $\tau _{i}^{{loc}} = \tau _{j}^{{loc}}$.

Для упрощения записи введем обозначения: $\alpha = {{c}_{1}} \cdot \sqrt {\frac{L}{\mu }} \cdot \log \left( {\frac{1}{\varepsilon }} \right)$, $\beta = {{c}_{2}} \cdot \sqrt {\frac{L}{\mu }} \cdot \log \left( {\frac{1}{\varepsilon }} \right)$. Теперь все готово к рассмотрению двух случаев по отдель-ности.

Реализация 1:

(a) $0 < {{b}_{1}} \leqslant b_{1}^{0}$ и ${{\mathcal{F}}_{1}}({{b}_{1}})$ = = $\left[ {N{{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}\, + \,{{\tau }_{{comm}}}} \right] \cdot \alpha b_{1}^{{ - \frac{1}{4}}}$ – $\alpha {{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}^{{ - 1}}}b_{1}^{{\frac{3}{4}}}$ + + $\tau _{1}^{{loc}} \cdot \beta {{b}_{1}}$. Предположим, что $\tau _{1}^{{loc}} \leqslant \tau _{2}^{{loc}} \leqslant \ldots \leqslant \tau _{n}^{{loc}}.$ Используя данное предположение, а так же что ${{\tau }_{{comm}}} \ll \tau _{i}^{{loc}}$, можно получить следующие оценки:

(8)

$\begin{gathered} {{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} = \frac{1}{{\frac{1}{{\tau _{1}^{{loc}}}} + \ldots + \frac{1}{{\tau _{n}^{{loc}}}}}} = \\ \, = \frac{{\tau _{2}^{{loc}} \cdot \ldots \cdot \tau _{n}^{{loc}}}}{{\tau _{3}^{{loc}} \cdot \ldots \cdot \tau _{n}^{{loc}} + \tau _{2}^{{loc}} \cdot \tau _{4}^{{loc}} \cdot \ldots \cdot \tau _{n}^{{loc}} + \ldots + \tau _{2}^{{loc}} \cdot \ldots \cdot \tau _{{n - 1}}^{{loc}}}} \geqslant \frac{{\tau _{2}^{{loc}}}}{{n - 1}} \gg {{\tau }_{{comm}}}. \\ \end{gathered} $

Получим оценку (8), функции ${{\mathcal{F}}_{1}}({{b}_{1}})$ и соответственно $\mathcal{F}_{1}^{'}({{b}_{1}}){\kern 1pt} '$ можно приблизительно упростить следующим образом:

${{\mathcal{F}}_{1}}({{b}_{1}}) = \alpha {{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} \cdot b_{1}^{{ - \frac{1}{4}}}(N - {{b}_{1}}) + \tau _{1}^{{loc}}\beta \cdot {{b}_{1}},$

$\mathcal{F}_{1}^{'}({{b}_{1}}) = \alpha {{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}^{{ - 1}}} \cdot \left( { - \frac{1}{4}b_{1}^{{ - \frac{5}{4}}}N - \frac{3}{4}b_{1}^{{ - \frac{1}{4}}}} \right) + \tau _{1}^{{loc}}\beta .$

Получаем уравнение в тех же степенях, и поэтому снова не можем выписать аналитическое решение, однако для этой задачи проще найти численное решение.

(b) $b_{1}^{0} \leqslant {{b}_{1}} \leqslant N$ and ${{\mathcal{F}}_{2}}({{b}_{1}}) = {{\tau }_{{comm}}} \cdot \alpha b_{1}^{{ - \frac{1}{4}}}$ + $\alpha \tau _{1}^{{loc}}b_{1}^{{\frac{3}{4}}} + \tau _{1}^{{loc}} \cdot \beta {{b}_{1}}$ = $\alpha \cdot b_{1}^{{ - \frac{1}{4}}}({{\tau }_{{comm}}} + \tau _{1}^{{loc}}{{b}_{1}}) + \beta \cdot \tau _{1}^{{loc}} \cdot {{b}_{1}}$. С предположением $\tau _{1}^{{loc}} \leqslant \tau _{2}^{{loc}} \leqslant \ldots \leqslant \tau _{n}^{{loc}}$, мы получаем

(9)

$\begin{gathered} \tau _{1}^{{loc}}{{b}_{1}} \geqslant \frac{{\tau _{1}^{{loc}}N\frac{{\tau _{2}^{{loc}}}}{{n - 1}}}}{{\tau _{1}^{{loc}} + \frac{{\tau _{n}^{{loc}}}}{{n - 1}}}} \geqslant \frac{{\tau _{1}^{{loc}}\tau _{2}^{{loc}}N}}{{(n - 1)(\tau _{1}^{{loc}} + \tau _{n}^{{loc}})}} \geqslant \\ \, \geqslant \frac{{\tau _{1}^{{loc}}\tau _{2}^{{loc}}N}}{{2(n - 1)\tau _{n}^{{loc}}}} \gg {{\tau }_{{comm}}}\frac{N}{{2(n - 1)}} \gg {{\tau }_{{comm}}}. \\ \end{gathered} $

Здесь, используя (9), можно также упростить ${{F}_{2}}({{b}_{1}})$ и затем $\mathcal{F}_{2}^{'}({{b}_{1}})$:

$\begin{gathered} {{\mathcal{F}}_{2}}({{b}_{1}}) = \alpha \cdot \tau _{1}^{{loc}} \cdot b_{1}^{{\frac{3}{4}}} + \beta \tau _{1}^{{loc}} \cdot {{b}_{1}}, \\ \mathcal{F}_{2}^{'}({{b}_{1}}) = \frac{3}{4}\alpha \cdot \tau _{1}^{{loc \cdot }}b_{1}^{{ - \frac{1}{4}}} + \beta \cdot \tau _{1}^{{loc}} > 0. \\ \end{gathered} $

Так как производная функции положительна, то функция возрастает, а значит, минимум будет находиться в точке ${{b}_{1}} = b_{1}^{0} = \frac{{N{{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}}{{\tau _{1}^{{loc}} + {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}}.$ Таким образом, в случае малых ${{\tau }_{{comm}}}$ получаем следующий результат: ${{b}_{{{{1}_{{\min }}}}}} \leqslant b_{1}^{0} = \frac{{N{{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}}{{\tau _{1}^{{loc}} + {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}}$.

Реализация 2:

Здесь тоже можно определить: $\tau : = \tau _{i}^{{loc}} $ $\forall i \in 1$, ..., n. Затем мы можем переписать целевую функцию из (6) следующим способом:

$\mathcal{F}({{b}_{1}}) = \left( {\max \left\{ {\tau {{b}_{1}};(N - {{b}_{1}})\frac{\tau }{{n - 1}}} \right\} + {{\tau }_{{comm}}}} \right) \cdot \frac{\alpha }{{\sqrt[4]{{{{b}_{1}}}}}} + \tau \beta {{b}_{1}}.$

Рассмотрим случай ${{\tau }_{{comm}}} = {{N}^{2}}\tau $. Можно также считать, что размер данных N большой, следовательно ${{\tau }_{{comm}}} \gg N\tau $. И тогда:

$\begin{gathered} \max \left\{ {\tau {{b}_{1}};(N - {{b}_{1}})\frac{\tau }{{n - 1}}} \right\} < \tau N \ll {{\tau }_{{comm}}} \Rightarrow \\ \, \Rightarrow \mathcal{F} \approx \frac{{\alpha {{\tau }_{{comm}}}}}{{\sqrt[4]{{{{b}_{1}}}}}} + \beta \tau {{b}_{1}} \\ \end{gathered} $

$\begin{gathered} \mathcal{F}{\kern 1pt} '({{b}_{1}}) = - \frac{{\alpha {{\tau }_{{comm}}}}}{{4{{b}_{1}}\sqrt[4]{{{{b}_{1}}}}}} + \beta \tau = 0 \Rightarrow \\ \, \Rightarrow b_{{{{1}_{{\min }}}}}^{{\frac{5}{4}}} = \frac{{{{\tau }_{{comm}}}\alpha }}{{4\beta \tau }} \Rightarrow {{b}_{{{{1}_{{\min }}}}}} = {{\left( {\frac{{{{\tau }_{{comm}}}\alpha }}{{4\beta \tau }}} \right)}^{{\frac{4}{5}}}}. \\ \end{gathered} $

Предполагая, что найденное значение b₁ лежит на интервале (0, N), т.е. при $0 < {{\left( {\frac{{{{\tau }_{{comm}}}\alpha }}{{4\beta \tau }}} \right)}^{{\frac{4}{5}}}} < N$, она будет точкой минимума функции $\mathcal{F}$. Тогда:

$\begin{gathered} \mathcal{F}({{b}_{{{{1}_{{\min }}}}}}) = (\alpha {{\tau }_{{comm}}}{{)}^{{\frac{4}{5}}}} \cdot {{(4\beta \tau )}^{{\frac{1}{5}}}} + {{(\beta \tau )}^{{\frac{1}{5}}}} \cdot {{\left( {\frac{{\alpha {{\tau }_{{comm}}}}}{4}} \right)}^{{\frac{4}{5}}}} = \\ \, = {{(\alpha {{\tau }_{{comm}}})}^{{\frac{4}{5}}}} \cdot {{(\beta \tau )}^{{\frac{1}{5}}}}{{(4}^{{\frac{1}{5}}}} + {{4}^{{ - \frac{4}{5}}}}). \\ \end{gathered} $

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

$\forall i$ ↪ ${{\tau }_{{comm}}} = \mathcal{O}({{N}^{k}}\tau _{i}^{{loc}})\quad {\text{with}}\quad k > 1,\quad {\text{and}}$ $\forall i \ne j$ ↪ $\tau _{i}^{{loc}} = \tau _{j}^{{loc}} = \tau ,$

(10)

$\min \mathcal{F}({{b}_{1}}) = \left\{ \begin{gathered} {{(\alpha {{\tau }_{{comm}}})}^{{\frac{4}{5}}}} \cdot {{(\beta \tau )}^{{\frac{1}{5}}}}{{(4}^{{\frac{1}{5}}}} + {{4}^{{ - \frac{4}{5}}}}), \hfill \\ 0 < {{\left( {\frac{{{{\tau }_{{comm}}}\alpha }}{{4\beta \tau }}} \right)}^{{\frac{4}{5}}}} < N \hfill \\ \frac{{\alpha {{\tau }_{{comm}}}}}{N} + \beta \tau N,\quad {{\left( {\frac{{{{\tau }_{{comm}}}\alpha }}{{4\beta \tau }}} \right)}^{{\frac{4}{5}}}} \geqslant N \hfill \\ \end{gathered} \right..$

3.5. Численное решение

Поскольку аналитическое решение найдено не для всех случаев, приведем общее численное решение нашей задачи. Для определения минимума этих функций на соответствующих полуинтервалах будем рассматривать точки, в которых производные $\mathcal{F}_{1}^{'}({{b}_{1}})$ и $\mathcal{F}_{2}^{'}({{b}_{1}})$ приближаются к нулю. Следует отметить, что, учитывая характер этих функций, их производные могут быть равны нулю лишь один раз на нужном полуинтервале. Поэтому, применив метод Ньютона [18] для $\mathcal{F}_{1}^{'}({{b}_{1}})$ и $\mathcal{F}_{2}^{'}({{b}_{1}})$, можно найти их нули. Далее необходимо сравнить значения соответствующей функции в этих точках со значением в крайней точке интервала. Одна из этих точек даст минимальное решение и, тем самым, послужит окончательным решением задачи (6) и (7).

4. ШУМ В СЕТЯХ

Перейдем к третьему предположению из Секции 1.3. Как уже говорилось выше, пусть ${{\tau }_{{comm}}}$ и $\tau _{i}^{{loc}}$ – случайные величины: $\exists \mathbb{E}[{{\tau }_{{comm}}}]$, $\mathbb{E}[\tau _{i}^{{loc}}]$, $\mathbb{D}[{{\tau }_{{comm}}}]\, < \,\infty ,$ $\mathbb{D}[\tau _{i}^{{loc}}] < \infty $. Здесь рассматривается случай $\delta = \frac{L}{{\sqrt {{{b}_{1}}} }}$. Аналитическое решение в этой постановке было получено в предельных случаях для малых и больших коммуникаций с учетом локального времени вычислений. Рассмотрим их по отдельности.

4.1. Случай большого времени коммуникаций

Наложим дополнительные ограничения на случайные величины ${{\tau }_{{comm}}}$ и $\tau _{i}^{{loc}}$: $\forall \{ \tau _{{comm}}^{k}\} _{{k = 1}}^{m},\{ \tau _{i}^{{loc, k}}\} _{{k = 1}}^{m}$ $\forall k,i$ ↪ $\tau _{{comm}}^{k} \gg \tau _{i}^{{loc, k}}$. Рассмотрим функцию времени работы задачи (7) в точке минимума. Ранее в 3 было получено:

(11)

$\mathcal{F}({{b}_{{{{1}_{{\min }}}}}}) = (\alpha \cdot {{\tau }_{{comm}}}{{)}^{{4/5}}} \cdot {{(\beta \cdot \tau _{1}^{{loc}})}^{{1/5}}} \cdot {{(4}^{{1/5}}} + {{4}^{{ - 4/5}}}),$

где $\alpha = {{c}_{1}} \cdot \sqrt {\frac{L}{\mu }} \cdot \log \left( {\frac{1}{\varepsilon }} \right)$, $\beta = {{c}_{2}} \cdot \sqrt {\frac{L}{\mu }} \cdot \log \left( {\frac{1}{\varepsilon }} \right)$.

Для получения результата произведем следующее равенство: $X,Y - $ независимые случайные величины $ \Rightarrow \mathbb{D}[XY] = \mathbb{E}[(XY - \mathbb{E}[XY{{])}^{2}}]$ = $\mathbb{E}[(XY{{)}^{2}}]$ – – $2{{\mathbb{E}}^{2}}[XY] + {{\mathbb{E}}^{2}}[XY]$ = $\mathbb{E}[{{X}^{2}}]\mathbb{E}[{{Y}^{2}}] - {{\mathbb{E}}^{2}}[X]{{\mathbb{E}}^{2}}[Y]$ = = $(\mathbb{D}[X] + {{\mathbb{E}}^{2}}[X]) \cdot (\mathbb{D}[Y] + {{\mathbb{E}}^{2}}[Y]) - {{\mathbb{E}}^{2}}[X]{{\mathbb{E}}^{2}}[Y]$ = = $\mathbb{D}[X]\mathbb{D}[Y] + \mathbb{D}[X]{{\mathbb{E}}^{2}}[Y] + \mathbb{D}[Y]{{\mathbb{E}}^{2}}[X]$. Применив это равенство к (11), получим искомую ошибку:

$\begin{gathered} \mathbb{D}[\mathcal{F}({{b}_{{1,\min }}})] = \\ \, = [{{\alpha }^{{4/5}}} \cdot {{\beta }^{{1/5}}} \cdot {{(4}^{{1/5}}} + {{4}^{{ - 4/5}}})] \cdot \{ \mathbb{D}[({{\tau }_{{comm}}}{{)}^{{4/5}}}]\mathbb{D}[(\tau _{1}^{{loc}}{{)}^{{1/5}}}] + \\ \, + \mathbb{D}[({{\tau }_{{comm}}}{{)}^{{4/5}}}]{{\mathbb{E}}^{2}}[(\tau _{1}^{{loc}}{{)}^{{1/5}}}] + \mathbb{D}[(\tau _{1}^{{loc}}{{)}^{{1/5}}}]{{\mathbb{E}}^{2}}[({{\tau }_{{comm}}}{{)}^{{4/5}}}]\} . \\ \end{gathered} $

4.2. Случай малого времени коммуникаций

Здесь будет рассматриваться шум только на коммуникациях, т.е. время коммуникаций будем представлять как случайную величину с математическим ожиданием и конечной дисперсией, а время локальных вычислений для каждого устройства – как постоянную величину. Аналогично предыдущему пункту наложим дополнительные ограничения: $\forall \{ \tau _{{comm}}^{k}\} _{{k = 1}}^{m}$ $\forall k,i$ ↪ $\tau _{{comm}}^{k} \ll \tau _{i}^{{loc}}$. Рассмотрим функцию времени работы задачи (7) в точке минимума (здесь возьмем точку $b_{1}^{0}$):

$\begin{gathered} \mathcal{F}({{b}_{{1,\min }}}) = \left[ {(N - b_{1}^{0}) \cdot {{{\left( {\sum\limits_{i = 2}^n \frac{1}{{\tau _{i}^{{loc}}}}} \right)}}^{{ - 1}}} + {{\tau }_{{comm}}}} \right] \cdot \alpha \cdot \frac{1}{{{{{(b_{1}^{0})}}^{{1/4}}}}} + \tau _{1}^{{loc}} \cdot b_{1}^{0} \cdot \beta = \\ \, = \left[ {\frac{{\tau _{1}^{{loc}} \cdot N \cdot {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}}{{\tau _{1}^{{loc}} + {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}}} + {{\tau }_{{comm}}}} \right] \cdot \alpha \cdot \frac{{{{{\left( {\tau _{1}^{{loc}} + {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}} \right)}}^{{1/4}}}}}{{{{{\left( {N \cdot {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}} \right)}}^{{1/4}}}}} + \tau _{1}^{{loc}} \cdot b_{1}^{0} \cdot \beta , \\ \end{gathered} $

Тогда искомая ошибка будет следующей:

$\begin{gathered} \mathbb{D}[\mathcal{F}({{b}_{{1,\min }}})] = \\ \, = {{\left[ {\alpha \cdot \frac{{{{{\left( {\tau _{1}^{{loc}} + {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}} \right)}}^{{1/4}}}}}{{{{{\left( {N \cdot {{{\left( {\sum\limits_{i = 2}^n {\frac{1}{{\tau _{i}^{{loc}}}}} } \right)}}^{{ - 1}}}} \right)}}^{{1/4}}}}}} \right]}^{2}} \cdot \mathbb{D}[{{\tau }_{{comm}}}]. \\ \end{gathered} $

5. ЭКСПЕРИМЕНТЫ

5.1. Эксперименты с распределением данных

Для экспериментальной проверки теоретических результатов рассмотрена задача гребневой регрессии:

(12)

$\mathop {\min }\limits_\omega \left[ {\frac{1}{{2N}}{\text{||}}X\omega - y{\text{||}}_{2}^{2} + \frac{\lambda }{2}{\text{||}}\omega {\text{||}}_{2}^{2}} \right],$

где ω – вектор весов модели, $\{ {{x}_{i}},{{y}_{i}}\} _{{i = 1}}^{N}$ – обучающий набор данных, $\lambda > 0$ – параметр регуляризации. Рассматриваем сеть с 21 устройством, смоделированную на однопроцессорной машине. Кроме того, используется набор данных из библиотеки LIBSVM [19]. Значение $\tau _{1}^{{loc}} = 1$, значения для остальных i $\tau _{i}^{{loc}},i \ne 1$, взяты относительно и равномерно генерируются от 3 до 7. ${{\tau }_{{comm}}}$ выбраны так, что $\frac{{{{\tau }_{{comm}}}}}{{\tau _{1}^{{loc}}}}{{ = 10}^{l}}$, $l = \overline { - 6,12} $.

Был реализован алгоритм 2 на Python 3.9.6, используя итерационный метод OGM-G из статьи [20] для нахождения argmin в 2 (именно это рекомендуется в оригинальной статье [17]). Подсчитав необходимое количество итераций для достижения определенной точности, находим значения констант ${{c}_{1}},\;{{c}_{2}}$ и, соответственно, α, β. С их помощью стало возможным распределение данных по устройствам в соответствии с приведенными выше формулами.

Далее был запущен алгоритм и измерено время работы на полученном распределении данных по устройствам и равномерном распределении. Наша цель – найти ускорение полученного нами распределения данных относительно равномерного разбиения.

Рассматриваются два случая различных $\delta $: $\delta = \frac{L}{{\sqrt {{{b}_{1}}} }}$ и $\delta = \frac{L}{{{{b}_{1}}}}$. Для случая $\delta = \frac{L}{{\sqrt {{{b}_{1}}} }}$ для нахождения ${{b}_{{1,\min }}}$ используем следующие подходы: 1) для всех случаев времени связи используем метод Ньютона для численного нахождения решения; 2) для малых и больших связей используем также результаты раздела 3.4.2. Для случая $\delta = \frac{L}{{{{b}_{1}}}}$ для нахождения ${{b}_{{1,\min }}}$ мы также используем метод Ньютона и дополнительно формулу Кардано из раздела 3.4.1. Результаты приведены на рис. 1.

Рис. 1.

Эксперименты с распределением данных.

5.2. Эксперименты с шумом

Мы модифицировали моделирование алгоритма 2, добавив шум в коммуникации и мощности устройств. Шум генерировался из равномерного распределения, и его величина составляла 10, 20, 30, 50 и 100% соответственно от абсолютного значения времени коммуникаций и мощности устройств. В новой модели шума были проведены измерения времени выполнения задачи Гребневой регрессии (Ридж-регрессии) с полученным распределением данных и с равномерным распределением, получив ускорение, дающее правильное распределение данных. При этом проводились измерения математического ожидания затрат на коммуникации и мощности устройств, а впоследствии было получено ускорение при этих ожидаемых значениях. Эксперименты проводились только в случае больших затрат на связь 4.1. На рис. 2 приведены график отношения этих ускорений и доверительные интервалы.

Рис. 2.

Эксперименты с шумом в сети.

Проанализируем полученные результаты. Из графика видно, что все прямые попадают в доверительные интервалы, а значит для любого значения шума, приведенные в Секции 4.1 теоретические расчеты подтверждаются экспериментом. Также отметим, что вблизи значения ${{t}_{{comm}}}{\text{/}}t_{1}^{{loc}}$ = = 10¹⁰ шум практически перестает влиять на результаты.

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

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

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

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.
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.
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.
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.
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.
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.
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.
Nesterov Y. et al. Lectures on convex optimization. Springer, 2018. T. 137.
Arjevani Y., Shamir O. “Communication complexity of distributed convex learning and optimization,” Advances in neural information processing systems. 2015. T. 28.
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.
Matsushima S., Yun H., Zhang X., Vishwanathan S. “Distributed stochastic optimization of the regularized risk,” arXiv preprint arXiv:1406.4363, 2014.
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.
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.
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.
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.
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.
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.
Polyak B.T. “Newton’s method and its use in optimization,” European Journal of Operational Research. 2007. T. 181. № 3. C. 1086–1096.
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.
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.

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

Инструменты

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

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

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