Децентрализованный метод Mirror-Prox Sliding с оракулами нулевого порядка для композитной компоненты

Чэнь Цзявэй Рогозин А. В. Гасников А.В. Лобанов А.В.

Журнал: Труды Московского физико-технического института @trudy-mipt

Рубрика: Математика

Статья в выпуске: 3 (71) т.18, 2026 года.

Бесплатный доступ

В данной работе исследуются децентрализованные композитные выпукло-вогнутые седловые задачи с композитной компонентой, доступной только через оракул нулевого порядка. Мы предлагаем ZO-DMPS — децентрализованный метод Mirror-Prox Sliding (MPS) нулевого порядка, объединяющий механизм скользящих шагов MirrorProx Sliding с отслеживанием градиента и оцениванием оператора композитной компоненты нулевого порядка. Применение сглаживания и двухточечных оценок по значениям функции к композитной компоненте позволяет предложенному методу обходиться без градиентной информации для композитной компоненты и использовать лишь оракул нулевого порядка. Предложенный алгоритм даёт доказуемо сходящееся и эффективное решение композитной децентрализованной задачи оптимизации в постановке нулевого порядка. Его эффективность демонстрируется в численных экспериментах.

задача седловой точки \ децентрализованная оптимизация \ метод зеркального прокс-скольжения \ негладкая оптимизация \ нулевого порядка оракул

Короткий адрес: https://sciup.org/142248887

IDS: 142248887   |   УДК: 519.85

Decentralized Mirror-Prox Sliding with zeroth-order coupling oracles

This paper studies decentralized composite convex-concave saddle-point problems with a zeroth order coupling component. We propose ZO-DMPS, a decentralized zeroth-order Mirror-Prox Sliding method (MPS) that combines the sliding mechanism of Mirror-Prox Sliding with gradient tracking and zeroth-order estimation of the coupling operator. By applying a smoothing technique and two-point function-value estimators to the coupling component, the proposed method does not require gradient information for the black-box coupling term. The proposed algorithm provides a provably convergent and efficient solution for composite decentralized optimization in the zeroth-order setting. Its effectiveness is demonstrated through numerical experiments.

Текст научной статьи Децентрализованный метод Mirror-Prox Sliding с оракулами нулевого порядка для композитной компоненты

Децентрализованная оптимизация стала одним из центральных направлений в крупномасштабном машинном обучении, распределенном управлении и многоагентных системах. Многие современные приложения, включая федеративное обучение, координацию множества роботов и распределённое обучение с подкреплением [1,2], естественным образом приводят к постановкам с седловой структурой. Такие постановки описывают состязательные взаимодействия, прямодвойственные модели и регуляризованные минимаксные целевые функции [3-5]. Поэтому разработка децентрализованных алгоритмов, способных эффективно решать подобные задачи, имеет фундаментальное значение.

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

Исследования композитных седловых задач в централизованной постановке уже достаточно развиты. В работе предложили ускоренный оптимальный градиентный метод спуска-подъема, который сочетает ускорение Нестерова [13] для разделимых слагаемых с оптимистическим градиентным шагом для композитной компоненты и достигает оптимальной итерационной сложности посредством перезапусков [14]. К другим важным результатам относятся первично-двойной метод [15] и PD-EG [16], основанные соответственно на прямодвойственном подъеме и разложении через выпукло-сопряженные функции. Еще одна ускоренная схема, APDG [17], использует стратегию прямого-обратного шага совместно с экстраполяцией.

1.1.    Related Workds

Метод Mirror-Prox Sliding. В работе [12] метод Mirror-Prox Sliding рассматривает структурированное вариационное неравенство с оператором вида V G + Н, где гладкий градиент VG вычисляется на внешних итерациях, а монотонный оператор Н используется во внутреннем цикле Mirror-Prox. Его стохастический вариант SMPS допускает несмещенные стохастические оценки Н с ограниченной дисперсией. В отличие от MPS/SMPS в нашей постановке оператор Н непосредственно недоступен и должен аппроксимироваться по значениям функции с помощью двухточечной оценки нулевого порядка. Кроме того, децентрализованная структура нашей задачи требует одновременно контролировать ошибку консенсуса и ошибку оценивания нулевого порядка.

Децентрализованные седловые задачи Метелев [13] рассматривает гладкие сильно выпукло-сильно вогнутые задачи с билинейной связью при доступе к оракулу первого порядка, тогда как Чэнь [14] применяет сглаживание к распределенным негладким минимаксным задачам с доступом нулевого порядка ко всей локальной целевой функции. В отличие от них наша работа рассматривает композитную постановку со смешанными оракулами: гладкие разделимые компоненты обрабатываются с использованием информации первого порядка, тогда как только композитная компонента Ф;(х,у) доступна посредством значений функции. Эта структура мотивирует децентрализованный метод Mirror-Prox Sliding со сглаженной двухточечной оценкой для Ф; и анализ, учитывающий как ошибку оракульной аппроксимации, так и ошибку консенсуса.

В данной работе изучаются децентрализованные композитные седловые задачи, в которых локальные композитные компоненты доступны через оракул нулевого порядка. Мы предлагаем ZO-DMPS — децентрализованный метод Mirror-Prox Sliding нулевого порядка, сочетающий рандомизированное сглаживание и процедуру отслеживания градиента. Далее MBi выводим гарантии сходимости и иллюстрируем поведение метода на синтетических экспериментах.

2.    Постановка задачи

Мы рассматриваем композитную седловую задачу min maxФo(x•у)• хех уеУ

1 п Ф о (х,у) = - ^^дД^у), - i =1

где Фi,o(x•у) = pi(x) + Фi(x•у) — qi(у). Функции pt и qi являются гладкими слагаемыми,

тогда как Фi — композитная компонента, доступная толвко посредством запросов значений функции. Обозначим z = (хт,ут)т Е Z := X хУ,    V(u,v) = -|u — г|2, и определим

1 п

G(z) := p(x) + q(у) = - ^2(pi(x) + qt(у)) .

- i =1

Усреднённая композитная компонента имеет вид Ф(z) ственный разрыв определяется как

п

п

^2 Фi (z). Исходный прямодвой-i =1

Gap0(Z) := шах Ф о (Х, у) — min Ф о (х, у), уеу           хех

z = (Х,у).

Предположение 1. Множество Z непусто, выпукло и компактно. Определим Dz := max ||u — ф|, Qzo :=maxV(zo,z).

u,vez             0     zez

Предположение 2. Для каждого агента i функция Gi(z) := Pi(x) + qi(y) выпукла и L^,max-гладка. Усредненная функция G выпукла и ^-гладка. Каждый агент может вычислять VGi(z).

Предположение 3. Для каждого агента i функция Фi(x, у) выпукла по х и вогнута по у. Существует М >  0, такое что все функции Фi являются М-липшицевыми на области оракульных запросов, используемой алгоритмом.

Предположение 4. В коммуникационной сети используется симметричная дважды стохастическая матрица. W Е Rnxn. Пусть J := 11 т, р := ||W — J |2< 1.

После К раундов консенсуса определим

$к := рК ,      SK :=        .                             (3)

1 — ^к

  • 3.    Методы

    3.1.    Сглаживание и свойства оракула

Пусть u = (uT,uT)T равномерно распределен на 5^(1). Двухточечная оценка нулевого порядка, используемая агентом i, имеет вид

HH i(z; u) := хг (^i(z + Pu) — ^i(z — Pu) f ^X   .

2P                            — uy/

Смена знака во втором блоке кодирует максимизацию по у. Определим сглаженный локальный седловой оператор

H‘^ (z) := (Д фД)) •    H“(z) ;= 1 £ ^(z).

У V У ФЬ/АН/               п i =1

Лемма 1. Пусть выполнены предположения 1 и 3. Тогда сглаженные локальные и глобальный седловые операторы являются М ^-липшицевыми, где

М = 0(

Кроме того, для всех z Е 2 оценка (4) удовлетворяет соотношениям

Eu[Hi(z; u)] = Hi^z),

Еи J|H i(z; u) - Hi,^(z)^2j <  а2 ,

где а2 = O(dM2).

Доказательства лемм 1 приведены в работе [14].

3.2. Децентрализованное скользящее зеркало-прокси

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

Algorithm 1: ZO-DMPS

Require: матрица смешивания W, число внешних итераций N, глубина консенсуса К, радиус сглаживания ц, размер мини-пакета В, пара метры {jk,3k 3^k ^k }

Initialize: z OUt = zf nc = z0

For к = 1 t nN do

For all агентов i do ext               out          anc zi,k ^ (1 - yk)zi,k-1 + ykzi,k-1 O,cur      anc zi,k ^ zi,k-1

Построить трекер gi,k для V Gi^z eXt )

For t = 1 tо F k do

Построить трекер h21 для H(^(z^cur) ,lb                         ,^p^ , zgre ^ argmm{(gi,k + h^z) + 3kV(z^z) + ykV(z^, z)}

% ^z>Z

ПвРТПГШТк ТПРТРРП 2t IT TTQ ^T^B^ ( T'^pre'l

F F Fl F- F j.1 Fl FF F Id F j.1 F. Ix Fl j.1 ‘ ^ik m^ H H i^ ( zik )

zitkor ^ argmin{(gi,k + h^, z) + 3kV(zfn-i,z) + p^V(z^cur, z)} ,              zEZ                                                          , t,cur    ^ К    t,cor zi,k ^     (^  )i,3 zi,k

3 =1

End For

Tk anc      Tfe,cur      mid , —~1     ^t,pre zi,k ^ zi,k    ' zi,k 'Jk / j zi,k t=1 out               out         mid zi,k ^ (1 - yk)zi,k-1 + ykzi,k

End For

End For

Алгоритм поддерживает трекер gi,k для гладко го сигнала VGi и трекер hfk Для стохастического оператора нулевого порядка посредством

п ч+ = Е(жк )v (—+^ - ^т),    * = 1,...,п.                (8)

3 =1

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

1 п 9k • = - E9i,k, п ^^ i =1

1 П hk •= П £Щ

Рассогласования отслеживания имеют вид

Rg,k

/1 п

= п Е и*

\ i=1

-

\ 1/2

9k |П

и

Rsh,k

/1 п

:= П Е «^

\ i=1

-

hk и2)

1 / 2

Set

Р2^—1 —    , _1_ Р2*—1       R2* — Р ,_1_ R2*

ua,k • ^gk + uh,k ,      ^c^k • ng,k + uh,k .

Кроме того, 1 п

•= 9k - VG(C t ) = п E рбЖЕ - VGr (z^) ] .

4. Основные результаты

Наш анализ строится вокруг сетевых средних итератов отдельных агентов, обозначае-1 п мых верхней чертой; например, zOut •= — Е^ zOut ■ Для количественного описания влияния п i=1

децентрализации введем следующие меры рассогласования:

* ^ eor ,k •

п

п

ЕК- ^kor \\2

i =1

п

i*        1 Е   *, pre _ -*, pre 2

'pre,k • п 2s \Zi,k      Zk    || i=1

Также будем использовать сокращенные обозначения

_            T9+—                      Т9+ ak •= ^k + 9k.     ak   •= 9k + hk ,     ak •= 9k + hk .

Первая лемма является усредненным аналогом стандартного неравенства для двух проксимальных шагов Mirror-Prox. По сравнению с централизованным доказательством единственными дополнительными слагаемыми являются величины рассогласования е^ k и е2 k> отражающие цену ошибок консенсуса и отслеживания.

Лемма 2. Зафиксируем к ^ 1 и t = 1,... ,Tk. Тогда для каждого z Е Z aak‘, zk,eor - z) + (а^«—1,   ■■ - ar) c Ilk [v ,      - V(zk-1, akpre)} + Щ'(z^u'.z)

  • - (Л + Ц) v(zkeor,z) - ^^ | |zk pre - zk   ' - ^ ||zk— kcur - zk ■ \ \ 2 + Щ + 4,k, (9)

где

c*   — lk F , I 9 k * —t-l I D2*—1

£ 1 , k •= 2 ^a ne , k— 1 + 2 ^ eur , k + ^a,k V ^ pre ,k ,

U

c*      ^L p ,     । 9k pt-3 । r2* kpt

  • e 2 , k •= 2 ^ ane ,k— 1 + 2 ^ eur ’k + ^a, kp ^ eor , k .

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


    C 2t-1 • = И tz11' Z211}

    >i,k ’ Hi.U(zi,k ’ >i,k )


    —


    тт Щ t-1x 22t __Д (ire^.t^t x тт (trerex

    Hi.n(zi,k hV.k — Hi.n(zi.k ; ^i,k ) — Hi.n(zi,k 3


    ПуСТБ


    A*- := 1

    k п


    n                        n n

    Е л2 t- 1      л 2 t 1 V^ ^2 t

    4k ,     Ak •- n2^(=iA .

    i =1                         i =1


    Ошибки усредненного оператора раскладываются следующим образом:


    ^-1 - н,^к1 + s*-1 +Akt-1, hkt - h^ )+■+Akt5


    где


    nn

    '5k‘-1 :- - E ДЖ-1) — Н,Ж-1)] • ^x :- - E Д.Ж,Г) — Н.Д^^ . пJ/tL

    i=1

    При размере мини-пакета В шаг усреднения уменьшает дисперсию оценки нулевого порядка согласно неравенствам

    .    . Жs

    EIIAMI2< В,    E||Ak*||2 ^ В .

    Следующая лемма преобразует внутреннюю рекурсию Mirror-Prox в одношаговую оценку сертификата.

    Лемма 3. Зафиксируем к. Предположим, что

    М* < 1 4 (3k + 3k ),     t -1,...,Tk .

    Предположим также, что

    3+ <  3k + 3k,    t -i,...,Tk — 1.


    Тогда для каждого фиксированного z Е Z


    Г1 T x

    E - E (VG(zT t ) + h^ ■. ere


    —


    z) <  —3k EV (zk-ci,zmil) +


    + (/3k + T) EV (zk-i,z) — J' EV (z^, z) + Ektoch + ЕГ,



    где


    E stoch__


    1 E 7z 2 -kj^ 2(3k + 3k ),


и

Eke :- E^ + E^, причем

Ekv :- DZ E^H + E

-k

Tk                                    Tk

E E [||<-11| + IKII] ,E e rox :- - E E [^k t=i                                     k t=i

+ e 2 . k].

Замечание 4. Предыдущая оценка полезна лишь в том случае, если сетевой вклад можно равномерно контролировать по k. Следующая оценка показывает, что это слагаемое геометрически убывает с глубиной консенсуса К с точностью до квадратичной поправки более высокого порядка.

net                            2

Ек  <  ^ avg SK + ^ ргох ,к SK,

(      1 Tk   \ где Cavg зависит только от липшицевых констант задачи, а Сргох,к = О \ flk + — ^ бк • к t=i

SK имеет меньший порядок, чем

При выборе параметров, используемом далее, слагаемое ведущее оптимизационное слагаемое.

Теорема 5. Предположим, что flk fl Ly к •

Определим

Г 1 = 1,

Гк = (1 - 7к )Гк- 1 ,

k fl 2

и предположим, что 71 = 1. Определим

7к

^к,t : Г N г т •

Предположим выполнение телескопического условия

7к Л + 6 k \ <  у к- 1 Ак- 1 + nti к                                                    ,

Г к         Тк/ Г к- 1      Тк- 1

k = 2,...,N.

Определим

g c^xp := sup E zEZ

Г               Nn

G(zNu') - G(z) + £ £ хи (нЛкЦт z^ - z к =1 1 =1

•

Если

z a nc = z o ,

^zo := sup У (z o ,z) zeZ

то

^txp <  Г ^ 61 + Т \ Qzo +F W £ '        1'              к =1

N

^E^ och + T n £ 7^ ( C avg SK + С ргох,к SK ) •    (11)

Г к                    Г к к=1

В следующей лемме мы укажем набор параметров, удовлетворяющий предположениям приведенной теоремы.

Лемма 6. Выберем

7к =

k + 1,      ^к =

2L g k ,

Тк =

Vs kM—

L g

Nk2a 2 +— + 2.1

^ z o L g

t a ы , LGТk

,     6к = Ак (t - 1) + k •

Тогда из оценки из тификата убывает с

теоремы 5

следует,

увеличенной скоростью gN— <

что математическое ожидание сер-

О(е), при условии, что

N = О

к     M1/eA □

,К = О           • Эквивалентно.

1 - Р

для ZO-DMPS получаются

следующие оракулъные и коммуникационные сложности в Сложность по градиентному оракулу равна

расчете на одного агента.

N ^ g = О

Сложность по оракулу оператора нулевого порядка равна

N О (a L g & z 0   M p^oo   & p^ Zo \

^ zo = С          +---+         .

Е           Е           Е2 I

Коммуникационная сложность составляет

Ncomm — О

(У

L g ^ z o +

Е

Mp^oo +

Е

^ ^Z0

Е2

.

Это следствие подчеркивает основную особенноств метода. Число точных вычислений градиента гладкого разделимого слагаемого соответствует ускоренной зависимости О(е -1 / 2 ), унаследованной от схемы сколвзящих шагов, тогда как коммуникационная нагрузка входит через логарифмический множитель и спектральный зазор. Дополнительные затраты нулевого порядка возникают из-за слагаемых сглаживания и дисперсии, что неизбежно, когда оператор композитной компоненты наблюдается только посредством значений функции.

Теперь необходима лемма, связывающая исходную задачу с приведенным выше следствием.

Лемма 7. Для любого z^ имеем Gapp(^) <  G nP Далее, согласно лемме 1 в [14], получаем

Gapo(zT) < Gapp (z^) + pM .

Следствие 8. Выбор p — e/(2M ) гарантирует Е-точное решение исходной седловой задачи нулевого порядка со следующими сложностями. Сложность по градиентному оракулу равна

Сложность по оракулу оператора нулевого порядка равна

/ LGCZo0 , VdM 2 Q zo , dM^o yv Е         Е2          Ве2

Коммуникационная сложность составляет

^ comm — О

(у

L g ^ z o

Е

+

dMM 2 QZ0

Е2

dM 2 Q oo

+ Ве 2

5.    Заключение

Мы исследовали децентрализованные седловые задачи, в которых локальные композитные компоненты доступны только через вычисления значений функций. Для работы в этой постановке мы использовали рандомизированное сглаживание для построения гладких аппроксимаций и двухточечную оценку нулевого порядка для аппроксимации градиентов. Затем эти компоненты были интегрированы в децентрализованный метод Mirror-Prox Sliding с отслеживанием градиента.

Полученный подход объединяет сглаживание, стохастическую аппроксимацию и децентрализованные вычисления в единой схеме. Наш анализ показывает, что метод обладает благоприятными гарантиями сходимости, достигает оптимальной итерационной сложности для сглаженной задачи и удерживает ошибку консенсуса под контролем при надлежащем выборе числа коммуникационных раундов. В этом смысле метод переносит идеи типа Mirror-Prox на децентрализованные седловые задачи нулевого порядка.

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

6.    Эксперименты

Мы оцениваем эффективность ZO-DMPS на сильно выпукло сильно вогнутой квадратично-билинейной седловой задаче. Глобальная минимаксная задача имеет вид

1 m min max F(х, у), хЕХ yEY V

F(х,у ) = m E fi(х,y'>, i =1

где m — число агентов. В наших экспериментах m = 20, х 6 R50, и у 6 R50, поэтому полная седловая переменная равна z = (х,у) 6 R100. Допустимые множества представляют собой евклидовы шары X = {х 6 R50 : ||х||2 < 10}, Y = {у 6 R50 : ||у||2 < 10}.

Каждый агент i располагает локальной целевой функцией вида fi (х,у) = 1 хт Qi х + ст х + ут Ai х - 1 ут Ri у - dT у.

Во всех трех исследованиях мы используем алгоритм ZO-DMPS с 50 внешними итерациями и параметром сглаживания ц = 0.01. Все результаты представлены по 5 случайным начальным значениям генератора (0,1, 2, 3,4). Для оценки сходимости основным критерием служит двойственный разрыв.

Мы варьируем размер мини-пакета по множеству {8,16, 32, 64,128}, фиксируя коммуникационную топологию в виде связного случайного графа и используя 4 раунда консенсуса. Увеличение размера мини-пакета улучшает качество оценки нулевого порядка и приводит к меньшим итоговым двойственным разрывам. Такое поведение согласуется с тем, что более крупные пакеты уменьшают дисперсию двухточечной оценки. В качестве базового метода мы включаем децентрализованный метод дополнительного шага нулевого порядка. Результаты показывают, что ZO-DMPS способен достигать сопоставимого качества, при этом сокращая вычислительные затраты для гладких слагаемых.

Рис. 1. Сравнение эффективности ZO-DMPS при различных размерах пакета с децентрализованным методом дополнительного шага нулевого порядка (размер пакета = 64): по числу коммуникационных раундов (слева) и запросов к оракулу нулевого порядка (справа)

  • 7.    Приложение

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

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

(^- 1^Г - q} < ^{V(С1,7) - V(^— 1 , д’рге) - v (<pre,q)} +

+ 4{V(z^ u , q) - V (z^ cur , k pre ) - V (zk pre, q)} + 8^ ,     (12)

(a^, % cor - z^ <  3k {V (z O — i ,z) - V (zf— 1 , k cor ) - V«’ cor , z)} +

+ 4 { V (zt-1’ c ur, z ) - V (zl-1’ c ur, % cor ) - V (< cor , z)} + ^.     (13)

Подстановка q = z tpCO° в (12) и прибавление полученного неравенства к (13) сокращают два промежуточных брегмановских слагаемых. Следовательно,

(a^zr - z) + (<-1дГе -z^ <

< A{V (z^, z) - V(C c1 , zi’pre)} + ^V (Jk1m, z) - (A + 4 ) V (z^, z) -

- ^V(4-1’cur, 4’pre) - (/3k + rk) V« pre, %cor ) + ^ + 4Л.                  (14)

Поскольку для двух последних слагаемых V (u,v) = - ||u - v|2, это в точности утверждаемое неравенство.

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

Доказательство. Обозначим

  • - t, pre               -t, cur     -t, cor               -t— 1 , cur

    anc

    = zk— 1 ,


    e = aft


p = zk   , c = zk = zk   , r = zk

Из леммы 1 получаем

(а%,с - z) + (а^ 1,p - с) ^3k[V(a,z) -V(a,p)] + fkV(r,z) - (3k + r^)V(c, z) -- 3k+rk |p - cl - r) |r - p|2 + Щ + 4k.(15)

Используя разложения akt—1 и af, получаем, что (15) эквивалентно

{VG(e) + Н(p),p - z) < Rk,t(z) + {H(p) - H(r),p - c) - (6fp - z) - (S2kt—1,p - c)-

- {^к-ч - z)- (△k 1,p - c) - (△kt,c - z) ,(16)

где

Rk,t(z) = 3k[V(a,z) - V(a,p)] +rkV(r,z) - (3k + rk )V(c,z) - ^ |p - c|k - ^ |r - p|k + Щ + 8 k ,k.

Из липшицевости H, неравенства Юнга и условия М 2 ^ rk (3k + Гк)/3 следует, что

{Н(p) - Н(r),p - c) ^ ^ |p - r|2 + 3k^k- |p - c|2 .

Кроме того,

-

( A2 t—1 n c}<  3 " △   " * + 3k + rk ||o   c||2

( △ ,p - c) ^ 2(3k +rk )+   6    |p - c| .

Таким образом, отрицательные квадратичные слагаемые в Rk,t поглощают две приведённые оценки. Объединяя это со стандартной оценкой второго шумового слагаемого и оценкой дисперсии, как в централизованном стохастическом методе Mirror-Prox Sliding, получаем консервативный стохастический вклад

7a2

2(Зк + ч1 ) ’

Взяв математическое ожидание в (16) и оценив детерминированные смещения величиной Dz |Ы|*, получим

E (VG(e) + Н (р),р - z) < Д E[V (a,z) - V (a,p)\ + Е[^ И (г, z) - (Зк + Чк )V (c, z)\ +

+ Dz E imi * + Dz E IP ? -1 1| * + Dz E |pkt II * + EPP + 4J + ^дщ •       CD

Усреднение no t даёт

Г1 n , k t - z)

⩽

E        \VG(zkxt) + H(

. к t =1

⩽ E

1 Тк

-Ya {V (zk- 1 ,z) - V (zt-Ak pre

)}

+

+ E

1 к

T E^v (

Тк =

-1 — 1 , cur zk ’

,z) - (A +4)V (zk’cur,z)}

+ E^ + Et rox + E

stoch к

Наконец,

1   Тк r E v (Zkk—c1, ztpre) > v «—t zmid), к t=1

^ё E MV (zk—1,cur, z) - (Зк + чк) V (z^” z)} « Д-HOT, z) - У±^£ V (zr, z), к t_i                                                              ^к                       ^к где первая строка следует из неравенства Йенсена, а вторая — из внутреннего телескопического соотношения чк+1 < Зк + Чк- Подстановка в (18) доказывает

’ 1    Тк

E ^ E (vG(Zkxt) + H(

t =i

zt’p re ) zt,PTe

-

z) «

< Ы + d ) EV«—с 1 , z) - Зк EVНк— 1 , гк'Д - У+Д EVЛ '-. z) +

+ Ekvg + Eprox + E^ ch

•

7.3.    Доказательство теоремы 5 G(z). Из гладкости G. равенства

Доказательство. Пусть Ак(z) = G(zkut) -zout - Z^t = Чк (zmid - Z aE1 ) II выпуклости следует

Ак(z) - (1 - Чк)Аk— 1 (z) ^ чк (vG^AA d - z) + ^Е ||z m id - ZT 1 1|2 •     (20)

Поскольку z mid

= гуе

zpe, добавление операторного слагаемого сертификата

и

при-

t менение леммы 2 дают

EAk(z) - (1 - 7k)EAk- i (z) + > ^E (Н (< pre ), z^ e - z} <  к t =i

< 7k (рк + Г) EV(zk-i, z) - 7k^к+г^-EV(z^, z) + 7kEktoch + 7kf '-

- >(h - L7k)E fmid - zk^ .(21)

Последнее слагаемое неположительно. Отбрасывая его, получаем

EAk(z) - (1 - 7k)EAk-i(z) + T £ E (н(z^re), z^e - z) < k t=i

< 7k (/3k + Г) EV(zkni,z) - 7k' ^ EV(Zknc, z) + 7kEktoch + 7kEke.(22)

Разделим на rk и просуммируем по к. Поскольку rk = (1-7k)rk-i, слагаемые с Ak телеско-пируются, а принятое условие на параметры обеспечивает телескопирование брегмановских слагаемых. Следовательно,

N     T                           i

Е-Т^ + Е 7F Е Е (н (z^),z^ - z} <  Ei + 7p П(z o , z) + \ 7.(Ektoch + E net ).

ГN k =i rk T                       7   7 t^          k =i rk

Умножая на Fn, используя Xk,t = Гм7k/(rkTk) и V(zo, z) < Иг0, а затем применяя оценку сетевой ошибки net                            2

Ek ^ ^avgS К + O/proX’kS К, получаем

E

N Tk

С(£У) - G(z) + ЕЕ Xk,t (Н(zt pre ),zt pre k =i t =i

-

z)

⩽

< Гу

/      i\            N                 N

3 + 7 ^ + Гу E 7-Ek toch + Гу E ? (^ avg SK + C prox , kSK ) .

'       T i/              k =i ik               k =i ik

Переход к супремуму no z Е Z дает заявленную оценку математического ожидания сертификата.

7.4. Доказательство результата о сложности

Доказательство. Из оценки математического ожидания разрыва сертификата получаем

/      i\            N                 N

Q N t <  ГN pi + 7p ^0 + ГN E , '' r. + ГN E r-E np

T                     Г                      Г

4       iZ            k=i k              k =i k

Сетевая оценка при S k = рК /(1 - рК ) дает

N                N

N

г \ ' 7k j-rnet                 \ л 7k I   а^ у \ ' 7k к'1

Г N    Г E k,fi ^ ^ avg S K 1 N 2s Г + S K Г N 2s Г ^ Prox ,k .

k =i 1 k                      k =i 1 k           k =i 1 k

Для 7/ = 2/(k + 1) и Г/г = 2/(k(k + 1)) имеем 7//Г/ = к, Fv = 2/(N(N + 1)), и потому v rv £к =

/ =1

1. Следовательно.

vv rv £ F^C/t < CavgSk + BvSK,         Sv := rv £ k,^.(26)

k=1 1 kk

Далее,

1г £ 7/ = L G(2 T / - 1) ,     kC prox ,/ = C2zLG(2Tk + 1) + 4CaCzk.

lk t=i

Используя

VskM"Nk

Tk <     ' +/ + 1

k I-  + ^L- + получаем

'                               r 9        2CZ’Nii2

kC prox ,k < 2^3CZM/k +        'k 2 + 3C z 2 L g + 4CaCzk.

'zoLG

v

Таким образом, £ kCpro x ik = O(N 2) +O(N 4 a2 /(Q Z 0L g )), и, поскольку rv = O(N -2), k =1

N2a 2

Bv = о (1 + »Д) =0(N2).

Следовательно, если S k < N 2, to

v

Fv £ 7^/ = O (S k ). r k

Для централизованного и стохастического слагаемых из 71 = L—T1 получаем rv (л +11) ^ = Nn^

Кроме того,

следовательно,

Еstoch = £ £   7а/   < 7а/ k < 7LG^zo k/    Tk =1 2(Fk + 7k) < 2 LgTk < 2Nk

v

7L-"

N(N + 1).

r \E 7k j^stoch rvA rkEk/ <

Объединяя эти оценки в (24), получаем cert

Pv,M <

13L g ' z o N (N + 1)

+ O(S k ).

Выберем К так, чтобы S k < N 2, например, рк< (2N 2) 1, что эквивалентно условию

К >

log(2N 2) - log р

о (К).

Тогда O(Sk ) = O(N 2). а выбор

N = О

К = о (^)

обеспечивает G’ /cv ^ Tt = О(е), что доказывает заявленную сложность.

7.5.    Доказательство леммы 7

Доказательство. Зафиксируем z G Z. Из монотонности Н следует (н(дрге),^рге - z^ >  ^H^(z),zk pre - z^ для всех k,t.

Умножая на Xk,t, суммируя и используя У^ Xk,t = 1 и zOUt = J^ Xk,tx^ e получаем k,t                             k,t

N Tk

EEXk,t H r k=1t=1

zt pre - z) » Н(z^ u - z ) .

Добавляя G(zNUt) - G(z) и переходя к супремуму по z G Z, получаем

Gap^ t ) <  Q^

Стохастическая версия следует из того же поточечного неравенства после взятия математического ожидания и последующего перехода к супремуму по z. Лемма доказана.

Работа выполнена при поддержке гранта Российского научного фонда № 23-11-00229, /