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

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

Представь, что ты настраиваешь рекомендательную систему Netflix 🎬. У тебя есть матрица “пользователь × фильм” с оценками, но она заполнена только на 1%! Остальные 99% — пропуски. Обычный градиентный спуск здесь буксует, потому что функция потерь не везде дифференцируема.

Где используются проксимальные методы: 💡 LASSO регрессия — отбор важных признаков в ML моделях 🖼️ Деноизинг изображений — удаление шума, сохраняя резкие границы
📊 Матричное восстановление — Netflix, Spotify для рекомендаций 🧠 Обучение нейросетей — sparse weights, pruning моделей

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

В 1960-х Роберт Тибширани работал над проблемой отбора признаков в статистике. Классические методы либо включали ВСЕ переменные, либо работали очень медленно. Он придумал L1-регуляризацию (LASSO), но как её оптимизировать?

В 1970-х Моро создал теорию проксимальных операторов. Но только в 2000-х эти идеи объединились! Оказалось, что многие “необучаемые” функции можно оптимизировать, если разбить их на гладкую + негладкую части.

💡 Интуиция

Основная идея: Что если у нас есть функция f(x) = g(x) + h(x), где:

• g(x) — гладкая (есть градиент) — например, MSE loss
• h(x) — негладкая (нет градиента) — например, L1-регуляризация

Обычный градиентный спуск: x ← x - α∇f(x) — не работает, если ∇h не существует!

Проксимальный подход: Делаем шаг по градиенту g, а потом “проксимальный шаг” для h:

1️⃣ Gradient step: y = x - α∇g(x)
2️⃣ Proximal step: x = prox_{αh}(y)

Проксимальный оператор prox_h(y) = argmin_x {½||x-y||² + h(x)}

Это как “притягивание” к точке y с учётом штрафа h(x)!

[МЕДИА: image_01] Описание: Визуализация проксимального шага как компромисс между близостью к градиентному шагу и минимизацией негладкой функции Промпт: “mathematical illustration showing proximal step as balance between gradient descent direction and non-smooth penalty function, 3D surface plot, blue gradient arrows, red proximal operator, educational visualization, clean modern style”

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

Проксимальный оператор функции h с параметром λ > 0:

prox_{λh}(v) = argmin_x {½||x - v||² + λh(x)}

Проксимальный градиентный алгоритм: Для f(x) = g(x) + h(x), где g гладкая, h выпуклая:

x^{k+1} = prox_{α_k h}(x^k - α_k ∇g(x^k))

Ключевые свойства:

• Если h = 0, то prox_h(v) = v (обычный градиентный спуск)
• Если g = 0, то это чистая проксимальная минимизация
• prox_h невозрастающий: ||prox_h(x) - prox_h(y)|| ≤ ||x - y||

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

Пример 1: L1-регуляризация (Soft Thresholding)

Задача: h(x) = λ|x| для скаляра x

prox_{λh}(v) = argmin_x {½(x-v)² + λ|x|}

Решение через производные:

• Если v > λ: оптимум в x = v - λ
• Если v < -λ: оптимум в x = v + λ
• Если |v| ≤ λ: оптимум в x = 0

Итого: prox_{λ|·|}(v) = sign(v)·max(|v| - λ, 0)

def soft_threshold(v, lam):
    return np.sign(v) * np.maximum(np.abs(v) - lam, 0)

[МЕДИА: image_02] Описание: График soft thresholding функции, показывающий как происходит “обрезание” малых значений Промпт: “graph showing soft thresholding operator, input values on x-axis, output on y-axis, characteristic shape with dead zone around zero, lambda parameter visualization, mathematical plot style”

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

Задача: min_w {½||Aw - b||² + λ||w||₁}

Здесь g(w) = ½||Aw - b||², h(w) = λ||w||₁

Алгоритм:

1. Градиентный шаг: y = w - α·Aᵀ(Aw - b)
2. Покомпонентный soft thresholding: w_i = soft_threshold(y_i, αλ)

def lasso_proximal_gd(A, b, lam, alpha, n_iter=1000):
    w = np.zeros(A.shape[1])
    
    for i in range(n_iter):
        # Градиентный шаг
        gradient = A.T @ (A @ w - b)
        y = w - alpha * gradient
        
        # Проксимальный шаг
        w = soft_threshold(y, alpha * lam)
    
    return w

Пример 3: Матричное восстановление

Задача: Восстановить матрицу X по частичным наблюдениям с ядерной нормой: min_X {½||P_Ω(X - M)||² + λ||X||_*}

Где ||X||_* — ядерная норма (сумма сингулярных чисел)

Проксимальный оператор: SVD + soft thresholding сингулярных чисел!

def nuclear_norm_prox(M, lam):
    U, s, Vt = np.linalg.svd(M, full_matrices=False)
    s_thresh = soft_threshold(s, lam)
    return U @ np.diag(s_thresh) @ Vt

🎮 Практика

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

Задание 1: Найди prox_{2|·|}(3)

Задание 2: Чему равен prox_{0.5|·|}(-0.3)?

Задание 3: Реализуй функцию vector_soft_threshold(v, lam) для вектора

Задание 4: Почему проксимальный оператор L1-нормы делает веса разреженными?

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

Задание 5: Выведи проксимальный оператор для h(x) = ½x²

Задание 6: Сравни сходимость LASSO с λ=0.1 и λ=1.0 на синтетических данных

# Генерируй A (100×20), true_w с 5 ненулевыми элементами
# b = A @ true_w + noise
# Запусти алгоритм с разными λ

Задание 7: Что произойдёт, если в LASSO взять α > 2/||AᵀA||?

Задание 8: Реализуй проксимальный оператор для индикаторной функции единичного шара

Челлендж 🔴

Задание 9: Докажи, что проксимальный оператор L1-нормы невозрастающий

Задание 10: Реализуй FISTA (Fast Iterative Shrinkage-Thresholding Algorithm)

# Hint: используй momentum term
# x^k = prox(y^k - α∇g(y^k))
# y^{k+1} = x^k + β_k(x^k - x^{k-1})

Задание 11: Примени матричное восстановление к задаче collaborative filtering на MovieLens dataset

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

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

❌ Ошибка: Неправильный выбор шага α в проксимальном градиенте
✅ Правильно: α ≤ 1/L, где L — константа Липшица градиента g 💡 Почему: Иначе алгоритм может не сходиться

❌ Ошибка: Забывать проверить выпуклость h(x) ✅ Правильно: Проксимальные методы гарантируют сходимость только для выпуклых h 💡 Почему: Для невыпуклых нужны специальные модификации

❌ Ошибка: Путать L1 и L2 регуляризацию в проксимальных операторах ✅ Правильно: L1 → soft thresholding, L2 → scaling
💡 Почему: У них разные проксимальные операторы и свойства

❌ Ошибка: Не учитывать computational cost проксимального оператора ✅ Правильно: Проксимальный шаг должен быть вычислимым за O(n) или O(n log n) 💡 Почему: Иначе алгоритм становится медленнее субградиентных методов

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

✅ Суть: Проксимальные методы = градиентный шаг + проксимальный шаг ✅ Формула: x^{k+1} = prox_{αh}(x^k - α∇g(x^k))
✅ Применение: Когда нужна регуляризация (LASSO, sparse ML, восстановление сигналов)

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

Назад к уроку 290: Градиентные методы — база для проксимальных Вперёд: ADMM, методы расщепления, современные техники в deep learning (pruning, quantization)