Автоматика и телемеханика, № 9, 2019

(Институт проблем управления им. В.А. Трапезникова РАН, Москва),

А.С. НЕМИРОВСКИЙ, д-р физ.-мат. наук (nemirovs@isye.gatech.edu)

(ISyE, Технологический институт Джорджии, Атланта, США),

А.Б. ЦЫБАКОВ, д-р физ.-мат. наук (alexandre.tsybakov@ensae.fr)

(CREST, ENSAE, Франция),

А.Б. ЮДИЦКИЙ, канд. техн. наук (anatoli.juditsky@univ-grenoble-alpes.fr)

(LJK, Университет Гренобль Альпы, Гренобль, Франция)

АЛГОРИТМЫ РОБАСТНОЙ СТОХАСТИЧЕСКОЙ ОПТИМИЗАЦИИ

НА ОСНОВЕ МЕТОДА ЗЕРКАЛЬНОГО СПУСКА¹

Предлагается подход к построению робастных неевклидовых итератив-

ных алгоритмов выпуклой композитной стохастической оптимизации, ос-

нованный на усечении стохастических градиентов. Для таких алгорит-

мов устанавливаются субгауссовские доверительные границы точности

при слабых предположениях о хвостах распределения шума в выпуклой

и сильно выпуклой постановках. Также предлагаются робастные оценки

точности стохастических алгоритмов общего вида.

Ключевые слова: робастные итеративные алгоритмы, алгоритмы стоха-

стической оптимизации, выпуклая композитная стохастическая оптими-

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

DOI: 10.1134/S000523101909006X

1. Введение

В данной статье рассматривается задача выпуклой композитной стоха-

стической оптимизации

(1)

min

F (x), F (x) = E{Φ(x, ω)} + ψ(x),

x∈X

где X — компактное выпуклое подмножество конечномерного векторного

пространства E с нормой ∥ · ∥, ω — случайная переменная на вероятностном

пространстве Ω с распределением P , функция ψ выпуклая и непрерывная,

а функция Φ : X × Ω → R. Предполагается, что математическое ожидание

∫

φ(x) := E{Φ(x, ω)} = Φ(x, ω)dP (ω)

¹ Работа А.Б. Юдицкого поддержана грантом PGMO

2016-2032H и совместно

А.Б. Юдицкого с А.С. Немировским — грантом NSF CCF-1523768. Работа А.В. Назина

поддержана Российским научным фондом (грант №16-11-10015). Работа А.Б. Цыбакова

поддержана институтом GENES и грантом Labex Ecodec (ANR-11-LABEX-0047).

конечно при всех x ∈ X и является выпуклой и дифференцируемой функцией

от x. При этих предположениях задача (1) имеет решение с оптимальным

значением F_∗ = min_x∈X F (x).

Предполагается, что доступен механизм (оракул), который для заданной

на входе точки (x, ω) ∈ X × Ω возвращает случайный градиент — вектор

G(x, ω), удовлетворяющий условиям

{

}

(2)

E{G(x, ω)} = ∇φ(x) и E

∥G(x, ω) - ∇φ(x)∥2∗

≤σ²

∀x∈X,

где ∥ · ∥_∗ — сопряженная норма к ∥ · ∥, а σ > 0 — некоторая постоянная. Цель

данной работы состоит в построении (1 - α)-надежных приближенных реше-

ний задачи (1), т.е. решений x_N , основанных на N вызовах стохастического

оракула и удовлетворяющих условию

(3)

Prob{F(x_N ) - F^∗ ≤ δ_N

(α)} ≥ 1 - α,

∀α ∈ (0,1),

с насколько возможно малым δ_N (α) > 0.

Заметим, что задачи стохастической оптимизации типа (1) возникают в

контексте минимизации пенализованного риска, где доверительные грани-

цы (3) напрямую преобразуются в доверительные границы для точности по-

лучаемых оценок. В этой статье отыскиваются границы (3) с δ_N (α) порядка

√

ln(1/α)/N . Такие границы часто называют субгауссовскими доверитель-

ными границами. Стандартные результаты о субгауссовских доверительных

границах для алгоритмов стохастической оптимизации предполагают конеч-

ность экспоненциальных или субэкспоненциальных моментов стохастическо-

го шума оракула G(x, ω)- ∇φ(x) (ср. [1-3]). В настоящей работе строятся ро-

бастные стохастические алгоритмы, которые удовлетворяют субгауссовским

границам типа (3) при существенно менее ограничительном условии (2).

Напомним, что понятие робастности процедур принятия статистических

решений было введено Дж. Тьюки [4] и П. Хубером [5-7] в 1960-е гг., что по-

служило основой для последующей разработки робастных алгоритмов стоха-

стической аппроксимации. В частности, в 1970-1980-х гг. алгоритмы, устой-

чивые к широким классам распределений шумов, были предложены для

задач стохастической оптимизации и параметрической идентификации. Их

асимптотические (с ростом размера выборки) свойства были хорошо изучены,

см., например, [8-16] и ссылки в них. Важный вклад в развитие робастного

подхода внес Я.З. Цыпкин. Так, исследованию итеративных алгоритмов ро-

бастной идентификации уделено значительное место в монографиях [17, 18].

Интерес к проблематике робастного оценивания возобновился в 2010-х

гг. в связи с необходимостью разработки статистических процедур, устойчи-

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

торые недавние работы [19-29] связаны с развитием метода медианы сред-

них (median-of-means) [30] для построения оценок, удовлетворющих субгаус-

совским доверительным границам при шумах с тяжелыми хвостами. Так,

в [27] была использована процедура median-of-means для построения (1 - α)-

надежной версии стохастической аппроксимации с усреднением (“пакетного”

алгоритма) в постановке стохастической оптимизации, подобной (1). Были

разработаны и другие оригинальные подходы [31-35], в частности, исполь-

зующие геометрическую медиану для робастной оценки сигналов и ковариа-

ционных матриц с субгауссовыми гарантиями [34, 35]. Также возобновился

интерес к робастным итеративным алгоритмам. Так, было показано, что ро-

бастность алгоритмов стохастической аппроксимации может быть повыше-

на за счет использования геометрической медианы стохастических градиен-

тов [36, 37]. Другой вариант процедуры стохастическoй аппроксимации для

вычисления геометрической медианы был изучен в [38, 39], где особая струк-

тура задачи — ограниченность стохастических градиентов — позволила по-

строить (1 - α)-надежные оценки при чрезвычайно слабом предположении о

хвостах распределения шума.

В настоящей статье рассматривается подход к построению робастных сто-

хастических алгоритмов методом усечения стохастических градиентов. По-

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

границам. В разделах 2 и 3 определяются основные компоненты рассмат-

риваемой задачи оптимизации. В разделе 4 дается определение алгоритма

робастного стохастического зеркального спуска и для него устанавливаются

доверительные границы. В разделе 5 строятся робастные оценки точности

для стохастических алгоритмов общего вида. Наконец, в разделе 6 устанав-

ливаются робастные доверительные границы для задач, в которых F име-

ет квадратичный рост. Приложение содержит доказательства утверждений

статьи.

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

Пусть E — конечномерное вещественное векторное пространство с нор-

мой ∥ · ∥, а E^∗ — сопряженное к E пространство. Обозначим через 〈s, x〉

значение линейной функции s ∈ E^∗ в точке x ∈ E и через ∥ · ∥_∗ сопряженную

к ∥ · ∥ норму на E^∗, т.е.

∥s∥_∗ = max{〈s, x〉 : ∥x∥ ≤ 1}, s ∈ E^∗.

Рассмотрим непрерывную выпуклую функцию θ : B → R на единичном шаре

B = {x ∈ E : ∥x∥ ≤ 1},

обладающую следующим свойством:

(4)

θ^′(x) - θ^′(x^′),x - x^′

≥ ∥x - x^′∥²,

∀x,x^′

∈ B,

где θ^′(·) — непрерывная в B^o = {x ∈ B : ∂θ(x) = ∅} версия субградиента θ(·),

а ∂θ(x) — субдифференциал функции θ(·) в точке x, т.е. множество всех суб-

градиентов в данной точке. Иными словами, функция θ(·) сильно выпукла

на B с коэффициентом 1 относительно нормы ∥ · ∥. Будем называть θ(·) нор-

мализованной прокс-функцией. Примерами таких функций являются:

• θ(x) =

∥x∥²² для (E, ∥ · ∥) = (Rⁿ, ∥ · ∥₂);

• θ(x) = 2e(ln n)∥x∥^p при p = p(n) := 1 +

для (E, ∥ · ∥) = (Rⁿ, ∥ · ∥₁);

2 ln n

• θ(x) = 4e(ln n)

^∑ |λ_i(x)|^p при p = p(n), для E = S_n, где S_n — пространство

i=1

∑

симметричных n × n матриц, оснащенное ядерной нормой ∥x∥ =

|λ_i(x)|,

i=1

а λ_i(x) — собственные значения матрицы x.

Здесь и далее через ∥ · ∥_p обозначается ℓ_p-норма в Rⁿ, p ≥ 1. Без ограничения

общности, будем предполагать в дальнейшем, что

0 = arg min θ(x).

x∈B

Введем также обозначение

Θ = maxθ(x) - minθ(x) ≥

x∈B

Пусть теперь X — выпуклое компактное подмножество в E, и пусть x₀ ∈ X

и R > 0 таковы, что max_x∈X ∥x - x₀∥ ≤ R. Снабдим X прокс-функцией

)

⁽x-x₀

ϑ(x) = R²θ

Обратим внимание, что ϑ(·) сильно выпукла с коэффициентом 1 и

maxϑ(x) - min ϑ(x) ≤ R2Θ.

x∈X

Пусть D := max ∥x - x^′∥ — диаметр множества X. Тогда D ≤ 2R.

x,x^′∈X

Далее также понадобится расхождение Брегмана

V_x(z) = ϑ(z) - ϑ(x) - 〈ϑ^′(x),z - x〉,

∀z,x ∈ X.

В дальнейшем через C и C^′ обозначаются положительные числовые констан-

ты, не обязательно одинаковые в различных случаях.

3. Предположения

Рассмотрим выпуклую стохастическую композитную задачу оптимиза-

ции (1) на выпуклом компактном множестве X ⊂ E. В дальнейшем пред-

полагается, что функция

φ(x) = E{Φ(x, ω)}

выпукла на X, дифференцируема в каждой точке множества X и ее градиент

удовлетворяет условию Липшица

(5)

∥∇φ(x^′) - ∇φ(x)∥_∗ ≤ L∥x - x^′∥,

∀ x,x^′

∈ X.

Предположим также, что функция ψ является выпуклой и непрерывной. Да-

лее предположим, что доступен стохастический оракул, который, имея на

входе точку (x, ω) ∈ X × Ω, возвращает случайный вектор G(x, ω), удовле-

творяющий условиям (2). Кроме того, предполагается, что при любых a ∈ E^∗

и β > 0 доступно точное решение задачи на минимум

min {〈a, z〉 + ψ(z) + βϑ(z)} .

z∈X

Это предположение выполняется для типичных штрафных функций ψ, та-

ких как выпуклые степенные функции от ℓ_p-нормы (если X — выпуклый

∑

компакт в Rⁿ) или отрицательная энтропия ψ(x) = κ x_j ln x_j , где k > 0 и

j=1

0 · ln0 = 0 (если X — стандартный симплекс в Rⁿ). Наконец, предполагается,

что доступен вектор g(x), где x ∈ X — некоторая точка в X, такой что

(6)

∥g(x) - ∇φ(x)∥_∗

≤ υσ,

где υ ≥ 0 — некоторая постоянная. Это предположение мотивируется следую-

щим образом.

Во-первых, если априори известно, что глобальный минимум функции φ

достигается во внутренней точке x_φ множества X (что часто имеет место в

статистических приложениях стохастической оптимизации), имеем ∇φ(x_φ) =

= 0. Поэтому, выбирая x = x_φ, можно положить g(x) = 0, и предположе-

ние (6) автоматически выполнено с υ = 0.

Во-вторых, в общей ситуации можно взять в качестве x произвольную точ-

ку множества X и в качестве g(x) геометрическую медиану стохастических

градиентов G(x, ω_i(, i =)1, . . . , m, по m вызовам оракула. Из [34] следует, что

если m порядка ln

ε-1

при некотором достаточно малом ε > 0, то

(7)

Prob{∥g(x) - ∇φ(x)∥_∗

> υσ} ≤ ε.

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

с точностью до поправки ε в вероятности уклонений.

4. Границы точности алгоритма РСЗС

Далее везде считается, что выполнены предположения, сформулирован-

ные в разделе 3. Введем композитное проксимальное преобразование

{

}

Prox_β,x(ξ) := arg min

〈ξ, z〉 + ψ(z) + βV_x(z)

z∈X

{

}

(8)

= arg min

〈ξ - βϑ^′(x), z〉 + ψ(z) + βϑ(z)

z∈X

где β > 0 — параметр настройки.

Для i = 1, 2, . . . определим алгоритм Робастного Стохастического Зер-

кального Спуска (РСЗС) следующими рекуррентными соотношениями:

(9)

x_i = Proxβi-1,xi-1(yi), x0

∈ X,

^{G(xi-1, ωi), если ∥G(xi-1, ωi) - g(x)∥∗ ≤ L∥x - xi-1∥ + λ + υσ,

(10)

y_i =

g(x)

в противном случае.

Здесь β_i > 0, i = 0, 1, . . ., и λ > 0 — параметры настройки, которые будут

определены ниже, а ω₁, ω₂, . . .

— независимые одинаково распределенные

(н.о.р.) реализации случайной величины ω, соответствующие вызовам ора-

кула на каждом шаге алгоритма.

Приближенное решение задачи (1) после N итераций определим как взве-

шенное среднее

[

]-1

∑

(11)

β-1

β-1i-1x_i.

xN =

i-1

i=1

В случае, когда глобальный минимум φ достигается во внутренней точке X

и υ = 0, определение (10) упрощается. В этом случае, заменяя ∥x - xi-1∥ на

верхнюю границу D и полагая υ = 0 и g(x) = 0 в (10), усеченный стохастиче-

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

^{G(xi-1, ω_i), если ∥G(xi-1, ωi)∥∗ ≤ LD + λ,

y_i =

в противном случае.

Следующее утверждение описывает некоторые полезные свойства рекур-

сии зеркального спуска (9). Обозначим:

ξ_i = y_i - ∇φ(xi-1)

∑

(12)

ε(x^N , z) =

β-1i-1[〈∇φ(xi-1),x_i - z〉 + ψ(x_i) - ψ(z)] +

Vxi-1(x_i

i=1

где x^N = (x₀, . . . , x_N ).

Предложение 1. Пусть β_i ≥ 2L при всех i = 0,1,... и пусть x_N опре-

делено в (11), где x_i - итерации (9) при любом y_i, не обязательно заданным

соотношением (10). Тогда для любого z ∈ X имеем

[

]

∑

β-1

[F (x_N ) - F (z)] ≤

β-1i-1[F(x_i) - F(z)] ≤ ε(x^N ,z)

i-1

i=1

]

∑

^[ 〈ξ_i, z - xi-1〉

∥ξ_i∥2∗

(13)

≤ Vx0(z) +

βi-1

β²

i=1

i-1

]

∑

^[ 〈ξ_i, zi-1 - xi-1〉

3 ∥ξ_i∥2∗

(14)

≤ 2Vx0 (z) +

βi-1

2 β²

i-1

i=1

где zi - случайный вектор со значениями в X, зависящий только от

x₀,ξ₁,... ,ξ_i.

Используя предложение 1, получим следующие границы для математическо-

го ожидания ошибки F (x_N ) - F_∗ приближенного решения задачи (1), ос-

нованного на алгоритме РСЗС. В дальнейшем будем обозначать через E{·}

математическое ожидание по распределению ω^N = (ω₁, . . . , ω_N ) ∈ Ω^⊗N .

√

Следствие 1. Обозначим: M = LR. Пусть λ ≥ max{M,σ

N}+υσ и

β_i ≥ 2L при всех i = 0,1,... Пусть x_N - приближенное решение (11), где

x_i - итерации РСЗС, определяемые соотношениями (9) и (10). Тогда

[

]-1 [

(

)]

∑

2Dσ

4σ²

(15)

E{F (x_N )} - F_∗ ≤

β-1

R²Θ +

√

i-1

βi-1

β²

i=1

i-1

В частности, если β_i

β при всех i = 0,1,..., где

{

√

}

(16)

β = max

2L,

√

то выполняются неравенства

{

√

}

{

}

LR²Θ

σR

(17)

E{F (x_N )} - F_∗ ≤

E sup

ε(x^N , z)

≤ C max

√

z∈X

Более того, в этом случае неравенство с явными константами имеет вид

{

√

}

2LR²Θ

4Rσ(1 +

Θ)

2Rσ(1 + 4

Θ)

E{F (x_N )} - F_∗ ≤ max

√

Из этого результата видно, что если порог усечения λ достаточно велик,

то математическое ожидание ошибки предложенного алгоритма оценивает-

ся аналогично математическому ожиданию ошибки стандартного алгоритма

зеркального спуска с усреднением, т.е. алгоритма, в котором стохастические

градиенты берутся без усечения: y_i = G(xi-1, ω_i).

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

горитма.

Теорема 1. Пусть β_i

β ≥ 2L при всех i = 0,1,... и пусть 1 ≤ τ ≤

≤ N/υ²,

{

√

}

(18)

λ = max σ

+ υσ.

Пусть x_N - приближенное решение (11), где x_i - итерации РСЗС, опреде-

ляемые соотношениями (9) и (10). Тогда существует случайное событие

A_N ⊂ Ω^⊗N вероятности не менее 1 - 2e^-τ такое, что при всех ω^N ∈ A_N

выполняется неравенство

F(x_N) - F_∗ ≤

sup ε(x^N ,z) ≤

z∈X

(

{

√

}

)

≤

βR²Θ + R max σ

τN,Mτ

β-1 max{Nσ²,M²τ}

В частности, выбира

β по формуле (16), при всех ω^N ∈ A_N имеем

{

√

}

LR²[τ ∨ Θ]

τ∨Θ

(19)

F(x_N ) - F_∗ ≤ max C₁

, C₂σR

где C₁ > 0 и C₂ > 0 — числовые постоянные.

Значения постоянных C₁ и C₂ в (19) можно получить из доказательства

теоремы, ср. границу в (Π.12).

Доверительная граница (19) в теореме 1 содержит два члена, соответст-

вующие детерминированной и случайной ошибкам. В отличие от случая шу-

ма с “легким хвостом” (см., например, [40]) и от границы в среднем (17) де-

терминированная ошибка LR²[τ ∨ Θ]/N зависит от τ. Заметим также, что

теорема 1 дает субгауссовскую доверительную границу (ср. порядок стохас-

√

тической ошибки σR

[τ ∨ Θ]/N). Однако при этом порог усечения λ зави-

сит от доверительного уровня τ. Это может быть неудобно при реализации

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

могут быть получены, если ис√льзовать универсальный порог, не завися-

щий от τ, а именно, λ = max{σ

N,M} + υσ. В частности, верно следующее

утверждение.

Теорема 2. Пустьβ_i

β ≥ 2L при всех i = 0,1,... и пусть N ≥ υ². По-

ложим

{

}

√

λ = max σ

N,M

+ υσ.

Пусть

∑

xN = N-1 xi,

i=1

где x_i - итерации РСЗС, определяемые соотношениями (9) и (10). Тогда

существует случайное событие A_N ⊂ Ω^⊗N вероятности не менее 1 - 2e^-τ

такое, что при всех ω^N ∈ A_N выполняется неравенство

F(x_N) - F_∗ ≤

sup ε(x^N ,z) ≤

z∈X

(

{

}

)

√

≤

βR²Θ + τR max σ

N,M

β-1 max{Nσ²,M²}

В частности, выбира

β по формуле (16), при всех ω^N ∈ A_N имеем

{

√

}

LR²[τ ∨ Θ]

(20)

F(x_N ) - F_∗ ≤

sup

ε(x^N , z) ≤ C max

, τσR

z∈X

Значения числовых постоянных C в теореме 2 можно получить из ee доказа-

тельства, ср. границу в (Π.12).

5. Робастные доверительные границы

для методов стохастической оптимизации

Рассматриваются произвольные алгоритмы решения задачи (1) по N

(ызовам стох)стического оракула. Пусть имеется последовательность

x_i,G(x_i,ωi+1)

, i = 0,...,N, где x_i ∈ X — точки поиска некоторого сто-

хастического алгоритма, а G(x_i, ωi+1)

— соответствующие наблюдения

стохастического градиента. Предполагается, что x_i зависит только от

{(xj-1, ω_j ), j = 1, . . . , i}. Приближенное решение задачи (1) определим в виде:

∑

xN = N-1 xi.

i=1

Целью является построение доверительного интервала субгауссовской точно-

сти для величины F (x_N ) - F_∗. Для этого воспользуемся следующим фактом.

Заметим, что для любого t ≥ L значение

{

}

∑[

]

(21) ϵ_N (t) = N-1 sup

〈∇φ(xi-1), x_i - z〉 + ψ(x_i) - ψ(z) + tVxi-1 (x_i)

z∈X i=1

является верхней границей точности приближенного решения x_N :

(22)

F(x_N) - F_∗ ≤ ϵ_N

(t)

(см. лемму 1 в Приложении). Этот факт верен для любой последовательности

точек x₀, . . . , x_N в X вне зависимости от того, как они получены. Однако

поскольку функция ∇φ(·) не известна, оценка (22) на практике не реализуема.

Заменяя в (21) градиенты ∇φ(xi-1) на их усеченные оценки y_i, определенные

в (10), получим реализуемый аналог величины ϵ_N (t):

{

}

∑[

]

(23)

ϵN (t) = N-1 sup

〈y_i, x_i - z〉 + ψ(x_i) - ψ(z) + tVxi-1 (x_i)

z∈X i=1

Заметим, что вычисление ϵ_N (t) сводится к решению задачи вида (8) с β = 0.

Таким образом, оно не сложнее, чем, например, один шаг алгоритма РСЗС.

Замена ∇φ(xi-1) на y_i вносит случайную ошибку, для компенсации которой

необходимо несколько увеличить ϵ_N (t), чтобы получить надежную верхнюю

границу для ϵ_N (t). А именно, добавим к ϵ_N (t) величину

{

}

√

ρN (τ) = 4R

5Θ max{Nσ², M²τ} + 16R max σ

Nτ,Mτ

{

}

∑

+ min

20μ max{Nσ², M²τ} + μ-1

Vxi-1(x_i)

μ≥0

i=1

где τ > 0.

(

)_N

Предложение 2. Пусть

x_i,G(x_i,ωi+1)

— траектория стохасти-

i=0

ческого алгоритма, для которого x_i зависит только от

{(xj-1, ω_j ),

j = 1,...,i}. Пусть 0 < τ ≤ N/υ² и пусть y_i = y_i(τ) — усеченные стохасти-

ческие градиенты, определенные в (10), где порог λ = λ(τ) выбран в виде (18).

Тогда при любом t ≥ L величина

Δ_N(τ,t) = ϵ_N(t) + ρ_N(τ)/N

является верхней границей для ϵ_N (t) с вероятностью 1 - 2e^-τ , так что

{

}

Prob

F(x_N) - F_∗ ≤ Δ_N(τ,t)

≥ 1 - 2e^-τ.

Так как Δ_N (τ, t) монотонно возрастает по t, поэтому L известно, то доста-

точно использовать эту границу при t = L. Заметим, что хотя Δ_N (τ, t) и

дает верхнюю границу для ϵ_N (t), предложение 2 не гарантирует, что Δ_N (τ, t)

достаточно близко к ϵ_N (t). Тем не менее для алгоритма РСЗС с постоян-

ным шагом это свойство имеет место, как явствует из следующего утверж-

дения.

Следствие 2. Пусть в условиях предложения 2 векторы x₀,...,x_N за-

даются соотношениями РСЗС рекурсии (9)-(10), где β_i

β ≥ 2L, i = 0,

...,N - 1. Тогда

√

ρN (τ) ≤ NϵN

β) + 4R

5Θ max {Nσ², M²τ} +

{

}

√

{

}

(24)

+16R max σ

Nτ,Mτ

+ 2

β-1 max

Nσ²,M²τ

Если, более того,

{

√

}

β ≥ max

2L,

√

то

√

ρN (τ) ≤ NϵN

β) + C₃LR²[Θ ∨ τ] + C₄σR

N [Θ ∨ τ],

исвероятностьюнеменее1-4e^-τ величинаΔ_N(τ

β) удовлетворяет нера-

венствам

√

LR²[Θ ∨ τ]

[Θ ∨ τ]

(25)

ϵ_N

β) ≤ Δ_N(τ

β)≤3ϵ_N

β) + 2C₃

+ 2C₄σR

где C₃ > 0 и C₄ > 0 — числовые постоянные.

Значения постоянных C₃ и C₄ можно вывести из доказательства данного

следствия.

6. Робастные доверительные границы для задач

с квадратичным ростом

В этом разделе предполагается, что F — функция квадратичного роста

на X в следующем смысле (ср. [41]). Пусть функция F непрерывна на X и

пусть X_∗ ⊂ X — множество ее точек минимума на X. Тогда F называется

функцией квадратичного роста на X, если существует постоянная κ > 0 та-

кая, что для любого x ∈ X найдется x(x) ∈ X_∗, для которого выполняется

неравенство

(26)

F (x) - F_∗ ≥

∥x - x(x)∥².

Заметим, что всякая сильно выпуклая на X функция F с коэффициентом

сильной выпуклости κ является функцией квадратичного роста на X. Однако

предположение о сильной выпуклости, если одновременно с ним накладывать

еще и условие Липшица с константой L на градиент F , имеет тот недоста-

ток, что за исключением случая, когда ∥ · ∥ является евклидовой нормой,

отношение L/κ зависит от размерности пространства E. Например, в важ-

ных случаях, когда ∥ · ∥ является ℓ₁-нормой, ядерной нормой, нормой полной

вариации, и ряде других, можно легко проверить (ср. [2]), что не существу-

ет функции с липшицевым градиентом, для которой отношение L/κ было бы

меньше, чем размерность пространства. Замена сильной выпуклости на усло-

вие роста (26) устраняет эту проблему, см. примеры в [41]. С другой стороны,

предполагать (26) в задаче композитной оптимизации вполне естественно по

той причине, что во многих интересных примерах составляющая φ гладкая,

а негладкая часть ψ целевой функции сильно выпуклая. В частности, ес-

ли E = Rⁿ и норма ∥ · ∥ является ℓ₁-нормой, это позволяет рассматривать

такие сильно выпуклые компоненты, как отрицательная энтропия ψ(x) =

∑

= κ x_j lnx_j (если X — стандартный симплекс в Rⁿ), ψ(x) = γ(κ)∥x∥^p с

j=1

1 ≤ p ≤ 2 и соответствующим выбором γ(κ) > 0 (если X — выпуклый ком-

пакт в Rⁿ) и др. Во всех этих случаях условие (26) выполнено с известной

постоянной κ, что позволяет применять подход [2, 42] для улучшения дове-

рительных границ стохастического зеркального спуска.

Алгоритм РСЗС для квадратично растущих функций определим поэтап-

но. На каждом этапе для специально подобранных r > 0 и y ∈ X решается

вспомогательная задача

min F (x)

x∈Xr(y)

с использованием РСЗС. Здесь

X_r(y) = {x ∈ X : ∥x - y∥ ≤ r}.

Инициализируем алгоритм, выбирая произвольные y₀ = x₀ ∈ X и r₀ ≥

≥ max∥z - x0∥. Положим r2k = 2-kr20, k = 1, 2, . . . Пусть C1 и C2 — число-

z∈X

вые постоянные в границе (19) теоремы 1. Для заданного параметра τ > 0 и

k = 1,2,... определим значения

{

}

L[τ ∨ Θ]

σ²[τ ∨ Θ]

(27)

N_k = max

4C₁

, 16C₂

, N_k =⌋N_k

⌊.

κ²r²

k-1

Здесь ⌋t⌊ — наименьшее целое число, большее или равное t > 0. Обозначим:

⎧

⎫

⎨ ∑k

⎬

m(N) := max

N_j ≤ N

⎩

⎭

j=1

Пусть теперь k ∈ {1, 2, . . . , m(N)}. На k-м этапе алгоритма решаем задачу ми-

нимизации F на множестве Xrk-1 (yk-1), вычисляем ее приближенное реше-

ние xNk в соответствии с (9)-(11), где заменяем x₀ на yk-1, X на Xrk-1 (yk-1),

R на rk-1, N на N_k, и полагаем

{

√

}

N_k

λ = max σ

,Lrk-1

+ υσ

{

}

σ√Nk

β_i ≡ max

2L,

√

rk-1

Предполагается, что на каждом этапе k алгоритма доступно точное решение

задачи минимизации

min

{〈a, z〉 + ψ(z) + βϑ(z)}

z∈Xrk-1 (yk-1)

при любых a ∈ E и β > 0. На выходе k-го этапа алгоритма получаем y_k:=xNk .

Теорема 3. Предположим, что m(N) ≥ 1, т.е. хотя бы один этап опи-

санного выше алгоритма завершен. Тогда существует случайное событие

Bm(N)⊂Ω^⊗N вероятности не менее 1-2m(N)e^-τ такое, что для ω^N ∈ Bm(N)

приближенное решение ym(N) после m(N) этапов алгоритма удовлетворяет

неравенству

{

(

)

}

C^′κN

σ²[τ ∨ Θ]

(28)

F (ym(N)) - F_∗ ≤ C max κr²⁰2-N/4, κr²⁰ exp

L[τ ∨ Θ]

κN

Теорема 3 показывает, что для функций квадратичного роста можно суще-

ственно уменьшить детерминированную составляющую ошибки, сделав ее

экспоненциально убывающей по N. Стохастическая составляющая ошибки

также существенно уменьшается. Заметим, что множитель m(N) логариф-

мического порядка слабо влияет(на вероя)ность уклонений. Действительно,

C^′κ²r²⁰N

из (27) следует, что m(N) ≤ C ln

. Пренебрегая этим множителем в

σ²(τ∨Θ)

вероятности уклонений и рассматривая стохастическую составляющую ошиб-

ки, видим, что доверительная граница теоремы 3 является приближенно суб-

экспоненциальной, а не субгауссовской.

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

Рассмотрены алгоритмы гладкой стохастической оптимизации в ситуации,

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

что при усечении наблюдений градиента c соответствующим порогом мож-

но построить доверительные множества для приближенных решений, анало-

гичные имеющимся в случае “легких хвостов”. Стоит отметить, что порядок

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

ным — он значительно больше оптимальных оценок (O(LR²N-2) в случае

√

выпуклой целевой функции и O(exp(-N

κ/L)) в сильно выпуклом случае),

достигаемых ускоренными алгоритмами [3, 40]. С другой стороны, предлага-

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

горитмов, так как при его применении для таких алгоритмов накапливается

смещение, вносимое усечением градиентов. Задача построения ускоренных

робастных стохастических алгоритмов с оптимальными гарантиями остается

открытой.

ПРИЛОЖЕНИЕ

П.1. Предварительные замечания. Начнем со следующего известного ре-

зультата.

Лемма 1. Предположим, что φ и ψ удовлетворяют предположениям

раздела 3, и пусть x₀, . . . , x_N - некоторые точки множества X. Обозначим:

εi+1(z) := 〈∇φ(x_i),xi+1 - z〉 + 〈ψ^′(xi+1),xi+1 - z〉 + LVxi(xi+1).

Тогда для любого z ∈ X выполнено неравенство

F (xi+1) - F (z) ≤ εi+1(z).

∑

Кроме того, для x_N =1N x_i имеем

i=1

∑

F(x_N ) - F(z) ≤ N-1

[F (x_i) - F(z)] ≤ N-1

εi+1(z).

i=1

i=0

Доказательство. Используя свойство V_x(z) ≥ ¹²∥x - z∥², выпуклость

функций φ и ψ и условие Липшица на ∇φ, для любого z ∈ X будем иметь:

F (xi+1) - F (z) = [φ(xi+1) - φ(z)] + [ψ(xi+1) - ψ(z)] =

= [φ(xi+1) - φ(x_i)] + [φ(x_i) - φ(z)] + [ψ(xi+1) - ψ(z)] ≤

≤ [〈∇φ(x_i), xi+1 - x_i〉 + LVxi (xi+1)] +

+ 〈∇φ(x_i), x_i - z〉 + ψ(xi+1) - ψ(z) ≤

≤ 〈∇φ(x_i), xi+1 - z〉 + 〈ψ^′(xi+1), xi+1 - z〉 + LVxi (xi+1) =

= εi+1(z).

Просуммировав эту границу по i от 0 до N - 1 и воспользовавшись выпук-

лостью F , получим второе утверждение леммы.

□

В дальнейшем будем обозначать через Exi {·} условное математическое

ожидание при фиксированном x_i.

Лемма 2. Пусть выполнены предположения раздела 3 и пусть x_i и y_i

удовлетворяют рекурсии РСЗС, ср. (9) и (10). Тогда

(a)

∥ξ_i∥_∗ ≤ 2(M + υσ) + λ,

)₂

⁽σ

σ²

(Π.1)

(b)

∥Exi-1 {ξ_i}∥_∗ ≤ (M + υσ)

Доказательство. Обозначим χ_i = 1{∥G(xi-1,ω_i)-g(x)∥∗>L∥xi-1-x∥+λ+υσ}^.

Заметим, что по построению χ_i ≤ η_i := 1{∥G(xi-1,ω_i)-∇φ(xi-1)∥∗>λ}^.Имеем

ξ_i = y_i - ∇φ(xi-1) = [G(xi-1,ω_i) - ∇φ(xi-1)](1 - χ_i) + [g(x) - ∇φ(xi-1)]χ_i =

= [G(xi-1, ω_i) - g(x)](1 - χ_i) + [g(x) - ∇φ(xi-1)] =

= [G(xi-1, ω_i) - ∇φ(xi-1)] + [g(x) - G(xi-1, ω_i)]χ_i.

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

∥ξ_i∥_∗ ≤ ∥G(xi-1, ω_i) - g(x)∥_∗(1 - χ_i) + ∥g(x) - ∇φ(xi-1)∥_∗ ≤ 2(M + υσ) + λ.

Кроме того, поскольку Exi-1 {G(xi-1, ω_i)} = ∇φ(xi-1), имеем



Ex



∥Exi-1 {ξ_i}∥_∗ =

{[(G(xi-1, ω_i) - ∇φ(xi-1)) - (g(x) - ∇φ(xi-1))]χ_i}

≤

i-1

∗

≤ Exi-1{[∥G(xi-1,ω_i) - ∇φ(xi-1)∥_∗ + ∥g(x) - ∇φ(xi-1)∥_∗]χ_i} ≤

}

≤ Exi-1{∥G(xi-1,ω_i) - ∇φ(xi-1)∥_∗ς_i

+ (M + υσ)Exi-1{ς_i} ≤

)₂

⁽σ

≤

+ (M + υσ)

Далее,

∥ξ_i∥_∗ ≤ ∥G(xi-1, ω_i) - ∇φ(xi-1)∥_∗(1 - χ_i) + ∥g(x) - ∇φ(xi-1)∥_∗χ_i

{

}1/2

Exi-1{∥ξ_i∥2∗}1/2 ≤ Exi-1

∥G(xi-1, ω_i) - ∇φ(xi-1)∥2∗

{

}1/2

+ Exi-1

∥g(x) - ∇φ(xi-1)∥2∗χ_i

≤

≤ σ + (M + υσ)E{χ_i}1/2 ≤ σ + (M + υσ)Exi-1{η_i}1/2 ≤

≤ σ + (M + υσ)

□

∑

В следующей лемме даются границы для отклонений сумм

〈ξ_i, xi-1 - z〉 и

^∑ ∥ξ_i∥2∗.

Лемма 3. Пусть выполнены предположения раздела 3 и пусть x_i и y_i

удовлетворяют рекурсии РСЗС, ср. (9) и (10).

{ √

}

(i) Если τ ≤ N/υ² и λ = max σ^Nτ , M

+ υσ, то для произвольного z ∈ X

{

}

∑

√

(Π.2)

Prob

〈ξ_i, z - xi-1〉 ≥ 16R max{σ

Nτ,Mτ}

≤e^-τ

i=1

{

}

∑

(Π.3)

Prob

∥ξ_i∥2∗ ≥ 40 max{Nσ², M²τ}

≤e^-τ.

i=1

{

}

√

(ii) Если N ≥ υ² и λ = max σ

N,M

+ υσ, то для произвольного z ∈ X

{

}

∑

√

(Π.4)

Prob

〈ξ_i, z - xi-1〉 ≥ 8(1 + τ)R max{σ

N,M}

≤e^-τ

i=1

{

}

∑

(Π.5)

Prob

∥ξ_i∥2∗ ≥ 8(2 + 3τ) max{Nσ², M²}

≤e^-τ.

i=1

Доказательство. Положим ζ_i = 〈ξ_i,z - xi-1〉 и ς_i = ∥ξ_i∥2∗, i = 1,2,...

Используя лемму 2, нетрудно проверить, что выполняются неравенства

[

]

(a)

|Exi-1 {ζ_i}| ≤ D

(M + υσ)(σ/λ)² + σ²/λ

(Π.6)

(b)

|ζ_i| ≤ D[2(M + υσ) + λ],

(a)

Exi-1{ς_i} ≤ [σ + (M + υσ)σ/λ]²,

(Π.7)

(b)

ς_i ≤ [2(M + υσ) + λ]²,

Далее несколько раз применяется неравенство Бернштейна и каждый раз

используются одинаковые обозначения r, A, s для величин, которые задают

равномерные верхние оценки для соответственно математического ожидания,

максимального модуля и среднеквадратического уклонения случайных вели-

чин.

√

1^o. Докажем сначала утверждение (i). Начнем со случая M ≤ σ^Nτ .

Из (Π.6) следует, что в этом случае

^√τ

|Exi-1 {ζ_i}| ≤ 2Dσ²/λ ≤ 4Rσ

=: r,

(Π.8)

|ζ_i| ≤ A := 3λD ≤ 6Rλ,

(Exi-1 {ζ2i})1/2 ≤ s := 2Dσ ≤ 4Rσ.

Используя (Π.8) и неравенство Бернштейна для мартингалов (см., напри-

мер, [43]), получим

{

}

{

}

∑

√

∑

√

Prob

ζ_i ≥ 16Rσ

Nτ

≤ Prob

ζ_i ≥ Nr + 3s

Nτ

≤

i=1

⎧

⎫

⎨

⎬

9τ

≤ exp

≤

⎩

√τA

⎭

2+²³

√

3 s

{

}

9τ

≤ exp

(

√

)

≤e^-τ

2+3

1+υ

τ /N

для всех τ > 0, удовлетворяющих условию τ ≤ 16N/(9υ²). С другой стороны,

в рассматриваемом случае выполняются неравенства (ср. (Π.7) и (Π.8))

})1/2 ≤ 6λσ_%&'( .

&'(^,ςi

%&'(,(Exi-1^{

=:r

=:A

=:s

Таким образом,

√

Nr + 3s

τN = 4Nσ² + 18λσ

τN = 22Nσ² + 18υσ²

Nτ ≤ 40Nσ²

для 0 < τ ≤ N/υ². Применяя снова неравенство Бернштейна, получим

{

}

{

}

∑

9τ

Prob

ς_i

≥ 40Nσ²

≤ exp

(

√

)

≤e^-τ

3 + 3υ

τ /N

i=1

для всех τ > 0, удовлетворяющих условию τ ≤ N/υ².

√

2^o. Предположим теперь, что M > σ^Nτ , так что λ = M + υσ и σ²

≤

≤ M²τ/N. Тогда

|Exi-1 ζ_i| ≤ 4Rσ²/λ ≤ 4RMτ/N,

|ζ_i| ≤ R(2(M + υσ) + λ) = 6R(M + υσ),

% &'

(

=:r

=:A

√

(Exi-1 {ζ2i})1/2 ≤ 4Rσ ≤ 4MR

τ /N

(

=:s

Далее,

√

Nr + 3s

τN = 4RMτ + 12RMτ = 16RMτ,

и, снова применяя неравенство Бернштейна, получим

⎧

⎫

{

}

∑

⎨

⎬

9τ

Prob

ζ_i ≥ 16RMτ

≤ exp

≤

⎩

3√τA

⎭

√

i=1

3 s

{

}

9τ

≤ exp

(

)

≤

3 + 3υσ/M

{

}

9τ

≤ exp

√

≤e^-τ

5 + 3υ

τ /N

для всех τ > 0, удовлетворяющих условию τ ≤ 16N/(9υ²). Кроме того, в рас-

сматриваемом случае

√

Exi-1 {ς_i} ≤ 4σ² ≤ 4τM²/N

})1/2 ≤ 6λσ%&'( ≤ 6λM

τ /N.

&'(,(Exi-1^{

% &'

(

=:A

=:s

=:r

Теперь

√

Nr + 3s

τN = 4τM² + 18λσ

τN ≤ 22M²τ + 18υσ²

Nτ ≤ 40M²τ

при 0 < τ ≤ N/υ². Применяя еще раз неравенство Бернштейна, получим

{

}

{

}

∑

9τ

Prob

ς_i

≥ 40τM²

≤ exp

(

√

)

≤e^-τ

3 + 3υ

τ /N

i=1

для всех τ > 0, удовлетворяющих условию τ ≤ N/υ².

√

3^o. Теперь рассмотрим случай λ = max{M,σ

N}+συ, и пусть M ≤ σ

√

так что λ = σ(

N + υ). Рассуждаем точно так же, как в доказательстве (i).

В силу (Π.6) имеем

|Exi-1 {ζ_i}| ≤ 4R√

=: r,

(Exi-1 {ζ2i})1/2 ≤ 4Rσ =: s,

√

|ζ_i| ≤ 6Rλ ≤ 12Rσ

N = 3s

так что, используя неравенство Бернштейна, получим

{

}

{

}

∑

√

∑

√

Prob

ζ_i ≥ 8Rσ

N (τ + 1)

≤ Prob

ζ_i ≥ Nr + (2τ + 1)s

≤

i=1

{

}

{

}

(2τ + 1)²s²N

(2τ + 1)

≤ exp

≤e^-τ.

2s²N +²³ 3s²N(2τ + 1)

2 + 2(2τ + 1)

Из (Π.7) также имеем

&'(^,

=:r

√

(Exi-1 {ς2i})1/2 ≤ 6λσ ≤ 12σ²

N =: s,

√

ς_i ≤ 9λ² ≤ 36σ²N = 4s

Теперь, снова применив неравенство Бернштейна, получим

{

}

{

}

∑

√

Prob

ς_i ≥ 16Nσ² + 24Nσ²τ

= Prob

ς_i ≥ Nr + (2τ + 1)s

≤

i=1

{

}

(2τ + 1)s²N

≤ exp

≤e^-τ.

[2 + 2(2τ + 1)]s²N

√

Доказательство границ (Π.4) и (Π.5) в случае M > σ

N и λ = M + συ вы-

текает из таких же рассмотрений.

□

П.2. Доказательство предложения 1. Докажем сначала неравенство (13).

Ввиду (8) условие оптимальности в (9) имеет вид

〈yi+1 + ψ^′(xi+1) + β_i[ϑ^′(xi+1) - ϑ^′(x_i)], z - xi+1〉 ≥ 0, ∀z∈X,

или в эквивалентной форме

〈yi+1 + ψ^′(xi+1), xi+1 - z〉 ≤ β_i〈[ϑ^′(xi+1) - ϑ^′(x_i)], z - xi+1〉 =

= 〈β_iV ^′x

(xi+1), z - xi+1〉 =

= β_i[Vxi(z) - Vxi+1(z) - Vxi(xi+1)],

∀z∈X,

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

(см., например, [44]): для любых u, u^′ и w ∈ X

〈V^′u(u^′), w - u^′〉 = V_u(w) - V_u′ (w) - V_u(u^′).

Принимая во внимание определение ξ_i = y_i - ∇φ(xi-1), получим

〈∇φ(x_i), xi+1 - z〉 + 〈ψ^′(xi+1), xi+1 - z〉 ≤ β_i[Vxi (z) - Vxi+1 (z) - Vxi (xi+1)] -

(Π.9)

-〈ξi+1, xi+1

− z〉.

Из леммы 1 и условия β_i ≥ 2L следует, что

F (xi+1) - F (z) ≤ εi+1(z) ≤

β_i

≤ 〈∇φ(x_i), xi+1 - z〉 + 〈ψ^′(xi+1), xi+1 - z〉 +

Vxi(xi+1).

Вместе с (Π.9) это неравенство влечет, что

[

]

εi+1(z) ≤ β_i Vxi(z) - Vxi+1(z) -

Vxi(xi+1)

- 〈ξi+1, xi+1 - z〉.

С другой стороны, благодаря сильной выпуклости V_x(·) имеем

β_i

〈ξi+1, z - xi+1〉 -

Vxi (xi+1) = 〈ξ_i,z - x_i〉 + 〈ξi+1,x_i - xi+1〉 -

Vxi(xi+1)

∥ξi+1∥2∗

≤ 〈ξi+1, z - x_i〉 +

β_i

Соединяя эти неравенства, получим, что

F (xi+1) - F (z) ≤ εi+1(z) ≤

(Π.10)

∥ξi+1∥2∗

≤ β_i[Vxi(z) - Vxi+1(z)] - 〈ξi+1,x_i - z〉 +

β_i

при всех z ∈ X. Деля (Π.10) на β_i и затем суммируя по i от 0 до N - 1,

получим (13).

Докажем теперь границу (14). Применяя лемму 6.1 из [1] с z₀ = x₀, будем

иметь

∑

(Π.11)

∀z ∈ X,

β-1i-1〈ξ_i,z - zi-1〉 ≤ Vx0 (z) +

β-2i-1∥ξ_i∥2∗,

i=1

{

}

где z_i = arg min_z∈X

μi-1〈ξ_i,z〉 + Vzi-1 (z)

зависит только от z₀, ξ₁, . . . , ξ_i. Да-

лее,

∑

β-1i-1〈ξ_i,z - xi-1〉 =

β-1i-1[〈ξ_i,zi-1 - xi-1〉 + 〈ξ_i,z - zi-1〉] ≤

i=1

∑

≤ Vx0(z) +

β-1i-1〈ξ_i,zi-1 - xi-1〉 +

β-2i-1∥ξ_i∥2∗.

i=1

Соединяя это неравенство с (13), получим (14).

□

П.3. Доказательство следствия 1. Заметим, что (15) является непосред-

ственным следствием (13) и оценок для моментов ∥ξ_i∥_∗, приведенных в лем-

ме 2. В самом деле, (Π.1)(b) влечет, что в условиях следствия 1

[

]

)₂

⁽σ

σ²

2Dσ²

2Dσ

|Exi-1 {〈ξ_i, z - xi-1〉}| ≤ D (M + υσ)

≤

√

Далее, ввиду (Π.1)(c)

Exi-1{∥ξ_i∥2∗}1/2 ≤ σ + (M + υσ)

≤ 2σ.

Беря математическое ожидание от обеих частей (13) и используя два по-

следних неравенства, получим (15). Граница (17) доказывается аналогич-

ным образом, с той лишь разницей, что вместо неравенства (13) использу-

ется (14).

□

П.4. Доказательство теоремы 1. В силу утверждения (i) леммы 3 при

условии τ ≤ N/υ² с вероятностью не менее 1 - 2e^-τ имеем

∑

√

〈ξ_i, zi-1 - xi-1〉 ≤ 16R max{σ

Nτ,Mτ},

i=1

∑

∥ξ_i∥2∗ ≤ 40 max{Nσ², M²τ}.

i=1

Подставляя эти оценки в неравенство (14), получим, что с вероятностью не

менее 1 - 2e^-τ верно следующее:

[

]

∑

β sup ε(x^N ,z) ≤

βVx0(z) +

〈ξ_i, zi-1 - xi-1〉 +

β-1∥ξ_i∥²

∗

≤

z∈X

i=1

√

≤

βR²Θ + 16R max{σ

Nτ,Mτ}+6

β-1 max{Nσ²,M²τ}.

√

{

}

Далее, полага

β = max

2L,σNRΘ

, будем иметь

√

N [F (x_N ) - F (z)] ≤ max{4LR²Θ, 2σR

NΘ} + 16R max{σ

Nτ,Mτ}+

√

+ 60 max{LR²τ/2, σR

NΘ} ≤

√

(Π.12)

≤ max{46LR²τ,4LR²Θ,62σR

N Θ, 16σR

Nτ}

при 1 ≤ τ ≤ N/υ². Это влечет (19).

□

П.5. Доказательство теоремы 2. Действуем точно так же, как при до-

казательстве теоремы 1 с той только разницей, что вместо утверждения (i)

леммы 3 используем утверждения (ii) той же леммы, которое влечет, что при

условии N ≥ υ² с вероятностью не менее 1 - 2e^-τ выполнены неравенства

∑

√

〈ξ_i, z - xi-1〉 ≤ 8(1 + τ)R max{σ

N,M},

i=1

∑

∥ξ_i∥2∗ ≤ 8(2 + 3τ) max{Nσ², M²}.

□

i=1

П.6. Доказательство предложения 2. Обозначим:

√

ρ_N(τ;μ,ν) = ν-1R²Θ + 16R max{σ

Nτ,Mτ}+

∑

+ 20(μ + ν) max{Nσ², M²τ} + μ-1 Vxi-1 (x_i).

i=1

Утверждение предложения является непосредственным следствием следую-

щего результата.

Лемма 4. Положим

ρN (τ) = min

ρ_N(τ;μ,ν) =

μ,ν>0

{

}

√

= 4R

5Θ max {Nσ², M²τ} + 16R max σ

Nτ,Mτ

{

}

{

}

∑

(Π.13)

+min

20μ max

Nσ²,M²τ

+μ-1

Vxi-1 (x_i)

μ>0

i=1

Тогда при 0 < τ ≤ N/υ² и t ≥ L справедливы неравенства

(a) Prob {ϵ_N (t) - ϵ_N (t) ≥ ρ_N (τ)/N} ≤ 2e^-τ ,

(Π.14)

(b) Prob {ϵ_N (t) - ϵ_N (t) ≥ ρ_N (τ)/N} ≤ 2e^-τ .

Доказательство леммы. Докажем первое неравенство в (Π.14). На-

помним, что ξ_i = y_i - ∇φ(xi-1), i = 1, . . . , N . Ввиду сильной выпуклости V_x(·)

имеем для любых z ∈ X и μ ≥ 0

〈ξ_i, z - x_i〉 = 〈ξ_i, z - xi-1〉 + 〈ξ_i, xi-1 - x_i〉 ≤

≤ 〈ξ_i, z - xi-1〉 +

∥ξ_i∥2∗ +

Vxi-1 (x_i).

Таким образом, для любых ν > 0

[

]

∑

〈ξ_i, z - x_i〉 ≤

〈ξ_i, z - xi-1〉 +

∥ξ_i∥2∗ +

Vxi-1 (x_i)

≤

i=1

]

∑

^[ν

≤

Vx0(z)+

∥ξ_i∥2∗ + 〈ξ_i, zi-1 - xi-1〉 +

Vxi-1 (x_i)+

∥ξ_i∥²

∗

i=1

(для получения последнего неравенства использовалась лемма 6.1 из [1] с

z₀ = x₀ так же, как в доказательстве предложения 1). По лемме 3 существу-

ет множество A_N в пространстве реализаций ω^N с вероятностью не менее

1 - 2e^-τ, такое что для всех ω^N ∈ A_N

∑

√

〈ξ_i, zi-1 - xi-1〉 ≤ 16R max{σ

Nτ,Mτ}

i=1

∑

∥ξ_i∥2∗ ≤ 40 max{Nσ², M²τ}.

i=1

Вспоминая, что Vx0 (z) ≤ R²Θ, приходим к заключению, что при всех z ∈ X

и всех ω^N ∈ A_N верно неравенство

∑

〈ξ_i, z - x_i〉 ≤ ρ_N (τ; μ, ν).

i=1

Следовательно, для ω^N ∈ A_N имеем

∑

ϵ_N(t) - ϵ_N(t) = N-1 sup

〈ξ_i, z - x_i〉 ≤ N-1 min

ρ_N(τ;μ,ν) = N-1 ρ_N(τ),

μ,ν≥0

z∈X i=1

что доказывает первое неравенство в (Π.14). Доказательство второго нера-

венства в (Π.14) аналогично и потому опускается.

□

П.7. Доказательство следствия 2. Из определения ϵ_N (·) заключаем, что

∑

β Vxi-1(x_i)≤ϵ_N

β),

i=1

и получаем (24), подставляя μ = 1

β. С другой стороны, можно убедиться,

{

√

}

что дл

β ≥ max

2L,^σ

√

выполняется неравенство

{

√

}

ρN (τ) ≤ NϵN

β)+max

[(20 + 4

Θ+16√τ]Rσ√N,(4√5Θτ +26τ)LR2

≤

√

≤Nϵ_N

β) + C₁Rσ

N [Θ ∨ τ] + C₂LR²[Θ ∨ τ].

Наконец, так как ϵ_N

β) ≤ ϵ_N

β) + ρ_N(τ)/N с вероятностью не менее 1 - 2e^-τ

(ср. (Π.14)(b)), то

Δ_N(τ

β)=ϵ_N

β) + ρ_N(τ)/N ≤ ϵ_N

β) + 2ρ_N(τ)/N

с той же вероятностью. Это влечет (25).

□

П.8. Доказательство теоремы 3.

1^o. Покажем сначала, что для каждого k = 1,... ,m = m(N) верно сле-

дующее.

Утверждение I_k. Существует случайное событие B_k ⊆ Ω^⊗N вероят-

ности не менее 1 - 2ke^-τ такое, что для всех ω^N ∈ B_k выполнены неравен-

ства

(a)

∥y_k - x(y_k)∥² ≤ r2k = 2^-kr²⁰ для некоторого x(y_k) ∈ X_∗,

(Π.15)

(b) F (y_k) - F_∗ ≤

r2k = 2-k-1κr²⁰.

Доказательство утверждения I_k проведем по индукции. Заметим, что

(Π.15)(a) выполняется с вероятностью 1 для k = 0. Положим B₀ = Ω^⊗N .

Предположим, что (Π.15)(a) справедливо для некоторого k ∈ {0, . . . , m - 1}

с вероятностью не менее 1 - 2ke^-τ , и покажем, что тогда верно утверждение

Ik+1.

Обозначим: F^k∗ = min

F (x). Пусть X^k∗ — множество точек минимума F

x∈Xrk (yk)

на Xrk (y_k). В силу теоремы 1 и определения N_k (ср. (27)) существует собы-

тие A_k вероятности не менее 1 - 2e^-τ такое, что для ω^N ∈ A_k после (k + 1)-го

этапа алгоритма имеем

∥yk+1 - x_k(yk+1)∥² ≤ F (yk+1) - F^k∗ ≤

{

√

}

Lr2k[τ ∨ Θ]

[τ ∨ Θ]

≤ max C₁

,C₂σr_k

≤

Nk+1

≤

r2k =

r2k+1,

где x_k(yk+1) — проекция yk+1 на X^k∗. Положим теперь Bk+1 = B_k ∩ A_k. Тогда

Prob{Bk+1} ≥ Prob{B_k} + Prob{A_k} - 1 ≥ 1 - 2(k + 1)e^-τ .

Кроме того, по индуктивному предположению на B_k (и, следовательно,

на Bk+1) имеем

∥y_k - x(y_k)∥ ≤ r_k,

т.е. расстояние от y_k до множества точек глобального минимума X_∗ не пре-

восходит r_k, и, значит множество Xrk (y_k) имеет непустое пересечение с X_∗.

Следовательно, X^k∗ ⊆ X_∗, точка x_k(yk+1) содержится в X_∗ и F^k∗ совпадает с

оптимальным значением F_∗ исходной задачи. Отсюда заключаем, что

∥yk+1 - x(yk+1)∥² ≤ F (yk+1) - F_∗ ≤

r2k+1 = 2^-kκr²⁰

для некоторого x(yk+1) ∈ X_∗.

2^o. Докажем теорему в случае, когда N₁ ≥ 1. Это условие эквивалентно

тому, что N_k ≥ 1 при всех k = 1, . . . , m(N), ибо по построению N₁ ≤ N₂ ≤ · · ·

··· ≤ Nm(N). Предположим, что ω^N ∈ Bm(N), так что (Π.15) выполняется с

k = m(N). Так как N_k ≥ 1, то N_k ≤ 2N_k. Кроме того, Nk+1 ≤ 2N_k. Учитывая

эти замечания и определение m(N), получим

m(N)+1∑

m(N)∑

(Π.16) N ≤

N_k ≤ 2

N_k + 4Nm(N) ≤ 6

N_k.

k=1

Итак, в силу определения N_k (ср. (27)) имеем

{

}

m(N)∑

L[τ ∨ Θ]

σ²[τ ∨ Θ]

N ≤6

max

4C₁

, 16C₂

≤

κ²r²

k=1

k-1

∑

m(N)∑

C₁L[τ ∨ Θ]

C₂σ²[τ ∨ Θ]

≤ 24

+ 96

κ²r2k-1

k=1

k=^k

(

S₁

S₂

где

{

}

k= min k :4C2σ

≥C₁L

κr²

k-1

Возможны два случая: либо S₁ ≥ N/2, либо S₂ ≥ N/2. Если S₁ ≥ N/2, то

k≥C′κN

L[τ ∨ Θ]

так что если ω^N ∈ Bm(N), то

F (ym(N)) - F_∗ ≤

r2m(N) ≤

r¯k =

{

}

(Π.17)

C^′κN

= 2-k-1κr²⁰ ≤ Cκr20 exp -

L[τ ∨ Θ]

Если же S₂ ≥ N/2, то справедливы неравенства

m(N)∑

κ²r²⁰N

Cκ²r²⁰

σ²[τ ∨ Θ]

≤

≤C^′2m(N)-k.

σ²[τ ∨ Θ]

κ²r²

k=^k

Следовательно, в этом случае для ω^N ∈ Bm(N) имеем

F (ym(N)) - F_∗ ≤

r2m(N) =

(Π.18)

[τ ∨ Θ]

r¯k2-m(N)+k ≤κr202-m(N)+k ≤ Cσ2

κN

3^o. Наконец, рассмотрим случай, когда

{

}

L[τ ∨ Θ]

σ²[τ ∨ Θ]

(Π.19)

N₁ := max

4C₁

, 16C₂

< 1.

κ²r²

Пусть k_∗ ≥ 2 — наименьшее целое k такое, что N_k ≥ 1. Если k_∗ > N/4, то

нетрудно видеть, что m(N) ≥ N/4, и, следовательно, для ω^N ∈ Bm(N) имеем

(Π.20)

F (ym(N)) - F_∗ ≤

r2m(N) ≤

r²⁰ 2-N/4.

Если же 2 ≤ k_∗ ≤ N/4, то верна цепочка неравенств

m(N)∑

N_k ≥ Nm(N)+1 +

N_k =

k=k∗

m(N)+1∑

∑

m(N)+1∑

N_k - N_k ≥

N_k - N/4 ≥ N/4,

k=1

где в первом неравенстве учтено, что Nm(N)+1 ≤ 2Nm(N), а последнее следует

из определения m(N). Используя эти замечания и то, что N_k/2^k ≤ Nk∗ /2k∗

при k ≥ k_∗, находим

m(N)∑

≤ N_k ≤

2k-k∗ Nk∗ ≤ 2m(N)-k∗+2,

k=k∗

где в последнем неравенстве учтено, что Nk∗ ≤ 2Nk∗-1 < 2. Итак, принимая

во внимание (Π.15)(b), для ω^N ∈ Bm(N) будем иметь

F (ym(N)) - F_∗ ≤ κr2k

2-m(N)+k∗ ≤ κr²⁰2-m(N)+k∗ ≤ Cκr²⁰/N.

∗

Соединяя последнюю оценку с (Π.17), (Π.18) и (Π.20), получим (28).

□

СПИСОК ЛИТЕРАТУРЫ

Nemirovski A., Juditsky A., Lan G., Shapiro A. Robust stochastic approximation

approach to stochastic programming // SIAM J. Optim. 2009. V. 19. No. 4.

P. 1574-1609.

Juditsky A., Nesterov Y. Deterministic and stochastic primal-dual subgradient

algorithms for uniformly convex minimization // Stochast. Syst. 2014. V. 4. No. 1.

P. 44-80.

Ghadimi S., Lan G. Optimal stochastic approximation algorithms for strongly convex

stochastic composite optimization I: A generic algorithmic framework // SIAM J.

Optim. 2012. V. 22. V. 4. P. 1469-1492.

Tukey J.W. A survey of sampling from contaminated distributions / I. Olkin,

Contribut. Probab. Statist. 1960. P. 448-485.

Huber P.J. Robust estimation of a location parameter // Ann. Math. Statist. 1964.

P. 73-101.

Huber P.J. The 1972 Wald lecture. Robust statistics: A review // Ann. Math.

Statist. 1972. V. 43. No. 4. P. 1041-1067.

Хьюбер П. Робастность в статистике. М.: Мир, 1984.

Martin R., Masreliez C. Robust estimation via stochastic approximation // IEEE

Transact. Inform. Theory. 1975. V. 21. No. 3. P. 263-271.

Поляк Б.Т., Цыпкин Я.З. Адаптивные алгоритмы оценивания (сходимость, оп-

тимальность, стабильность) // АиТ. 1979. № 3. С. 71-84.

Polyak B., Tsypkin Ya.Z. Adaptive Estimation Algorithms: Convergence, Optimality,

Stability // Autom. Remote Control. 1979. V. 40. No. 3. P. 378-389.

10.

Поляк Б.Т., Цыпкин Я.З. Робастные псевдоградиентные алгоритмы адапта-

ции // АиТ. 1980. № 10. С. 91-97.

Polyak B.T., Tsypkin Ya.Z. Robust Pseudogradient Adaptation Algorithms //

Autom. Remote Control. 1981. V. 41. No. 10. P. 1404-1409.

11.

Polyak B., Tsypkin J.Z. Robust identification. Automatica. 1980. V. 16. No. 1.

P. 53-63.

12.

Price E., VandeLinde V. Robust estimation using the Robbins-Monro stochastic

approximation algorithm // IEEE Transact. Inform. Theory. 1979. V. 25. No. 6.

P. 698-704.

13.

Stanković S.S., Kovačević B. D. Analysis of robust stochastic approximation

algorithms for process identification // Automatica. 1986. V. 22. No. 4. P. 483-488.

14.

Chen H.-F., Guo L., Gao A.J. Convergence and robustness of the Robbins-Monro

algorithm truncated at randomly varying bounds // Stochast. Proc. Appl. 1988.

V. 27. No. 2. P. 217-231.

15.

Chen H.-F., Gao A.J.

Robustness analysis for stochastic approximation

algorithms // Stochastics. 1988. V. 26. No. 1. P. 3-20.

16.

Nazin A.V., Polyak B.T., Tsybakov A.B. Optimal and robust kernel algorithms for

passive stochastic approximation // IEEE Transact. Inform. Theory. 1992. V. 38.

No. 5. P. 1577-1583.

17.

Цыпкин Я.З. Основы информационной теории идентификации. М.: Наука, 1984.

18.

Цыпкин Я.З. Информационная теория идентификации. М.: Наука, 1995.

19.

Kwon J., Lecué G., Lerasle M. Median of means principle as a divide-and-

conquer procedure for robustness, sub-sampling and hyper-parameters tuning //

arXiv:1812.02435.

20.

Chinot G., Lecué G., Lerasle M. Statistical learning with Lipschitz and convex loss

functions // arXiv:1810.01090.

21.

Lecué G., Lerasle M. Robust machine learning by median-of-means: theory and

practice // arXiv preprint. arXiv:1711.10306. Annals of Stat., 2017, to appear.

22.

Lecué G., Lerasle M., Mathieu T. Robust classification via MOM minimization //

arXiv preprint, 2018. arXiv:1808.03106.

23.

Lerasle M., Oliveira R.I. Robust empirical mean estimators // arXiv preprint, 2011.

arXiv:1112.3914.

24.

Lugosi G., Mendelson S. Risk minimization by median-of-means tournaments //

arXiv preprint, 2016. arXiv:1608.00757.

25.

Lugosi G., Mendelson S. Regularization, sparse recovery, and median-of-means

tournaments // arXiv preprint, 2017. arXiv:1701.04112.

26.

Lugosi G., Mendelson S. Near-optimal mean estimators with respect to general

norms // arXiv preprint, 2018. arXiv:1806.06233.

27.

Hsu D., Sabato S. Loss minimization and parameter estimation with heavy tails //

J. Machin. Learning Res. 2016. V. 17. No. 1. P. 543-582.

28.

Bubeck S., Cesa-Bianchi N., Lugosi G. Bandits with heavy tail // IEEE Transact.

Inform. Theory. 2013. V. 59. No. 11. P. 7711-7717.

29.

Devroye L., Lerasle M., Lugosi G., Oliveira R.I. Sub-gaussian mean estimators //

Ann. Statist. 2016. V. 44. No. 6. P. 2695-2725.

30.

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

тимизации. М.: Наука, 1979.

31.

Lugosi G., Mendelson S. Sub-gaussian estimators of the mean of a random vector //

Ann. Statist. 2019. V. 47. No. 2. P. 783-794.

32.

Catoni O. Challenging the empirical mean and empirical variance: a deviation

study // Ann. l’IHP Probab. Statist. 2012. V. 48. No. 4. P. 1148-1185.

33.

Audibert J.-Y., Catoni O. Robust linear least squares regression // Ann. Statist.

2011. V. 39. No. 5. P. 2766-2794.

34.

Minsker S. Geometric median and robust estimation in Banach spaces // Bernoulli.

2015. V. 21. No. 4. P. 2308-2335.

35.

Wei X., Minsker S. Estimation of the covariance structure of heavy-tailed

distributions / Advances in Neural Information Processing Systems. 2017. P. 2859-

2868.

36. Chen Y., Su L., Xu J. Distributed statistical machine learning in adversarial settings:

Byzantine gradient descent / Proceedings of the ACM on Measurement and Analysis

of Computing Systems, ACM, 2017. V. 1. No. 2. P. 44.

37. Yin D., Chen Y., Ramchandran K., Bartlett P. Byzantine-robust distributed

learning: Towards optimal statistical rates. arXiv preprint, 2018. arXiv:1803.01498.

38. Cardot H., Cénac P., Chaouch M. Stochastic approximation for multivariate and

functional median / Proceedings of COMPSTAT’2010. P. 421-428. Springer, 2010.

39. Cardot H., Cénac P., Godichon-Baggioni A. Online estimation of the geometric

median in Hilbert spaces: Nonasymptotic confidence balls // Ann. Statist. 2017.

V. 45. No. 2. P. 591-614.

40. Lan G. An optimal method for stochastic composite optimization // Math.

Programm. 2012. V. 133. No. 1-2. P. 365-397.

41. Necoara I., Nesterov Y., Glineur F. Linear convergence of first order methods for

non-strongly convex optimization // Math. Programm. 2018. P. 1-39.

42. Juditsky A., Nemirovski A. First order methods for nonsmooth convex large-scale

optimization, I: general purpose methods / Sra, S., Nowozin, S., Wright, S.J. (eds.)

Optimization for Machine Learning, MIT Press, Cambridge, MA, 2011. P. 121-148.

43. Freedman D.A. On tail probabilities for martingales // Ann. Probab. 1975. V. 3.

No. 1. P. 100-118.

44. Chen G., Teboulle M. Convergence analysis of a proximal-like minimization

algorithm using Bregman functions // SIAM J. Optim. 1993. V. 3. No. 3. P. 538-543.

Статья представлена к публикации членом редколлегии П.В. Пакшиным.

Поступила в редакцию 18.07.2018

После доработки 03.09.2018

Принята к публикации 08.11.2018