Предобусловливание и импульс в оптимизации: взгляд на алгоритмы PHB/PN от исследователей Яндекса / Habr

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

Для ускорения сходимости широко применяются методы с механизмом импульса (momentum): классический метод Поляка — Heavy Ball (HB) — и метод Нестерова (ускоренный градиент). Оба эти метода используют идею накапливать «инерцию» градиента, благодаря чему могут двигаться по направлению оптимума быстрее обычного градиентного спуска.

Однако, хотя импульс позволяет ускорить алгоритм, сам по себе он не решает проблему плохой обусловленности функции. Если у функции большое отношение $L/\mu$ (кондиционирование, где — Константа Липшица градиента, а $\mu$ — константа сильной выпуклости), даже методы Нестерова будут требовать много итераций для достижения высокой точности. В таких ситуациях на помощь приходит предобусловливание — масштабирование шагов оптимизации по разным координатам на основе дополнительной информации о функции, чтобы выровнять скорость сходимости по различным направлениям задачи.

Идея предобусловливания не нова: ещё методы Ньютона и квази‑Ньютона фактически предобусловливают задачу с помощью второй производной (Гессиана) или её приближений. Вычислять обратный Гессиан напрямую дорого, поэтому на практике применяются приближённые методы (BFGS, L‑BFGS и др.) либо более простые схемы адаптивного масштабирования шага.

Последние годы огромную популярность получили так называемые адаптивные методы первого порядка: AdaGrad, RMSProp, Adam и их производные. В них предобусловливание осуществляется за счёт диагональной матрицы (по сути, индивидуального шага для каждой координаты), которая обновляется по ходу алгоритма на основе прошлых градиентов. Например, AdaGrad накапливает сумму квадратов градиента по каждой координате и делит на её корень, RMSProp и Adam используют экспоненциальное затухание этих сумм, а Adam дополнительно сочетает это с импульсом (моментом) градиента.

На практике адаптивные методы зачастую значительно превосходят по скорости сходимости обычный градиентный спуск и де‑факто стали стандартом при обучении нейросетей. Однако до сих пор сочетание импульсного ускорения (как в методах Heavy Ball или Нестерова) с общим предобусловливанием изучено не полностью. Существующие адаптивные схемы либо не обеспечивают теоретического ускорения до уровня метода Нестерова, либо анализируются только в частных случаях.

Всем привет! Меня зовут Степан Трифонов, я аналитик‑разработчик в Яндекс Пэй. Недавно мы с коллегами, Леонидом Левиным и Савелием Чежеговым, опубликовали научную статью Incorporating Preconditioning into Accelerated Approaches: Theoretical Guarantees and Practical Improvement, где ввели предобусловленные версии классических ускоренных методов — Preconditioned Heavy Ball (PHB) и Preconditioned Nesterov (PN) — и доказали для них оценки сходимости при весьма общих допущениях на предобусловливающую матрицу. Также мы провели численные эксперименты, которые продемонстрировали практический выигрыш новых алгоритмов по сравнению с обычными (непредобусловленными) методами HB и Нестерова.

Метод Heavy Ball и метод Нестерова: ускорение и ограничения

Перед тем как перейти к новому алгоритму, кратко напомню идеи классических методов с импульсом и их проблемы на плохо обусловленных задачах. Метод импульса Поляка (Heavy Ball, HB) в каждой итерации сохраняет часть предыдущего шага и добавляет его к новому шагу градиентного спуска. В простейшей форме обновление можно записать как:

$x_{k+1} = x_k - \gamma\nabla f(x_k) + \beta(x_k - x_{k−1})$

, где $\beta\in[0,1)$ — коэффициент импульса, а $\gamma>0$ — шаг (темп) обучения. Иными словами, переменная x получает «толчок» в направлении предыдущего движения с весом $\beta$ , сглаживая зигзагообразные колебания градиентного метода и зачастую ускоряя спуск по узким долинам.

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

Метод Нестерова (Accelerated Gradient Descent, AGD) идёт дальше и достигает теоретически оптимальной скорости сходимости в классе гладких выпуклых задач. Его схема чуть сложнее: помимо текущей точки поддерживается вспомогательная точка , которая забегает вперёд на шаг импульса, после чего выполняется градиентный шаг из . В одной из распространённых реализаций обновление выглядит так:

$y_k = x_k +\beta(x_k - x_{k−1}), \;\;\;\;\;\;\;\;\;\;x_{k+1} = y_k -\gamma\nabla f(y_k)$

, где коэффициент $\beta$ последовательно уменьшается от значения, близкого к 1 (в начале оптимизации), к 0 (в конце) по особой формуле. Благодаря этому при $beta \approx 1$ метод делает довольно длинные упреждающие прыжки, которые компенсируются последующим градиентным шагом.

В итоге удаётся доказать, что убывает как для несильно выпуклых задач, а в случае $\mu$ ‑сильно выпуклой функции достигается линейная сходимость с коэффициентом $O \left( \sqrt{\frac{L}{\mu}} \right)$ в числе итераций — существенно лучше, чем $O\Big(\frac{L}{\mu}\Big)$ у градиентного спуска.

Таким образом, метод Нестерова обеспечивает ускорение в теории и на практике стал базовым методом для многих сложных задач. Тем не менее ни HB, ни классический AGD не решают проблем плохой обусловленности самостоятельно. Если условное число $\kappa = L/\mu$ велико, то даже с импульсом сходимость может оставаться неудовлетворительной. Например, метод Поляка в строго выпуклом случае вообще не улучшает скорость сходимости по порядку — его теоретическая оценка совпадает с градиентным спуском. Метод Нестерова в худшем случае упирается в фактор $\sqrt{\kappa}$ , который всё ещё может быть большим.

Для преодоления этой проблемы и применяется предобусловливание.

Предобусловливание и адаптивные методы

Предобусловливание (preconditioning) в общем виде означает замену исходной задачи $\min_x f(x)$ на эквивалентную задачу в других координатах: вводится невырожденная матрица (предобусловливания), после замены переменных $x = P^{-1}z$ функция переходит к $\tilde f(z) = f(P^{-1}z)$ . Градиентный шаг по эквивалентен шагу по с умножением на : $x \leftarrow x - P^{-1} \nabla f(x)$ . Выбор , близкой к $(\nabla^2 f(x^*))^{-1}$ (обратному оптимальному Гессиану), теоретически дал бы идеальную сходимость за один шаг, но на практике точно вычислить такой невозможно. Тем не менее различные приближённые и адаптивные схемы предобусловливания позволяют значительно ускорить спуск.

Квазиньютоновские методы (BFGS, L‑BFGS) динамически обновляют приближение обратного Гессиана по результатам предыдущих шагов. Методы AdaGrad, RMSProp, Adam и их аналоги используют более простую форму — диагональную матрицу — и обновляют её элементы на основе накопленной информации о градиентах. Например, AdaGrad изначально выбирает и далее вычисляет диагональ $(D_k){ii} = \varepsilon + \sum$ в шаге — большие градиенты по данной координате автоматически уменьшают шаг, а небольшие компоненты градиента наоборот дают больший эффективный шаг. RMSProp и Adam модифицируют эту идею, используя экспоненциальное сглаживание:

$(D_k)_{ii} = \max{(\varepsilon, \beta_2(D_k−1)_{ii} +(1 - \beta_2)[∇f(x_k)]^2_i)}$

, где $\beta_2 \approx 0.9\text{--}0.999$ — параметр сглаживания, а $\varepsilon>0$ не даёт делителю обращаться в 0. В Adam дополнительно вводится момент первого порядка (импульс для градиента, $\beta_1$ ).

Схожие идеи масштабирования подпространств лежат в основе многих методик — от естественного градиента и адаптивного сжатия шага в SGD до методов второго порядка для больших моделей. $^k [\nabla f(x_t)]_i^2$ (накопленные квадраты ‑й компоненты градиента) за счёт $\frac{1}{\sqrt{D_{k}}}$ . Важно отметить, что предобусловливание зачастую не нарушает теоретической сходимости метода, если матрица ограничена в разумных пределах.

В нашей статье сделано естественное предположение: существуют константы $0 < e \le \Gamma$ , такие, что для всех итераций матрица удовлетворяет $eI \preceq D_k \preceq Γ$ I.

Другими словами, ни один собственный элемент предобусловливания не становится меньше и больше $\Gamma$ Это обычно выполняется на практике: например, в AdaGrad или Adam диагональные элементы связаны с суммой квадратов градиента, которая заведомо конечна и положительна.

Тем не менее нижнюю грань иногда приходится вводить искусственно — в алгоритмах это реализуется как $\max{e, \text{обновлённое значение}}$ на диагонали. Такое ограничение предобусловливания означает, что мы не делаем бесконечно большие шаги ни в одном направлении и не «замораживаем» полностью какие‑либо координаты. Оно приводит к тому, что в оценках сложности появляется множитель $\Gamma/e$ (немного ухудшающий константы, но не порядок сходимости).

Таким образом предобусловливание в форме диагональной матрицы способно существенно ускорить сходимость методов первого порядка на плохо обусловленных задачах. Логично ожидать, что сочетание предобусловливания с импульсом (то есть объединение идей AdaGrad, Adam и Nesterov) даст ещё более эффективный метод. Именно этого мы и пытались достичь, предложив два алгоритма: предобусловленный Heavy Ball и предобусловленный Nesterov.

Предобусловленные алгоритмы: PHB и PN

Мы сформулировали два алгоритма: Preconditioned Heavy Ball (PHB) и Preconditioned Nesterov (PN). Это модификации классического метода Поляка и метода Нестерова с добавлением предобусловливания. Оба алгоритма работают с диагональной матрицей масштабирования , обновляемой по общему правилу (обозначим процедуру обновления как $\text{Update}(D_k, H_{k+1})$ на основе некоторой матрицы $H_{k+1}$ , содержащей информацию о функции на итерации . В частных реализациях может быть, например, матрицей квадратов градиента $\operatorname{diag} (\nabla f(x_k)\odot \nabla f(x_k))$ для адаптивных методов первого порядка либо матрицей, связанной с аппроксимацией Гессиана (как в OASIS или AdaHessian).

Обновление предполагается удовлетворяющим изложенному выше условию ограниченности ( $eI \preceq D_k \preceq \Gamma I$ ). Ниже приведён псевдокод алгоритма PHB.

У алгоритма PHB та же структура, что и у оригинального HB, за тем исключением, что градиент накапливается во временной переменной с учётом матрицы $D_k^{-1}$ . В строке 2 произведение $D_k^{-1}\nabla f(x_k)$ означает, что каждое измерение градиента масштабируется индивидуально: если по ‑й координате накоплена большая величина $D_{k,ii}$ (например, большой разброс или кривизна), то шаг по этой координате автоматически уменьшается.

После вычисления импульсного шага алгоритм обновляет точку $x_{k+1}$ привычным образом (строка 3). Наконец, строка 4 отвечает за пересчёт предобусловливания $D_{k+1}$ : вызывается некоторая процедура $\text{Update}$ , которая на основе текущего и новой информации $H_{k+1}$ генерирует матрицу, затем каждому её диагональному элементу применяется порог (как обсуждалось, это гарантирует положительность и ограниченность снизу).

Preconditioned Nesterov (PN) сочетает предобусловливание с двухшаговой схемой Нестерова — вычислением упреждающей точки и последующей коррекцией. Для него вводятся две последовательности коэффициентов ${\xi_k}$ и ${\theta_k}$ (как и в нестеровских методах, они могут быть выбраны по теоретической формуле, обеспечивающей ускорение). Ниже — псевдокод PN.

Алгоритм PN использует два состояния точки на каждой итерации: — условно быстрое приближение (после градиентного шага), и (без верхнего индекса) — скорректированное приближение. Порядок действий такой: сначала вычисляется $x_{k+1}^f$ — результат предобусловленного градиентного шага из некой точки (строка 2). Здесь играет роль точки, из которой считаем градиент; в начале алгоритма , а далее эта точка будет задаваться линейной комбинацией предыдущих состояний (строка 4).

После полученный промежуточный результат $x_{k+1}^f$ комбинируется с предыдущим : строка 3 выполняет корректирующий шаг Нестерова $x_{k+1} = x_k^f + \xi_k ,(x_{k+1}^f - x_k^f)$ . Если положить $\xi_k=0$ , то этой строкой можно пренебречь, и алгоритм PN превратится фактически в предобусловле��ный градиентный спуск. При ненулевых $\xi_k$ происходит «подтягивание» решения по направлению от старого к свежей точке $x_{k+1}^f$ .

Наконец, строка 4 вычисляет новую точку для расчёта градиента $x_{k+1}^g$ на следующей итерации как выпуклую комбинацию $x_{k+1}^f$ и $x_{k+1}$ .

Правильный выбор параметров $\xi_k$ и $\theta_k$ (например, как в классическом методе Нестерова) обеспечивает ускоренный режим сходимости алгоритма. Предобусловливание обновляется аналогично алгоритму PHB (строка 5).

Оба предложенных алгоритма представляют по сути обобщённые схемы, которые включают многие частные случаи. Если, например, взять (отсутствие предобусловливания), то PHB сведётся к обычному HB, а PN — к методу Нестерова. Если же выбрать правило Update аналогично Adam (диагональное экспоненциальное усреднение квадратов градиента) и при этом в PN положить $xi_k = \theta_{k+1}$ , мы получим алгоритм, очень близкий к оптимизатору Nadam (Nesterov Adam).

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

Теоретические гарантии и скорость сходимости

Главный результат нашего исследования, отражённый в статье, — доказательство сходимости алгоритмов PHB и PN при наложенных предположениях (сильная выпуклость и гладкость функции , а также ограниченность матриц предобусловливания ).

Ниже — упрощённые версии основных теорем и следствий (без технических деталей вроде приёмов ребалансировки точек и так далее).

Теорема 1: сходимость PHB

Пусть функция удовлетворяет условиям $\mu$ ‑сильной выпуклости и ‑гладкости, а матрица на каждой итерации удовлетворяет $eI \preceq D_k \preceq \Gamma I$ .

Тогда для алгоритма PHB с постоянным шагом $\displaystyle \gamma = \frac{(1-\beta_1)^2e}{12L}$ выполняется неравенство:

$f\!\left(\frac{1}{W_{K-1}} \sum_{k=0}^{K-1} w_k x_k\right) - f(x^*) \le 4 \exp\!\left( - \frac{(1 - \beta_1)\,\mu\, e\, K}{48\,L\,\Gamma} \right) \frac{L \,\|x_0 - x^*\|_{D^{-1}}^{2}}{1}\,$

, где $W_{K-1} = \sum_{k=0}^{K-1} w_k$ и $w_k = \Big(1 - \frac{\mu e}{4\Gamma}\Big)^{-(k+1)}$ .

Это довольно громоздкое выражение можно интерпретировать следующим образом: значения функции (в определённой средневзвешенной точке) убывают экспоненциально быстро с коэффициентом, пропорциональным $(1-\beta_1)\mu e/(L\Gamma)$ . Если пренебречь влиянием предобусловливания ( и $\Gamma$ заменить на 1) и выбрать оптимальное $\beta_1$ , то порядок сходимости будет $O!\Big(\frac{L}{\mu}\ln\frac{1}{\varepsilon}\Big)$ , что соответствует градиентному спуску.

Это неудивительно: известно, что HB в худшем случае не ускоряет сходимость сверх этого предела. Тем не менее теорема гарантирует, что линейная сходимость сохраняется и в присутствии масштабирования , пусть и с несколько иными константами.

Из этой теоремы напрямую вытекает утверждение о количестве итераций для достижения заданной точности: чтобы обеспечить $f(x_{\text{out}}) - f(x^*) \le \varepsilon$ , алгоритму PHB достаточно выполнить

$K = O\!\left( \frac{L\,\Gamma}{\mu\, e\, (1 - \beta_1)} \ln\!\frac{L \, \|x_0 - x^*\|^2}{\varepsilon} \right)$

итераций.

Отметим появление множителя $\Gamma/e$ при $L/\mu$ и $(1-\beta_1)$ в этой оценке — это плата за использование предобусловливания (в худшем случае условное число задачи увеличивается максимум в $\Gamma/e$ раз из‑за различия масштабов по осям).

Также присутствует делитель $(1-\beta_1)$ : при $\beta_1 \to 1$ метод стремится к пределу безусловной стабильности (но и без импульса нет смысла брать $\beta_1=0$ ). В экспериментальной части мы брали $\beta_1=0,9$ как компромисс.

Теорема 2: сходимость PN

Пусть выполнены те же условия на и . Тогда для алгоритма PN с шагом $\gamma_k = \frac{1}{L}\sqrt{\frac{\mu e}{L}}$ и последовательностями параметров $\xi_k \equiv \sqrt{\frac{\mu e}{L}}$ и $\theta_k \equiv \sqrt{\frac{\mu e}{L}}$ выполняется оценка:

$\|x_{k+1} - x^*\|_{D_{k+1}}^{2} \le \exp\!\left( - K \sqrt{\frac{\mu e}{4 L \Gamma}} \right) \left( \|x_0 - x^*\|_{D_0^{-1}}^{2} + \frac{2\Gamma}{\mu}\big(f(x^0) - f(x^*)\big) \right)$

Не вдаваясь в тонкости, заметим главное отличие от теоремы 1: в показателе экспоненты появился квадратный корень из $\mu/L$ (с дополнительным фактором $e/\Gamma$ ). Это означает, что алгоритм PN достигает ускоренной сходимости: при больших норма расстояния до оптимума убывает примерно как $O(\sqrt{L/\mu}\ln(1/\varepsilon))$ , что соответствует сложности $O(\sqrt{L/\mu}\ln(1/\varepsilon))$ итераций до заданной точности (с точностью до констант).

Формально это отражено в следующем следствии: алгоритму PN достаточно

$K = O\!\left( \sqrt{\frac{L\Gamma}{\mu e}}\; \ln \frac{ L\|x_0 - x^*\|^{2} + \dfrac{L\Gamma}{\mu}\big(f(x^{0}) - f(x^{*})\big) }{\varepsilon} \right)$

итераций для достижения критерия $|x_K - x^*|^2_{D_K} \le \varepsilon$ (или аналогичного по функциям).

Таким образом, предобусловленный метод Нестерова сохраняет ключевое преимущество оригинального AGD — ускорение порядка $\sqrt{\kappa}$ , где $\kappa = \frac{L\Gamma}{\mu e}$ можно интерпретировать как некое эффективное условное число с учётом масштабирования.

Для сравнения: у метода PHB в аналогичном месте формулы стоит $\kappa = \frac{L\Gamma}{\mu e(1-\beta_1)}$ , то есть нет квадратного корня, и зависимость от $(1-\beta_1)$ добавляет к ещё один множитель (это характерно и для обычного HB).

Также в статье мы отдельно обсуждаем два аспекта полученных оценок:

Норма, индуцированная . В теоремах прогресс сходимости оценивается в норме $| x - x^|{D^{-1}}$ или $|x - x^|{D}$ , связанной с матрицей предобусловливания. Это немного усложняет вид формул, но не меняет сути — можно показать, что переход к евклидовой норме приведёт лишь к появлению уже знакомого коэффициента $\Gamma$ (впрочем, под логарифмом или под корнем, то есть без влияния на порядок сложности).
Улучшение за счёт предобусловливания. В оценках для PHB и PN экспоненциальный коэффициент (обуславливающий скорость линейной сходимости) отличается. Для PHB присутствует множитель $\frac{(1-\beta_1)\mu e}{L\Gamma}$ , который по порядку такой же, как в ряде предшествующих работ по масштабированию градиентных методов.

Иными словами, PHB не улучшает теоретическую зависимость от $\kappa$ по сравнению с уже известными результатами (что согласуется с тем, что HB не даёт ускорения в худшем случае). Для предобусловленного Нестерова же экспонента содержит $\sqrt{\frac{\mu e}{L\Gamma}}$ , что эквивалентно ускорению — зависимость от $\kappa$ улучшена до $\sqrt{\kappa}$ .

Таким образом, PN в теории опережает PHB на классах задач, где достигается режим ускорения.

В целом анализ показывает, что добавление масштабирования (диагонального предобусловливания) не мешает сходимости ни HB, ни AGD. Для сильно выпуклых задач PHB остаётся линейно сходящимся методом порядка $O(L/\mu)$ , а PN — ускоренным методом порядка $O(\sqrt{L/\mu})$ . Дополнительный ценой является коэффициент $\Gamma/e$ при $L/ \mu$ в оценках сложности, который появляется из‑за допускаемой неоднородности предобусловливания. Однако такой множитель стандартен и неизбежен в анализе адаптивных методов.

Практические эксперименты

Также мы подкрепили теоретические результаты численным экспериментом на задаче бинарной классификации. В качестве датасетов выбраны два стандартных набора из библиотеки LibSVM: a9a (данные из UCI Adult для задачи определения дохода по анкетным данным) и w8a (данные по веб‑кликам). Обе выборки разделены на обучающую и тестовую части.

Сравнение сходимости методов на датасете a9a. По оси ординат отложена норма градиента (в логарифмическом масштабе), по оси абсцисс — число итераций. Синим показан метод HBl, оранжевым — PHB, зелёным — Nesterov, красным — PN. Предобусловленные версии заметно опережают оригинальные по скорости убывания градиента — Сравнение сходимости методов на датасете a9a. По оси ординат отложена норма градиента $|\nabla f(w)|^2$ (в логарифмическом масштабе), по оси абсцисс — число итераций. Синим показан метод HBl, оранжевым — PHB, зелёным — Nesterov, красным — PN. Предобусловленные версии заметно опережают оригинальные по скорости убывания градиента

Сравнение сходимости методов на датасете a9a. По оси ординат отложена норма градиента $|\nabla f(w)|^2$ (в логарифмическом масштабе), по оси абсцисс — число итераций. Синим показан метод HBl, оранжевым — PHB, зелёным — Nesterov, красным — PN. Предобусловленные версии заметно опережают оригинальные по скорости убывания градиента

Как и предсказывает теория, на обоих датасетах предобусловленные версии алгоритмов сходятся быстрее. График выше показывает типичную картину: метод Нестерова убывает быстрее, чем HB. Добавление предобусловливания ускоряет оба метода (оранжевая и красная кривые лежат ниже).

Особенно заметен выигрыш у метода Нестерова: красная кривая (PN) уходит вниз гораздо круче, чем зелёная (классический AGD), — примерно на порядок по $|\nabla f(w)|^2$ за тот же интервал итераций. PHB (оранжевый) тоже показывает более быструю сходимость, чем обычный HB (синий), хотя разрыв между ними чуть меньше.

На втором датасете (w8a) наблюдается аналогичная картина.

Сравнение методов на датасете w8a. Видно, что качественные выводы совпадают с предыдущим графиком: предобусловливание даёт выигрыш в скорости сходимости как для HB, так и (особенно сильно) для метода Нестерова

Небольшое отличие в том, что кривая HB осцилирует сильнее, — это связано со свойством конкретных данных и шагом метода, из‑за чего импульс порождает колебания. Тем не менее финальная точность (уровень, на котором значение $|\nabla f(w)|^2$ выходит на плато) у предобусловленных методов выше.

В обоих экспериментах алгоритм PN достиг наименьшего значения критерия за заданное число итераций. Хотя наши теоретические оценки сложности для предобусловленных методов содержат дополнительный неблагоприятный множитель $\Gamma/ e$ (по сути, из‑за возможного ухудшения кондиции при масштабировании), на практике этот эффект не мешает достичь ускорения.

Полученные графики подтверждают применимость подхода: предобусловливание действительно позволяет алгоритмам с импульсом быстрее находить минимум по сравнению с их «неадаптивными» аналогами.

Заключение

По итогу нашей работы мы предложили два ускоренных алгоритма оптимизации, объединяющих методы импульса (HB, Nesterov AGD) с механизмом предобусловливания первого порядка (адаптивным масштабированием шагов). Для методов Preconditioned Heavy Ball и Preconditioned Nesterov мы провели теоретический анализ сходимости и доказали, что на сильно выпуклых гладких задачах PHB сходится линейно, а PN — линейно с ускорением (в терминах числа итераций примерно на $\sqrt{\kappa}$ быстрее). Эти гарантии получены при достаточно общих требованиях к матрице масштабирования (диагональный , ограниченный сверху и снизу положительными константами). Причём в оценках появляется лишь стандартный для адаптивных методов множитель $\Gamma/e$ , немного влияющий на константы.

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

Когда же стоит применять PHB и PN? Они перспективны в ситуациях, где обычно помогают адаптивные методы, — то есть при резком различии масштабов по параметрам, при наличии разреженных признаков, в больших по размерности задачах, а также в глубоком обучении. В таких случаях предобусловливание ускоряет сходимость, а сочетание с импульсом даёт дополнительное преимущество.

Предобусловленный HB может быть полезен, если по каким‑то причинам метод Нестерова использовать неудобно (например, из‑за сложности настройки или в стохастических условиях), так как PHB проще и менее требователен к адаптации коэффициентов. С другой стороны, если главной целью является максимальное ускорение с теоретическими гарантиями, PN выглядит более привлекательным, показывая лучшую зависимость от $\kappa$ . Ограничением работы является фокус на детерминированных гладких задачах — в условиях стохастического шума или негладкости функции требуются отдельные исследования.

Наша работа открывает возможности для дальнейших исследований: попробовать внедрить предобусловливание в стохастические варианты метода Нестерова в задачи с седловой структурой или неевклидовой геометрией, а также изучить поведение PHB и PN при ослаблении условий ‑гладкости (например, для моделей с разрывной субградиентной структурой).

Кроме того, довольно интересное направление — выбор оптимальной стратегии обновления под конкретную задачу. Здесь возможны заимствования из вторых производных, методов типа AdaHessian, а также более сложных адаптивных правил.

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

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

Предобусловливание и импульс в оптимизации: взгляд на алгоритмы PHB/PN от исследователей Яндекса