Метод условного градиента (алгоритм Франка — Вульфа) (оптимизация)

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

Статья написана с использованием LLM ChatGPT (GPT-5.6 Sol Medium в режиме агента ChatGPT Work) и проверена участником Aleksei Kovalenko 20:00, 15 июля 2026 (MSD). Промпт приводится полностью в Обсуждение:Метод условного градиента (алгоритм Франка — Вульфа) (оптимизация).

Содержание

1 Постановка задачи
2 Классический алгоритм Франка — Вульфа
- 2.1 Геометрическая интуиция
3 Выпуклый анализ и двойственность
4 Выбор длины шага
5 Основные результаты о сходимости
6 Активное множество и варианты алгоритма
7 Геометрия типичных допустимых множеств и линейные оракулы
8 Применения в машинном обучении
9 Сравнение с другими методами первого порядка
10 Вычислительная сложность и реализация
11 Ограничения и типичные ошибки
12 Когда метод предпочтительнее проекционных методов
13 Современные направления
14 См. также
15 Примечания
16 Литература

Метод условного градиента, или алгоритм Франка — Вульфа (англ. conditional gradient method, Frank–Wolfe algorithm), — метод первого порядка для условной оптимизации, в котором трудная проекция на допустимое множество заменяется минимизацией линейной функции на этом множестве. Метод был предложен М. Франк и Ф. Вульфом для квадратичного программирования^[1]; название «метод условного градиента» закрепилось после работы Е. С. Левитина и Б. Т. Поляка^[1].

Главная область применимости метода — задачи, в которых линейный оракул минимизации существенно дешевле проекции или проксимального оператора. Это характерно для симплексов, многогранников комбинаторного происхождения, шаров атомарных и ядерных норм, спектров и выпуклых оболочек очень большого числа атомов. Итерации являются выпуклыми комбинациями найденных атомов; поэтому метод естественно строит разреженные векторы, смеси с малым числом компонент и матрицы малого ранга.

Постановка задачи

Пусть $({\cal X},\|\cdot\|)$ — конечномерное нормированное пространство, ${\cal D}\subset {\cal X}$ — непустое компактное выпуклое множество, а $f:{\cal D}\to\mathbb R$ — дифференцируемая функция. Рассматривается задача

$f^*:=\min_{x\in{\cal D}} f(x).$

Компактность гарантирует существование решения для непрерывной $f$ . Выпуклость ${\cal D}$ необходима для допустимости отрезка между текущей точкой и ответом оракула. В базовой теории предполагается, что $f$ выпукла и гладка; сам шаг алгоритма определён и для невыпуклой $f$ .

Линейный оракул минимизации (ЛОМ, англ. linear minimization oracle, LMO) по ковектору $c\in{\cal X}^*$ возвращает

${\rm LMO}_{\cal D}(c)\in{\rm argmin}_{s\in{\cal D}}\langle c,s\rangle.$

Точный оракул должен решать линейную задачу глобально. Если ${\cal D}={\rm conv}{\cal A}$ , где ${\cal A}$ — множество атомов, минимум достигается на атоме; хранить всю выпуклую оболочку не требуется.

Классический алгоритм Франка — Вульфа

Пусть задано $x_0\in{\cal D}$ . На итерации $t=0,1,\ldots$ выполняются действия:

вычислить градиент $\nabla f(x_t)$ ;
вызвать линейный оракул
$s_t\in{\rm argmin}_{s\in{\cal D}}\langle\nabla f(x_t),s\rangle;$
выбрать направление условного градиента
$d_t^{\rm FW}=s_t-x_t;$
выбрать шаг $\gamma_t\in[0,1]$ и положить
$x_{t+1}=x_t+\gamma_t d_t^{\rm FW}=(1-\gamma_t)x_t+\gamma_t s_t.$

Так как $x_t,s_t\in{\cal D}$ и ${\cal D}$ выпукло, все итерации допустимы. Если $x_t$ не стационарна, то

$\langle\nabla f(x_t),d_t^{\rm FW}\rangle=-g_t<0,$

где

$g_t:=\max_{s\in{\cal D}}\langle\nabla f(x_t),x_t-s\rangle=\langle\nabla f(x_t),x_t-s_t\rangle$

— разрыв Франка — Вульфа (FW gap). Это одновременно мера стационарности и вычислимая верхняя оценка primal-разрыва.

Геометрическая интуиция

В точке $x_t$ функция заменяется своей аффинной нижней моделью

$m_t(s)=f(x_t)+\langle\nabla f(x_t),s-x_t\rangle.$

Линейный оракул находит точку допустимого множества, наиболее выгодную для этой модели. Алгоритм не переносит минимум модели целиком в новую точку: он движется к нему по хорде множества, а длина шага ограничивает ошибку линеаризации. На многограннике $s_t$ обычно является вершиной; на шаре ядерной нормы — матрицей ранга один; на симплексе — единичным вектором. Поэтому геометрия допустимого множества непосредственно задаёт элементарную структуру обновления.

Условие оптимальности первого порядка для выпуклой задачи должно выполняться для всех $s\in{\cal D}$ и имеет вид

$\langle\nabla f(x^*),s-x^*\rangle\geq 0.$

Следовательно, $g(x)=0$ эквивалентно оптимальности при выпуклой $f$ и эквивалентно стационарности первого порядка в общем дифференцируемом случае.

Выпуклый анализ и двойственность

Сертификат двойственного разрыва

Из выпуклости следует

$f(x^*)\geq f(x)+\langle\nabla f(x),x^*-x\rangle\geq f(x)-g(x),$

то есть

$0\leq h(x):=f(x)-f^*\leq g(x).$

Поэтому условие $g_t\leq\varepsilon$ является проверяемым сертификатом $\varepsilon$ -оптимальности. В отличие от разности последовательных значений функции, разрыв имеет прямой смысл и не требует знания $f^*$ .

Пусть $\delta_{\cal D}$ — индикатор множества, а $\sigma_{\cal D}(y)=\sup_{s\in{\cal D}}\langle y,s\rangle$ — его опорная функция. Тогда задача записывается как минимизация $f+\delta_{\cal D}$ , а

$g(x)=\langle\nabla f(x),x\rangle+\sigma_{\cal D}(-\nabla f(x)).$

Это выражение является разрывом Фенхеля — Юнга для пары $\delta_{\cal D}$ и $\sigma_{\cal D}$ . ЛОМ вычисляет одновременно значение опорной функции и субградиент её аргумента. Такая запись объясняет связь метода с двойственностью Фенхеля и позволяет строить primal-dual-сертификаты^[1].

Ф. Бах показал, что для ряда составных задач обобщённый условный градиент в одной из двойственных постановок эквивалентен субградиентному или зеркальному спуску в сопряжённой постановке^[1]. Это двойственная эквивалентность алгоритмических траекторий при специальных представлениях, а не тождество методов в одной и той же прямой задаче.

Нормы и двойственные нормы

Для нормы $\|\cdot\|$ двойственная норма определяется как

$\|y\|_*:=\sup_{\|x\|\leq1}\langle y,x\rangle.$

Если градиент $L$ -липшицев относительно этой пары норм,

$\|\nabla f(x)-\nabla f(y)\|_*\leq L\|x-y\|,$

то выполняется лемма о спуске

$f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+{L\over2}\|y-x\|^2.$

Обозначив диаметр $D=\sup_{x,y\in{\cal D}}\|x-y\|$ , получают верхнюю оценку кривизны $C_f\leq LD^2$ . Выбор нормы меняет числа $L$ и $D$ , но их произведение часто отражает реальную геометрию лучше, чем автоматически выбранная евклидова норма.

Константа кривизны

Аффинно-инвариантная константа кривизны функции на множестве определяется формулой^[1]

$C_f:=\sup_{x,s\in{\cal D},\;0<\gamma\leq1}{2\over\gamma^2}\left[f(x+\gamma(s-x))-f(x)-\gamma\langle\nabla f(x),s-x\rangle\right].$

Отсюда для шага Франка — Вульфа следует основная рекурсия

$f(x_{t+1})\leq f(x_t)-\gamma_t g_t+{\gamma_t^2\over2}C_f.$

В отличие от $L$ и $D$ по отдельности, $C_f$ не меняется при невырожденной аффинной замене координат. Именно поэтому строгий анализ метода часто формулируют через $C_f$ .

Выбор длины шага

Априорный шаг

Классический выбор

$\gamma_t={2\over t+2}$

не требует параметров задачи и обеспечивает оценку порядка $O(1/t)$ . При нумерации, начинающейся с другой точки, встречается эквивалентная формула $2/(t+3)$ . Ошибка на единицу в индексе несущественна асимптотически, но шаг должен принадлежать $[0,1]$ .

Точный одномерный поиск

Выбирают

$\gamma_t\in{\rm argmin}_{\gamma\in[0,1]}f(x_t+\gamma d_t^{\rm FW}).$

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

Шаг по квадратичной верхней модели

Если известна $C\geq C_f$ , минимизация правой части основной рекурсии даёт

$\gamma_t=\min\left\{{g_t\over C},1\right\}.$

Если известна липшицева константа, можно использовать более локальную модель

$\gamma_t=\min\left\{{g_t\over L\|d_t^{\rm FW}\|^2},1\right\}.$

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

Правило Армихо

Backtracking по условию достаточного убывания также допустим. Проверять надо направление $d_t^{\rm FW}$ и ограничение $\gamma\in[0,1]$ . Использование стандартного правила для неограниченного градиентного спуска без учёта этого интервала может вывести точку из ${\cal D}$ .

Основные результаты о сходимости

Гладкая выпуклая функция: классическая оценка

Теорема. Пусть ${\cal D}$ компактно и выпукло, $f$ выпукла, дифференцируема и имеет конечную константу кривизны $C_f$ . Для точного ЛОМ и шага $\gamma_t=2/(t+2)$ (с полным первым шагом при $t=0$ ) выполняется

$f(x_t)-f^*\leq {2C_f\over t+2},\qquad t\geq1.$

Та же асимптотика получается при точном одномерном поиске и при минимизации квадратичной верхней модели. Если градиент $L$ -липшицев, то достаточно подставить $C_f\leq LD^2$ :

$f(x_t)-f^*\leq {2LD^2\over t+2}.$

Следовательно, для достижения ошибки по значению не более $\varepsilon$ достаточно $O(C_f/\varepsilon)$ вызовов градиента и ЛОМ. Эта оценка в общем классе задач с линейным оракулом не улучшается для классического алгоритма без дополнительных предпосылок.

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

$\min_{0\leq t\leq T}g_t=O(C_f/T).$

Конкретная константа зависит от правила шага и от того, усредняется ли «хвост» последовательности; поэтому оценку значения функции и оценку последнего FW-разрыва нельзя без доказательства отождествлять.

Сильно выпуклая целевая функция

Функция $f$ называется $\mu$ -сильно выпуклой относительно $\|\cdot\|$ , если

$f(y)\geq f(x)+\langle\nabla f(x),y-x\rangle+{\mu\over2}\|y-x\|^2.$

Отсюда следует контроль расстояния до единственного минимума:

$\|x_t-x^*\|^2\leq {2\over\mu}\bigl(f(x_t)-f^*\bigr).$

Однако одна лишь сильная выпуклость $f$ не превращает классический Frank–Wolfe в линейно сходящийся метод: если решение лежит на границе многогранника, алгоритм может продолжать добавлять вершины и сохранять скорость $O(1/t)$ . Это существенное отличие от градиентного спуска без ограничений и проекционного градиентного спуска.

Классический метод сходится линейно при дополнительных геометрических условиях, например если сильно выпуклая гладкая функция имеет решение в относительной внутренности ${\cal D}$ на положительном расстоянии от относительной границы^[1]. Условие часто нарушается в задачах разреженного обучения, где искомое решение специально находится на низкоразмерной грани.

Сильно выпуклая геометрия множества

Множество ${\cal D}$ называется $\alpha$ -сильно выпуклым относительно нормы, если вместе с любыми $x,y\in{\cal D}$ оно содержит окрестность соответствующей хорды радиуса, пропорционального $\alpha\gamma(1-\gamma)\|x-y\|^2$ . Шары некоторых $\ell_p$ - и Schatten-норм обладают этим свойством, а многогранники — нет.

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

$\inf_{x\in{\cal D}}\|\nabla f(x)\|_*>0$

классический метод с подходящим поиском шага достигает $O(1/t^2)$ ^[1]. Условие на градиент, в частности, выполняется, когда безусловный минимум находится вне допустимого множества и градиент непрерывен. Без подобных условий объявлять скорость $O(1/t^2)$ только из сильной выпуклости множества нельзя. Современный аффинно-инвариантный анализ заменяет нормозависимые параметры геометрическими функционалами множества^[1].

Невыпуклая гладкая функция

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

$\min_{0\leq t<T}g_t=O(T^{-1/2}),$

то есть для $g_t\leq\varepsilon$ требуется $O(\varepsilon^{-2})$ итераций^[1]. Это гарантия стационарности, а не глобальной оптимальности.

Неточный линейный оракул

При аддитивной ошибке оракула

$\langle\nabla f(x_t),s_t\rangle\leq\min_{s\in{\cal D}}\langle\nabla f(x_t),s\rangle+\delta_t$

в рекурсии появляется член $\gamma_t\delta_t$ . Чтобы сохранить точность $O(1/t)$ , ошибка должна убывать согласованно с требуемой точностью, например $\delta_t=O(C_f/(t+2))$ . Постоянная аддитивная ошибка обычно создаёт ненулевой предел точности. Мультипликативную точность следует задавать относительно FW-разрыва, а не относительно абсолютного значения линейной цели, которое меняется при добавлении константы. Для комбинаторных ЛОМ приближённость должна быть доказана в той модели ошибки, которую использует теорема.

Активное множество и варианты алгоритма

Пусть ${\cal D}={\rm conv}{\cal A}$ и текущая точка хранится как

$x_t=\sum_{v\in S_t}\alpha_v v,\qquad \alpha_v>0,\qquad\sum_{v\in S_t}\alpha_v=1,$

где $S_t\subset{\cal A}$ — активное множество. Обычный FW умеет добавлять новый атом, но удаляет старые веса лишь общим умножением на $1-\gamma_t$ . Варианты ниже позволяют быстрее изменять грань.

Away-step Frank–Wolfe

Выбираются FW-атом $s_t$ и away-атом

$v_t\in{\rm argmax}_{v\in S_t}\langle\nabla f(x_t),v\rangle.$

Сравниваются направления

$d_t^{\rm FW}=s_t-x_t,\qquad d_t^{\rm A}=x_t-v_t.$

Берётся направление с большим отрицательным скалярным произведением с градиентом. Для away-направления допустимый шаг ограничен величиной

$\gamma_{\max}={\alpha_{v_t}\over1-\alpha_{v_t}}.$

Если достигнут $\gamma_{\max}$ , атом удаляется из представления. Метод особенно эффективен на многогранниках, когда классический алгоритм «зигзагообразно» подходит к границе.

Pairwise Frank–Wolfe

Парный вариант переносит массу непосредственно от плохого активного атома к новому:

$d_t^{\rm PFW}=s_t-v_t,\qquad 0\leq\gamma_t\leq\alpha_{v_t}.$

В отличие от away-step FW, компонент $x_t$ не входит в направление. Шаг может одновременно удалить старый и добавить новый атом. Недостаток — возможные swap steps, меняющие представление почти без уменьшения функции; при доказательстве линейной скорости их считают отдельно.

Fully corrective Frank–Wolfe

После добавления $s_t$ полностью пересчитываются коэффициенты:

$x_{t+1}\in{\rm argmin}_{x\in{\rm conv}(S_t\cup\{s_t\})}f(x).$

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

Линейная сходимость на многогранниках

Пусть $f$ имеет $L$ -липшицев градиент и является $\mu$ -сильно выпуклой на многограннике ${\cal D}={\rm conv}{\cal A}$ . Away-step, pairwise и fully corrective варианты имеют геометрическую сходимость по числу хороших шагов^[1]:

$h_{t+1}\leq(1-\rho)h_t$

на каждом таком шаге, где $\rho>0$ зависит от обусловленности функции и геометрии многогранника. Через пирамидальную ширину ${\rm PWidth}({\cal A})$ типичную консервативную оценку для away-step FW можно записать с некоторой абсолютной константой $c>0$ , зависящей от соглашений в определениях:

$\rho\geq c\,{\mu\over L}\left({{\rm PWidth}({\cal A})\over{\rm diam}({\cal D})}\right)^2.$

Точная числовая константа зависит от определения аффинной сильной выпуклости и кривизны. Для away-step FW число хороших шагов не меньше примерно половины общего числа: drop-шагов не может быть больше, чем шагов добавления. Для pairwise FW учёт swap-шагов сложнее. Формулировка «линейная сходимость любого FW на сильно выпуклой функции» неверна: нужны вариант, допускающий удаление атомов, и положительная геометрическая константа многогранника либо иные дополнительные условия.

Геометрия типичных допустимых множеств и линейные оракулы

Множество ${\cal D}$	Ответ ЛОМ для ковектора $c$	Структура итерации
Симплекс $\{x\geq0:\sum_i x_i=1\}$	Единичный вектор $e_j$ , где $j\in\arg\min_i c_i$	Смесь не более чем $t+1$ выбранных вершин
Шар $\ell_1$ : $\\|x\\|_1\leq\tau$	$-\tau\,{\rm sign}(c_j)e_j$ , где $j\in{\rm argmax}_i\|c_i\|$	Добавляется не более одной координаты
Шар $\ell_2$ : $\\|x\\|_2\leq\tau$	$-\tau c/\\|c\\|_2$ при $c\ne0$	Обычно плотный атом; проекция здесь также дешева
Шар ядерной нормы $\\|X\\|_*\leq\tau$	$-\tau uv^{\mathsf T}$ , где $u,v$ — ведущие сингулярные векторы $c$	Ранг увеличивается не более чем на единицу
Спектр $\{X\succeq0:{\rm tr}X=\tau\}$	$\tau uu^{\mathsf T}$ , где $u$ — собственный вектор минимального собственного значения $c$	Положительная полуопределённость и низкий ранг
Выпуклая оболочка структур ${\rm conv}{\cal A}$	Решение $\min_{a\in{\cal A}}\langle c,a\rangle$	Разреженное атомарное представление

Для шара нормы $\|x\|\leq\tau$ значение линейной подзадачи равно $-\tau\|c\|_*$ ; таким образом, двойственная норма не является декоративным элементом анализа, а непосредственно определяет оракул. Практическая выгода зависит от отношения стоимости ЛОМ к стоимости проекции. Например, на евклидовом шаре обе операции имеют замкнутую формулу, поэтому преимущество FW невелико; на шаре ядерной нормы ЛОМ требует только ведущую сингулярную пару, тогда как точная проекция требует существенно более полного сингулярного разложения.

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

Разреженное обучение и атомарные нормы

Для задачи

$\min_{\|w\|_1\leq\tau}\ell(w)$

каждый ЛОМ выбирает координату с максимальным по модулю компонентом градиента. После $t$ итераций классического FW решение содержит не более $t+1$ выбранных атомов. Это даёт явный путь регуляризации по вычислительному бюджету. Для групповой и структурной разреженности атомы являются допустимыми группами, путями, деревьями или другими структурами; сложность переносится в задачу линейного выбора структуры.

Разреженность здесь относится к атомарному представлению итерации. Она не означает, что истинный оптимум обязательно разрежен, и может ухудшаться из-за неединственности разложения. Fully corrective и away-step варианты способны удалять лишние атомы.

Матричное дополнение и ядерная норма

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

$\min_{\|X\|_*\leq\tau}{1\over2}\|P_\Omega(X-M)\|_F^2.$

ЛОМ возвращает ранговую единичную матрицу, построенную по ведущей сингулярной паре отрицательного градиента. Поэтому ранг итерации растёт не более чем на единицу, а разреженные наблюдения можно использовать без формирования плотной матрицы. Подход был развит для крупномасштабных задач с ядерной нормой и продемонстрирован на матричном дополнении^[1]. Ограничение состоит в том, что при высокой требуемой точности ранг и память растут; тогда полезны коррекции на активном подпространстве, in-face-направления или факторизованные локальные шаги.

Структурированное предсказание

В двойственной задаче структурированного SVM допустимое множество является произведением симплексов. Блочный Frank–Wolfe обновляет один объект обучения и вызывает loss-augmented inference oracle, то есть решает задачу структурированного предсказания вместо проекции на огромный симплекс. Метод имеет оценку $O(1/\varepsilon)$ по двойственному разрыву при стандартной гладкой выпуклой двойственной цели и уменьшает стоимость итерации по сравнению с полным оракулом^[1].

Обучение на симплексе и смеси

Симплекс возникает при обучении весов ансамбля, распределений тем, портфелей, смесей экспертов и дискретных вероятностных распределений. Итерация FW добавляет одну вершину, то есть одну компоненту смеси. После $t$ шагов носитель имеет размер не более $t+1$ , если не проводились иные операции. Это удобно, когда стоимость применения модели пропорциональна числу компонент; если же нужен плотный вероятностный вектор и проекция на симплекс дешева, проекционный или зеркальный метод обычно конкурентоспособнее.

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

В задачах вывода по маргинальному многограннику линейная оптимизация часто эквивалентна MAP-выводу. Поэтому условный градиент позволяет приближать маргиналы последовательностью вызовов хорошо разработанного MAP-оракула. Для tree-reweighted-вариационных целей требуется учитывать барьерное поведение энтропийных членов у границы; стандартная глобальная липшицевость градиента там отсутствует, и применяются contraction/barrier-варианты^[1].

В функциональной оптимизации по вероятностным мерам атомом служит, например, распределение из простой параметрической семьи или частица, а итерация строит конечную смесь. Сходимость требует отдельно определить топологию, дифференциал функционала и компактность; конечномерную теорему нельзя переносить автоматически. Модифицированные FW-процедуры в пространстве мер применяются к минимизации функционалов расхождения и генеративному моделированию^[1].

Полуопределённая и спектральная оптимизация

На спектре ЛОМ сводится к вычислению одного экстремального собственного вектора. Это позволяет получать низкоранговые приближения решений больших полуопределённых программ и хранить только фактор или скетч матрицы. Метод применим к релаксациям кластеризации, Max-Cut, фазового восстановления и задачам метрического обучения. Выигрыш особенно велик, когда полная матрица не помещается в память, но доступны произведения матрицы градиента на вектор.

Сравнение с другими методами первого порядка

Метод	Основная операция с ограничением	Типичная оценка для гладкой выпуклой задачи	Структура итераций	Когда предпочтителен
Метод условного градиента	$\min_{s\in{\cal D}}\langle c,s\rangle$	$O(LD^2/t)$ ; линейная скорость вариантов на многограннике при сильной выпуклости и положительной геометрической константе	Выпуклая комбинация атомов; разреженность или низкий ранг контролируются числом итераций	ЛОМ намного дешевле проекции; нужны допустимые структурированные промежуточные решения
Проекционный градиентный спуск	$\Pi_{\cal D}(x-\eta\nabla f(x))$	$O(L\\|x_0-x^*\\|^2/t)$ ; линейная скорость для сильно выпуклой гладкой цели	Проекция часто создаёт плотную точку	Проекция проста или нужна высокая точность без дорогого управления активным множеством
Зеркальный спуск	Bregman-проксимальная задача, заданная зеркальной функцией	Для липшицевых негладких задач обычно $O(1/\sqrt t)$ ; для гладких вариантов оценки зависят от относительной гладкости	Геометрия выбирается через дивергенцию Брэгмана; на симплексе обновления часто плотные и положительные	Энтропийная геометрия, вероятностные векторы, онлайн- и стохастическая оптимизация
Проксимальный градиентный метод	${\rm prox}_{\eta r}(x-\eta\nabla f(x))$	$O(1/t)$ , ускоренный вариант $O(1/t^2)$ ; линейно при подходящей сильной выпуклости	Может точно занулять координаты для сепарабельных регуляризаторов	Составная цель $f+r$ и дешёвый проксимальный оператор
Координатный спуск	Выбор и оптимизация координаты или блока	Зависит от покоординатных констант гладкости; линейно при сильной выпуклости в стандартных условиях	Изменяет существующие координаты, но допустимость при связанных ограничениях нетривиальна	Дешёвые частичные производные, разреженные данные, сепарабельная структура

Отличие от проекционного градиентного спуска

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

$\Pi_{\cal D}(z)={\rm argmin}_{x\in{\cal D}}{1\over2}\|x-z\|_2^2.$

FW решает линейную задачу и движется по допустимой хорде. Линейная оптимизация и проекция могут иметь радикально разную сложность: над ядерным шаром это ведущая сингулярная пара против полного порогового сингулярного разложения; над некоторыми комбинаторными многогранниками ЛОМ является известной задачей кратчайшего пути или сопоставления, тогда как евклидова проекция требует общей квадратичной оптимизации. Но над ящиком, евклидовым шаром или стандартным симплексом проекция дешева, и меньшая стоимость одной FW-итерации не гарантирована.

Отличие от зеркального и проксимального методов

Зеркальный спуск минимизирует локальную линейную модель плюс Bregman-регуляризатор; его геометрия задаётся зеркальным отображением, а не атомами допустимого множества. Проксимальный метод решает нелинейную регуляризованную подзадачу и естественен для составной цели. Условный градиент, напротив, обращается только к линейной поддерживающей задаче над ${\cal D}$ . Двойственная связь между этими методами не отменяет различий в оракулах, промежуточной структуре и стоимости итерации.

Отличие от координатного спуска

На $\ell_1$ -шаре FW-атом действительно выбирает одну координату, поэтому шаг внешне похож на жадный координатный. Однако FW сохраняет связанные ограничения посредством выпуклой комбинации и сравнивает все допустимые атомы в линейном оракуле. Координатный спуск изменяет координату в текущем представлении и обычно анализируется через покоординатную гладкость. На общем атомарном множестве «координата» может быть деревом, перестановкой или матрицей ранга один, что выходит за рамки обычного координатного спуска.

Вычислительная сложность и реализация

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

Практически важны следующие приёмы:

хранить коэффициенты активных атомов, а не плотную точку, если это уменьшает память;
использовать warm start для спектрального или комбинаторного ЛОМ;
кэшировать ранее найденные атомы и сначала искать улучшение в кэше; lazy-варианты уменьшают число дорогих вызовов ЛОМ без изменения требуемого сертификата при корректной проверке^[1];
периодически удалять нулевые веса и контролировать численную нормировку коэффициентов;
вычислять истинный FW-разрыв полным ЛОМ перед остановкой, если внутренние итерации использовали кэш или приближённый оракул;
для суммы по объектам применять блочные, стохастические или variance-reduced варианты только с соответствующей им теорией, поскольку подстановка шумного градиента в детерминированную оценку некорректна;
сравнивать время до заданного разрыва и память, а не только число эпох.

Условно-градиентное скольжение отделяет число вычислений полного градиента от числа линейных оракулов и при гладкой выпуклой цели может достигать ускоренной сложности по градиентам, сохраняя порядок $O(1/\varepsilon)$ по ЛОМ^[1]. Это новый алгоритмический слой, а не улучшенная оценка классической одношаговой схемы.

Ограничения и типичные ошибки

Медленное приближение к границе. Классический FW может зигзагообразно двигаться между вершинами и имеет скорость $O(1/t)$ даже для сильно выпуклой цели. На многогранниках следует рассмотреть away-step, pairwise или fully corrective вариант.
Рост активного множества. Один новый атом на итерацию означает рост памяти и стоимости предсказания. Нужны удаление атомов, коррекция, сжатие по теореме Каратеодори или скетчирование.
Неверный ЛОМ. Минимизация отдельных координат не решает линейную задачу при связанных ограничениях. Знак также критичен: минимизировать надо скалярное произведение с градиентом, а не максимизировать его.
Необоснованно неточный оракул. Эвристическое решение комбинаторной подзадачи не даёт сертификата FW-разрыва, если неизвестна его гарантированная ошибка.
Слишком большой шаг. Значение $\gamma_t>1$ для обычного FW нарушает представление выпуклой комбинацией. Для away- и pairwise-шагов верхняя граница ещё меньше и зависит от активного веса.
Постоянный слишком малый шаг. Он может дать ненулевую окрестность решения; постоянный шаг не заменяет убывающую схему или поиск по модели.
Слепое применение точного line search. При шумной функции точный поиск не определён практически, а многочисленные вычисления цели могут стоить дороже сохранённых итераций.
Остановка по изменению функции. Малое $|f(x_{t+1})-f(x_t)|$ не доказывает оптимальность. Для выпуклой задачи следует использовать FW-разрыв с достаточно точным полным ЛОМ.
Игнорирование негладкости. Для негладкой цели константа кривизны может быть бесконечной. Простая замена градиента субградиентом не наследует классическую оценку; нужны сглаживание, составной условный градиент или специальные projection-free-методы.
Смешение сильной выпуклости функции и множества. Это разные свойства с разными последствиями. Сильная выпуклость цели сама по себе не гарантирует линейную скорость классического FW; сильная выпуклость множества не заменяет гладкость цели и дополнительные условия невырождения.
Плохая масштабировка нормы. Евклидова оценка $LD^2$ может быть огромной, хотя аффинно-инвариантная кривизна умеренна. Масштабирование переменных и выбор естественной пары норм влияют на практику и на интерпретируемые границы.

Когда метод предпочтительнее проекционных методов

Метод условного градиента практически предпочтителен, если одновременно выполняется значительная часть следующих условий:

точный или контролируемо приближённый ЛОМ решается существенно дешевле проекции;
допустимое множество имеет атомарное описание, а малая мощность активного множества полезна сама по себе;
промежуточные точки должны оставаться допустимыми и структурированными;
матрица слишком велика для полного спектрального разложения, но доступны произведения на вектор;
существует быстрый MAP-, shortest-path-, matching- или иной комбинаторный оракул;
нужна умеренная точность, при которой разреженность итераций важнее асимптотической высокоточной сходимости;
память является главным ограничением.

Проекционный или проксимальный метод обычно лучше, если проекция дешева, требуется очень высокая точность, плотные итерации приемлемы, а управление активным множеством и повторные ЛОМ доминируют по времени. Выбор должен основываться на стоимости конкретных оракулов, а не на ярлыке «без проекций».

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

После классического результата 1956 года и анализа условных градиентов 1960-х годов основные новые направления включают аффинно-инвариантные сертификаты и кривизну, линейно сходящиеся варианты на многогранниках, блочные и стохастические схемы, lazy-оракулы, ускорение числа градиентов, методы для невыпуклых и составных задач, оптимизацию в пространствах мер и управление размером активного множества. Современный обзор с систематизацией этих направлений дан в работе Г. Брауна и соавторов^[1] и в одноимённой монографии 2025 года.

Новые варианты следует отличать от классического FW по трём вопросам: какой оракул вызывается, какая вспомогательная задача решается и относительно какой величины доказана скорость. Например, ускоренная сложность по градиентам не обязательно означает меньше линейных оракулов; линейная скорость по хорошим шагам не равна линейной скорости по всем итерациям; сходимость FW-разрыва в невыпуклой задаче не означает сходимость к глобальному минимуму.

См. также

Примечания

Литература

Frank M., Wolfe P. An Algorithm for Quadratic Programming // Naval Research Logistics Quarterly. — 1956. — Т. 3. — № 1—2. — С. 95—110.
Левитин Е. С., Поляк Б. Т. Методы минимизации при наличии ограничений // Журнал вычислительной математики и математической физики. — 1966. — Т. 6. — № 5. — С. 787—823.
Bertsekas D. P. Nonlinear Programming. — 3rd ed.. — Belmont, MA: Athena Scientific, 2016. — 861 с. — ISBN 978-1-886529-05-2
Beck A. First-Order Methods in Optimization. — Philadelphia: SIAM, 2017. — (MOS-SIAM Series on Optimization). — ISBN 978-1-61197-498-0
Jaggi M. Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization // Proceedings of the 30th International Conference on Machine Learning. — 2013. — Т. 28. — С. 427—435.
Bach F. Duality between Subgradient and Conditional Gradient Methods // SIAM Journal on Optimization. — 2015. — Т. 25. — № 1. — С. 115—129.
Lacoste-Julien S., Jaggi M. On the Global Linear Convergence of Frank-Wolfe Optimization Variants // Advances in Neural Information Processing Systems. — 2015. — Т. 28. — С. 496—504.
Garber D., Hazan E. Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets // Proceedings of the 32nd International Conference on Machine Learning. — 2015. — Т. 37. — С. 541—549.
Lan G., Zhou Y. Conditional Gradient Sliding for Convex Optimization // SIAM Journal on Optimization. — 2016. — Т. 26. — № 2. — С. 1379—1409.
Bomze I. M., Rinaldi F., Zeffiro D. Frank–Wolfe and Friends: a Journey into Projection-Free First-Order Optimization Methods // 4OR. — 2021. — Т. 19. — С. 313—345.
Braun G., Carderera A., Combettes C. W., Hassani H., Karbasi A., Mokhtari A., Pokutta S. Conditional Gradient Methods2022.
Braun G., Carderera A., Combettes C. W., Hassani H., Karbasi A., Mokhtari A., Pokutta S. Conditional Gradient Methods: From Core Principles to AI Applications. — Philadelphia: SIAM, 2025.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B3%D1%80%D0%B0%D0%B4%D0%B8%D0%B5%D0%BD%D1%82%D0%B0_%28%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D1%80%D0%B0%D0%BD%D0%BA%D0%B0_%E2%80%94_%D0%92%D1%83%D0%BB%D1%8C%D1%84%D0%B0%29_%28%D0%BE%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F%29»

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