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

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

Перейти к: навигация, поиск

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

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

Содержание

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

Классическая постановка задачи безградиентной оптимизации — \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-инженера.

Литература

  1. Conn A. R., Scheinberg K., Vicente L. N. Introduction to Derivative-Free Optimization. — SIAM, 2009.
  2. Nesterov Yu., Spokoiny V. Random gradient-free minimization of convex functions // Foundations of Computational Mathematics, 2017. (Предварительная версия: CORE DP 2011/2, 2011).
  3. Spall J. C. Introduction to Stochastic Search and Optimization. — Wiley, 2003.
  4. Larson J., Menickelly M., Wild S. M. Derivative-free optimization methods // Acta Numerica, 2019, Vol. 28, pp. 287–404.
  5. 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.
  6. Liu S., Kailkhura B., Chen P.-Y., Ting P., Chang S., Amini L. Zeroth-order stochastic variance reduction for nonconvex optimization // NeurIPS, 2018.
  7. Salimans T., Ho J., Chen X., Sutskever I. Evolution strategies as a scalable alternative to reinforcement learning // arXiv:1703.03864, 2017.
  8. Sun T., Shao Y., Qian H., Huang X., Qiu X. Black-box tuning for language-model-as-a-service // ICML, 2022.
  9. 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.
  10. Fang C., Li C. J., Lin Z., Zhang T. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator // NeurIPS, 2018.
  11. 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.
  12. Boyd S., Vandenberghe L. Convex Optimization. — Cambridge University Press, 2004.
  13. Nocedal J., Wright S. J. Numerical Optimization. — 2nd ed., Springer, 2006.
  14. 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://recognition.su/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»