Безградиентная оптимизация

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

= Безградиентная оптимизация

Безградиентная оптимизация (Derivative-Free Optimization, DFO) — совокупность методов решения задач минимизации (или максимизации) функции, не требующих аналитического вычисления её производных. В более узком смысле выделяют Zero-Order оптимизацию (ZO), которая полагается исключительно на значения целевой функции для построения оценок градиента, как правило, с помощью случайных конечных разностей. Статья обобщает и систематизирует современные подходы, связывая их с классическими разделами численной оптимизации, стохастической оптимизации, эволюционных алгоритмов и байесовской оптимизации.

Содержание

1 Мотивация и постановка задачи
2 Производная-свободная и безградиентная оптимизация: соотношение понятий
3 Математические основы: оценивание градиента по значениям функции
4 Основные классы безградиентных методов
5 Теоретические свойства и гарантии сходимости
6 Применения в машинном обучении
7 Преимущества и недостатки
8 Современные направления исследований
9 Связь с другими разделами оптимизации
10 Литература

Мотивация и постановка задачи

Классическая постановка задачи безградиентной оптимизации — $\min_{x\in\mathbb{R}^d} f(x),$ где целевая функция $f:\mathbb{R}^d \to \mathbb{R}$ доступна лишь через «оракул нулевого порядка»: для любого $x$ можно получить (возможно, зашумлённое) значение $f(x)$ , но не её градиент. Подобная ситуация возникает, когда

$f(x)$ задана чёрным ящиком (проприетарное ПО, физический эксперимент, сложная симуляция);
модель реализована в виде API (большие языковые модели, облачные сервисы);
функция потерь принципиально недифференцируема (ранжирование, метрики качества);
требуется атаковать обученную модель в режиме чёрного ящика;
вычисление градиента требует чрезмерных затрат памяти или нарушает конфиденциальность данных (федеративное обучение).

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

Производная-свободная и безградиентная оптимизация: соотношение понятий

Термины Derivative-Free Optimization (DFO) и Zero-Order Optimization (ZO) часто используют как синонимы, однако между ними существует тонкое, но важное различие.

DFO — более широкий класс методов, которые не требуют кода для вычисления производных, но могут использовать любые доступные данные о функции (значения, сравнения, историю). Сюда входят прямые методы поиска, модельно-ориентированные алгоритмы, эволюционные стратегии и байесовская оптимизация.
ZO — подмножество DFO, фокусирующееся на построении стохастических оценок градиента исключительно по значениям функции (рандомизированные конечные разности). ZO-методы, как правило, наследуют архитектуру градиентных алгоритмов (SGD, Adam) и представляют особый интерес для современного машинного обучения.

В англоязычной литературе по ML термин «Zero-Order Optimization» закрепился именно за методами типа ZO-SGD, ZO-Adam, SPSA. Мы будем следовать этой конвенции: когда речь идёт о стохастических оценках градиента на основе случайных направлений, используется ZO, а DFO охватывает и все остальные безградиентные стратегии.

Математические основы: оценивание градиента по значениям функции

Сердцевина ZO-оптимизации — приближение градиента при помощи конечных разностей вдоль случайных направлений. Пусть $\mu > 0$ — параметр сглаживания, а $u \sim \mathcal{N}(0, I_d)$ — случайный вектор из стандартного многомерного нормального распределения.

Одноточечная оценка (one-point estimator): $\hat g_{\text{OP}}(x) = \frac{f(x + \mu u)}{\mu}\, u.$ Её математическое ожидание равно градиенту сглаженной функции $f_\mu(x) = \mathbb{E}_{u}[f(x + \mu u)]$ , то есть $\mathbb{E}_u[\hat g_{\text{OP}}(x)] = \nabla f_\mu(x).$

Двухточечная (центральная) оценка уменьшает смещение на порядок: $\hat g_{\text{CT}}(x) = \frac{f(x + \mu u) - f(x - \mu u)}{2\mu}\, u,$ причём $\mathbb{E}_u[\hat g_{\text{CT}}(x)] = \nabla f_\mu(x) + O(\mu^2).$

Аналогичные оценки существуют для равномерного распределения на единичной сфере; тогда появляется множитель $d / \mu$ . В практических реализациях предпочитают двухточечную гауссовскую схему как компромисс между точностью и числом обращений к функции.

Используя оценку $\hat g(x)$ , параметры обновляются по правилу, аналогичному стохастическому градиентному спуску: $x_{k+1} = x_k - \eta_k \hat g(x_k),$ где $\eta_k > 0$ — размер шага. На этом принципе построены все ZO-алгоритмы: ZO-SGD, ZO-Adam, ZO-SVRG и др.

Основные классы безградиентных методов

Методы прямого поиска

Исторически первые DFO-методы (Метод Нелдера–Мида, метод Хука–Дживса, поиск по образцу, MADS). Они сравнивают значения функции в нескольких точках и двигаются в направлениях, обещающих убывание. Не строят явной модели и не требуют численного оценивания градиента; хорошо работают в задачах малой и средней размерности (<100), включая негладкие и зашумлённые функции. Теоретический анализ основан на понятии обобщённого градиента Кларка.

Модельно-ориентированные методы

Строят локальную суррогатную модель (чаще всего квадратичную или на основе радиальных базисных функций) по набору точек и оптимизируют её в доверительной области. Методы типа DFO-TR (Conn, Scheinberg, Vicente) гарантируют сходимость к точке первого порядка для гладких задач, но сложность резко растёт с размерностью ( $O(d^2)$ вычислений функции на итерацию). Широко применяются в инженерном проектировании, когда расчёт одного значения занимает часы.

Стохастические методы

Помимо ZO-алгоритмов, к стохастическим DFO относят:

Метод стохастической аппроксимации Кифера–Вольфовица (Kiefer–Wolfowitz) — классический двухточечный конечно-разностный метод;
SPSA (Simultaneous Perturbation Stochastic Approximation, Spall) — одновременно варьирует все координаты случайными возмущениями, требуя всего двух измерений функции на итерацию независимо от размерности $d$ . Обладает сильными теоретическими гарантиями и широко используется в настройке сложных систем.
Адаптивные методы с уменьшением дисперсии: ZO-SVRG, ZO-SPIDER, ZO-SARAH.

Эволюционные алгоритмы

Методы, вдохновлённые природной эволюцией: Генетические алгоритмы, CMA-ES (Covariance Matrix Adaptation Evolution Strategy), дифференциальная эволюция, роевой интеллект. Оперируют популяцией решений, используют операторы мутации, скрещивания и отбора. CMA-ES считается одним из самых эффективных безградиентных методов для непрерывной оптимизации умеренной размерности (<100) и автоматически адаптирует ковариационную матрицу. Широко применяются в обучении с подкреплением (Evolution Strategies, ES).

Байесовская оптимизация

Применяется для дорогостоящих чёрных ящиков, когда число обращений к функции жёстко ограничено. Строит вероятностную суррогатную модель (обычно гауссовский процесс) и выбирает следующую точку, максимизируя функцию приобретения (expected improvement, GP-UCB). Эффективна при размерности до 20–30. Используется для подбора гиперпараметров, автоматического машинного обучения (AutoML) и экспериментального дизайна.

Zero-Order методы на основе случайных направлений

Современное поколение ZO-алгоритмов, непосредственно нацеленных на задачи машинного обучения, где $d$ может достигать миллионов. Ключевые представители:

ZO-SGD — стохастический градиентный спуск с одно- или двухточечной оценкой градиента;
ZO-Adam, ZO-AdaGrad — адаптивные ZO-методы;
ZO-SVRG, ZO-SAGA — методы с редукцией дисперсии, значительно уменьшающие фактор размерности в оценках сложности;
ZO-BCD (Block Coordinate Descent) — ZO-оптимизация по блокам координат.

Все они используют двухточечную рандомизированную оценку градиента и наследуют скорость сходимости своих градиентных аналогов с поправкой на $O(d)$ или, после редукции дисперсии, на гораздо меньшую величину.

Сравнительная таблица классов

Класс методов	Модель функции	Вычислительная сложность итерации	Обращения к функции на итерацию	Масштабируемость (до $d$ )	Теоретические гарантии	Типичные приложения
Прямой поиск (Nelder–Mead, MADS)	Нет	Низкая ( $O(d)$ )	2– $d+1$	Малая ( $d < 100$ )	Первый порядок (обобщённые градиенты)	Негладкая оптимизация, прототипирование
Модельно-ориентированные (DFO-TR)	Локальная квадратичная	Средняя ( $O(d^2)$ )	$O(d^2)$	Средняя ( $d < 200$ )	Первый порядок для гладких функций	Инженерные расчёты, дорогие симуляции
SPSA	Нет (стох. градиент)	Низкая	2	Высокая (любое $d$ )	Асимптотическая сходимость, конечные выборки	Настройка параметров, адаптивное управление
Эволюционные стратегии (CMA-ES)	Нет (популяция)	Средняя ( $O(dp)$ , $p$ — размер популяции)	$p$ (до тысяч)	Средняя ( $d < 1000$ )	Глобальная сходимость для унимодальных	Обучение с подкреплением, робототехника
Байесовская оптимизация	Гауссовский процесс	Высокая ( $O(n^3)$ )	1 (добавляет точку)	Низкая ( $d < 30$ )	Regret bounds (GP-UCB)	Подбор гиперпараметров, AutoML
ZO-методы (ZO-SGD, ZO-SVRG)	Нет (сглаженный градиент)	Низкая ( $O(d)$ )	2 ( $\hat g$ )	Высокая (миллионы)	Первый порядок для сглаженной задачи	Black-box атаки, LLM API, федеративное обучение

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

Теория сходимости безградиентных методов опирается на сглаженную функцию $f_\mu$ , которая для липшицева $f$ близка к исходной. Ключевой результат Nesterov & Spokoiny (2011): для выпуклой функции с липшицевым градиентом ZO-метод с двухточечной гауссовской оценкой достигает точности $\varepsilon$ по функции за $O(d/\varepsilon)$ итераций против $O(1/\varepsilon)$ у градиентного спуска. Дополнительный множитель $d$ — цена отсутствия градиента.

Для невыпуклых задач Ghadimi & Lan (2013) показали, что ZO-SGD находит $\varepsilon$ -стационарную точку ( $\mathbb{E}\|\nabla f(x)\|^2 \le \varepsilon$ ) за $O(d/\varepsilon^2)$ итераций. Методы с редукцией дисперсии (ZO-SVRG, ZO-SPIDER) позволяют снизить фактор $d$ до константы при определённых предположениях о структуре задачи (например, конечная сумма).

Методы прямого поиска при мягких условиях (наличие всюду плотного множества дифференцируемости) гарантируют сходимость к стационарной точке Кларка. Байесовская оптимизация даёт сублинейные оценки накопленного сожаления (regret) для GP-UCB. Эволюционные стратегии, как правило, опираются на эмпирическую эффективность, хотя для CMA-ES доказана логарифмическая сходимость на унимодальных выпукло-квадратичных задачах.

Применения в машинном обучении

Black-box adversarial attacks. ZO-методы (ZOO, AutoZOOM) генерируют состязательные примеры, используя только вероятностные метки модели-жертвы. Оценки градиента строятся через симметричные разности, не требуя внутреннего доступа.
Подбор гиперпараметров. Байесовская оптимизация — стандарт де-факто; также применяются эволюционные алгоритмы и SPSA.
Обучение с подкреплением. Evolution Strategies (ES), предложенные Salimans et al. (2017), обучают нейросетевые политики, оценивая приращение награды по случайным возмущениям параметров. Метод легко масштабируется на тысячи параллельных воркеров.
Оптимизация недифференцируемых метрик. Прямая оптимизация AUC, F1, среднего обратного ранга возможна ZO-методами, где градиент заменяется сглаженной оценкой.
Федеративное обучение. Обмен градиентами часто требует значительных коммуникационных затрат. ZO-оптимизация на клиенте позволяет передавать лишь скалярные значения, снижая объём трафика на порядок (Liu et al., 2020).
API больших языковых моделей. Тонкая настройка больших языковых моделей через чёрный ящик (Black-Box Tuning, BBT) использует ZO-оценки градиента по запросам к API, обходя необходимость внутренних градиентов модели. BBTv2 и аналоги применяют проекцию на низкоразмерное подпространство для обхода проклятия размерности.
Научное машинное обучение. В физически информированных нейросетях (PINNs) и гибридных моделях, где часть компонент задана недифференцируемыми симуляторами, ZO-подход позволяет обучать нейросеть сквозным образом.
Генеративные модели и обратные задачи. Оптимизация скрытых кодов StyleGAN или диффузионных моделей без доступа к градиенту генератора.

Преимущества и недостатки

Преимущества:

Не требуют программирования градиента — снижение инженерных затрат и исключение ошибок;
Применимы к любым чёрным ящикам, включая недифференцируемые и дискретные компоненты;
Естественная параллелизация (эволюционные стратегии, ZO с большими батчами);
Робастность к шуму в измерениях функции.

Недостатки:

Проклятие размерности: число обращений к функции масштабируется как $O(d)$ в худшем случае;
Высокая дисперсия оценок градиента, требующая тщательного подбора $\mu$ и методов уменьшения дисперсии;
Медленная практическая сходимость по сравнению с градиентными аналогами при одинаковом бюджете вычислений;
Невозможность точного нахождения седловых точек и чувствительность к локальным особенностям ландшафта.

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

Уменьшение дисперсии. Интеграция техник стохастической рекуррентности (SPIDER, SARAH, STORM) в ZO-оптимизацию позволила получить оценки сложности, сравнимые с градиентными методами с точностью до константы (Fang et al., 2018; Liu et al., 2018).
Адаптивное сэмплирование направлений. Использование активных подпространств, importance sampling и координатных спусков снижает эффективную размерность и ускоряет сходимость в задачах с низкоразмерной структурой.
Распределённая и децентрализованная ZO-оптимизация. Разработаны асинхронные алгоритмы для рабочих узлов, каждый из которых имеет доступ только к локальному оракулу (Hajinezhad et al., 2019).
Высокоразмерная ZO-оптимизация. Методы проекции градиента на подпространство (ZO-BCD, ZO-SGD с dropout-направлениями) позволяют обучать модели с миллиардами параметров через API, например, BBTv2 использует низкоранговую матрицу возмущений.
ZO второго порядка. Исследуются оценки Гессиана через конечные разности (ZO-Newton), ускоряющие локальную сходимость.
Теория для негладких и невыпуклых задач. Активно развиваются оценки для функций, удовлетворяющих условию Куроды–Лоджа, и для оптимизации с ограничениями без вычисления градиента.
ZO для федеративного и приватного обучения. Доказано, что ZO-апдейты обеспечивают дифференциальную приватность «из коробки» благодаря естественной стохастичности, что открывает новые перспективы.

Связь с другими разделами оптимизации

Безградиентная оптимизация не является изолированной дисциплиной; она заимствует идеи из численных методов (доверительные области, линейный поиск), стохастической аппроксимации (SPSA, SGD), эволюционных вычислений (популяционные стратегии) и глобальной оптимизации (GP-сюррогаты). ZO-методы, в свою очередь, дополняют теорию стохастического градиентного спуска, предоставляя инструменты для ситуаций, когда даже стохастический градиент недоступен. В контексте онлайн-обучения и бандитов безградиентная обратная связь описывается как bandit feedback, а методы ZO-оптимизации сглаживают задачу, сводя её к стандартной стохастической оптимизации.

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

Литература

Conn A. R., Scheinberg K., Vicente L. N. Introduction to Derivative-Free Optimization. — SIAM, 2009.
Nesterov Yu., Spokoiny V. Random gradient-free minimization of convex functions // Foundations of Computational Mathematics, 2017. (Предварительная версия: CORE DP 2011/2, 2011).
Spall J. C. Introduction to Stochastic Search and Optimization. — Wiley, 2003.
Larson J., Menickelly M., Wild S. M. Derivative-free optimization methods // Acta Numerica, 2019, Vol. 28, pp. 287–404.
Ghadimi S., Lan G. Stochastic first- and zeroth-order methods for nonconvex stochastic programming // SIAM Journal on Optimization, 2013, Vol. 23(4), pp. 2341–2368.
Liu S., Kailkhura B., Chen P.-Y., Ting P., Chang S., Amini L. Zeroth-order stochastic variance reduction for nonconvex optimization // NeurIPS, 2018.
Salimans T., Ho J., Chen X., Sutskever I. Evolution strategies as a scalable alternative to reinforcement learning // arXiv:1703.03864, 2017.
Sun T., Shao Y., Qian H., Huang X., Qiu X. Black-box tuning for language-model-as-a-service // ICML, 2022.
Wang Z., Chen J., Liu S., Lin Q., Ma S., Chen T. ZOO: Zeroth order optimization based black-box attacks to deep neural networks // AAAI, 2018.
Fang C., Li C. J., Lin Z., Zhang T. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator // NeurIPS, 2018.
Hajinezhad D., Hong M., Zhao T., Wang Z. NESTT: A nonconvex primal-dual splitting method for distributed and stochastic optimization // IEEE Trans. Signal Processing, 2019.
Boyd S., Vandenberghe L. Convex Optimization. — Cambridge University Press, 2004.
Nocedal J., Wright S. J. Numerical Optimization. — 2nd ed., Springer, 2006.
Chen P.-Y., Zhang H., Sharma Y., Yi J., Hsieh C.-J. ZOO: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models // ACM Workshop on AISec, 2017.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%91%D0%B5%D0%B7%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F»

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