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

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

(Различия между версиями)
Перейти к: навигация, поиск
(Новая: {{Статья | название = Безградиентная оптимизация | категория = Методы оптимизации | авторы ...)
Строка 1: Строка 1:
-
{{Статья
 
-
| название = Безградиентная оптимизация
 
-
| категория = Методы оптимизации
 
-
| авторы = Редакторы MachineLearning.ru
 
-
}}
 
-
 
-
__TOC__
 
-
 
== Введение ==
== Введение ==
'''Безградиентная оптимизация''' (также известная как ''производная-свободная оптимизация'', англ. ''Derivative-Free Optimization, DFO'', или ''оптимизация нулевого порядка'', англ. ''Zero-Order Optimization, ZO'') — класс методов численной [[оптимизация|оптимизации]], предназначенных для решения задач минимизации или максимизации целевой функции, когда аналитическое выражение для её [[градиент|градиента]] (или производных более высоких порядков) недоступно, не существует или его вычисление сопряжено с чрезмерно высокими вычислительными затратами.
'''Безградиентная оптимизация''' (также известная как ''производная-свободная оптимизация'', англ. ''Derivative-Free Optimization, DFO'', или ''оптимизация нулевого порядка'', англ. ''Zero-Order Optimization, ZO'') — класс методов численной [[оптимизация|оптимизации]], предназначенных для решения задач минимизации или максимизации целевой функции, когда аналитическое выражение для её [[градиент|градиента]] (или производных более высоких порядков) недоступно, не существует или его вычисление сопряжено с чрезмерно высокими вычислительными затратами.

Версия 15:13, 15 июля 2026

Содержание

Введение

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

Математическая постановка задачи записывается в классическом виде: \min_{x \in \mathbb{R}^d} f(x), где f: \mathbb{R}^d \to \mathbb{R} — целевая функция (вообще говоря, не обязательно выпуклая или гладкая). Доступ к функции осуществляется исключительно через оракул нулевого порядка (Zero-Order Oracle), который возвращает значение f(x) в любой запрашиваемой точке x, но не предоставляет информацию о производных.

Исторический контекст и терминология

Исторически в математическом программировании закрепился термин Derivative-Free Optimization (DFO). В рамках численных методов под DFO чаще всего понимают детерминированные локальные методы (такие как методы прямого поиска или доверительных областей), разработанные для оптимизации ресурсоёмких («тяжёлых») детерминированных функций (например, при аэродинамическом проектировании).

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

Мотивация: почему градиентные методы неприменимы?

Классические методы первого порядка (например, градиентный спуск, L-BFGS, Adam) лежат в основе современного машинного обучения. Однако существует широкий класс задач, где их применение невозможно или нецелесообразно по следующим причинам:

  1. Отсутствие аналитического выражения: Функция f(x) может задаваться в виде сложного программного симулятора, физического эксперимента или закрытого проприетарного API (например, оценка качества генерации большой языковой модели через сторонний сервис).
  2. Недифференцируемость: Целевая функция может содержать разрывы, кусочно-постоянные участки или быть существенно негладкой (например, ступенчатые функции потерь, операции квантования в нейронных сетях).
  3. Экстремальный шум: Измерения целевой функции могут быть подвержены сильному стохастическому шуму f(x) = \phi(x) + \epsilon, из-за чего численное дифференцирование классическими методами (такими как конечные разности) приводит к катастрофической потере точности.
  4. Вычислительная сложность градиента: В некоторых задачах вычисление точного градиента с помощью автоматического дифференцирования (backpropagation) требует огромного объёма памяти или времени, превышающего затраты на многократное вычисление самой функции.

Классификация безградиентных методов

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

1. Методы прямого поиска (Direct Search)

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

  • Метод Нелдера-Мида (метод деформируемого многогранника): Использует геометрическую фигуру — симплекс из d+1 вершин. На каждом шаге худшая вершина отображается, растягивается или сжимается относительно центра тяжести остальных вершин. Метод эвристический, но крайне эффективен для малых размерностей (d < 10).
  • Методы координатного спуска (Coordinate Descent): Последовательная одномерная оптимизация вдоль базисных векторов без вычисления производных.
  • Методы обобщённого паттерного поиска (Generalized Pattern Search, GPS): Исследуют пространство вдоль адаптивной сетки (шаблона), шаг которой уменьшается при неудаче и увеличивается при успешном нахождении точки с меньшим значением функции.

2. Модельно-ориентированные методы (Model-Based / Surrogate Methods)

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

  • Методы доверительных областей (Trust-Region DFO): Строится локальная квадратичная модель m_k(x) \approx f(x) в окрестности текущей точки x_k с помощью полиномиальной интерполяции. Оптимизация модели производится внутри некоторого радиуса (доверительной области) \Delta_k</font>. Представителями являются алгоритмы серии NEWUOA, BOBYQA и DFO-LS. </p><p>=== 3. Стохастические и эволюционные алгоритмы === Ориентированы на поиск глобального экстремума в невыпуклых и мультимодальных задачах. </p> <ul><li> '''[[Эволюционные алгоритмы]] (включая [[Генетический алгоритм|генетические]]):''' Популяционные методы, использующие операторы мутации, кроссинговера (скрещивания) и селекции. </li><li> '''Алгоритм CMA-ES (Covariance Matrix Adaptation Evolution Strategy):''' Один из наиболее мощных эволюционных методов для непрерывной оптимизации. Адаптирует матрицу ковариации многомерного нормального распределения, используемого для генерации новых кандидатов (особей), фактически оценивая кривизну целевой функции (аналог матрицы Гессе). </li><li> '''[[Метод имитации отжига]] (Simulated Annealing):''' Метод случайного поиска, допускающий переходы в точки с худшим значением функции с вероятностью, зависящей от параметра «температуры», что позволяет выходить из локальных минимумов. </li></ul> <p>=== 4. Байесовская оптимизация === [[Байесовская оптимизация]] применяется для оптимизации крайне дорогих для вычисления функций (например, подбор гиперпараметров нейронных сетей, где одно вычисление — это обучение модели в течение нескольких часов). </p> <ul><li> В качестве суррогатной модели чаще всего используются '''Гауссовские процессы''' (Gaussian Processes), предоставляющие не только точечную оценку функции, но и меру неопределенности (дисперсию) в каждой точке пространства. </li><li> Выбор следующей точки для вычисления целевой функции осуществляется путём максимизации так называемой функции полезности (Acquisition Function), такой как Expected Improvement (EI) или Upper Confidence Bound (UCB). Это позволяет сбалансировать исследование новых областей (exploration) и эксплуатацию известных экстремумов (exploitation). </li></ul> <p>=== 5. Zero-Order методы на основе оценки градиента === Эти методы аппроксимируют направление градиента по значениям функции и используют его в классических итерационных схемах градиентного спуска. Это связующее звено между классической оптимизацией и DFO, наиболее активно развивающееся в области машинного обучения. </p><p>== Математические основы Zero-Order оценки градиента == Современные ZO-методы строятся на идее рандомизированной аппроксимации градиента. Для этого вводится понятие '''сглаженной функции''' (smoothed function), предложенное Ю. Е. Нестеровым и В. Г. Спокойным. </p><p>=== Сглаживание функции === Пусть целевая функция <tex>f недифференцируема. Её сглаженная версия f_\mu(x) с параметром сглаживания \mu > 0 определяется как математическое ожидание: f_\mu(x) = \mathbb{E}_{u}[f(x + \mu u)], где u — случайный вектор, распределённый по стандартному нормальному закону \mathcal{N}(0, I_d) или равномерно на единичной сфере S^{d-1}.

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

    Одноточечная оценка градиента

    Если на каждой итерации доступен запрос значения функции только в одной точке, используется одноточечная оценка (one-point estimator): \hat g(x) = \frac{d}{\mu} f(x + \mu u) u, где u равномерно распределён на единичной сфере S^{d-1}. Данная оценка является несмещённой для градиента сглаженной функции: \mathbb{E}_u[\hat g(x)] = \nabla f_\mu(x)</font>. </li><li> ''Недостаток:'' Одноточечная оценка обладает огромной дисперсией, пропорциональной размерности пространства <tex>d^2, которая не стремится к нулю при \mu \to 0</font>, если значение <tex>f(x) велико.

Двухточечная оценка градиента

Если в рамках одной итерации можно вычислить значение функции дважды, применяется двухточечная оценка (two-point estimator): \hat g(x) = \frac{d}{2\mu} \bigl(f(x + \mu u) - f(x - \mu u)\bigr) u. Эта оценка также является несмещённой: \mathbb{E}_u[\hat g(x)] = \nabla f_\mu(x)</font>. </li><li> ''Преимущество:'' Дисперсия двухточечной оценки значительно ниже (имеет порядок <tex>O(d) вместо O(d^2)) и стремится к нулю при \mu \to 0</font> для гладких функций, что делает этот подход на порядки более стабильным и быстрым на практике. </p><p>=== Схема обновления параметров === Полученная стохастическая оценка градиента <tex>\hat g(x_k) подставляется в стандартный шаг обновления параметров (например, стохастический градиентный спуск): x_{k+1} = x_k - \eta_k \hat g(x_k), где \eta_k > 0 — темп обучения (learning rate). Аналогично могут быть адаптированы методы с импульсом (Momentum) и адаптивным шагом (ZO-Adam, ZO-AdaGrad).

Сравнительный анализ классов методов

Ниже представлена сравнительная таблица основных классов безградиентных методов:

Класс методов Требуется модель функции? Число вызовов f(x) на шаг Масштабируемость по размерности d Теоретические гарантии Основные области применения
Методы прямого поиска (Нелдер-Мид и др.) Нет Низкое (1 - 2d) Низкая (d < 20) Слабые (локальная сходимость) Низкоразмерная детерминированная оптимизация, инженерное проектирование.
Модельно-ориентированные (Trust-Region) Да (квадратичная, радиальные базисные функции) Низкое к среднему Средняя (d < 100</font>) | Хорошо изучены для гладких локальных задач | Проектирование физических систем, аэродинамика, калибровка моделей. |- | '''Эволюционные алгоритмы''' (CMA-ES, GA) | Нет | Высокое (размер популяции <tex>\lambda</font>) | Низкая к средней (<tex>d < 500</font>) | Асимптотическая глобальная сходимость | Робототехника, нейроэволюция, дискретная и мультимодальная оптимизация. |- | '''Байесовская оптимизация''' | Да (Гауссовские процессы) | Низкое (очень дорогая функция) | Очень низкая (<tex>d < 20</font>) | Сильные (скорость сублинейной глобальной сходимости) | Подбор гиперпараметров ML, автоматическое проектирование лекарств. |- | '''Zero-Order методы''' (на основе оценки градиента) | Нет (неявное сглаживание) | Фиксированное (<tex>1</font> или <tex>2</font> вызова) | Высокая (<tex>d \approx 10^5</font> и более) | Строгие гарантии сходимости в стохастическом анализе | Черноящичные атаки на глубокие сети, RL, федеративное обучение, LLM. |} </p><p>== Теоретические свойства и гарантии сходимости == Теоретический анализ безградиентных методов нулевого порядка во многом опирается на результаты выпуклого анализа и теории стохастической аппроксимации. </p><p>=== Ограничения по размерности (Dimension Penalty) === Основная плата за отсутствие градиента — сильная зависимость скорости сходимости от размерности пространства <tex>d.

  • Для L-гладких выпуклых функций классический стохастический градиентный спуск (SGD) гарантирует сходимость к экстремуму по функции со скоростью:

O\left(\frac{1}{\sqrt{K}}\right), где K — число итераций. Эта оценка не зависит от размерности явным образом.

  • В то же время для ZO-SGD с двухточечной оценкой градиента скорость сходимости составляет:

O\left(\sqrt{\frac{d}{K}}\right). Таким образом, для достижения точности \epsilon</font> безградиентному методу требуется в <tex>O(d)</font> раз больше вызовов оракула (запросов значения функции), чем градиентному методу. При использовании одноточечной оценки этот штраф возрастает до <tex>O(d^2)</font>. </p><p>=== Сходимость в невыпуклом случае === Для невыпуклых гладких задач гарантируется сходимость к стационарной точке <tex>\mathbb{E}[\|\nabla f(x)\|^2] \le \epsilon</font> за <tex>O(d/\epsilon^2)</font> запросов оракула нулевого порядка, что является неулучшаемой оценкой для общего класса черноящичных методов высокой размерности. </p><p>== Применения в машинном обучении == </p><p>=== 1. Настройка гиперпараметров (Hyperparameter Tuning) === Каждое вычисление значения функции — это полный цикл обучения модели машинного обучения на обучающей выборке и замер метрики качества на валидационном множестве. Поскольку функция не имеет аналитического вида и дифференцировать её по размеру пакета (batch size) или коэффициенту регуляризации невозможно, здесь доминируют методы байесовской оптимизации (библиотеки Optuna, Hyperopt). </p><p>=== 2. Черноящичные атаки на нейросети (Adversarial Machine Learning) === Для проверки робастности (устойчивости) глубоких нейронных сетей генерируются состязательные атаки (adversarial attacks). Если атакующий не имеет доступа к весам и архитектуре модели (Black-Box), а видит лишь выходные вероятности классов, задача генерации минимального возмущения, меняющего класс изображения, формулируется как: <tex>\min_{\delta \in \mathbb{R}^d} \mathcal{L}(M(x+\delta), y_{target}) + \lambda \|\delta\|_2, где M</font> — модель-черный ящик. ZO-методы (например, алгоритм ZOO — Zero-Order Optimization) позволяют эффективно находить состязательные возмущения <tex>\delta</font> высокого разрешения. </li></ul> <p>=== 3. Обучение с подкреплением (Reinforcement Learning) === В задачах управления агентами (Policy Optimization) функция награды часто является дискретной, недетерминированной и зависит от недифференцируемой среды симулятора. Алгоритмы эволюционных стратегий (Evolution Strategies, ES) часто используются как альтернатива методам градиента политики (Policy Gradient), поскольку они легче распараллеливаются на кластерах и не страдают от проблемы «затухания градиентов» на длинных траекториях. </p><p>=== 4. Оптимизация больших языковых моделей (LLM) через API === Современные коммерческие LLM (такие как GPT-4) доступны пользователям только через API. Безградиентная оптимизация (в частности, алгоритмы семейства Black-Box Prompt Tuning) позволяет подбирать непрерывные промпты (soft prompts) или осуществлять тонкую настройку (fine-tuning) весов верхних слоёв локально, оптимизируя качество ответов модели, получаемых в виде текстовых ответов или логитов через внешние запросы. </p><p>=== 5. Федеративное обучение (Federated Learning) === В распределённых системах, где клиенты не могут передавать сырые градиенты на центральный сервер из соображений конфиденциальности или ограничений связи, Zero-Order методы позволяют проводить оптимизацию глобальной модели, обмениваясь лишь локальными скалярными оценками потерь (loss values). </p><p>== Современные направления исследований == </p><p>=== Методы уменьшения дисперсии (Variance Reduction) === Поскольку случайная оценка градиента вносит огромный шум, исследователи адаптируют техники уменьшения дисперсии из стохастической оптимизации. Алгоритмы '''ZO-SVRG''' (Zero-Order Stochastic Variance Reduced Gradient) и '''ZO-SPIDER''' позволяют снизить количество запросов к функции за счёт периодического вычисления точных суррогатных градиентов по подвыборкам данных и отслеживания разностей градиентов. </p><p>=== Высокоразмерная оптимизация (High-Dimensional ZO) === Для работы в пространствах, где размерность <tex>d</font> измеряется миллионами (например, параметры нейросетей), классический случайный поиск неэффективен. Современные подходы используют предположение о '''малой внутренней размерности''' задачи (intrinsic dimension) и проецируют градиентный поиск в низкоразмерное случайное подпространство (развитие методов типа Рандомизированного координатного спуска). </p><p>=== Распределённая и асинхронная ZO-оптимизация === Оценки градиентов по независимым случайным направлениям <tex>u_i</font> могут вычисляться абсолютно независимо на разных вычислительных узлах. Это обеспечивает идеальное линейное ускорение алгоритмов при параллельных вычислениях на GPU/TPU кластерах. </p><p>== Литература == </p> <ol><li> ''Conn A. R., Scheinberg K., Vicente L. N.'' Introduction to Derivative-Free Optimization. — SIAM, 2009. </li><li> ''Larson J., Menickelly M., Wild S. M.'' Derivative-Free Optimization Methods // Acta Numerica. — 2019. — Vol. 28. — P. 287–367. </li><li> ''Nesterov Y., Spokoiny V.'' Random Gradient-Free Minimization of Convex Functions // Foundations of Computational Mathematics. — 2017. — Vol. 17, no. 2. — P. 527–566. </li><li> ''Spall J. C.'' Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control. — John Wiley & Sons, 2005. </li><li> ''Nocedal J., Wright S. J.'' Numerical Optimization. — Springer Science & Business Media, 2006. </li><li> ''Boyd S., Vandenberghe L.'' Convex Optimization. — Cambridge University Press, 2004. </li><li> ''Liu S., Pin-Yu C., Kailasampathy B., Hero A.'' Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning // IEEE Signal Processing Magazine. — 2020. — Vol. 37, no. 5. — P. 43–54. </li></ol> <p>== Ссылки == </p> <ul><li> [[Градиентный спуск]] </li><li> [[Стохастическая оптимизация]] </li><li> [[Эволюционные алгоритмы]] </li><li> [[Байесовская оптимизация]] </li><li> [[Численные методы]]

Источник — «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»