Алгоритмы редукции дисперсии (SAGA, SVRG, SARAH)

Материал из MachineLearning.

Версия от 15:02, 25 июня 2026; Renal Gazizullin (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Введение
2 Общая концепция редукции дисперсии
3 Алгоритм SVRG
4 Алгоритм SAGA
5 Алгоритм SARAH
6 Практическое применение: Проксимальный вариант SAGA для LASSO
7 Сравнение алгоритмов
8 Литература

Введение

Обучение большинства моделей машинного обучения формализуется как задача выпуклой оптимизации на конечной сумме (Finite-Sum Minimization):

$\min_{w \in \mathbb{R}^d} F(w) = \frac{1}{n} \sum_{i=1}^n f_i(w)$

где $f_i(w)$ — функция потерь на $i$ -м объекте выборки. Очевидно, что вычисление полного градиента $\nabla F(w)$ на каждом шаге требует $O(nd)$ операций, что делает классический градиентный спуск практически бесполезным на больших данных. Наивный SGD решает вычислительную проблему, используя градиент по одному случайно выбранному объекту $\nabla f_{i_t}(w_t)$ . Будучи несмещенной оценкой матожидания ( $\mathbb{E}[\nabla f_{i_t}(w_t)] = \nabla F(w_t)$ ), такой стохастический градиент обладает неустранимой дисперсией $\sigma^2 > 0$ . Шум градиента не исчезает даже в точке глобального оптимума $w^*$ . Это вынуждает асимптотически уменьшать длину шага $\eta_t \to 0$ , что фатально снижает скорость сходимости до сублинейной $O(1/T)$ . Алгоритмы редукции дисперсии устраняют этот недостаток, позволяя использовать постоянный шаг и достигать линейной сходимости.

Общая концепция редукции дисперсии

В основе семейства методов (SVRG, SAGA, SARAH) лежит статистический прием контрольных переменных (control variates). Конструируется новая оценка градиента $v_t$ , использующая сильно коррелированную вспомогательную переменную, матожидание которой известно:

$v_t = \nabla f_{i_t}(w_t) - \nabla f_{i_t}(\tilde{w}) + \nabla F(\tilde{w})$

где $\tilde{w}$ — точка «привязки» (снапшот), полный градиент в которой $\nabla F(\tilde{w})$ вычисляется периодически. При сходимости $w_t \to w^*$ и $\tilde{w} \to w^*$ разность $\nabla f_{i_t}(w_t) - \nabla f_{i_t}(\tilde{w}$ стремится к нулю, а дисперсия $\mathbb{E}[\|v_t - \nabla F(w_t)\|^2] \to 0$ .

Алгоритм SVRG

SVRG (Stochastic Variance Reduced Gradient)^[1] использует жесткую стратегию эпох. В начале каждой эпохи фиксируется точка $\tilde{w}$ , вычисляется ресурсоемкий полный градиент $\nabla F(\tilde{w})$ , после чего выполняется внутренний цикл из $m$ стохастических шагов.

Псевдокод SVRG:

Инициализация: $\tilde{w}_0$
Для эпох :
- $\tilde{w} = \tilde{w}_{s-1}$
- $\mu = \frac{1}{n} \sum_{i=1}^n \nabla f_i(\tilde{w})$
- $w_0 = \tilde{w}$
- Для :
  - Выбрать индекс $i_t \in \{1, \dots, n\}$ равномерно случайно.
  - Вычислить скорректированный градиент: $v_t = \nabla f_{i_t}(w_t) - \nabla f_{i_t}(\tilde{w}) + \mu$
  - Шаг: $w_{t+1} = w_t - \eta v_t$
- $\tilde{w}_s = w_m$

Для $L$ -гладкой и $\mu$ -сильно выпуклой функции SVRG сходится с экспоненциальной скоростью, требуя $O((n + L/\mu) \log(1/\epsilon))$ вычислений градиентов $f_i$ для достижения $\epsilon$ -точности. Главное преимущество — константные требования к памяти $O(d)$ .

Алгоритм SAGA

SAGA^[1] избавляется от концепции эпох и двойных циклов, но требует хранения информации о градиентах каждого объекта.

Псевдокод SAGA:

Инициализация $w_0$ и таблицы градиентов $g_i = \nabla f_i(w_0)$ для $i = 1, \dots, n$ . Среднее $\bar{g} = \frac{1}{n} \sum_{i=1}^n g_i$ .
Для :
- Выбрать $i_t$ случайно.
- Вычислить: $v_t = \nabla f_{i_t}(w_t) - g_{i_t} + \bar{g}$
- Сделать шаг: $w_{t+1} = w_t - \eta v_t$
- Обновить среднее: $\bar{g} \leftarrow \bar{g} + \frac{1}{n}(\nabla f_{i_t}(w_t) - g_{i_t})$
- Обновить элемент таблицы: $g_{i_t} \leftarrow \nabla f_{i_t}(w_t)$

Скорость сходимости идентична SVRG. Очевидный недостаток: метод требует $O(nd)$ памяти для хранения таблицы. Однако для широкого класса обобщенных линейных моделей, где $f_i(w) = \ell(x_i^T w)$ , достаточно хранить скаляры $\nabla \ell$ , что тривиально редуцирует память до $O(n)$ .

Алгоритм SARAH

SARAH (StochAstic Recursive grAdient algoritHm)^[1] предлагает принципиально иную, рекурсивную оценку:

$v_t = \nabla f_{i_t}(w_t) - \nabla f_{i_t}(w_{t-1}) + v_{t-1}$

В отличие от SAGA и SVRG, оценка SARAH смещена ( $\mathbb{E}[v_t] \neq \nabla F(w_t)$ ). Несмотря на это, метод обеспечивает монотонное убывание нормы градиента $\mathbb{E}[\|v_t\|^2] \to 0$ . SARAH стал стандартом де-факто для невыпуклых задач (например, обучения глубоких сетей без Batch Normalization), поскольку доставляет сложность $O(n + \sqrt{n}/\epsilon^2)$ для нахождения стационарной точки первого порядка, опережая $O(n + n^{2/3}/\epsilon^2)$ у базового SVRG.

Практическое применение: Проксимальный вариант SAGA для LASSO

В задачах с негладкими регуляризаторами редукция дисперсии напрямую комбинируется с проксимальными методами. Рассмотрим задачу LASSO:

$\min_{w} \frac{1}{n} \sum_{i=1}^n f_i(w) + h(w)$

где гладкая часть $f_i(w) = \frac{1}{2} (x_i^T w - y_i)^2$ , а регуляризатор $h(w) = \lambda \|w\|_1$ . Шаг проксимального SAGA формализуется так:

$w_{t+1} = \text{prox}_{\eta h}(w_t - \eta v_t)$

Для $\ell_1$ -нормы проксимальный оператор имеет замкнутую форму и известен как оператор мягкого порога (Soft Thresholding):

$S_{\eta \lambda}(z)_j = \text{sign}(z_j) \max(|z_j| - \eta \lambda, 0)$

Строгий математический разбор шага SAGA-LASSO:

Оценивается стохастический градиент только гладкой части: $v_t = x_{i_t} (x_{i_t}^T w_t - y_{i_t}) - g_{i_t} + \bar{g}$ .
Выполняется смещение по направлению антиградиента: $z_t = w_t - \eta v_t$ .
Отсекается шум и индуцируется разреженность (покомпонентно): $w_{t+1} = S_{\eta \lambda}(z_t)$ .
Скалярное произведение $x_{i_t}^T w_{t+1}$ сохраняется, таблица градиентов $g_{i_t}$ и вектор $\bar{g}$ обновляются.

Такой подход позволяет находить строгий оптимум $w^*$ с нулевыми компонентами на линейной скорости, недостижимой для субградиентных методов.

Сравнение алгоритмов

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

Алгоритм	Пространственная сложность	Сложность (кол-во $\nabla f_i$ для $\epsilon$ )	Требует настройки эпох	Смещение $v_t$
SGD	$O(d)$	$O(1/\epsilon)$	Нет	Нет
SVRG	$O(d)$	$O((n + L/\mu) \log(1/\epsilon))$	Да	Нет
SAGA	$O(nd)$	$O((n + L/\mu) \log(1/\epsilon))$	Нет	Нет
SARAH	$O(d)$	$O((n + L/\mu) \log(1/\epsilon))$	Да	Да

$m$ .

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_%D1%80%D0%B5%D0%B4%D1%83%D0%BA%D1%86%D0%B8%D0%B8_%D0%B4%D0%B8%D1%81%D0%BF%D0%B5%D1%80%D1%81%D0%B8%D0%B8_%28SAGA%2C_SVRG%2C_SARAH%29»

Категории: Методы оптимизации | Энциклопедия анализа данных | Машинное обучение | Математическая оптимизация

Алгоритмы редукции дисперсии (SAGA, SVRG, SARAH)

Материал из MachineLearning.

Содержание

Введение

Общая концепция редукции дисперсии

Алгоритм SVRG

Алгоритм SAGA

Алгоритм SARAH

Практическое применение: Проксимальный вариант SAGA для LASSO

Сравнение алгоритмов

Литература

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты