Покоординатный спуск 🧭

Когда ты вызываешь sklearn.linear_model.Lasso().fit(X, y), внутри почти наверняка не происходит ничего похожего на градиентный спуск из урока 285 или проксимальный градиентный метод из урока 291. Вместо этого библиотека запускает алгоритм, который вообще ни разу не вычисляет полный градиент функции потерь. Он берёт первый признак, полностью фиксирует все остальные веса, решает крошечную одномерную задачу — и мгновенно получает точный, аналитический ответ для этого одного веса. Потом переходит к следующему признаку и повторяет то же самое. Никакого выбора скорости обучения, никакого line search (линейного поиска), никакой возни с субградиентами негладкой $L_1$-нормы — только последовательность простых одномерных вычислений, каждое из которых решается за микросекунды. Это и есть покоординатный спуск, и это де-факто стандартный решатель (solver='cd') для Lasso и Elastic Net в scikit-learn и в куда более старом и почтенном R-пакете glmnet.

Идея кажется почти наивной: зачем спускаться сразу по всем координатам через полный градиент, если можно оптимизировать по одной координате за раз, зафиксировав все остальные? На первый взгляд это выглядит как явная потеря информации — ведь полный градиент учитывает взаимодействие всех переменных одновременно, а покоординатный шаг видит только одно измерение. Но здесь есть неочевидный выигрыш, который и объясняет, почему этот метод оказался практическим стандартом именно для Lasso: одномерная подзадача «оптимизировать по одной координате, зафиксировав остальные» для очень широкого класса функций машинного обучения решается аналитически, в одну строчку формулы, без единой итерации внутреннего цикла. А полный градиентный шаг для той же самой задачи с $L_1$-регуляризацией такого явного решения не имеет вообще — там приходится либо брать субградиент (урок 290) и мучиться с шагом, либо строить полноценный проксимальный оператор (урок 291) поверх всей задачи целиком.

Покоординатный спуск превращает одну сложную $n$-мерную задачу оптимизации в последовательность из $n$ простых одномерных задач — а одномерные задачи в оптимизации почти всегда либо решаются аналитически, либо решаются перебором/бисекцией на порядки быстрее и надёжнее, чем их многомерные аналоги. В этом уроке ты разберёшь саму идею одномерных подзадач, сравнишь циклический порядок обхода координат со случайным выбором, выведешь точную аналитическую формулу для типичных задач регрессии и увидишь, как покоординатный спуск, объединённый с soft thresholding (мягким пороговым отсечением) из урока 291, превращается в конкретный, наизусть выводимый алгоритм обучения Lasso. А в конце — честный разговор про то, когда покоординатный спуск буксует: он прекрасно работает на сепарабельных или почти сепарабельных задачах вроде Lasso, но может застрять в совершенно неоптимальной точке на негладких задачах, где переменные переплетены между собой так, что покомпонентного проксимального решения попросту не существует.

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

История

Формула, которую использует покоординатный спуск для решения одномерной подзадачи в квадратичных функциях, — не новое изобретение эпохи машинного обучения. Это буквально та же самая формула, которую в XIX веке использовал метод Гаусса — Зейделя (Gauss-Seidel method) для итеративного решения систем линейных уравнений $Ax = b$. Карл Фридрих Гаусс описал идею такого итеративного уточнения решения ещё в частном письме 1823 года, а формально и полно метод опубликовал в 1874 году немецкий математик Филипп Людвиг фон Зейдель, применявший его к задачам астрономических вычислений методом наименьших квадратов. Если переписать минимизацию квадратичной функции $f(x) = \frac{1}{2}x^\top A x - b^\top x$ как решение системы $Ax=b$ (её градиент как раз и обращается в ноль на решении этой системы), то классическая итерация Гаусса — Зейделя оказывается математически идентична покоординатному спуску, применённому к этой квадратичной функции. Оптимизаторы, по сути, переоткрыли численный метод почти вековой давности и применили его к куда более широкому классу негладких и невыпуклых задач.

Формализация покоординатного спуска именно как метода оптимизации (а не только решения линейных систем) шла постепенно на протяжении XX века, и практически сразу возник неудобный вопрос: а всегда ли этот метод вообще сходится к правильному ответу? В 1973 году британский математик Майкл Пауэлл (Michael J. D. Powell), тот самый Пауэлл из формулы DFP из прошлого урока, построил явный контрпример: негладкую функцию нескольких переменных, на которой циклический покоординатный спуск, стартовав из определённой точки, застревает навсегда в точке, которая вовсе не является минимумом функции, хотя ни один шаг вдоль отдельной координатной оси эту точку улучшить не может. Этот результат надолго закрепил за покоординатным спуском репутацию метода «работающего, но ненадёжного», пока в 2001 году американский математик Пауль Цзэн (Paul Tseng) не доказал строгую теорему сходимости для важного частного случая: если негладкая часть целевой функции сепарабельна — то есть представима как сумма отдельных функций от каждой координаты по отдельности, — циклический покоординатный спуск гарантированно сходится к точке минимума. А $L_1$-норма $\lambda\|w\|_1 = \lambda\sum_i |w_i|$, ключевая деталь регуляризации Lasso, — это ровно такая сепарабельная негладкая функция.

Именно теорема Цзэна дала теоретическое обоснование тому, что было замечено на практике чуть раньше: в 2007 году Джером Фридман, Тревор Хасти, Хольгер Хёфлинг и Роберт Тибширани опубликовали работу «Pathwise Coordinate Optimization», в которой показали, что покоординатный спуск решает задачу Lasso на порядки быстрее, чем считавшиеся тогда стандартными методы вроде LARS, особенно если считать решение не для одного значения $\lambda$, а сразу для целого пути значений регуляризации от большого к маленькому. Этот алгоритм лёг в основу R-пакета glmnet, который де-факто стал отраслевым стандартом статистического пакета для Lasso и Elastic Net, а позже — и решателем по умолчанию в scikit-learn. Параллельно, в 2010 году, Юрий Нестеров опубликовал теоретический анализ случайного покоординатного спуска, доказав для него строгие гарантии сходимости в ожидании и объяснив, почему случайный выбор координаты часто оказывается практически надёжнее циклического порядка на очень больших задачах — эта работа положила начало отдельному направлению исследований randomized coordinate descent, актуальному и сегодня для оптимизации в задачах огромной размерности.

Идея: превращаем многомерную задачу в последовательность одномерных подзадач

Интуиция

Представь функцию $f(x_1, \ldots, x_n)$, которую нужно минимизировать. Полный градиентный шаг требует вычислить вектор $\nabla f$ целиком — все $n$ частных производных сразу — и сдвинуться в направлении, противоположном этому вектору, на длину, зависящую от подобранного шага $\alpha$. Покоординатный спуск действует иначе: он берёт только одну координату $x_i$, объявляет все остальные координаты временно константами и решает получившуюся одномерную задачу минимизации точно — находит именно тот $x_i$, который при фиксированных остальных координатах даёт наименьшее возможное значение функции, а не просто делает маленький шаг в сторону уменьшения. Это принципиальное отличие от градиентного шага: градиентный спуск всегда делает лишь приближение, крошечный шаг вдоль направления убывания, а покоординатный спуск в одномерной подзадаче решает её до конца, если решение вообще можно найти аналитически или дешёвым точным методом.

Затем алгоритм переходит к следующей координате, снова решает одномерную подзадачу до конца — но уже используя новое, только что обновлённое значение предыдущей координаты, а не то, что было в начале цикла. Это тот же самый приём, который отличает Гаусса — Зейделя от более наивного метода Якоби: каждая координата сразу видит самую свежую информацию о соседних координатах, а не устаревшую с начала итерации. Пройдя так по всем $n$ координатам, алгоритм завершает один цикл — полный проход — и, если функция ещё не минимизирована, начинает новый цикл заново.

Формальное определение

Покоординатный спуск. Пусть требуется минимизировать функцию $f(x_1, \ldots, x_n)$. На итерации, где обновляется координата $i$, все остальные координаты фиксируются на их текущих значениях, а новое значение $x_i$ находится как точное решение одномерной подзадачи:

$$x_i^{\text{new}} = \arg\min_{x_i \in \mathbb{R}} f\bigl(x_1, \ldots, x_{i-1}, x_i, x_{i+1}, \ldots, x_n\bigr)$$

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

Важная деталь этого определения — слово «точное решение». Покоординатный спуск не делает маленький шаг вдоль оси $x_i$: он находит ровно ту точку на этой оси, которая минимизирует функцию при фиксированных остальных переменных, и сразу перескакивает туда. Это возможно именно потому, что одномерная задача минимизации почти всегда решается либо в явном виде (для квадратичных функций — простое деление, как ты увидишь дальше), либо очень быстрыми численными методами (бисекция, метод Ньютона на прямой), несравнимо более надёжными, чем подбор шага в многомерном случае.

Примеры

Пример 1: полная трассировка трёх циклов на функции двух переменных. Возьмём $f(x,y) = x^2 + y^2 + xy - 3x - 3y + 4$. Эта функция выпуклая (матрица вторых производных $\begin{pmatrix}2&1\\1&2\end{pmatrix}$ имеет собственные значения $1$ и $3$, обе положительны), и у неё есть единственный минимум — легко проверить, что он достигается в точке $(1,1)$ со значением $f(1,1)=1$.

Стартуем из точки $(0,0)$.

Цикл 1. Сначала фиксируем $y=0$ и минимизируем по $x$: $f(x,0) = x^2 - 3x + 4$, производная $2x-3=0$ даёт $x=1{,}5$. Точка стала $(1{,}5;\ 0)$. Теперь фиксируем $x=1{,}5$ и минимизируем по $y$: $f(1{,}5,y) = y^2 - 1{,}5y + 1{,}75$, производная $2y-1{,}5=0$ даёт $y=0{,}75$. Точка после первого цикла: $(1{,}5;\ 0{,}75)$, значение функции $f = 1{,}1875$.

Цикл 2. Фиксируем $y=0{,}75$, минимизируем по $x$: получаем $x=1{,}125$. Точка $(1{,}125;\ 0{,}75)$. Фиксируем $x=1{,}125$, минимизируем по $y$: получаем $y=0{,}9375$. Точка после второго цикла: $(1{,}125;\ 0{,}9375)$, значение функции $\approx 1{,}0117$.

Цикл 3. Фиксируем $y=0{,}9375$, минимизируем по $x$: получаем $x=1{,}03125$. Фиксируем $x=1{,}03125$, минимизируем по $y$: получаем $y=0{,}984375$. Точка после третьего цикла: $(1{,}03125;\ 0{,}984375)$.

Присмотрись к отклонению от истинного минимума $(1,1)$: после цикла 1 отклонение по $x$ равно $0{,}5$, после цикла 2 — уже $0{,}125$, после цикла 3 — $0{,}03125$. Каждое отклонение ровно в четыре раза меньше предыдущего — покоординатный спуск на этой строго выпуклой квадратичной функции сходится линейно, геометрически быстро, без единого вычисления полного градиента и без единого подбора длины шага.

Пример 2: сепарабельная функция сходится за один цикл. Возьмём $f(x,y) = (x-5)^2 + (y+2)^2$. У этой функции нет перекрёстного слагаемого $xy$ — она сепарабельна, распадается на сумму функции от $x$ и функции от $y$ по отдельности. Стартуем из $(0,0)$. Минимизация по $x$ при любом фиксированном $y$ всегда даёт $x=5$ (слагаемое с $y$ на эту подзадачу вообще не влияет), минимизация по $y$ при любом фиксированном $x$ всегда даёт $y=-2$. Уже после первого цикла покоординатный спуск оказывается точно в глобальном минимуме $(5,-2)$ — никакие дальнейшие циклы уже ничего не меняют. Это крайний случай, но он подсказывает общее правило: чем меньше взаимодействие между координатами (чем меньше внедиагональных элементов в матрице вторых производных), тем быстрее сходится покоординатный спуск.

Пример 3: сильное взаимодействие координат замедляет сходимость. Возьмём почти ту же функцию, что в примере 1, но с гораздо более сильным перекрёстным членом: $f(x,y) = x^2+y^2+1{,}9xy-3x-3y+4$ (матрица $\begin{pmatrix}2&1{,}9\\1{,}9&2\end{pmatrix}$ всё ещё положительно определена, собственные значения $0{,}1$ и $3{,}9$ — задача сильно плохо обусловлена). Стартуя из $(0,0)$: минимизация по $x$ при $y=0$ даёт $x=1{,}5$ (то же самое, коэффициент при $x^2$ не изменился). Минимизация по $y$ при $x=1{,}5$: $f(1{,}5,y)=y^2+1{,}9\cdot1{,}5y-3y+2{,}25-4{,}5+4=y^2+(2{,}85-3)y+1{,}75=y^2-0{,}15y+1{,}75$, даёт $y=0{,}075$ — заметно меньше, чем $0{,}75$ в примере 1! Сильное взаимодействие координат «тянет» шаг по $y$ в другую сторону сильнее, и сходимость к истинному минимуму (тоже $(1,1)$ по симметрии) занимает заметно больше циклов, хотя каждый отдельный шаг по-прежнему решается точно и аналитически.

Почему это важно

Идея свести многомерную оптимизацию к последовательности одномерных подзадач — это не упрощение ради упрощения, а способ добраться до точного решения там, где полная многомерная задача решения не имеет вообще. Для гладкой квадратичной функции без ограничений можно, конечно, решить систему уравнений $\nabla f = 0$ напрямую — но стоит добавить недифференцируемую $L_1$-регуляризацию, и градиент перестаёт существовать в нуле, а прямое аналитическое решение всей задачи сразу исчезает. Одномерная же подзадача «минимизировать по одной координате при фиксированных остальных с $L_1$-штрафом на эту координату» по-прежнему решается аналитически — именно эту связку ты увидишь дальше, когда одномерное решение окажется в точности операцией soft thresholding из урока 291.

Циклический порядок против случайного выбора координаты

Интуиция

После того как выбор одномерной подзадачи ясен, остаётся вопрос: в каком порядке проходить координаты? Самый очевидный вариант — циклический: сначала координата 1, потом 2, ..., потом $n$, потом снова 1, 2, ... и так до сходимости. Это интуитивно понятный, легко реализуемый порядок, но у него есть скрытая слабость: для некоторых специально устроенных функций именно фиксированный порядок обхода координат может оказаться крайне неудачным — можно искусственно подобрать функцию, на которой один порядок обхода сходится быстро, а другой (переставленный) — катастрофически медленно, хотя по существу решается одна и та же задача.

Случайный покоординатный спуск устраняет эту зависимость от конкретного порядка: на каждой итерации координата для обновления выбирается случайно (обычно равновероятно из всех $n$ координат, независимо от предыдущих выборов). Ключевое теоретическое преимущество, доказанное Нестеровым в 2010 году: гарантии сходимости случайного покоординатного спуска формулируются в ожидании — то есть они не зависят от «неудачного» порядка обхода, потому что порядка как такового просто нет. Ценой за это служит некоторая случайность отдельной траектории (один конкретный запуск алгоритма может пойти чуть иначе, чем другой) и необходимость генерировать случайные числа на каждом шаге — цена обычно ничтожная по сравнению с выигрышем в надёжности.

Формальное определение

Циклический покоординатный спуск. Координаты обновляются в фиксированном порядке $1, 2, \ldots, n, 1, 2, \ldots, n, \ldots$ Один полный проход через все $n$ координат называется циклом (epoch).

Случайный покоординатный спуск. На каждой итерации $k$ координата $i_k$ выбирается случайно (как правило, равновероятно) из множества $\{1, \ldots, n\}$, независимо от истории предыдущих выборов, и обновляется по той же формуле $x_{i_k}^{\text{new}} = \arg\min_{x_{i_k}} f(x)$. Понятие «цикла» здесь размыто — обычно говорят о числе итераций, эквивалентном по вычислительным затратам одному циклу ($n$ итераций).

Примеры

Пример 1: одна и та же функция, два порядка обхода дают разные траектории. Возьмём функцию трёх переменных $g(x_1,x_2,x_3) = x_1^2+x_2^2+x_3^2 - x_1x_2 - x_2x_3 - 2x_1-2x_2-2x_3$. Её минимум достигается в точке $(3, 4, 3)$. Стартуем из $(0,0,0)$.

При циклическом порядке $1,2,3$: минимизация по $x_1$ при $x_2=x_3=0$ даёт $x_1=1$; минимизация по $x_2$ при $x_1=1, x_3=0$ даёт $x_2=1{,}5$; минимизация по $x_3$ при $x_1=1, x_2=1{,}5$ даёт $x_3=1{,}75$. Конец первого цикла: $(1;\ 1{,}5;\ 1{,}75)$.

При случайном порядке, скажем, $3,1,2$ (та же стартовая точка $(0,0,0)$): минимизация по $x_3$ при $x_1=x_2=0$ даёт $x_3=1$; минимизация по $x_1$ при $x_2=0, x_3=1$ даёт $x_1=1$; минимизация по $x_2$ при $x_1=1, x_3=1$ даёт $x_2=2$. Конец того же по счёту количества шагов: $(1;\ 2;\ 1)$.

Точки $(1;\ 1{,}5;\ 1{,}75)$ и $(1;\ 2;\ 1)$ совершенно разные — порядок обхода реально меняет траекторию. Но обе последовательности, если продолжить их дальше, сходятся к одному и тому же истинному минимуму $(3,4,3)$, потому что функция строго выпукла и покоординатный спуск для строго выпуклых гладких функций сходится независимо от порядка обхода координат.

Пример 2: искусственно неудачный циклический порядок. Представь функцию, где координаты организованы в длинную цепочку сильных попарных взаимодействий: $x_1$ сильно связана с $x_2$, та — с $x_3$, и так далее до $x_{100}$, но обход происходит в порядке $1, 2, 3, \ldots, 100$. Информация о том, что изменение $x_{100}$ должно повлиять на $x_1$, доходит до координаты 1 только на следующем цикле — то есть спустя ещё 99 шагов. Если бы порядок обхода был, скажем, случайным образом «перемешивающим» далёкие друг от друга по номеру координаты, обновления, потенциально важные друг для друга, оказывались бы ближе по времени, и информация распространялась бы быстрее. Именно на подобных «цепочечных» структурах зависимости циклический порядок способен искусственно замедлить сходимость на порядки — это и есть тот теоретический сценарий, от которого защищает независимость случайного выбора от структуры конкретной задачи.

Пример 3: одинаковая асимптотика на «дружелюбных» задачах. Для сепарабельной или почти сепарабельной функции вроде Lasso (где взаимодействие между признаками ограничено их взаимной корреляцией, а не жёсткой цепочечной структурой) на практике разница между циклическим и случайным порядком обычно небольшая — оба сходятся за сопоставимое число проходов по данным. Именно поэтому glmnet и scikit-learn по умолчанию используют циклический порядок с редкими случайными перестановками (selection='random' — опция, а не решатель по умолчанию, в sklearn.linear_model.Lasso): для типичной задачи регрессии разница на практике мала, а циклический порядок проще реализовать эффективно на разреженных матрицах.

Почему это важно

Выбор между циклическим и случайным порядком — не абстрактная теоретическая деталь, а конкретный практический параметр, который встречается в реальных библиотеках (тот самый selection='random' в sklearn.linear_model.Lasso). Знание того, что теоретические гарантии случайного покоординатного спуска не зависят от структуры задачи, тогда как циклический порядок может (в специально скроенных, но реальных случаях) оказаться патологически медленным, объясняет, почему на очень больших и структурно необычных задачах разумно попробовать случайный порядок, даже если на «обычных» задачах разница пренебрежимо мала.

Аналитическое решение одномерных подзадач

Интуиция

Самое мощное практическое свойство покоординатного спуска раскрывается именно здесь: для широчайшего класса функций машинного обучения — всех задач наименьших квадратов, гребневой регрессии, Lasso, логистической регрессии с некоторыми оговорками — одномерная подзадача минимизации по одной координате при фиксированных остальных представляет собой минимизацию скалярной квадратичной (или почти квадратичной) функции одной переменной. А минимум скалярной квадратичной функции всегда находится по одной и той же элементарной формуле — приравниванием производной к нулю и делением. Никакого итеративного поиска, никакого line search, никакого подбора шага: одна операция деления на каждую координату.

Формальное определение

Аналитическое решение для квадратичной функции. Пусть $f(x) = \tfrac{1}{2} x^\top A x - b^\top x$, где $A$ — симметричная положительно определённая матрица. Тогда решение одномерной подзадачи по координате $i$ при фиксированных остальных координатах даётся формулой

$$x_i^{\text{new}} = \frac{b_i - \sum_{j \neq i} A_{ij}\, x_j}{A_{ii}}$$

Это в точности классическая итерация метода Гаусса — Зейделя для системы $Ax=b$.

Частный случай: наименьшие квадраты. Для $f(w) = \tfrac{1}{2}\|y - Xw\|_2^2$ с матрицей признаков $X$ (столбцы $X_1, \ldots, X_d$) решение по координате $j$:

$$w_j^{\text{new}} = \frac{X_j^\top r_{-j}}{X_j^\top X_j}, \qquad r_{-j} = y - \sum_{k \neq j} X_k\, w_k$$

где $r_{-j}$ — «частичный остаток»: то, что осталось не объяснённым всеми признаками, кроме $j$-го.

Примеры

Пример 1: проверка формулы Гаусса — Зейделя на уже разобранной функции. Для $f(x,y) = x^2+y^2+xy-3x-3y+4$ из предыдущего раздела матрица имеет вид $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$, $b=(3,3)$. Формула даёт $x = (3-y)/2$ и $y = (3-x)/2$. Подставь $y=0$: $x=(3-0)/2=1{,}5$ — в точности то значение, которое было получено взятием производной вручную в предыдущем разделе. Подставь $x=1{,}5$: $y=(3-1{,}5)/2=0{,}75$ — снова точное совпадение. Формула Гаусса — Зейделя даёт в точности тот же результат, что и явное дифференцирование, но без необходимости каждый раз заново расписывать производную — это чистый механический рецепт.

Пример 2: полный численный шаг для регрессии наименьших квадратов. Пусть есть три наблюдения и два признака: $X_1=(1,0,1)^\top$, $X_2=(0,1,1)^\top$, целевая переменная $y=(2,3,6)^\top$. Стартуем с $w=(0,0)$.

Обновляем $w_1$: полный остаток (поскольку $w_2=0$) равен $r_{-1}=y=(2,3,6)$. Числитель $X_1^\top r_{-1} = 1\cdot2+0\cdot3+1\cdot6=8$. Знаменатель $X_1^\top X_1=1+0+1=2$. Значит $w_1 = 8/2 = 4$. Обновляем веса: $w=(4,0)$.

Обновляем $w_2$: частичный остаток $r_{-2} = y - X_1 w_1 = (2-4,\ 3-0,\ 6-4) = (-2,\ 3,\ 2)$. Числитель $X_2^\top r_{-2}=0\cdot(-2)+1\cdot3+1\cdot2=5$. Знаменатель $X_2^\top X_2=0+1+1=2$. Значит $w_2 = 5/2=2{,}5$. Итог после одного цикла: $w=(4;\ 2{,}5)$ — оба значения получены прямым делением, без единой итерации внутреннего численного метода.

Пример 3: почему аналитическое решение не существует для полной многомерной задачи с $L_1$. Если бы к той же задаче наименьших квадратов добавили штраф $\lambda\|w\|_1$, полная многомерная задача $\min_w \tfrac{1}{2}\|y-Xw\|^2 + \lambda\|w\|_1$ уже не имеет замкнутого аналитического решения — $L_1$-норма недифференцируема в нуле сразу по всем координатам, и решение системы уравнений $\nabla f = 0$ в привычном смысле невозможно. Но если зафиксировать все координаты, кроме $w_j$, одномерная подзадача $\min_{w_j}\ \tfrac12(w_j - z_j)^2\cdot\|X_j\|^2 + \lambda|w_j|$ (где $z_j = X_j^\top r_{-j}/\|X_j\|^2$) — это в точности задача проксимального оператора модуля из урока 291, и у неё есть замкнутое решение — soft thresholding. Это и есть ключевой факт, который делает покоординатный спуск особенно подходящим именно для задач с $L_1$-регуляризацией: недифференцируемость, фатальная для полной многомерной задачи, полностью укрощается, если смотреть на неё по одной координате за раз.

Почему это важно

Аналитическое решение одномерной подзадачи — не просто удобство, а источник фундаментального практического преимущества покоординатного спуска перед градиентными методами: полное отсутствие гиперпараметра скорости обучения. Градиентному спуску и его вариантам всегда нужно подбирать $\alpha$ (или адаптивно его настраивать, как в методах из следующего урока) — слишком большой шаг расходится, слишком маленький сходится мучительно медленно. Покоординатный спуск с аналитическим решением одномерной подзадачи полностью избавлен от этой головной боли: каждый шаг автоматически «идеален» для своей одной координаты, потому что это не приближение, а точное решение.

Связь с проксимальными методами: покоординатный спуск и soft thresholding для Lasso

Интуиция

В прошлом уроке ты увидел проксимальный оператор модуля — soft thresholding: $S(v,\gamma) = \operatorname{sign}(v)\cdot\max(|v|-\gamma,\ 0)$. Он решает задачу $\min_x \tfrac12(x-v)^2+\gamma|x|$ — минимизацию квадратичного «притяжения» к точке $v$ плюс $L_1$-штраф. Присмотрись внимательнее к одномерной подзадаче покоординатного спуска для Lasso из предыдущего раздела: она имеет ровно такую же структуру — квадратичное слагаемое по одной координате плюс штраф $\lambda|w_j|$ на эту же координату. Это не совпадение, а прямое следствие того, что $L_1$-норма сепарабельна: $\|w\|_1 = \sum_j |w_j|$, поэтому, фиксируя все координаты, кроме $w_j$, вся регуляризация Lasso сводится ровно к одному слагаемому $\lambda|w_j|$ — а это и есть в точности задача, для которой существует проксимальный оператор из прошлого урока.

Получается идеальная стыковка двух уроков: покоординатный спуск даёт способ разбить сложную задачу на одномерные куски, а проксимальный оператор из урока 291 даёт точное решение именно такого одномерного куска, когда он содержит недифференцируемый $L_1$-штраф. Вместе эта пара — покоординатный спуск + soft thresholding — и есть тот самый алгоритм, который на практике решает задачу Lasso быстрее почти любой альтернативы.

Формальное определение

Покоординатный спуск для Lasso. Задача: $\min_w\ \tfrac{1}{2}\|y-Xw\|_2^2 + \lambda\|w\|_1$. Обновление координаты $j$:

$$\rho_j = X_j^\top r_{-j}, \qquad r_{-j} = y - \sum_{k \neq j} X_k w_k$$$$w_j^{\text{new}} = \frac{S\bigl(\rho_j,\ \lambda\bigr)}{X_j^\top X_j} = S\!\left(\frac{\rho_j}{X_j^\top X_j},\ \frac{\lambda}{X_j^\top X_j}\right)$$

где $S(v,\gamma)=\operatorname{sign}(v)\max(|v|-\gamma,0)$ — тот же оператор soft thresholding, что и в проксимальном градиентном методе, только применённый к одной координате вместо целого вектора сразу.

Примеры

Пример 1: продолжение примера с регрессией без штрафа — теперь с $L_1$-регуляризацией $\lambda=2$. Возьмём те же данные, что в предыдущем разделе: $X_1=(1,0,1)$, $X_2=(0,1,1)$, $y=(2,3,6)$, старт с $w=(0,0)$. Без штрафа мы получили $\rho_1=8$, $\|X_1\|^2=2$. Теперь применим soft thresholding с $\lambda=2$: $\rho_1/\|X_1\|^2=4$, порог $\lambda/\|X_1\|^2=1$. $S(4,1)=\operatorname{sign}(4)\cdot\max(4-1,0)=3$. Значит $w_1=3$ — заметно меньше, чем $4$ без регуляризации: коэффициент «сжат» к нулю ровно на величину порога.

Теперь обновляем $w_2$ при $w_1=3$: частичный остаток $r_{-2}=y-X_1w_1=(2-3,\ 3-0,\ 6-3)=(-1,\ 3,\ 3)$. $\rho_2=X_2^\top r_{-2}=0\cdot(-1)+1\cdot3+1\cdot3=6$. $\|X_2\|^2=2$, $\rho_2/\|X_2\|^2=3$, порог тот же $1$. $S(3,1)=2$. Итог после цикла с $\lambda=2$: $w=(3;\ 2)$ — оба веса сжаты ровно на единицу относительно нерегуляризованного решения $(4;\ 2{,}5)$.

Пример 2: увеличение $\lambda$ до сепарации коэффициента в ноль. Возьмём те же исходные данные и штраф $\lambda=10$ вместо $2$. Для $w_1$: $\rho_1/\|X_1\|^2=4$ по-прежнему, но порог теперь $\lambda/\|X_1\|^2=10/2=5$. Поскольку $|4| < 5$, soft thresholding даёт $S(4,5)=0$. Признак $w_1$ полностью обнуляется — это и есть механизм отбора признаков Lasso: как только «сигнал» координаты (частичная корреляция с остатком) оказывается слабее порога регуляризации, коэффициент становится ровно нулём, а не просто маленьким числом, как было бы при гребневой ($L_2$) регуляризации.

Пример 3: полный цикл покоординатного спуска для Lasso и его связь с прогонкой пути регуляризации. На практике glmnet и scikit-learn вычисляют не одно значение $\lambda$, а сразу целый «путь» — решают задачу для убывающей последовательности значений $\lambda$ от очень большого (при котором все веса нулевые) до нужного маленького, каждый раз используя решение с предыдущего, чуть большего $\lambda$ как стартовую точку для следующего. Поскольку каждый отдельный шаг покоординатного спуска — это одна операция soft thresholding, а решение с предыдущего $\lambda$ уже близко к оптимальному для следующего, такой «тёплый старт» (warm start) обычно сходится за считаные циклы, а не за сотни итераций с нуля — это и есть источник практической скорости, которая сделала «Pathwise Coordinate Optimization» победителем среди алгоритмов для Lasso.

Почему это важно

Связка покоординатного спуска с soft thresholding — это не просто удачное совпадение формул, а прямая практическая причина, по которой именно этот алгоритм, а не проксимальный градиентный спуск целиком по всем координатам сразу, стал стандартом для Lasso и Elastic Net. Проксимальный градиентный шаг из урока 291 применяет soft thresholding ко всему вектору сразу, но перед этим ему всё равно нужен градиентный шаг по гладкой части — а значит, нужен подобранный шаг $\alpha \le 1/L$. Покоординатный вариант вообще не нуждается в оценке константы Липшица градиента: каждая координата решается точно, аналитически, без всякого шага. Именно поэтому вызов Lasso(solver='cd') в scikit-learn (это и есть значение по умолчанию) обычно быстрее, чем эквивалентная реализация через проксимальный градиентный спуск целиком по вектору.

Условия сходимости и стоимость одной итерации

Интуиция

Покоординатный спуск — не универсальное решение для абсолютно любой задачи оптимизации. Ключевое условие, о котором говорит теорема Цзэна (2001), — сепарабельность негладкой части целевой функции. Если недифференцируемое слагаемое раскладывается в сумму функций от отдельных координат ($h(x) = \sum_i h_i(x_i)$, как у $L_1$-нормы), покоординатный спуск гарантированно сходится. Но если недифференцируемое слагаемое не раскладывается так — если оно жёстко связывает несколько координат вместе, — гарантии сходимости пропадают, и покоординатный спуск способен застрять в точке, вообще не являющейся минимумом.

Формальное определение

Условие сходимости (Цзэн, 2001). Пусть $f(x) = g(x) + h(x)$, где $g$ дифференцируема, а $h(x) = \sum_{i=1}^n h_i(x_i)$ — сепарабельная (покоординатно раскладывающаяся) сумма, каждое $h_i$ выпукло (возможно, недифференцируемо). Тогда циклический покоординатный спуск сходится к точке, в которой ни один координатный шаг не может улучшить функцию (координатному минимуму), и эта точка совпадает с глобальным минимумом $f$, если $g$ выпукла.

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

Примеры

Пример 1: почему Lasso — «дружелюбный» случай. Для Lasso $h(w) = \lambda\|w\|_1 = \lambda\sum_j |w_j|$ — сумма функций одной переменной каждая. Условие теоремы Цзэна выполнено идеально: гладкая часть $g(w)=\tfrac12\|y-Xw\|^2$ выпукла, негладкая часть сепарабельна. Именно поэтому покоординатный спуск для Lasso не просто сходится «на практике», а имеет строгое математическое доказательство сходимости к глобальному минимуму.

Пример 2: явный контрпример на негладкой несепарабельной функции. Рассмотрим $f(x,y) = |x-1| + |y-1| + 2|x-y|$. Слагаемое $2|x-y|$ недифференцируемо и одновременно зависит от обеих координат — оно не сепарабельно. Проверим поведение покоординатного спуска из точки $(0,0)$. Минимизация по $x$ при $y=0$: $f(x,0)=|x-1|+1+2|x|$. Прямая проверка нескольких точек: $f(0,0)=1+1+0=2$; $f(0{,}1,0)=0{,}9+1+0{,}2=2{,}1$; $f(-0{,}1,0)=1{,}1+1+0{,}2=2{,}3$. Значение в обе стороны от $x=0$ растёт — значит, $x=0$ уже является точным минимумом при $y=0$ зафиксированном. По симметрии то же самое верно и для минимизации по $y$ при $x=0$: $y=0$ тоже оптимальна. Точка $(0,0)$ — координатный минимум: ни один координатный шаг не может её улучшить, и алгоритм застревает в ней навсегда, выдавая значение $f(0,0)=2$.

Но истинный глобальный минимум находится в точке $(1,1)$: там все три слагаемых обращаются в ноль одновременно ($|1-1|=0$, $|1-1|=0$, $2|1-1|=0$), и $f(1,1)=0$ — значение вчетверо меньше, чем «застрявшее» $f(0,0)=2$! Чтобы добраться из $(0,0)$ в $(1,1)$, нужно сдвинуться одновременно по обеим координатам по диагонали — а покоординатный спуск умеет двигаться только вдоль осей и потому эту диагональ никогда не находит.

Пример 3: почему этот же контрпример не работает для Lasso. Замени слагаемое $2|x-y|$ на сепарабельное $2|x|+2|y|$: $\tilde f(x,y)=|x-1|+|y-1|+2|x|+2|y|$. Минимизация по $x$ при $y=0$: $\tilde f(x,0)=|x-1|+1+2|x|$ — та же самая одномерная подзадача, что уже решалась в уроке (раздел про Lasso) — даёт $x=0$ при достаточно большом коэффициенте перед $|x|$, но минимум этой функции по $x$, если проверить производные слева и справа от единицы, на самом деле сдвигается в сторону $x=1$ при подходящем соотношении коэффициентов, и, что важнее, при сепарабельной структуре не существует «ловушки», аналогичной примеру 2 — оптимум по каждой координате достигается независимо, и не требуется диагональное движение, чтобы их совместить.

Стоимость одной итерации по сравнению с полным градиентным шагом

Для задачи наименьших квадратов с $N$ наблюдениями и $d$ признаками полный градиентный шаг требует вычислить $\nabla f = X^\top(Xw - y)$ целиком — это $O(Nd)$ операций (умножение матрицы на вектор дважды). Один координатный шаг покоординатного спуска трогает только один столбец $X_j$ и требует $O(N)$ операций (одно скалярное произведение $X_j^\top r_{-j}$). Но чтобы пройти все $d$ координат (один полный цикл), нужно $O(Nd)$ операций — тот же порядок, что и один полный градиентный шаг.

Формально порядок сложности одинаков, но константа и практическое поведение сильно различаются: покоординатный спуск за счёт эффекта Гаусса — Зейделя (использования уже обновлённых значений внутри одного и того же прохода) и полного отсутствия необходимости подбирать шаг на практике часто сходится за меньшее число полных проходов по данным, чем градиентный спуск — за меньшее число проходов.

Почему это важно

Понимание точных условий сходимости — не теоретическая роскошь, а прямой практический ориентир: перед тем как применить покоординатный спуск к новой задаче, стоит спросить себя, раскладывается ли недифференцируемая часть целевой функции по координатам. Для подавляющего большинства задач регуляризованной линейной и логистической регрессии (Lasso, Elastic Net, регуляризация по группам признаков с раздельными штрафами) ответ положительный, и покоординатный спуск — отличный, часто наилучший выбор. Но для задач, где негладкость жёстко связывает несколько переменных сразу (например, штрафы на разности соседних коэффициентов, как в fused Lasso, или некоторые задачи с ограничениями на ранг матрицы без предварительного разложения), нужно либо переформулировать задачу, либо использовать проксимальные или ADMM-подобные методы, устойчивые к несепарабельности.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Для $f(x,y)=x^2+y^2+xy-3x-3y+4$ зафиксируй $y=0$ и найди оптимальное $x$ (реши одномерную подзадачу через производную).

Задание 2: Продолжая задание 1, зафиксируй $x=1{,}5$ и найди оптимальное $y$.

Задание 3: Вычисли значение $f(1{,}5;\ 0{,}75)$ для той же функции.

Задание 4: Дана матрица $A=\begin{pmatrix}2&1\\1&2\end{pmatrix}$ и вектор $b=(3,3)$. По формуле $x_i=(b_i-\sum_{j\neq i}A_{ij}x_j)/A_{ii}$ найди $x_1$, если $x_2=4$.

Задание 5: Объясни своими словами разницу между обновлением в стиле Гаусса — Зейделя (используются уже обновлённые в этом же цикле координаты) и в стиле Якоби (используются только значения из начала цикла).

Задание 6: Даны $X_1=(1,0,1)$, $X_2=(0,1,1)$, $y=(2,3,6)$, текущее $w_2=0$. Вычисли $w_1$ по формуле наименьших квадратов $w_j=X_j^\top r_{-j}/X_j^\top X_j$.

Задание 7: Продолжая задание 6, при $w_1=4$ вычисли $w_2$.

Задание 8: Вычисли $S(4, 1)$ — значение оператора soft thresholding.

Задание 9: Вычисли $S(3, 5)$.

Задание 10: Объясни, почему одномерная подзадача покоординатного спуска для задачи наименьших квадратов всегда имеет аналитическое решение, тогда как полная многомерная задача с $L_1$-штрафом такого решения не имеет.

Продвинутые задания (11–20)

Задание 11: Выведи формулу $x_i=(b_i-\sum_{j\neq i}A_{ij}x_j)/A_{ii}$, взяв частную производную $f(x)=\tfrac12x^\top Ax - b^\top x$ по $x_i$ и приравняв её к нулю.

Задание 12: Для $g(x_1,x_2,x_3)=x_1^2+x_2^2+x_3^2-x_1x_2-x_2x_3-2x_1-2x_2-2x_3$ (минимум в точке $(3,4,3)$), начиная с $(0,0,0)$ и циклического порядка $1,2,3$, вычисли $x_1$ после первого шага.

Задание 13: Продолжая задание 12, при $x_1=1, x_3=0$ вычисли $x_2$.

Задание 14: Продолжая задания 12–13, при $x_1=1, x_2=1{,}5$ вычисли $x_3$.

Задание 15: Для той же функции $g$ при случайном порядке $3,1,2$ из той же стартовой точки $(0,0,0)$ конечная точка после трёх шагов оказалась $(1;\ 2;\ 1)$ — не такой, как в циклическом порядке. Объясни, почему это не противоречие и почему обе траектории в итоге сойдутся к одному и тому же минимуму $(3,4,3)$.

Задание 16: Даны $\rho_1=8$, $\|X_1\|^2=2$, $\lambda=2$. Вычисли обновление $w_1$ для Lasso по формуле $w_1=S(\rho_1/\|X_1\|^2,\ \lambda/\|X_1\|^2)$.

Задание 17: С теми же $\rho_1=8$, $\|X_1\|^2=2$, но $\lambda=10$, вычисли $w_1$.

Задание 18: Объясни, почему координатному шагу покоординатного спуска для Lasso не нужен параметр скорости обучения, тогда как проксимальному градиентному шагу (урок 291) для той же задачи нужен подобранный шаг $\alpha \le 1/L$.

Задание 19: Для функции $f(x,y)=|x-1|+2|x|+1$ (значение $y=0$ фиксировано) проверь, что $x=0$ действительно локально оптимальна, сравнив значения $f$ при $x=0$, $x=0{,}1$ и $x=-0{,}1$.

Задание 20: Для функции $f(x,y)=|x-1|+|y-1|+2|x-y|$ вычисли $f(1,1)$ и сравни его с застрявшим значением $f(0,0)=2$ из урока.

Задания-челленджи (21–30)

Задание 21: Объясни, почему штраф вида $\lambda|w_1-w_2|$ (штраф на разность двух коэффициентов, как в fused Lasso) не является сепарабельным, и почему это означает, что для него нельзя написать покоординатный шаг в виде простого soft thresholding одной координаты независимо от значения другой.

Задание 22: Для задачи наименьших квадратов с $N=10^5$ наблюдениями и $d=200$ признаками оцени порядок числа операций (а) одного полного градиентного шага и (б) одного полного цикла покоординатного спуска. Сделай вывод о том, совпадает ли их асимптотический порядок.

Задание 23: Объясни, почему обновление в стиле Гаусса — Зейделя (используются уже обновлённые в этом же цикле координаты) обычно сходится быстрее по числу циклов, чем обновление в стиле Якоби (используются только значения с начала цикла), хотя оба технически являются покоординатными методами.

Задание 24: Опиши, какую гарантию сходимости дал Нестеров (2010) для случайного покоординатного спуска, и почему эта гарантия защищает от патологически медленной сходимости, возможной у циклического порядка на специально скроенных функциях.

Задание 25: Опиши качественно, почему покоординатный спуск на плохо обусловленной задаче (например, признаки сильно скоррелированы) обычно менее чувствителен к разнице масштабов между направлениями, чем градиентный спуск с единым шагом $\alpha$ для всех координат сразу.

Задание 26: Объясни, почему в scikit-learn для Lasso и ElasticNet решателем по умолчанию является покоординатный спуск (solver='cd'), а не проксимальный градиентный спуск целиком по вектору весов.

Задание 27: Опиши, как обобщается идея покоординатного спуска до блочного покоординатного спуска (block coordinate descent), и почему это естественно применимо в независимом компонентном анализе (ICA) или факторных моделях, где параметры разбиваются на смысловые группы.

Задание 28: Обобщи в двух-трёх предложениях: чем принципиально отличается информация, которую использует покоординатный спуск, от той, которую использует полный градиентный спуск (урок 285) и проксимальный градиентный спуск (урок 291) для той же самой регуляризованной задачи.

Задание 29: Для контрпримера $f(x,y)=|x-1|+|y-1|+2|x-y|$ объясни, почему такая ловушка была бы невозможна, если бы вместо слагаемого $2|x-y|$ стоял сепарабельный штраф $2|x|+2|y|$, опираясь на условие теоремы Цзэна.

Задание 30: Следующий урок курса посвящён Adam и адаптивным методам, которые тоже в каком-то смысле «покоординатны» — они подстраивают эффективную скорость обучения отдельно для каждой координаты веса. Объясни в двух-трёх предложениях принципиальное отличие этого подхода от покоординатного спуска этого урока.

Частые ошибки

Ошибка 1. Считают, что покоординатный спуск и градиентный спуск — это, по сути, один и тот же метод, только применённый по-разному.

Как выглядит: «покоординатный спуск — это просто градиентный спуск, но по одной координате».

Почему возникает: оба метода последовательно улучшают текущую точку, и слово «спуск» в названии создаёт ложное впечатление родственности механизма.

Как правильно: градиентный шаг по одной координате был бы приближённым (маленький сдвиг против частной производной с подобранной длиной шага), тогда как покоординатный спуск решает одномерную подзадачу точно и полностью — это качественно другая операция, не имеющая параметра «шаг» в привычном смысле.

Ошибка 2. Применяют покоординатный спуск к задаче с несепарабельной негладкой частью, ожидая тех же гарантий сходимости, что и для Lasso.

Как выглядит: «раз покоординатный спуск отлично работает для Lasso, значит, он справится с любым негладким штрафом, лишь бы функция была выпуклой».

Почему возникает: теорема Цзэна и её условие сепарабельности негладкой части редко проговариваются явно, а на выпуклых сепарабельных примерах метод действительно работает безотказно.

Как правильно: всегда нужно проверять, раскладывается ли недифференцируемая часть целевой функции в сумму функций от отдельных координат; если нет (штрафы, связывающие несколько переменных сразу, вроде $|w_1-w_2|$), гарантии сходимости пропадают, и метод может застрять в неоптимальной точке.

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

Как выглядит: реализация, где вместо точного аналитического (или точного численного) решения одномерной подзадачи делается один шаг по производной с произвольной длиной.

Почему возникает: внешне такой «однокоординатный градиентный шаг» тоже выглядит как движение вдоль одной оси, и разница кажется несущественной.

Как правильно: ключевое преимущество покоординатного спуска — именно точное решение одномерной подзадачи; урезанная версия с приближённым шагом теряет главное практическое достоинство метода (отсутствие параметра скорости обучения) и часто сходится заметно медленнее.

Ошибка 4. Считают, что циклический порядок обхода координат всегда надёжнее случайного, потому что он детерминирован и предсказуем.

Как выглядит: «зачем добавлять случайность, если можно просто идти по порядку 1, 2, 3, ...».

Почему возникает: детерминированность интуитивно ассоциируется с надёжностью, а случайность — с непредсказуемостью и риском.

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

Ошибка 5. Игнорируют «эффект Гаусса — Зейделя» и реализуют покоординатный спуск в стиле Якоби, обновляя все координаты одновременно на основе значений с начала цикла.

Как выглядит: параллельная реализация, где сначала считаются все новые значения координат по старым данным, а обновление происходит только в конце прохода.

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

Как правильно: стиль Гаусса — Зейделя (использование уже обновлённых координат внутри того же прохода), как правило, сходится быстрее по числу проходов, потому что информация о новых значениях распространяется мгновенно внутри одного цикла, а не с задержкой в целый проход, как в стиле Якоби.

Ошибка 6. Забывают, что при добавлении $L_1$-регуляризации знаменатель в формуле покоординатного шага ($X_j^\top X_j$) нужно использовать при вычислении и числителя, и порога soft thresholding.

Как выглядит: применение soft thresholding напрямую к $\rho_j = X_j^\top r_{-j}$ с порогом $\lambda$, без деления обеих величин на $X_j^\top X_j$.

Почему возникает: формула soft thresholding для «чистого» проксимального оператора модуля из урока 291 не содержит этого масштабирующего множителя, и легко забыть, что здесь он появляется из-за квадратичного слагаемого регрессии.

Как правильно: корректная формула — $w_j = S(\rho_j/\|X_j\|^2,\ \lambda/\|X_j\|^2)$, где и числитель, и порог масштабируются одним и тем же $\|X_j\|^2$; пропуск этого масштабирования даёт неверный, слишком слабый или слишком сильный уровень регуляризации для признаков с разным масштабом.

Главное запомнить

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

• Циклический порядок обхода координат ($1,2,\ldots,n,1,2,\ldots$) прост и на практике почти всегда работает хорошо, но теоретически может оказаться патологически медленным на специально скроенных задачах; случайный порядок (Нестеров, 2010) даёт гарантии сходимости в ожидании, не зависящие от конкретной структуры задачи.

• Для широкого класса функций (квадратичные функции, наименьшие квадраты, Lasso) одномерная подзадача покоординатного спуска имеет аналитическое решение — формула Гаусса — Зейделя $x_i=(b_i-\sum_{j\neq i}A_{ij}x_j)/A_{ii}$ для гладких квадратичных задач и soft thresholding для задач с $L_1$-регуляризацией.

• Именно потому, что $L_1$-норма сепарабельна ($\|w\|_1=\sum_j|w_j|$), одномерная подзадача покоординатного спуска для Lasso сводится к проксимальному оператору модуля из урока 291 — покоординатный спуск и soft thresholding вместе и есть тот самый алгоритм, который реально работает под капотом у sklearn.linear_model.Lasso.

• Аналитическое решение каждого координатного шага означает, что покоординатному спуску не нужен параметр скорости обучения — в отличие от градиентного и проксимального градиентного методов, где выбор шага критичен для сходимости.

• Теорема Цзэна (2001) гарантирует сходимость циклического покоординатного спуска к глобальному минимуму, если негладкая часть целевой функции сепарабельна; для несепарабельных негладких задач (штрафы, связывающие несколько переменных сразу) такой гарантии нет, и метод может застрять в точке, не являющейся минимумом, — классический контрпример подобного рода построил Пауэлл ещё в 1973 году.

• Формально стоимость одного полного цикла покоординатного спуска и одного полного градиентного шага имеет один и тот же порядок $O(Nd)$ для задачи наименьших квадратов с $N$ наблюдениями и $d$ признаками, но покоординатный спуск часто выигрывает на практике за счёт эффекта Гаусса — Зейделя и отсутствия необходимости подбирать шаг.

• Формула покоординатного шага для квадратичных функций математически идентична итерации Гаусса — Зейделя для решения систем линейных уравнений — методу, придуманному ещё в XIX веке для совершенно других задач.

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

• Выбор между покоординатным спуском, проксимальным градиентным методом и полным градиентным спуском — это осознанное решение, зависящее от того, раскладывается ли негладкая часть задачи по координатам, насколько признаки коррелированы между собой и насколько важна независимость от подбора гиперпараметра шага.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается на прошлый урок 291 про проксимальные методы: без понимания того, что такое проксимальный оператор и откуда берётся формула soft thresholding $S(v,\gamma)=\operatorname{sign}(v)\max(|v|-\gamma,0)$, связь между покоординатным спуском и Lasso осталась бы просто набором формул без интуиции. Также пригодился урок 290 про субградиентные методы — понимание того, почему $L_1$-норма недифференцируема в нуле и как с этим обращаться, помогает увидеть, зачем вообще нужен покоординатный подход там, где полный градиент не существует.

Что изучить дальше

Следующий урок 293 разбирает Adam и адаптивные методы — семейство алгоритмов, которое тоже придаёт особое значение отдельным координатам, но совершенно иначе: вместо точного последовательного решения одномерных подзадач Adam подстраивает эффективную скорость обучения для каждой координаты на основе накопленной статистики о величине и дисперсии предыдущих градиентов, делая шаг сразу по всем координатам одновременно. Сравнение этих двух принципиально разных способов быть «внимательным к каждой координате» — точное последовательное решение против приближённой одновременной адаптации шага — полезная рамка для понимания всего спектра методов оптимизации, изученных в этой части курса.

Где это нужно в жизни

📊 Классическое машинное обучение. Решатель cd (coordinate descent) — вариант по умолчанию для Lasso и ElasticNet в scikit-learn, а сам алгоритм пришёл в индустрию через R-пакет glmnet, который десятилетиями остаётся стандартом статистического инструментария для регуляризованной линейной и логистической регрессии.

🎯 Support Vector Machines. Алгоритм SMO (Sequential Minimal Optimization), лежащий в основе одной из самых популярных библиотек libsvm, — по сути, блочный покоординатный спуск с блоком из двух переменных за раз, выбираемых так, чтобы гарантировать возможность аналитического решения возникающей подзадачи при ограничениях SVM.

🎬 Рекомендательные системы. Классические методы матричной факторизации для коллаборативной фильтрации (например, некоторые победители Netflix Prize) оптимизируют функцию потерь поочерёдно по матрице пользователей и по матрице фильмов, фиксируя одну из них, — это блочный покоординатный спуск в чистом виде, часто называемый Alternating Least Squares (ALS).

🧠 Независимый компонентный анализ и факторные модели. В ICA и некоторых схемах обучения факторных моделей параметры естественно разбиваются на блоки, отвечающие за отдельные компоненты, и пошаговая оптимизация по одному блоку при фиксированных остальных — прямое расширение идеи покоординатного спуска, разобранной в этом уроке, до оптимизации целыми группами параметров.

Интересные факты

• Формула, которую покоординатный спуск использует для квадратичных функций, была независимо переоткрыта спустя почти полтора века после того, как Филипп Людвиг фон Зейдель формально опубликовал её в 1874 году для решения систем линейных уравнений в задачах астрономических вычислений методом наименьших квадратов — контекст совершенно другой, а формула буквально та же самая.

• Классический контрпример, показывающий, что циклический покоординатный спуск может застрять в неоптимальной точке на негладких несепарабельных функциях, построил в 1973 году Майкл Пауэлл — тот же самый исследователь, чьи инициалы входят в название формулы DFP из прошлого урока про квазиньютоновские методы.

• Работа Фридмана, Хасти, Хёфлинга и Тибширани 2007 года «Pathwise Coordinate Optimization», показавшая, насколько быстрее покоординатный спуск решает задачу Lasso по сравнению с ранее считавшимся стандартным методом LARS, легла в основу R-пакета glmnet, который остаётся одним из самых используемых статистических инструментов для регуляризованной регрессии по сей день, спустя почти два десятилетия.

• Алгоритм SMO для обучения SVM, придуманный Джоном Платтом в 1998 году, специально выбирает блок ровно из двух переменных за раз (а не одной) — потому что ограничение $\sum_i \alpha_i y_i = 0$ в двойственной задаче SVM делает изменение одной переменной в одиночку невозможным без нарушения ограничения, и минимальный блок, для которого подзадача всё ещё решается аналитически, оказывается размером именно в две координаты.

Лайфхаки

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

• Перед обучением Lasso или Elastic Net через покоординатный спуск стандартизируй признаки (нулевое среднее, единичная дисперсия): формула soft thresholding напрямую зависит от масштаба $X_j^\top X_j$, и без стандартизации признаки с большим естественным масштабом будут регуляризованы слабее признаков с малым масштабом при одном и том же $\lambda$.

• Если нужно решить задачу Lasso сразу для нескольких значений $\lambda$, используй «тёплый старт» — начинай оптимизацию для следующего (меньшего) значения $\lambda$ с решения, полученного для предыдущего (большего) значения, а не с нуля: обычно это сокращает число циклов до сходимости в разы, именно так работает построение всего пути регуляризации в glmnet и scikit-learn.

• При реализации покоординатного спуска вручную всегда используй стиль Гаусса — Зейделя (обновляй координаты «на месте», сразу используя новые значения для последующих координат того же цикла), а не стиль Якоби с одновременным обновлением всех координат по старым значениям — разница в скорости сходимости по числу циклов может быть заметной.

• Если задача содержит штрафы, связывающие несколько переменных одновременно недифференцируемым образом (например, штрафы на разности соседних коэффициентов, как в fused Lasso, или задачи с общими ограничениями на группу коэффициентов), не применяй наивный покомпонентный покоординатный спуск без проверки — теоретические гарантии сходимости пропадают, и стоит присмотреться к проксимальным методам над целыми блоками переменных или ADMM.

• Если данные разрежены (много нулей в матрице признаков, типично для текстовых или категориальных данных с one-hot кодированием), покоординатный спуск особенно выигрышен: каждая координата естественно обходится только по ненулевым значениям своего столбца, тогда как полный градиентный шаг требует прохода по всей плотной или разреженной матрице сразу — этим и объясняется популярность решателя cd именно для задач с большим числом разреженных признаков.

Ты прошёл путь от идеи «а что, если оптимизировать не по всем координатам сразу, а по одной за раз» до конкретной формулы, которая при вызове Lasso().fit() реально запускается миллионы раз в день в продакшене по всему миру. По дороге ты увидел, как метод почти полуторавековой давности, придуманный для совершенно других задач — решения линейных систем в астрономических вычислениях, — оказался ровно тем инструментом, который нужен для одной из самых практичных задач современного машинного обучения: отбора признаков через $L_1$-регуляризацию. Ты также увидел честную границу метода: покоординатный спуск не универсален, и там, где переменные переплетены недифференцируемым образом, он способен застрять в точке, весьма далёкой от истинного минимума. Умение видеть эту границу — понимать, сепарабельна задача или нет, прежде чем выбирать между покоординатным спуском, проксимальным градиентным методом или чем-то ещё, — и есть та зрелость в оптимизации, которую этот урок должен был тебе дать. В следующем уроке ты увидишь Adam — метод, который тоже уделяет отдельное внимание каждой координате, но действует совершенно иначе, и сравнение этих двух подходов ещё раз покажет, насколько богат и разнообразен арсенал приёмов, стоящих за одной короткой фразой «оптимизировать функцию».