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

Структура статьи следующая. В п. 2 мы описываем рандомизированный МЗС. Стоит обратить внимание на случай, когда оптимизация происходит на неограниченном множестве, и при этом выводятся оценки вероятностей больших уклонений. Тут есть некоторые тонкости, проработка которых делает п. 2 не просто вводным материалом для последующего изложения, но и представляющим самостоятельный интерес. В п. 3 результаты п. 2 переносятся на задачи с функциональными ограничениями, на которые мы не умеем эффективно проектироваться. В детерминированном случае (когда используется обычный градиент) такого типа задачи рассматривались достаточно давно. Разработаны эффективные способы их редуцирования к задаче с простыми ограничениями. Предлагались различные эффективные методы (Поляк–Шор–Немировский–Нестеров). Однако в случае, когда вместо градиента мы используем его несмещенную оценку (для функционала и ограничений), нам не известны оценки, поэтому в п. 3 приводится соответствующее обобщение МЗС и устанавливаются необходимые в дальнейшем оценки. В п. 4 на основе теоретических заготовок пп. 2 ,3 мы описываем класс разреженных задач (обобщающих задачу PageRank), для которых удаётся за счет рандомизации получить дополнительную выгоду.

Рассмотрим задачу выпуклой оптимизации

/(ж) ^ min .                                       ⁽¹⁾

x ^ Q

Под решением этой задачи будем понимать такой Ж ^N G Q С R ⁿ , что с вероятностью >  1 — а имеет место неравенство

/(sN) — А < Е, где А = /(ж*) — оптимальное значение функционала в задаче (1), ж* G Q — решение задачи (1). На каждой итерации к = 1, ...,N нам доступен стохастический (суб-)градиент Vxf к(ж,^к) в одной, выбранной нами (методом), точке жк.

Опишем метод зеркального спуска (МЗС) для решения задачи (1) (мы в основном будем следовать работам [5, 6]). Введем норму ‖ · ‖ в прямом пространстве (сопряженную норму будем обозначать || • ||*) и прокс-функцию d(ж) сильно выпуклую относительно этой нормы, с константой сильной выпуклости > 1. Выберем точку старта ж1 = argmin d(ж'), xEQ считаем, что d(ж1) = 0, Vd(ж1) = 0.

Введем брэгмановское «расстояние»

V X (y) = d ( y ) — d ( x ) — (V d(ж),y — ж ) .

Определим «размер» решения

d(ж * ) = V _x i (ж * ) = R ² .

Определим оператор «проектирования» согласно этому расстоянию

-

^"^ ⁺ ' X / (y)} .

Mirr _x fe (v) = argmin <  Gy у yeQ ^{1 x}

МЗС для задачи (1) будет иметь вид, см., например, [6]

ж ^к+1 = Mirr _x fe ^« V _x / _k (ж ^к ,G )) , к = 1,..., N.

Будем считать, что {^ ^k } ^Ni представляет собой последовательность независимых случайных величин, и для всех ж G Q имеют место условия (к = 1,..., N)

• 1)    Е ■  ^7 _x f_k Е k) ] = V f(x);

• 2)    Е [ || V fk ^ ) | * ] < M ² .

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

• 3)    И V f k (x,f ^k ) II * <  MM ² почти наверное по f ^k .

При выполнении условия 1 для любого u Е Q,k = 1,..., N имеет место неравенство, см., например, [6]

а ( V f k (x ^k Е/ ) ,x ^k - u) <  '2 2 || v f k (x ^k ,f ^k ) | 2 - V (u) - V _{x k +}i (u).

Это неравенство несложно получить в случае евклидовой прокс-структуры [7]

d ( x ) = ||x|| ² /2, V _x ( y ) = \\ y - x \ ² /2.

В этом случае МЗС для задачи (1) есть просто вариант обычного метода проекции градиента (см. примеры 1, 2 ниже).

Разделим сначала выписанное неравенство на а и возьмем условное математическое ожидание E ^k [•| S ^{k - 1}] (S ^{k -1} — сигма алгебра, порожденная £ 1 ,..., £ ^{k - 1} ), затем просуммируем то, что получится по к = 1,..., N, используя условие 1. Затем возьмем от того, что получилось при суммировании, полное математическое ожидание, учитывая условие 2. В итоге, выбрав и = х * , и определив

" x " = N Е x ^k . k=1

получим

N • Е [f (х " ^)] - f * ⁾<       - ^EV ■ ^x * + 1 M ² аN <  ^R + - M 2 aN.

^L              ' а             а          2             а 2

Выбирая ¹

R ПГ ^а = Mv N, получим

E [f (x " )] - f * < MR^|.                         (2)

Заметим, что в детерминированном случае вместо x" можно брать x" = argmin f (xk).

k=1,...,N

Немного более аккуратные рассуждения (использующие неравенство Азума–Хефдинга) с

“ = JI

MN N позволяют уточнить оценку (2) следующим образом (см., например, [8, 9]):

f (x " ) - f * <  Ml^|-N ( r + 2-RVln(2/^>)                      (3)

с вероятностью >  1 - ст, где

R = sup \x - x* II, xEQ

Q = {x G Q : ||x — x * ||2 <  65 R 2 ln(4V/CT)} .

Собственно, для справедливости оценки (3) достаточно требовать выполнение условий 1–3 лишь на множестве Q С Q. Это замечание существенно, когда рассматриваются неограниченные множества Q (см., например, п. 4).

Оценки (2), (3) являются неулучшаемыми с точностью до мультипликативного числового множителя по V ист. Наряду с этим можно обеспечить и их неулучшаемость по размерности пространства п путем «правильного» выбора прокс-функции [5] (такой выбор всегда возможен и известен для многих важных в приложениях случаев выбора множества Q). Собственно прокс-структура (новая степень свободы по сравнению с классическим методом проекции градиента) и вводилась для того, чтобы была возможность обеспечить последнее свойство.

Ввиду того, что мы используем рандомизированный метод и всегда

/(xN) — /* > 0, то, используя идею амплификации (широко распространенную в Computer Science), можно немного «улучшить» оценку (3). Для этого сначала перепишем оценку (2) в виде

Е [/(xN)] —/* < Е, где (здесь V, конечно, должно быть натуральным числом, поэтому эту формулу и последующие формулы такого типа надо понимать с точностью до округления к наименьшему натуральному числу, большему написанного)

V =

2 М 2 R ²

Е2

Отсюда по неравенству Маркова

Р (/ (X ^N ) — / * >  2 е ) <  ^{Е[/ ( Х} ₂ " _Е ^{)] f} * <  2.

Можно параллельно (независимо) запустить log 2 (CT ^{- 1} ) траекторий метода. Обозначим x ^Nin тот из x ^N на этих траекториях, который доставляет минимальное значение /(x ^N ). Из выписанного неравенства Маркова получаем, что имеет место неравенство

Р (/ (® Nin ) — / * >  2 е ) <  ст.

Таким образом, можно не более чем за

V =

8М 2 R ²

Е ²

^lo g 2 ^{( CT} 1 )

обращений за стохастическим градиентом и не более чем за log 2 (CT ^{- 1} ) обращений за значением функции найти решение задачи (1) x ^N с требуемой точностью е и доверительным уровнем ст.

Как уже отмечалось, во многих приложениях множество Q неограничено (см., например, п. 4). Поскольку х * априорно не известно, то это создает проблемы для определения R, которое входит в формулу для расчета шага метода

R р2 ^а = M\V^.

Однако если мы заранее выбрали желаемую точность е , то с помощью формулы (4) можно выразить шаг следующим образом:

Q = -- ~.

М ²

Рассмотрим три конкретных примера множества Q, которые нам понадобятся в дальнейшем (см. п. 4). В примерах 1, 2 мы не приводим оценки скорости сходимости, поскольку они будут иметь вид (2), (3), т.е. никакой уточняющей информации тут не появляется в отличие от примера 3.

Пример 1 (все пространство) . Предположим, что Q = R ⁿ . Выберем

INI = «-« 2 , d^ = 2 « х | 2 .

Тогда МЗС примет следующий вид (а = е/М ² , х ¹ = 0):

х ^к+1 = х ^к - а^ к (х ^к ..) , к = 1,...,V. □

Пример 2 (неотрицательный ортант) . Предположим, что

Q = R + = { х € R ⁿ : х >  0 } .

Выберем

11-1 = Л • « 2 , d ( x ) = 2 « х - х « 2 , х € intQ.

Тогда МЗС примет следующий вид (а = е/М ² , х ¹ = х):

хк+1 = [хк - a^xfk х$к,£к)] = max |хк - а^х f к х^Лк^ , о} , к = 1,..., V,

где max {} берется покомпонентно. □

Пример 3 (симплекс) . Предположим, что

Q = £ п (1) =

х >  0 : ^^ х _г = 1 J^ .

Выберем

п

II • || = || • ||1 , d(x)=lnx + ^ln х г .

г=1

Тогда МЗС примет следующий вид:

х1 = 1/п, г = 1,..., п, при к = 1,..., V, г = 1,..., п

. к+1 ■ г

exp (- /М ')

²² exp ( - 12 а ⁸-Муа )

1=1     \ Г=1        ' /

^{х к} exp (^{-а 8f k}d_X;^^k ))

_t£ х к exp ( - J²^ ^^^^ )

Оценки скорости сходимости будут иметь вид:

E [f (х ^ )] - f * <  M

1 2lnn N V

(при а = M 1 ^2lnn/V);

f (х ^ ) - f * < M l^^ ( V lnn + 4^ln(^ 1 )^ (при а = M l 1 ^ 2 In n/V ) с вероятностью >  1 - ст. □

Представим себе, что задача (1) видоизменилась следующим образом:

f (х) ^ min . g(x)<0

x E Q

Можно ли к ней применить изложенный выше подход, если «проектироваться» на множество (в отличие от Q)

{ж G Q : д(ж) < 0} мы эффективно не умеем? В случае, когда мы знаем оптимальное значение f*, то мы можем свести новую задачу к задаче (1):

min { f (ж) — f * , д(ж) } ^ min . x e Q

Несложно записать рандомизированный МЗС для такой задачи и применить к ней все, что изложено выше. Однако мы не будем здесь этого делать, поскольку в следующем пункте мы приведем более общий вариант МЗС, который не предполагает, что известно f * .

• 3.    Рандомизированный метод зеркального спуска с функциональными ограничениями

Рассмотрим задачу f (ж) ^ min .                                       (5)

дМ<0 x E Q

Под решением этой задачи будем понимать такой Ж ^{^} G Q, что имеют место неравенства

Е [f (ж^)] - f* < EJ = МЕд, д(^) < Ед, где f * = f (ж*) — оптимальное значение функционала в задаче (5), ж* G Q — решение задачи (5). Будем считать, что имеется такая последовательность независимых случайных величин {£к} и последовательности {Vжfk(ж,^к)}, {Vжgk(ж,^к)}, к = 1, ...,N, что для всех ж G Q имеют место следующие соотношения (можно считать их выполненными при ж G Q, см. п. 2 и последующий текст в этом пункте)

Е [V_xf_k (х, V )] = Vf (ж), Е [V_xg_k (ж, : )] = V g(ж);

Е [^ V _ж f k (ж,е ^к ) | | 2] <  М 2² ,    Е ^_ж д к (ж,е ^к ) | | 2] <  М д² .

МЗС для задачи (5) будет иметь вид (см., например, в детерминированном случае двойственный градиентный метод из [10]):

жк+1 = Mirr^ (hf Vxfk^k ,^к)), если д (жк) < Ед, жк+1 = Mirr^k ^hgV хдк ж®,Л^

если д

(■■

> Е д ,

где h _д = Е _д /М д , h j = Е _д / ( M j M _g ), к = 1, ...,N. Обозначим через I множество индексов к, для которых д ( ж ^к ) <  Е. Введем также обозначения

[N ]= { 1,...,N } ,   J =[N] \ I,   N = | I | , N j = I J | , Ж ^{^} = 4- Е ж ^к .

Nr ‘— ^J кеі

Тогда имеет место неравенство hjNi • (Е [f (Ж^)] — f*) <

< 4 ^е

ТЛ^Ек [^к(ж^к ,e ^к)] . кеі

,ж к

-

ж *

< 1 Е^Е [І |^V ^ ^f k (ж ^к -і ^{к )}|[* ] - кеі    ^{L                       J}

-

h g е Е E ⁵^ [v - g k X ^{x k} ’^^k) ]’X k k e J '------------------v-----------

-

X *

) + '2 Е Е [I |v.gk     ; )||2] + keJ    L                       J

Будем считать,

> g ( - ^k ) - g($ * )>e ₉

⁺ Е ^{( E} Wx ^{k ( x} * ^{)] — E} \ V _x k+i ^{( x} * ^)]) <  ke[N ]

< 2 ^h f ^M f ^N i - 2 M 2 ^E<g ^N J ^{+ е} \^ - ^{1 ( х} * ^)] - ^е \^ ® ^{w +1 ( x} * ^)] =

= 2 ^^M f ⁺ M rgg^ ^{Ni -} 2MM g ^{E g N + д} 2 ^{- Е}'' '^{/, х} ' ^{( х} * ^{)] .}

что (следует сравнить с формулой (4)):

2Mn' Д

N = N ( E g ) = --- "   + 1.

^E g

Тогда N i >  1 и

Е [f (X ^N )] - f * <  2 ^f M f +

^Е 2

^{M g h} l

MiF

) = M g ^{E g} =^{E f} .

Соотношение

g (XN) < Eg следует из того, что по построению g(xk) < Eg, к Е I и из Заметим, что в детерминированном случае вместо XN

выпуклости функции д(х). можно брать

X ^N

= argmin f (х^к\ . kei         '

Если известно, что для всех х Е Q и почти наверное по £k

\\^_к E’^ek ) I 2 <  м 2 ,

||v-gk (x,ek)| 12 < M2,   к = 1,...,N, то для описанного в этом пункте метода (с е = Ef = Eg и hf = hg = e/M2) вид оценки вероятностей больших уклонений (3) из п. 2 сохранится (оценка получается чуть лучше, чем нижняя оценка из работы [11], когда ограничений-неравенств больше одного, поскольку мы имеем доступ к точному значению д(х))

f (xN) - f* < 2M^N , д + 2.RУШ(27^)) , если N = 2N(e) (см. формулу (6)). К сожалению, трюк с амплификацией (см. п. 2) здесь уже не проходит в том же виде, как и раньше, поскольку теперь уже нельзя гарантировать f (XN) - f* > 0.

Однако если ввести обозначение

Ед = f* — min f(х) = min f(х) — min f(х), g(-)

P (f (X^N) — /. + ЕД > 2 (Ef + Ед)) < ^Е^^? L^f) ^{+ ЕД}

< 1 2

^{2 (E}f ^{+ Е}д)

Можно параллельно (независимо) запустить log2 (ст-¹) траекторий метода. Обозначим :т^_п тот из ж^ на этих траекториях, который доставляет минимальное значение f (ж^). Из выписанного неравенства Маркова получаем, что имеет место неравенство

Р (f (^min) -f* > 2Еу + Ед) < С.

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

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

Основные приложения описанного подхода, это задачи вида f (ж) ^      min max ^^(АТ х)<0 к = 1 ,...,т с разреженной матрицей

А = [А_ъ...,А_т]^т.

В частности, задачи вида f (ж) ^ min Ах<Ь и приводящиеся к такому виду задачи f (ж) ^ min .

Ах<Ь Сх=а

В этих задачах, как правило, выбирают || • || = || • Ц2, ^(ж) = ||ж|2/2. Подобно [10] можно попутно восстанавливать (без особых дополнительных затрат) и двойственные множители к этим ограничениям. Причем эта процедура позволяет сохранить дешевизну итерации даже в разреженном случае.

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

Начнем с известного примера [12], демонстрирующего практически все основные способы рандомизации, которые сейчас активно используются в самых разных приложениях. Рассмотрим задачу поиска левого собственного вектора ж, отвечающего собственному значению 1, стохастической по строкам матрицы Р = Цр^ Ц^^і 1 (такой вектор называют вектором Фробениуса–Перрона, а с учетом контекста – PageRank вектором). Изложение рандомизации, связанной с ускоренными покомпонентными методами, мы опускаем, поскольку она не завязана на МЗС. Тем не менее приведем ссылки на работы, в которых такой подход к поиску PageRank описан: замечание 5 [4] и пример 4 [13] (см. также замечания 10, 11 [14]).

Перепишем задачу поиска вектора PageRank следующим образом [3]:

• ^f(ж)= ~ ^|Аж|2 ^ min,,

• 2            xES„(1)

где 5_П(1) — единичный симплекс в R”, А = Р^Т — I, I — единичная матрица. Далее будем использовать обозначения А^ — к-й столбец матрицы А, А" — транспонированная к-я строка (то есть А" — это вектор) матрицы А. Следуя [12], воспользуемся для решения этой задачи рандомизированным МЗС со стохастическим градиентом²

Vxfk (ж,^) = (Р — I)^)> — (Р — I)^> , где

^^k = г с вероятностью ж^, г = 1,..., п;

j (^)

= j с вероятностью р^к j,

j = 1, -,п.

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

М²= max ||Vxfk (ж,^) || < 4. же5„(1)Л^к V /Н^

Даже в случае, когда матрица Р полностью заполнена, амортизационная (средняя) стоимость одной итерации будет О(п) (вместо О(п²), в случае честного расчета градиента). Таким образом, общее число арифметических операций будет О(п1nп/е²).

К худшей оценке приводит другой способ рандомизации (рандомизации суммы [4]). Чтобы его продемонстрировать, перепишем исходную задачу следующим образом:

п 1 1

f(ж) = п       (АГж)²^ min .

^V             п 2 ^{V к} ’      xES„(1)

k=1

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

Vx fk^,C^k) =nA_SkA_Skj(_x),

где

^^k = г с вероятностью 1/п, г = 1, ...,п;

j(ж) = j с вероятностью Жj, j = 1,..., п.

Амортизационная (средняя) стоимость одной итерации будет по-прежнему О(п), но вот оценка М²получается похуже. Здесь мы имеем пример, когда М²и М²существенно отличаются, в действительности, можно вводить промежуточные условия, не такие жесткие, как условие 3, и получать более оптимистичные оценки вероятностей больших уклонений [4].

К сожалению, эти методы не позволяют полноценно воспользоваться разреженностью матрицы Р, которая, как правило, имеет место. Собственно, этот пункт отчасти и будет посвящен тому, как можно сочетать рандомизацию и разреженность. В частности, если переписать задачу PageRank следующим образом:

^Ажх ^ min_А, xGS„(1)

что равносильно (факт из теории неотрицательных матриц [15])

max АТж ^ min , k=1,...,n           xES_n(1)

то исходя из примера 3 (в детерминированном случае), можно получить следующую оценку [16] на общее число арифметических операций О(п 1пп/е²), при условии, что число элементов в каждой строке и столбце матрицы Р не больше О( ^п/ 1пп). Здесь не использовалась рандомизация, а использовалась только разреженность матрицы Р (следовательно, и А). По-сути, способ получения этой оценки всецело базируется на возможности организации эффективного пересчета субградиента функционала, подобно [1–3]. Далее мы распространим этот пример на более общий класс задач, и постараемся привнести в подход рандомизацию.

Итак, рассмотрим сначала класс задач с Q из примера 1 или 2 п. 2

max № (АГж) ^ min, k=1,...,m k V k ’     xEQ где ст/ () — выпуклые функции с константой Липшица, равномерно ограниченной известным числом М, (суб-)градиент каждой такой функции (скалярного аргумента) можно рассчитать за 0(1). Введем матрицу

А = [А1,..., Ат]т и будем считать, что в каждом столбце матрицы А не больше 8 т < т ненулевых элементов, а в каждой строке — не больше 8 п < п. Заметим, что некоторую обременительность этим условиям создает требование, что в «каждом» столбце/строке. Это требованиe можно ослаблять, приближаясь к некоторым средним показателям разреженности (численные эксперименты в этой связи также проводились [3]), однако в данной работе для большей наглядности и строгости рассуждений мы ограничимся случаем, когда именно в каждом столбце/строке имеет место такая (или еще большая) разреженность.

Из работ [1–3] следует, что МЗС из примеров 1, 2 (в детерминированном случае) для задачи (7) будет требовать

М²max ||Afe 12-^2 /=1,...,т

Е²

итераций, где А2 — квадрат евклидова расстояния от точки старта до решения, а одна итерация (кроме первой) будет стоить

0(min{8„8m log2 т, п}).

И все это требует препроцессинг (предварительных вычислений, связанных с «правильным» приготовлением памяти) объема О(т + п). Таким образом, в интересных для нас случаях общее число арифметических операций для МЗС из примеров 1, 2 будет

/           М²max ЦА/ ||2^2 \

О I 8_п8т log2 т------’...’^тI .                              (8)

I                                    Е²                 I

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

А = ^А+

-

А

где каждый из векторов А+, А— имеет неотрицательные компоненты. Согласно этим векторам приготовим память таким образом, чтобы генерирование случайных величин из распределений А+/| А+|1 и А^-/||А^-11 занимало бы O(log2n). Это всегда можно сделать [3]. Однако это требует хранения в «быстрой памяти» довольно большого количества соответствующих «деревьев». Весь этот препроцессинг и затраченная память будут пропорциональны числу ненулевых элементов матрицы А, что в случае huge-scale задач сложно осуществить из-за ресурсных ограничений. Тем не менее далее мы будем считать, что такой препроцессинг можно осуществить, и (самое главное) такую память можно получить. Введем стохастический (суб-)градиент

• V.A(^) = ^А/  ||1 е_і($,) - Ц4-Д _W„

где

k(x) G Argmax о^ (А^т$) ,

/=1,...,т причем не важно, какой именно представитель Argmax выбирается;

п

⏞⏟ ег = (0,..., 0,1, 0,..., 0);

⏟⏞

г

‘И

= ‘

с вероятностью

А**! Һ^л+<»>Һі^,

‘ = 1,..., п;

^'И

= 3

с вероятностью

А- v k(Aj

/ ІК-)ІІ1,

3 = 1,..., п;

Легко проверить выполнение условия 1 п. 2 (заметим, что V /(ж) = А^)). Также легко оценить

ЛЛ²<М²max ^k||1.

k=1,...,m

И получить из примеров 1, 2 следующую оценку числа итераций (ограничимся для большей наглядности сходимостью по математическому ожиданию, т.е. без оценок вероятностей больших уклонений)

Л²max ^k ||1 R2

k=1,...,m

E²

Основная трудоемкость тут в вычислении ^(ж). Однако за исключением самой первой итерации можно эффективно организовать перерешивание этой задачи. Действительно, предположим, что уже посчитано ^(ж^/), а мы хотим посчитать ^(ж^/+1). Поскольку согласно примерам 1, 2 ж^/+1может отличаться от ж^/только в двух компонентах, то пересчитать max CTk (А^ж^¹), исходя из известного max CTk (А^ж^, можно за (см., например, [1,3]) k=1,...,m                                                k=1,...,m

O(2s_mlog2 m). Таким образом, общее ожидаемое число арифметических операций нового рандомизированного варианта МЗС из примеров 1, 2 для задачи (7) будет

O

ЛЛ²max || Ak ||1 R2 k=1,...,m

Sm log2 m---------₅---------

E²

Для матриц А, все отличные от нуля элементы которых одного порядка, скажем 0(1), имеем max ||Ak |2 = sn, max ||Ak ||1 = s2.

k=1,...,m                    k=1,...,m

В таком случае не стоит ожидать выгоды (формулы (8) и (9) будут выглядеть одинаково). Но если это условие (ненулевые элементы А одного порядка) выполняется не очень точно, то можно рассчитывать на некоторую выгоду.

Рассмотрим теперь более общий класс задач, возникающих, например, при поиске равновесий в транспортных сетях [9]

1 ^r

- max   ст/ (А^ж) ^ min,

Г 2—' /=ак + 1,...,bk                 xEQ k=1

0 = а₁< b₁= а₂< b₂ = аз < ... < b_r-1 = а_г< b_r = m.

Матрица А и числа s_n, s_m определяются аналогично. Привнося (при расчете стохастического градиента) к описанным выше двум подходам для задачи (7) сначала равновероятный (и независимый от других рандомизаций) выбор одного из слагаемых в этой сумме, получим соответствующие обобщения (для задачи (10)) оценок (8), (9), которые будут иметь точно такой же вид. Только матрица А собирается теперь из всех слагаемых суммы (10).

Возвращаясь к примеру 3, заметим, что все описанные выше конструкции (в том числе, связанные с задачей (10)) можно перенести на этот пример, в случае, когда

CTk (А^ж) = А^ж - bk.

При этом

R2 ^ Inn,  ЛЛ = 1 (для (8), (9))

max Щк||2 ^ max |Ajj|, min{snsm log2 m,n} ^ max{snsm log2 m,n} (для (8)) k=1,...,m              г=1,...,т J j=1,...,n max ||Ak ||1 ^ max Щк ||i, Sm log2 m ^ max{sm log2 m,n} (для (9)).

k=1,...,m             k=1,...,m

Собственно, пример PageRank, изложенный в начале этого пункта, как раз подходил под применение оценки (8).

С помощью п. 3 все написанное выше переносится и на задачи вида f (ж) ^ min Ax

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

Исследование в части 2 выполнено при поддержке гранта РФФИ 14-01-00722-а, исследования в частях 3, 4 — при поддержке гранта РФФИ 15-31-20571-мол_а_вед.