Методы уменьшения дисперсии (Variance Reduction) в Zero-Order-оптимизации

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

Перейти к: навигация, поиск
Статья написана с использованием LLM GPT-5.3-mini и проверена участником ~~Dovlat Demin~~


Содержание

Методы уменьшения дисперсии (Variance Reduction) в Zero-Order-оптимизации

Методы уменьшения дисперсии (Variance Reduction, VR) — совокупность методов, предназначенных для снижения случайных ошибок при построении стохастических оценок градиента в безградиентной (Zero-Order, ZO) оптимизации. Они позволяют повысить точность оценок направления спуска без существенного увеличения вычислительной стоимости, благодаря чему ускоряют сходимость алгоритмов, уменьшают число необходимых вычислений функции и повышают устойчивость оптимизации.

Методы уменьшения дисперсии являются одним из ключевых направлений развития современной стохастической оптимизации и особенно важны для ZO-методов, поскольку последние строят оценку градиента исключительно по значениям функции. В отличие от градиентных методов, где источником случайности обычно служит выбор мини-пакета данных, в Zero-Order-оптимизации дополнительная дисперсия возникает вследствие случайного выбора направлений поиска и процедуры сглаживания функции.

Мотивация

Рассматривается задача минимизации функции

\min_{x\in\mathbb{R}^d} f(x),

где аналитическое выражение градиента отсутствует либо его вычисление невозможно или экономически нецелесообразно.

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

  • оптимизируемая функция представляет собой результат сложного моделирования;
  • модель доступна только через программный интерфейс («черный ящик»);
  • вычисление производных запрещено архитектурой системы;
  • градиенты недоступны по причинам безопасности или конфиденциальности;
  • функция содержит недифференцируемые или дискретные компоненты.

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

Современная Zero-Order-оптимизация применяется в широком круге задач:

  • black-box оптимизация;
  • обучение моделей при отсутствии доступа к производным;
  • гиперпараметрическая оптимизация;
  • поиск архитектур нейронных сетей;
  • black-box adversarial attack;
  • обучение с подкреплением;
  • калибровка сложных инженерных моделей;
  • задачи дорогостоящей симуляционной оптимизации.

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

Сглаживание функции

Даже если функция f(x) является негладкой или недоступной для непосредственного дифференцирования, можно определить её сглаженную версию.

Наиболее распространено гауссово либо сферическое сглаживание

f_\mu(x)=\mathbb{E}_{u}[f(x+\mu u)],

где \mu>0 — параметр сглаживания, а случайный вектор u обычно выбирается либо из стандартного нормального распределения

u\sim\mathcal N(0,I),

либо равномерно на единичной сфере.

При достаточно малом \mu функция f_\mu является более гладкой, чем исходная функция, а её градиент можно выразить через математическое ожидание случайной величины. Именно это свойство лежит в основе большинства современных Zero-Order-алгоритмов.

Следует учитывать компромисс между смещением и дисперсией. Большое значение \mu уменьшает случайные колебания оценки, однако усиливает смещение относительно истинного градиента исходной функции. Малые значения \mu уменьшают смещение, но делают оценку значительно более шумной.

Стохастические оценки градиента

После сглаживания функция допускает построение случайных оценок градиента.

Одноточечная оценка

Одной из простейших является одноточечная оценка

\hat g(x)=\frac{d}{\mu}f(x+\mu u)u.

Для сглаженной функции выполняется

\mathbb E[\hat g(x)] = \nabla f_\mu(x),

то есть оценка является несмещённой относительно градиента сглаженной функции.

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

Двухточечная оценка

Гораздо чаще используется симметричная двухточечная схема

\hat g(x)= \frac{d}{2\mu} \bigl( f(x+\mu u)-f(x-\mu u) \bigr)u.

Использование центральной разности позволяет существенно уменьшить влияние случайных флуктуаций и сократить смещение разностной аппроксимации.

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

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

Выбор случайных направлений

Наиболее распространёнными являются следующие распределения случайных направлений:

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

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

Источники дисперсии

Пусть

\hat g

обозначает случайную оценку градиента.

Её дисперсия определяется выражением

\operatorname{Var}(\hat g) = \mathbb E \left[ \| \hat g- \mathbb E[\hat g] \|^2 \right].

Высокая дисперсия приводит к нескольким отрицательным последствиям:

  • замедлению скорости сходимости;
  • увеличению числа обращений к функции;
  • росту чувствительности к выбору шага;
  • сильным колебаниям траектории оптимизации;
  • ухудшению качества решения при ограниченном бюджете вычислений.

В Zero-Order-оптимизации существует несколько независимых источников случайности.

Случайные направления

Основной источник дисперсии связан со случайным выбором направления u.

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

Дисперсия большинства классических оценок возрастает с увеличением размерности пространства. Именно поэтому разработка методов уменьшения влияния случайных направлений является одним из центральных направлений современной ZO-оптимизации.

Шум вычислений функции

Во многих практических задачах наблюдается не сама функция, а её шумная реализация

\tilde f(x)=f(x)+\varepsilon,

где \varepsilon — случайная ошибка.

Подобный шум возникает при использовании Монте-Карло-моделирования, стохастических симуляторов, мини-пакетов данных или физических экспериментов.

Ошибки вычисления функции непосредственно переходят в оценку градиента и могут многократно усиливаться при малом параметре сглаживания \mu.

Стохастическая природа целевой функции

В задачах машинного обучения оптимизируемая функция часто имеет вид математического ожидания

f(x)=\mathbb E_{\xi}[F(x,\xi)],

где \xi — случайная обучающая выборка, мини-пакет или случайная среда.

В этом случае дисперсия складывается из двух независимых составляющих:

  • случайности при выборе направления u;
  • случайности наблюдений \xi.

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

Ошибка сглаживания

Даже при отсутствии шума оценка вычисляется не для исходной функции f(x), а для её сглаженной версии f_\mu(x). Поэтому возникает систематическая ошибка (смещение), зависящая от параметра сглаживания \mu. Хотя смещение формально не является дисперсией, при выборе параметров алгоритма оно образует классический компромисс bias–variance.

Методы уменьшения дисперсии

Variance Reduction объединяет методы, уменьшающие разброс стохастических оценок градиента без существенного увеличения их смещения. Идеальный метод уменьшает дисперсию, сохраняя несмещённость оценки и требуя минимального числа дополнительных вычислений.

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

Antithetic sampling

Antithetic sampling (симметричная выборка) является одним из наиболее распространённых способов уменьшения дисперсии.

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

u,\quad -u.

Соответствующая оценка имеет вид

\hat g(x)= \frac{d}{2\mu} \left( f(x+\mu u)-f(x-\mu u) \right)u.

Использование центральной разности приводит к взаимной компенсации части случайных ошибок и уменьшает влияние нечётных членов разложения Тейлора.

Основные достоинства метода:

  • уменьшение дисперсии практически без изменения алгоритма;
  • уменьшение смещения конечной разности;
  • сохранение несмещённости относительно \nabla f_\mu.

Недостатком является удвоение числа вычислений функции.

Практически все современные ZO-алгоритмы используют именно симметричную двухточечную оценку.

Common Random Numbers

Метод Common Random Numbers (CRN) применяется тогда, когда сама функция вычисляется посредством случайного моделирования.

Пусть

f(x)=\mathbb E[F(x,\omega)].

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

f(x+\mu u)

и

f(x-\mu u)

используется одна и та же последовательность случайных чисел \omega.

Поскольку шум в обеих оценках становится положительно коррелированным, при вычислении разности

f(x+\mu u)-f(x-\mu u)

значительная часть случайной ошибки сокращается.

Метод особенно эффективен в:

  • Монте-Карло-оптимизации;
  • имитационном моделировании;
  • reinforcement learning;
  • задачах управления.

Усреднение и mini-batching

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

Пусть построено m независимых оценок

\hat g_1,\ldots,\hat g_m.

Тогда используется

\bar g= \frac1m \sum_{i=1}^m \hat g_i.

Если оценки независимы,

\operatorname{Var}(\bar g) = \frac1m \operatorname{Var}(\hat g).

Таким образом, дисперсия уменьшается обратно пропорционально размеру мини-пакета.

Цена такого улучшения очевидна — требуется приблизительно в m раз больше обращений к функции.

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

Averaging

Если вычисления функции очень дороги, вместо увеличения размера мини-пакета часто используют усреднение направлений поиска между соседними итерациями.

Экспоненциальное усреднение оценок

g_k= (1-\beta)g_{k-1} + \beta\hat g_k

уменьшает случайные колебания и делает траекторию оптимизации более гладкой.

Подобные идеи используются совместно с методами Momentum, Adam и их Zero-Order-аналогами.

Ортогональные случайные направления

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

Поэтому вместо независимых векторов строят ортогональные направления

u_i^\top u_j = 0,\; i\neq j.

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

На практике используются:

  • случайные ортогональные матрицы;
  • преобразования Хаара;
  • матрицы Адамара;
  • ортогонализованные гауссовы направления.

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

Importance Sampling

Во многих задачах разные координаты функции обладают существенно различной чувствительностью.

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

u\sim p(u),

сконцентрированное на наиболее информативных направлениях.

Вероятности могут определяться:

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

Importance sampling позволяет уменьшить дисперсию без увеличения числа вычислений функции, однако требует дополнительной информации о структуре задачи.

Control Variates

Control variates являются одним из наиболее мощных способов уменьшения дисперсии.

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

Тогда строится новая оценка

\hat g_{\rm cv} = \hat g - c\left( Z-\mathbb E Z \right),

где коэффициент c выбирается таким образом, чтобы минимизировать дисперсию.

Если корреляция высока, выигрыш может быть весьма существенным.

В Zero-Order-оптимизации в роли контрольной величины используются:

  • оценки предыдущих итераций;
  • локальные линейные модели;
  • приближённые градиенты;
  • суррогатные модели функции.

Рекурсивные методы Variance Reduction

Наиболее заметный прогресс последних лет связан с переносом идей стохастической градиентной оптимизации в Zero-Order-методы.

Классические алгоритмы SVRG, SARAH и SPIDER используют информацию о предыдущих итерациях для построения значительно менее шумных оценок градиента.

В Zero-Order-оптимизации аналогичная идея реализуется посредством рекурсивного обновления случайных оценок.

Общий принцип состоит в следующем.

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

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

Подобные подходы получили названия:

  • ZO-SVRG;
  • ZO-SARAH;
  • ZO-SPIDER;
  • SPIDER-SZO;
  • Recursive Variance Reduction.

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

Сравнение основных методов

Метод Дополнительные вычисления Снижение дисперсии Требования к памяти Основные области применения
Antithetic sampling 2 вычисления функции высокое отсутствуют универсальные ZO-методы
Common Random Numbers практически отсутствуют высокое при шумных вычислениях отсутствуют Монте-Карло, RL
Mini-batching пропорциональны размеру пакета пропорционально 1/m отсутствуют обучение моделей
Averaging отсутствуют умеренное хранение предыдущих оценок онлайн-оптимизация
Orthogonal directions небольшие умеренное—высокое генерация ортогональных направлений высокоразмерные задачи
Importance sampling небольшие зависит от качества распределения статистика процесса структурированные задачи
Control variates умеренные высокое дополнительные модели симуляционная оптимизация
ZO-SVRG / ZO-SARAH / ZO-SPIDER периодические полные оценки очень высокое требуется хранение промежуточной информации крупномасштабное машинное обучение

Теоретические гарантии

Эффективность методов уменьшения дисперсии оценивается по нескольким критериям:

  • несмещённость оценки;
  • величина дисперсии;
  • вычислительная сложность;
  • число обращений к функции (query complexity);
  • скорость сходимости алгоритма.

Несмещённость

Для большинства классических двухточечных оценок выполняется

\mathbb E[\hat g(x)] = \nabla f_\mu(x),

то есть оценка является несмещённой относительно градиента сглаженной функции.

Следует подчеркнуть, что в общем случае

\nabla f_\mu(x)\neq\nabla f(x),

поэтому итоговая ошибка складывается из двух составляющих:

  • смещения, обусловленного сглаживанием;
  • случайной ошибки оценки.

Выбор параметра сглаживания \mu представляет собой компромисс между этими величинами.

Уменьшение дисперсии

Главная цель методов Variance Reduction заключается в уменьшении величины

\operatorname{Var}(\hat g) = \mathbb E \left[ \| \hat g- \mathbb E\hat g \|^2 \right].

Для различных методов существуют собственные оценки выигрыша.

  • Усреднение по m независимым оценкам уменьшает дисперсию приблизительно в m раз.
  • Antithetic sampling уменьшает дисперсию благодаря отрицательной корреляции между симметричными направлениями и одновременно снижает ошибку конечной разности.
  • Common Random Numbers уменьшает вклад шума вычислений функции за счёт положительной корреляции между двумя вычислениями значения функции.
  • Control variates минимизируют дисперсию за счёт использования коррелированной вспомогательной случайной величины.
  • Рекурсивные методы семейства ZO-SVRG, ZO-SARAH и ZO-SPIDER уменьшают накопление случайной ошибки между последовательными итерациями.

Скорость сходимости

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

Работы Ю. Нестерова и В. Спокойного показали, что случайные направления позволяют получать оптимальные по порядку оценки сложности для широкого класса выпуклых задач.

Для невыпуклой оптимизации современные алгоритмы с уменьшением дисперсии позволяют уменьшить число обращений к функции по сравнению с классическими стохастическими Zero-Order-методами. Особенно заметный выигрыш достигается в задачах большого масштаба, где стоимость вычисления функции значительно превышает стоимость арифметических операций.

Хотя конкретные оценки сложности зависят от предположений о гладкости функции, уровне шума и используемой схеме сглаживания, современные методы Variance Reduction обычно достигают лучшего компромисса между точностью оценки и числом вычислений функции.

Применение

Обучение нейронных сетей

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

Типичные примеры:

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

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

Black-box оптимизация

В задачах оптимизации типа black box исследователь располагает только возможностью вычислять значения функции.

Такой сценарий характерен для:

  • автоматического проектирования;
  • инженерной оптимизации;
  • настройки сложных программных систем;
  • оптимизации физических экспериментов.

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

Black-box adversarial attack

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

Для построения состязательных примеров используются Zero-Order-оценки градиента по запросам к модели.

Методы уменьшения дисперсии позволяют:

  • уменьшить число запросов;
  • повысить стабильность атаки;
  • увеличить вероятность успешного построения возмущения.

Поэтому они широко используются в современных алгоритмах black-box adversarial attack.

Обучение с подкреплением

Во многих алгоритмах Reinforcement Learning оптимизация проводится по шумным оценкам ожидаемого вознаграждения.

Использование Common Random Numbers, control variates, усреднения и рекурсивных методов Variance Reduction существенно уменьшает влияние стохастичности среды и ускоряет обучение.

Особенно заметный эффект наблюдается при использовании методов эволюционных стратегий (Evolution Strategies), где оценка градиента строится по случайным возмущениям параметров.

Гиперпараметрическая оптимизация

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

Zero-Order-методы с уменьшением дисперсии позволяют эффективнее использовать ограниченный вычислительный бюджет и быстрее находить качественные значения гиперпараметров.

Преимущества и ограничения

Основные достоинства методов Variance Reduction:

  • уменьшение случайных колебаний оценки градиента;
  • повышение устойчивости алгоритмов;
  • сокращение числа обращений к функции;
  • ускорение практической сходимости;
  • возможность применения совместно с большинством существующих ZO-методов.

Вместе с тем существуют и ограничения.

  • Многие методы требуют дополнительных вычислений на каждой итерации.
  • Рекурсивные алгоритмы нуждаются в хранении промежуточных оценок.
  • Эффективность importance sampling зависит от качества априорной информации о задаче.
  • Выбор параметров сглаживания, размера мини-пакета и периода обновления контрольных оценок остаётся нетривиальной задачей.

Кроме того, при очень высокой размерности пространства влияние случайных направлений полностью устранить невозможно, поэтому проблема зависимости сложности от размерности остаётся одним из центральных вопросов современной Zero-Order-оптимизации.

Современные направления исследований

Активно развиваются следующие направления:

  • адаптивный выбор параметра сглаживания;
  • адаптивное распределение случайных направлений;
  • сочетание Variance Reduction с квазиньютоновскими ZO-методами;
  • использование низкоразмерных подпространств;
  • квазислучайные последовательности;
  • комбинация Zero-Order- и First-Order-информации;
  • распределённая и федеративная Zero-Order-оптимизация;
  • применение методов уменьшения дисперсии в крупных языковых моделях и других фундаментальных моделях искусственного интеллекта.

Связь с градиентными методами

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

Несмотря на различия в построении оценок, многие современные подходы имеют общую концептуальную основу. Так, ZO-SVRG, ZO-SARAH и ZO-SPIDER являются естественными аналогами одноимённых градиентных алгоритмов, а методы mini-batching, control variates и importance sampling используются как в градиентной, так и в безградиентной оптимизации. Это подчёркивает тесную связь между двумя направлениями и позволяет переносить результаты стохастической оптимизации на класс Zero-Order-методов.

См. также

Литература

  1. Nesterov Y., Spokoiny V. Random Gradient-Free Minimization of Convex Functions. Foundations of Computational Mathematics, 2017.
  2. Conn A. R., Scheinberg K., Vicente L. N. Introduction to Derivative-Free Optimization. SIAM, 2009.
  3. Larson J., Menickelly M., Wild S. M. Derivative-Free Optimization Methods. Acta Numerica, 2019.
  4. Spall J. C. Introduction to Stochastic Search and Optimization. Wiley, 2003.
  5. Ghadimi S., Lan G. Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming. SIAM Journal on Optimization, 2013.
  6. Duchi J. C., Jordan M. I., Wainwright M. J., Wibisono A. Optimal Rates for Zero-Order Convex Optimization. Mathematical Programming, 2015.
  7. Nesterov Y. Introductory Lectures on Convex Optimization. Springer, 2004.
  8. Nemirovski A., Yudin D. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
  9. Wang X., Fang C., Liu Z. и др. Работы по Zero-Order Variance Reduction и ZO-SVRG.
  10. Liu S., Kailkhura B., Chen P.-Y., Ting P. и соавт. Работы по ZO-SGD, ZO-SVRG и black-box optimization.
  11. Fang C., Li C. J., Lin Z., Zhang T. SPIDER: Near-Optimal Non-Convex Optimization. NeurIPS, 2018.
  12. Nguyen L. M., Liu J., Scheinberg K., Takáč M. SARAH. ICML, 2017.
  13. Johnson R., Zhang T. Accelerating Stochastic Gradient Descent using Predictive Variance Reduction. NeurIPS, 2013.
  14. Duchi J. C., Hazan E., Singer Y. Adaptive Subgradient Methods for Online Learning and Stochastic Optimization. JMLR, 2011.
  15. Rios L. M., Sahinidis N. V. Derivative-Free Optimization: A Review. Journal of Global Optimization, 2013.
  16. Audet C., Hare W. Derivative-Free and Blackbox Optimization. Springer, 2017.
  17. Bergstra J., Bengio Y. Random Search for Hyper-Parameter Optimization. JMLR, 2012.
  18. Salimans T. и др. Evolution Strategies as a Scalable Alternative to Reinforcement Learning. arXiv, 2017.
  19. Liu S., Chen P.-Y., Kailkhura B., Zhang X. Zeroth-Order Online Alternating Direction Method of Multipliers. AISTATS, 2018.
  20. Современные публикации NeurIPS, ICML, ICLR, AISTATS, JMLR и SIAM Journal on Optimization по Zero-Order Optimization и Variance Reduction.
Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D1%83%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B4%D0%B8%D1%81%D0%BF%D0%B5%D1%80%D1%81%D0%B8%D0%B8_%28Variance_Reduction%29_%D0%B2_Zero-Order-%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8»
Личные инструменты