Безградиентная и нулевого порядка оптимизация

Вы хотите обучить робота ходить - но у симулятора нет градиента. Хотите найти лучшую архитектуру нейросети - но backprop через NAS невозможен. Хотите оптимизировать форму крыла самолёта - но CFD-симуляция занимает час. Что делать, когда математического градиента нет? **Безградиентная оптимизация** - искусство учиться, видя только результат.

• **Neural Architecture Search (NAS)**: EfficientNet, NASNet найдены эволюционными алгоритмами - оптимизация дискретных архитектурных решений, где backprop неприменим
• **Reinforcement Learning без backprop**: OpenAI использовал ES для обучения роботов ходить - параллелизация на 1000+ CPU без gradient communication overhead
• **Drug design**: молекулярная оптимизация через CMA-ES - каждый «вызов функции» это физическая или химическая симуляция

Предварительные знания

• Distributed Optimization
• Optimization in ML and Production

Введение: когда градиента нет

Большинство методов оптимизации предполагают доступ к **градиенту ∇f(x)**. Но что если функция - это симуляция физики, результат запроса к внешнему API, дифференцируемая только численно, или вообще не имеет аналитической формы? Это задачи **безградиентной оптимизации** (zeroth-order / derivative-free optimization).

**Black-box функции**: оптимизация гиперпараметров нейросети (каждый вызов = полное обучение), A/B-тестирование (метрика - результат эксперимента), game playing (счёт = результат симуляции). **Недифференцируемые функции**: задачи с дискретными переменными, пороговые функции, min/max операции, integer programming. **Симуляции**: аэродинамическая оптимизация (CFD simulation), молекулярный дизайн, роботика (движение оценивается симулятором). **Ключевое ограничение**: только оракул f(x) - можно вычислить значение в точке, но не производную.

Безградиентные методы работают с **сотнями вызовов функции** вместо тысяч итераций SGD. Их слабость - **масштабируемость с размерностью**: стандартные методы эффективны для d ≤ 10³, в то время как нейросети имеют 10⁶-10¹² параметров. Для последних используются специальные подходы: Evolution Strategies с параметрическим семплированием.

Конечные разности: численный градиент

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

**Gradient check** - стандартная техника отладки реализаций backpropagation. Вы вычисляете числовой градиент через конечные разности (медленно, но корректно) и сравниваете с аналитическим (быстро, но может быть с багами). Relative error ≈ 1e-7 или меньше → аналитический градиент верен. Relative error > 1e-2 → ошибка в реализации backprop. CS231n (Стэнфорд) рекомендует gradient check как обязательный шаг отладки любой новой архитектуры.

Evolution Strategies: CMA-ES

**Evolution Strategies (ES)** - класс алгоритмов, вдохновлённых биологической эволюцией. В отличие от конечных разностей, ES не аппроксимирует градиент по одному параметру за раз, а **семплирует популяцию** решений и обновляет распределение поиска на основе лучших результатов.

**Когда CMA-ES побеждает**: невыпуклые ландшафты с многими локальными минимумами, разрывные функции, шумные оракулы (каждый вызов случайно колеблется), нет доступа к градиенту. **Когда градиентные методы лучше**: гладкие дифференцируемые функции, d > 1000 параметров, каждый вызов функции дорогой (нейросеть тренируется часами). **Популяционный оптимизм**: CMA-ES параллелизируется линейно - λ вычислений в поколении независимы. При λ=64 GPU каждое поколение занимает столько же времени, сколько одна оценка.

Случайный поиск и теоретические гарантии

**Случайный поиск** - наивный baseline: семплировать x из какого-то распределения, оценить f(x), запомнить лучший результат. Удивительно, но для многих задач random search работает конкурентно с более сложными методами.

Для **гладких функций** (Lipschitz-непрерывный градиент) можно доказать: **Случайный поиск** на единичном шаре: E[f(x*) - f(xₜ)] = O(1/√T) **CMA-ES** на квадратичных функциях: линейная сходимость - E[f(xₜ)] ∝ ρᵗ для ρ < 1 **ES как конечно-разностный метод**: при определённом семплировании ES ≈ SGD по функционалу Jₛ(θ) = E_{ε~N(0,I)}[f(θ+σε)] ∇_θ Jₛ(θ) = (1/σ) · E_ε[f(θ+σε)·ε] Оценка методом Монте-Карло (OpenAI ES, Salimans et al. 2017): ∇̂ Jₛ(θ) = (1/nσ) · Σᵢ f(θ+σεᵢ) · εᵢ Это позволяет масштабировать ES на нейросети с миллионами параметров!

Ключевые идеи

• **Zeroth-order**: только оракул f(x) - симуляции, недифференцируемые функции, black-box системы
• **Конечные разности**: ∇f ≈ [f(x+heᵢ)-f(x)]/h, стоимость O(d) вызовов, инструмент gradient check для отладки backprop
• **CMA-ES**: адаптирует матрицу ковариаций поиска, эффективен для d ≤ 1000, лучший выбор для гладких black-box задач
• **No Free Lunch**: нет универсального алгоритма - CMA-ES лучше random search только для гладких структурированных функций

Связанные темы

Безградиентная оптимизация дополняет другие методы там, где градиент недоступен:

• Байесовская оптимизация — Ещё один black-box метод - суррогатная модель (GP/TPE) вместо эволюционного поиска, эффективнее при малом числе вызовов
• Метаэвристики — Генетические алгоритмы, PSO - родственные методы из той же категории popular population-based zero-order optimization
• Безградиентная и нулевого порядка оптимизация — Адаптивные оптимизаторы Adam/SGD - противоположность: требуют дифференцируемости, но работают с миллиардами параметров

Вопросы для размышления

• Если у вас есть функция с 1000 параметров и каждый вызов занимает 10 секунд, какой метод вы выберете и почему?
• OpenAI ES масштабировался на 1000+ CPU лучше, чем RL с backprop. Почему параллелизация проще для ES?
• No Free Lunch theorem говорит, что нет универсального алгоритма. Как это влияет на выбор метода на практике?

Связанные уроки

• calc-01-sequences