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

🎯 Зачем это нужно?

Представь, что ты настраиваешь алгоритм рекомендаций в TikTok 📱. У тебя есть функция потерь от миллиона параметров, и считать полный градиент по всем сразу - это как пытаться оптимизировать работу всего завода одновременно. Слишком сложно!

💡 Идея покоординатного спуска: давайте оптимизировать по одной переменной за раз, зафиксировав остальные. Как настройка гитары - крутим один колок, потом другой.

🌍 Где применяется:

• LASSO регрессия: 90% реализаций используют coordinate descent
• SVM: libsvm (самая популярная библиотека) внутри использует SMO - вариант coordinate descent
• Матричная факторизация: Netflix Prize победители применяли именно этот подход

📚 История вопроса

В 1951 году Gauss-Seidel предложил итеративный метод для систем уравнений. Но настоящий бум coordinate descent’а начался в 2000-х с развитием ML. В 2007 году Stephen Boyd показал, что для многих ML-задач этот метод работает даже быстрее обычного градиентного спуска!

🎖️ Интересный факт: алгоритм Expectation-Maximization (EM), который лежит в основе многих unsupervised методов, - это тоже разновидность coordinate descent’а!

💡 Интуиция

Обычный градиентный спуск - это как идти в гору, ориентируясь по компасу, который показывает направление наискорейшего подъёма. Но что если компас сломался или его показания слишком сложно вычислить?

[МЕДИА: image_01] Описание: 3D визуализация функции с траекториями обычного градиентного спуска (плавная кривая) и покоординатного спуска (ступенчатая траектория) Промпт: “3D mathematical surface plot showing optimization paths, smooth curved path for gradient descent in blue, step-like zigzag path for coordinate descent in red, modern scientific visualization style, clean white background”

🤔 Покоординатный спуск говорит: “А давай просто будем двигаться по одной оси за раз!”

Зафиксировали все переменные кроме x₁ - оптимизируем только по ней. Потом зафиксировали все кроме x₂ - оптимизируем по ней. И так далее.

Плюсы: ✅ Каждый шаг = решение простой одномерной задачи ✅ Не нужно вычислять полный градиент ✅ Часто можно найти аналитическое решение для каждой координаты

Минусы: ❌ Может медленно сходиться на некоторых функциях ❌ Не всегда находит глобальный минимум

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

Задача: минимизировать f(x₁, x₂, …, xₙ)

Алгоритм покоординатного спуска:

На итерации k:

1. Выбираем координату i (циклически или случайно)
2. Фиксируем все xⱼ при j ≠ i
3. Решаем одномерную задачу: xᵢ⁽ᵏ⁺¹⁾ = argmin f(x₁⁽ᵏ⁾, …, xᵢ₋₁⁽ᵏ⁾, xᵢ, xᵢ₊₁⁽ᵏ⁾, …, xₙ⁽ᵏ⁾)

Варианты:

• Циклический: i = 1, 2, …, n, 1, 2, …
• Случайный: i выбираем случайно на каждой итерации
• Greedy: выбираем i с наибольшим градиентом

🔍 Примеры с разбором

Пример 1: Квадратичная функция

f(x₁, x₂) = x₁² + 4x₂² + 2x₁x₂ - 6x₁ - 8x₂

Начальная точка: (0, 0)

[МЕДИА: image_02] Описание: Контурный график квадратичной функции с пошаговой траекторией покоординатного спуска Промпт: “contour plot of quadratic function, step-by-step coordinate descent path marked with numbered points and arrows, mathematical visualization, educational style, blue and red color scheme”

Итерация 1: Оптимизируем по x₁, зафиксировав x₂ = 0 f(x₁, 0) = x₁² - 6x₁ ∂f/∂x₁ = 2x₁ - 6 = 0 → x₁ = 3

Итерация 2: Оптимизируем по x₂, зафиксировав x₁ = 3
f(3, x₂) = 9 + 4x₂² + 6x₂ - 18 - 8x₂ = 4x₂² - 2x₂ - 9 ∂f/∂x₂ = 8x₂ - 2 = 0 → x₂ = 1/4

Итерация 3: Снова по x₁ при x₂ = 1/4 f(x₁, 1/4) = x₁² + x₁/2 - 6x₁ + const ∂f/∂x₁ = 2x₁ + 1/2 - 6 = 0 → x₁ = 11/4

И так далее до сходимости…

Пример 2: LASSO регрессия

Задача: min ||Ax - b||² + λ||x||₁

Для каждой координаты xⱼ получаем задачу soft thresholding:

xⱼ⁽ᵏ⁺¹⁾ = soft_threshold(zⱼ, λ/||Aⱼ||²)

где zⱼ = (Aⱼᵀ(b - A₋ⱼx₋ⱼ))/||Aⱼ||²

def coordinate_descent_lasso(A, b, lam, max_iter=1000):
    n_features = A.shape[1]
    x = np.zeros(n_features)
    
    for iteration in range(max_iter):
        for j in range(n_features):
            # Вычисляем остаток без j-той переменной
            residual = b - A @ x + A[:, j] * x[j]
            
            # Обновляем j-тую координату
            rho = A[:, j] @ residual
            x[j] = soft_threshold(rho, lam) / (A[:, j] @ A[:, j])
            
    return x

def soft_threshold(z, gamma):
    return np.sign(z) * max(0, abs(z) - gamma)

🎮 Практика

Базовый уровень 🟢

Задача 1: Примени одну итерацию покоординатного спуска к функции f(x, y) = x² + 2y² - 4x - 6y из точки (0, 0).

Задача 2: Объясни, почему для функции f(x, y) = x² + y² покоординатный спуск сойдётся за одну итерацию?

Задача 3: Напиши псевдокод циклического покоординатного спуска для функции n переменных.

Задача 4: Что произойдёт, если применить coordinate descent к функции f(x, y) = xy? Сойдётся ли алгоритм?

Продвинутый уровень 🟡

Задача 5: Реализуй coordinate descent для Ridge регрессии: min ||Ax - b||² + λ||x||²

Задача 6: Докажи, что для сепарабельной функции f(x) = f₁(x₁) + f₂(x₂) + … + fₙ(xₙ) покоординатный спуск найдёт точный минимум за одну итерацию по всем координатам.

Задача 7: Сравни скорость сходимости coordinate descent и gradient descent на функции f(x, y) = αx² + y² при α » 1.

Задача 8: Предложи эвристику для выбора координаты в “умном” coordinate descent (не циклическом и не случайном).

Челлендж 🔴

Задача 9: Реализуй coordinate descent для Elastic Net: min ||Ax - b||² + λ₁||x||₁ + λ₂||x||²

Задача 10: Исследуй поведение случайного coordinate descent на функции Розенброка. При каких параметрах он сходится?

Задача 11: Примени Block Coordinate Descent для матричной факторизации V ≈ WH, где нужно минимизировать ||V - WH||²_F.

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

❌ Ошибка: Применяют coordinate descent к функциям с сильной зависимостью между переменными ✅ Правильно: Сначала анализируют структуру функции - есть ли cross-terms 💡 Почему: На функции f(x,y) = (x-y)² coordinate descent может ходить зигзагами очень долго

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

❌ Ошибка: Не проверяют выпуклость функции ✅ Правильно: Coordinate descent гарантированно работает только для выпуклых функций 💡 Почему: Для невыпуклых может застрять в локальном минимуме

❌ Ошибка: Используют слишком маленький шаг при line search внутри каждой координаты ✅ Правильно: Для многих задач ML можно найти точное решение одномерной подзадачи 💡 Почему: Зачем делать приближение, если можно найти точное решение?

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

✅ Покоординатный спуск = оптимизация по одной переменной за раз ✅ Ключевая идея: превращаем сложную многомерную задачу в последовательность простых одномерных ✅ Применяется в LASSO, SVM, матричных разложениях и многих других ML-алгоритмах

🔗 Связь с другими темами

Назад: Опирается на градиентный спуск (урок 291) - это его “ленивая” версия Вперёд: Приведёт к изучению Block Coordinate Descent, Proximal методов и ADMM Связи: Тесно связан с методом Gauss-Seidel из численных методов и EM-алгоритмом из статистики