Stochastic Gradient Descent with Pre-Conditioned Polyak Step-Size

Texto integral

1. ВВЕДЕНИЕ

В настоящей статье мы рассматриваем задачу минимизации эмпирического риска (МЭР, англ. Empirical risk minimization, ERM), имеющую вид оптимизации конечной суммы:

$w^{\ast }\in \underset{w\in {ℝ}^d}{\mathrm{argmin}}\left\{f\left(w\right):=\frac{1}{n}\sum _{i=1}^n{f}_i\left(w\right)\right\}$, (1)

где $w\in {ℝ}^d$ является параметром весов и каждая целевая функция $f_i:{ℝ}^d\to ℝ$ является гладкой и дважды дифференцируемой. Функция потерь f_i(w) вычисляет разницу между предсказанием модели с параметрами весов w и целевым значением y. Целью является минимизация средней потери $f\left(w\right)=\frac{1}{n}{\sum }_{i=1}^n{f}_i\left(w\right)$ на n данных ${\left\{\right(x_i,y_i\left)\right\}}_{i=1}^n$, где x_i — входная точка данных и y_i — соответствующее целевое значение. В связи с нетривиальностью данной задачи решение в явном виде не всегда доступно, что подталкивает к применению численных методов оптимизации. Одним из таких численных методов является стохастический градиентный спуск (SGD) со следующим обновлением параметров весов:

$w_{t+1}=w_t-{\gamma }_t\nabla f_i\left(w_t\right)$, (2)

где ${\gamma }_t\in ℝ$ — размер шага метода. Использование мини-батчей для датасетов с большой размерностью при обучении значительно уменьшает время сходимости к оптимальной точке w^*. Были проведены обширные исследования в области стохастических методов оптимизации первого порядка начиная с фундаментальных работ Г. Роббинса и С. Монро [1], Б. Т. Поляка [2], Б. Т. Поляка и А. Б. Юдицкого [3], А. С. Немировского и др. [4] и ускоренные версии от Г. Лан [5]. Стоить отметить, что каждая комбинация функции потерь и датасета требует отдельной ручной настройки размера шага γ_t для поиска минимума, что делает γ_t гиперпараметром. Эта проблема ручной настройки γ_t является одним из мотивирующим факторов разработки методов с адаптивным размером шага, где γ_t заменена адаптивно меняющимся выражением по ходу оптимизации. В последнее время такие адаптивные методы получили широкое распространение (см. [6]–[13]) особенно в области обучения глубоких нейронных сетей.

Другое направление адаптивных стохастических методов — стохастический градиентный спуск с размером шага им. Б. Т. Поляка, который был вдохновлен размером шага для субградиентных методов, предложенным Борисом Теодоровичем Поляком в 1969 г. (см. [14], [15]). Позже был предложен стохастический вариант этого шага в [16], [17] и другие различные расширения в [18]–[24]. В следующем разделе мы детально разберем некоторые из них.

Одним из главных предметов обсуждения статьи является получение методов, предназначенных для решения задач с плохой обусловленностью с помощью техники предобуславливания градиента. Несмотря на то, что достижение идеального предобусловливания практически невозможно, наше решение использует различные техники, предложенные в таких адаптивных алгоритмах, как Adam [7] и AdaGrad [6], а также метод Хатчинсона [25].

Введем обозначения. Мы наделяем прямое пространство w ∈ E и двойственное пространство g ∈ E* сопряженными нормами ||w|| и ||g||_* соответственно. Как частный случай для положительно-определенной матрицы $B\in {ℝ}^{d\times d}$ мы определяем двойственные евклидовы нормы: ||w||_B = <Bw, w>^1/2 и ${||g||}_{B^{-1}}={〈g,B^{-1}g〉}^{1/2}$. Отметим, что ∇f(w) ∈ E и ∇²f(w)h ∈ E для h ∈ E. Оператор $\odot$ определяется как покомпонентное умножение двух векторов, также известное как произведение Адамара. Мы обозначаем diag(v) диагональную матрицу по заданному вектору v и вектор $diagonal\left(H\right)\in {ℝ}^d$ как диагональ матрицы $H\in {ℝ}^{d\times d}$. Для простоты мы также вводим следующее обозначение: (x)₊ = max {0, x}.

2. ОБЗОР ЛИТЕРАТУРЫ И СВЯЗАННЫЕ РАБОТЫ

Давайте введем общее правило обновления для рассматриваемых методов как

$w_{t+1}=w_t-{\gamma }_t{B}_t^{-1}{m}_t$, (3)

где γ_t — размер шага, H_t = B_t^–1 — специальная предобуславливающая матрица, и m_t обозначает либо g_t (градиент или его некоторая аппроксимация), либо первый момент градиента с параметром β₁. Для объяснения этого обновления мы можем представить, что направление спуска m_t шкалируется и вращается предобуславливающей матрицей H_t, и делается шаг с размером шага γ_t. Некоторые известные адаптивные методы первого порядка пользуются слегка упрощенной формой того же правила обновления:

$w_{t+1}=w_t-{\gamma }_t{m}_t/v_t$, (4)

где m_t и v_t — первый и второй моменты, а m_t/v_t — покоординатное деление. Упомянутые типы шагов заключают в себе одну и ту же идею предобуславливания направления спуска и могут быть для простоты использованы взаимозаменяемо на протяжении всей статьи.

Таким же образом можно описать классические методы оптимизации. Например, для получения обновления SGD требуется обозначить предобуславливающую матрицу B_t = I, первый момент m_t = g_t и размер шага γ_t как константу. Стоить отметить, что γ_t в SGD является особенно важным гиперпараметром, который требует специальной настройки в соответствии с заданными данными и функцией потерь, а методы с адаптивным размером шага, некоторые из которых используют предобуславливающую матрицу, основанную на локальной кривизне функции потерь, были представлены для устранения этой проблемы.

Классические методы с размером шага им. Б. Т. Поляка не используют такую информацию, но, тем не менее, стоит умопянуть о том, как получить классический детерминистический размер шага им. Б. Т. Поляка. Рассмотрим выпуклую функцию f(w) и ограниченное сверху расстояние от w_{t + 1} до оптимальной точки w^*:

${||w_{t+1}-w^{\ast }||}^2\le Q\left(\gamma \right), где Q\left(\gamma \right)={||w_t-w^{\ast }||}^2-2\gamma \left[f\left(w_t\right)-f^{\ast }\right]+{\gamma }_t^2{||g_t||}_{\ast }^2$.

Здесь g_t обозначает субградиент функции f(w), а f^* — минимум функции. Минимизируя верхнюю границу Q(γ), мы получаем размер шага им. Б. Т. Поляка и можем выразить его через правило обновления (3):

${\gamma }_t=\underset{\gamma \in ℝ}{\mathrm{argmin}}\left[Q\left(\gamma \right)\right]=\frac{f\left(w_t\right)-f^{\ast }}{{||g_t||}_{\ast }^2}, B_t=I и m_t=g_t$. (5)

Подробный разбор доказательства приведен в [26]. Заметим, что размер шага (5) может быть применен только в том случае, когда оптимальное значение f^* уже известно. Несмотря на то, что иногда это значение известно как f^* = 0 (например в задачах классификации), детерминистическая природа данного метода делает его непрактичным. Для решения этой проблемы был представлен стохастический градиентный спуск с размером шага им. Б. Т. Поляка (SPS, Stochastic Gradient Descent with Polyak Step-size) (см. [17]) вместе с более практичной версией SPS_max, который ограничивает γ_t постоянной γ_b:

${\gamma }_t^{SPS}=\frac{f_i\left(w_t\right)-f_i^{\ast }}{{||\nabla f_i\left(w_t\right)||}_{\ast }^2} и {\gamma }_t^{SPS\max }=\min \left\{\frac{f_i\left(w_t\right)-f_i^{\ast }}{{||\nabla f_i\left(w_t\right)||}_{\ast }^2},{\gamma }_b\right\}$. (6)

Метод SPS все еще требует знания f_i^*, но при определенных режимах оптимизации стандартной нерегуляризированной функции потерь, таких как квадратичная задача для линейной регрессии и логистическая регрессия для классификации, оптимальное решение f_i^* равно 0. Если f^* = 0, то правило обновления SPS выражается как

${\gamma }_t=\frac{f_i\left(w_t\right)}{\parallel \nabla f_i\left(w_t\right){\parallel }_{\ast }^2}, H_t=I и m_t=\nabla f_i\left(w_t\right)$. (7)

Также существует другой способ получения метода SPS. Если предположить, что выполнено условие интерполяции, то мы можем решить (1) путем выборки i ∈ {1, 2,..., n} н. о. р.с.в. на каждой итерации t и решением нелинейного уравнения

$w_{t+1}=\underset{w\in {ℝ}^d}{\mathrm{argmin}}\parallel w-w^t{\parallel }^2 т.ч. f_i\left(w\right)=0$. (8)

Хотя приведенная выше проекция может иметь аналитическое решение для некоторых простых функций потерь, для большинства нелинейных моделей, таких как глубокие нейронные сети, не существует решения в замкнутой форме. Поэтому вместо точного решения мы можем линеаризовать f_i(w) вокруг текущей итерации w^t, чтобы получить

$w_{t+1}=\underset{w\in {ℝ}^d}{\mathrm{argmin}}{||w-w^t||}^2 т.ч. f_i\left(w^t\right)+<\nabla f_i\left(w^t\right),w-w^t>=0$.

Правило обновления (7) и есть аналитическое решение этой задачи.

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

$$\begin{gathered} \underset{w\in {ℝ}^d,s\ge 0}{\mathrm{argmin}}s \\ т.ч. f_i\left(w\right)\le s для i=\mathrm{1,} \mathrm{2,}\dots , n; \\ \underset{w\in {ℝ}^d,s\ge 0}{\mathrm{argmin}}{s}^2 \\ т.ч. f_i\left(w\right)\le s для i=\mathrm{1,} \mathrm{2,}\dots , n; \end{gathered}$$

которые называются L1- и L2-остаточными минимизациями (см. [19]) соответственно. Отметим, что цель этого метода состоит в том, чтобы приблизить s к нулю, что позволяет решать задачи, в которых предположение интерполяции не выполняется.

3. РЕЗУЛЬТАТЫ

В статье мы объединяем предобусловливание и варианты остаточно-регуляризованных методов SPS. Затем мы демонстрируем, что эти новые предобусловленные методы хорошо работают на плохо масштабированных и плохо обусловленных данных.

• Усовершенствованный SPS. Мы расширили методы SPS и представили три новых алгоритма: PSPS, PSPSL1 и PSPSL2, которые используют метод Хатчинсона, Adam и AdaGrad для предобусловливания градиентного шага с использованием размера шага им. Б. Т. Поляка для взвешенной евклидовой нормы. Правила обновлений наших методов в явном виде описаны ниже.
• Имплементация в PyTorch. Мы разработали практические варианты наших методов в качестве оптимизаторов PyTorch и опубликовали программный код в нашем репозитории GitHub¹.
• Эмпирические Результаты. Мы привели несколько экспериментов с двумя разными задачами, чтобы сравнить наши результаты с SGD, Adam, AdaGrad и с вариантами SPS, в которых не применяются какие-либо методы предобусловливания. Мы показали, что предложенные нами алгоритмы демонстрируют заметные улучшения на плохо обусловленных задачах.

4. ПРЕДОБУСЛОВЛИВАНИЕ

Данные могут быть плохо масштабированы и/или плохо обусловлены, тогда предобусловливание градиента — это один из способов улучшить сходимость алгоритмов. Методы, использующие предобусловливание, имеют следующее общее правило обновления:

$w_{t+1}=w_t-{\gamma }_t{B}_t^{-1}\nabla f_i\left(w_t\right)$,

где $B_t\in {ℝ}^{d\times d}$ — обратимая и положительно-определенная матрица. Метод Ньютона — один из самых наглядных примеров метода, использующего предобусловливание. В этом случае $B_t={\nabla }^{2}f\left(w_t\right)$ и γ_t = 1. Среди более современных и практичных методов с предобуславливанием отметим AdaHessian [27], Adagrad [6] и OASIS [28]. Эти методы включают кривизну функции потерь посредством адаптивных оценок Гессиана.

4.1. Метод Хатчинсона

Метод Хатчинсона (см. [25]) используется для оценки диагонали матрицы Гессиана. Для вычисления этой оценки метод Хатчинсона использует лишь несколько произведений Гессиана на вектор, которые, в свою очередь, можно эффективно вычислить с помощью быстрого автоматического дифференцирования (см. [29]). Произведение матрицы Гессиана ∇²f(w) и фиксированного вектора z можно вычислить через производную градиента по направлению. Чтобы понять, как этот метод используется для предобусловливания, сначала мы покажем, что затраты на вычисление произведения Гессиана на вектор близки к двух вычислениям градиентов, т. е.

${\nabla }^{2}f\left(w\right)z=\nabla (z^T\nabla f(w\left)\right)$. (9)

Затем мы можем вычислить диагональ Гессиана, используя метод Хатчинсона:

$diag\left({\nabla }^{2}f\right(w\left)\right)=\mathbb{E}\left[z\odot \left({\nabla }^{2}f\right(w\left)z\right)\right]$,

где z — случайный вектор с распределением Радемахера² или нормальным распределением, а ∇²f(w)z вычисляется с помощью произведения Гессиана на вектор, заданного в (9).

Можно доказать, что математическое ожидание $z\odot \left({\nabla }^{2}f\right(w\left)z\right)$ является диагональю Гессиана (см. [30]). Используя это тождество, мы оцениваем диагональ Гессиана по заданному D₀, генерируя случайный вектор z на каждой итерации и обновляя нашу оценку с использованием средневзвешенного значения следующим образом:

$D_t=\beta D_{t-1}+(1-\beta )diag(z\odot {\nabla }^{2}f(w\left)z\right)$,

где β ∈ (0,1) — параметр момента и

$D_0=\frac{1}{m}\sum _{i=1}^{m}diag(z_i\odot {\nabla }^{2}f(w_0\left)z_i\right)$.

Наконец, чтобы гарантировать, что D_t остается положительно-определенным, несмотря на возможную невыпуклость функций потерь, мы используем усечение и сохраняем только абсолютные значения элементов следующим образом: (${\hat{D}}_t$)_{j, j} = max{α, |D_t| _{j, j}}.

Algorithm 1. Аппроксимация диагонали Гессиана с использованием метода Хатчинсона

1: Ввод: β ∈ (0,1), α > 0

2: Инициализация: $D_0=\frac{1}{m}{\sum }_{i=1}^{m}diag(z_i\odot {\nabla }^{2}f(w_0\left)z_i\right)$

3: for t = 1, 2,..., T do

4: Генерируем случайный вектор z из Радемахера/нормального распределения

5: $D_t=\beta D_{t-1}+(1-\beta )diag(z\odot {\nabla }^{2}f(w_0\left)z\right)$

6: (${\hat{D}}_t$)_{j, j} = max{α,| D_t | _{j, j}}

7: Вывод: ${\hat{D}}_T$

4.2. Метод AdaGrad

AdaGrad — это метод стохастической оптимизации, который аппроксимирует Гессиан функции, чтобы адаптировать размер шага в зависимости от информации о кривизне. Ключевая идея заключается в использовании информации о кумулятивном квадрате градиента для шкалирования размера шага. В форме (4) правило обновления для AdaGrad может быть задано следующим образом:

$m_t=g_t и v_t=\sqrt{\sum _{i=1}^t{g}_i\odot g_i}$.

Накопление всех предыдущих градиентов в предобуславливателе v_t приводит к уменьшению размера шага γ_t, что повышает производительность при разреженных данных (нечастых признаках), при этом ухудшается в случае плотных данных.

4.3. Метод Adam

Представленный в [7] Adam разработан для преодоления недостатков других популярных алгоритмов оптимизации, таких как AdaGrad [6] и RMSProp [31], путем включения как адаптивного размера шага, так и обновлений на основе метода “тяжелого шарика” (momentum). Правило обновления Adam предполагает вычисление скользящего среднего как для первого, так и для второго моментов градиентов. Первый момент — это среднее значение градиентов, а второй момент — нецентрированная дисперсия градиентов. Правило обновления для Adam может быть выражено в терминах (4) следующим образом:

$m_t=\frac{(1-{\beta }_1){\displaystyle {\sum }_{i=1}^t}{\beta }_1^{t-i}{g}_i}{1-{\beta }_1^t}, v_t=\sqrt{\frac{(1-{\beta }_2){\displaystyle {\sum }_{i=1}^t}{\beta }_2^{t-i}{g}_i\odot g_i}{1-{\beta }_2^t}}$,

где 0 < β₁, β₂ < 1 — два гиперпараметра, называемых коэффициентами первого и второго моментов. Смещенные оценки корректируются путем деления их на члены коррекции смещения, которые являются степенями скоростей затухания β₁ и β₂ соответственно.

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

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

$w_{t+1}=\underset{w\in {ℝ}^d}{\mathrm{argmin}}{||w-w_t||}^2 т.ч. f_i\left(w\right)=0$. (10)

Обратите внимание, что ограничение f_i(w)= 0 определено как условие интерполяции.

Определение 1. Мы предполагаем, что условие интерполяции выполняется для набора функций {f_i(w)}ⁿ_{i = 1} по заданному набору данных {(x_i, y_i)}ⁿ_{i = 1} с неотрицательными функциями потерь f_i(w) ≥ 0, когда

$\exists w^{\ast }\in {ℝ}^d т.ч. f_i\left(w^{\ast }\right)=0\forall i\in \{\mathrm{1,2,}\dots ,n\}$.

Одним из представленных методов, используемых в настоящей работе, является использование предобуславливания для улучшения скорости сходимости в случае плохо обусловленных данных. Чтобы получить это, мы изменяем норму в проекции (10) на взвешенную норму, основанную на предобуславливателе $B_t\succ 0$. Другой важной частью является линейная аппроксимация условия интерполяции f_i(w) = 0. Согласно разложению Тейлора функции f_i(w), линейное приближение (первого порядка) задается через $f_i\left(w\right)\approx f_i\left(w_t\right)+<\nabla f_i\left(w_t\right),w-w_t>$. Мы используем это приближение, чтобы ослабить условие интерполяции, которое не допускает решения в явном виде для большинства нелинейных моделей. Другой способ получения аналитического решения — ввести дополнительную переменную остатка (описано позже).

Предобусловленный SPS. Мы рассматриваем дифференцируемую выпуклую функцию f_i и линеаризацию условия интерполяции. Чтобы вывести предобусловленное правило обновления, мы используем взвешенную норму в проекции, полученный метод мы называем PSPS (Preconditioned Stochastic Gradient Descent with Polyak Step-size). В настоящей статье мы рассмотрим три варианта предобуславливания, а именно, метод Хатчинсона и предобуславливание оптимизаторов AdaGrad и Adam.

Лемма 1 (PSPS). Пусть $B_t\succ 0$ для всех t ≥ 0, тогда итеративный явный шаг для задачи

$w_{t+1}=\underset{w\in {ℝ}^d}{argmin}\frac{1}{2}{||w-w_t||}_{B_t}^2, т.ч. f_i\left(w_t\right)+<\nabla f_i\left(w_t\right),w-w_t>=0$

выражается как

$w_{t+1}=w_t-\frac{f_i\left(w_t\right)}{\left|\right|\nabla f_i\left(w_t\right)|{|}_{B_t^{-1}}^2}{B}_t^{-1}\nabla f_i\left(w_t\right)$.

Отметим, что данный шаг может быть переформулирован в виде шага (3), где

${\gamma }_t=\frac{f_i\left(w_t\right)}{\left|\right|\nabla f_i\left(w_t\right)|{|}_{B_t^{-1}}^2} и m_t=\nabla f_i\left(w_t\right)$.

Аналогичным образом мы можем применить предобуславливание для методов с остатком и получить следующие два метода: PSPSL1 и PSPSL2.

Лемма 2 (PSPSL1). Пусть $B_t\succ 0$ для любых t ≥ 0 и μ, λ > 0, тогда явный вид шага для задачи

$\begin{array}{c}{w}_{t+1},s_{t+1}=\underset{w\in {ℝ}^d,s\ge 0}{argmin}\frac{1}{2}\parallel w-w_t{\parallel }_{B_t}^2+\mu {\left(s-s_t\right)}^2+\lambda s,\\ т.ч. f_i\left(w_t\right)+〈\nabla f_i\left(w_t\right),w-w_t〉\le s\end{array}$

выражается как

${\gamma }_t^{L1}=\frac{{\left(f_i\right(w_t)-s_t+\lambda /2\mu )}_{+}}{1/2\mu +\parallel \nabla f_i\left(w_t\right){\parallel }_{B_t^{-1}}^2}, {\gamma }_t=\min \left\{{\gamma }_t^{L1},\frac{f_i\left(w_t\right)}{\parallel \nabla f_i\left(w_t\right){\parallel }_{B_t^{-1}}^2}\right\}$.

Лемма 3 (PSPSL2). Пусть $B_t\succ 0$ для любых t ≥ 0 и μ, λ > 0, тогда явный вид решения задачи

$\begin{array}{c}{w}_{t+1}, s_{t+1}=\underset{w\in {ℝ}^d,s\in ℝ}{argmin}\parallel w-w_t{\parallel }_{B_t}^2+\mu {(s-s_t)}^2+\lambda s^2,\\ т.ч. f_i\left(w_t\right)+〈\nabla f_i\left(w_t\right),w-w_t〉\le s\end{array}$ (11)

выражается как

$$\begin{gathered} w_{t+1}=w_t-\frac{{\left(f_i\left(w_t\right)-\mu \hat{\lambda }{s}_t\right)}_{+}}{\hat{\lambda }+{\left|\left|\nabla f_i\left(w_t\right)\right|\right|}_{B_t^{-1}}^2}{B}_t^{-1}\nabla f_i\left(w_t\right), \\ {s}_{t+1}=\hat{\lambda }\left(\mu s_t\frac{{\left(f_i\left(w_t\right)-\mu \hat{\lambda }{s}_t\right)}_{+}}{\hat{\lambda }+{\left|\left|\nabla f_i\left(w_t\right)\right|\right|}_{B_t^{-1}}^2}\right), \end{gathered}$$

где $\hat{\lambda }=1/\left(\mu +\lambda \right)$. Здесь остаточная параметр  заставляет s быть ближе к 0, пока µ не дает s_{t + 1} быть далеко от s_t.

6. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ

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

Мы использовали датасеты из LIBSVM³, а именно, mushrooms и colon-cancer, для иллюстрации эффективности предложенных методов, минимизирующих функцию потерь логистической регрессии и нелинейных наименьших квадратов в задачах бинарной классификации. Кроме того, каждый эксперимент дополнительно проводится на плохо обусловленной версии тех же наборов данных, где столбцы умножаются на вектор $e={\left\{\exp \right(x_i\left)\right\}}_{i=1}^d$, где x_i генерируется из равномерного распределения с интервалом [−k, k]. На всех приведенных далее иллючтрациях термин k относится к этому коэффициенту шкалирования, где k = 0 — исходные данные.

Во время обучения предложенными методами мы применяли параметры остатка $\lambda =0.01$ и µ = 0.1. Для метода Хатчинсона мы применили α = 10⁻⁴ и β = 0,999. Гиперпараметры (за исключением размера шага) для других методов (SGD, Adam и т. д.) были сохранены в качестве значений по умолчанию. Все эксперименты проводились с пятью различными ключами генераторов случайности (seed), используя PyTorch 1.11.0.

Оптимизируемые функции. Пусть ${\left\{(x_i,y_i)\right\}}_{i=1}^n$ — это данные из выбранного датасета. Логистическая регрессия определена следующим образом:

$f_{Log\mathrm{Re}g}\left(w\right)=\frac{1}{n}{\sum }_{i=1}^n\log (1+\exp (-y_i{x}_i^{т}w\left)\right)$,

где $x_i\in {ℝ}^d$ и y_i ∈ {−1, +1}. Нелинейные наименьшие квадраты заданы как

$f_{NLLSQ}\left(w\right)=\frac{1}{n}{\sum }_{i=1}^n{(y_i-1/(1+\exp (-x_i^{т}w)\left)\right)}^2$,

где y_i ∈ {0, 1}.

На фиг. 3 мы сравниваем скорости сходимости SPS с предобуславливателем Adam и без него. Наблюдаем, что в случае плохо обусловленных данных нам необходимо точно настроить размер шага оптимизатора Adam, чтобы избежать расхождений, поскольку выбор одинаковых размеров шага в обоих версиях данных привело к расхождению с k = 6. Кроме того, мы можем наблюдать, как различные методы предобуславливания превосходят SPS без какого-либо предобуславливания как для исходных данных, так и для плохо обусловленных. Отсутствие необходимости ручной настройки размера шага является одним из преимуществ предобусловленных методов SPS. Аналогичные результаты можно наблюдать на фиг. 6 и 9 для датасета colon-cancer. На фиг. 3б мы видим, что шкалирование данных приводит к тому, что размер шага Adam приходится уменьшать по мере увеличения коэффициента шкалирования k, чтобы метод не расходился.

 

Фиг. 1. Метод Adam vs PSPS с разным предобуславливанием для логистической регрессии на датасете mushrooms

 

Фиг. 2. Методы AdaGrad vs PSPS с разным предобуславливанием для логистической регрессии на датасет mushrooms

 

Фиг. 3. Методы Adam vs PSPS с разным предобуславливанием для логистической регрессии на датасете colon-cancer

 

Мы также сравниваем наши методы с оригинальными SPS, SPSL1, SPSL2, SGD и Adam (фиг. 4 и 5).

 

Фиг. 4. Сравнение эффективности PSPSL1 и PSPSL2 с SPS, SGD и Adam для логистической регрессии на оригинальных и плохо обусловленных версиях датасета colon-cancer

 

Фиг. 5. Сравнение эффективности PSPSL1 и PSPSL2 с SPS, SGD и Adam для логистической регрессии на оригинальных и плохо обусловленных версиях датасета mushrooms

 

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

В статье мы изучили влияние предобуславливания на семейство методов SPS (стохастический градиентный спуск с размером шага им. Б. Т. Поляка). Мы предложили новые методы PSPS, PSPSL1, PSPSL2 в (11)–(13). Эксперименты проводились как в выпуклых, так и в невыпуклых случаях с двумя разными датасетами. В настоящей статье отсутствует теоретический анализ предлагаемых нами методов, который может быть проведен в качестве последующей исследовательской работы. Кроме того, интересно провести эксперименты с более сложными моделями, такими как глубокие нейронные сети.

¹ https://github.com/fxrshed/ScaledSPS.

² z_i ∈ {−1, +1} с равной вероятностью.

³ https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/

Sobre autores

F. Abdukhakimov

Mohamed bin Zayed University of Artificial Intelligence

Autor responsável pela correspondência
Email: farshed888@gmail.com
Emirados Árabes Unidos, Abu Dhabi

Ch. Xiang

Mohamed bin Zayed University of Artificial Intelligence

Email: chulu.xiang@mbzuai.ac.ae
Emirados Árabes Unidos, Abu Dhabi

D. Kamzolov

Mohamed bin Zayed University of Artificial Intelligence

Email: kamzolov.opt@gmail.com
Emirados Árabes Unidos, Abu Dhabi

M. Takáč

Mohamed bin Zayed University of Artificial Intelligence

Email: takac.mt@gmail.com
Emirados Árabes Unidos, Abu Dhabi

Bibliografia

Arquivos suplementares