Субградиентные методы: оптимизация негладких функций

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

Представь, что ты тренируешь нейросеть для распознавания мемов в TikTok 📱. Твоя функция потерь выглядит гладко на 99% случаев, но иногда встречаются “острые углы” - места, где производная не существует. Классический градиентный спуск тут пасует!

🧠 Где встречается:

• ReLU активации в нейросетях (излом в нуле)
• L1-регуляризация (Lasso) - создаёт разреженные модели
• Функция потерь SVM - максимизация зазора между классами

💰 Почему важно: Netflix использует субградиентную оптимизацию в рекомендательных системах с L1-регуляризацией, экономя миллионы на хранении разреженных матриц!

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

В 1960-х математик Надир Шор работал в СССР над задачами планирования экономики. Он заметил, что многие важные функции (например, максимум из нескольких линейных функций) не имеют производных в некоторых точках, но их всё равно нужно оптимизировать 🏭

Его идея: “А что если заменить производную на множество возможных направлений спуска?” Так родилась концепция субградиента - обобщения производной для негладких функций.

💡 Интуиция

🏔️ Аналогия с горой: Обычная производная - это склон горы в конкретном направлении. Но что делать на остром гребне, где склон не определён? Субградиент говорит: “Вот множество всех возможных склонов в этой точке - выбирай любой!”

[МЕДИА: image_01] Описание: Визуализация негладкой функции с субградиентами в точке излома Промпт: “educational illustration showing non-smooth convex function with a sharp corner, multiple subgradient vectors at the corner point, gradient descent paths, mathematical visualization style, blue and orange colors”

🎮 Игровая аналогия: Ты играешь в паркур-игру. На гладких поверхностях направление движения очевидно (градиент). Но на острых рёбрах зданий у тебя есть несколько вариантов - можешь пойти влево или вправо по рёбру. Субградиент - это все эти варианты одновременно!

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

Субградиент функции f в точке x - это любой вектор g такой, что:

f(y) ≥ f(x) + g^T(y - x) для всех y

📝 Что это значит: Субградиент задаёт линейную функцию, которая лежит “снизу” от исходной функции и касается её в точке x.

Множество субградиентов ∂f(x) называется субдифференциалом.

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

✅ Для гладких функций: ∂f(x) = {∇f(x)} (один элемент - обычный градиент)
✅ Для негладких: ∂f(x) может содержать множество векторов
✅ В точке минимума: 0 ∈ ∂f(x) (необходимое условие оптимальности)

[МЕДИА: image_02] Описание: Сравнение градиента и субградиента для гладкой и негладкой функций Промпт: “side-by-side comparison of smooth function with single gradient vector versus non-smooth function with multiple subgradient vectors, supporting hyperplanes visualization, educational mathematical diagram”

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

Пример 1: Модуль (основа L1-регуляризации)

f(x) = |x|

📍 При x > 0: f’(x) = 1, значит ∂f(x) = {1}
📍 При x < 0: f’(x) = -1, значит ∂f(x) = {-1}
📍 При x = 0: ∂f(0) = [-1, 1] - весь интервал!

# Субградиент модуля
def subgradient_abs(x):
    if x > 0:
        return 1
    elif x < 0:
        return -1
    else:
        return random.uniform(-1, 1)  # Любое значение из [-1,1]

Пример 2: ReLU активация

f(x) = max(0, x) = ReLU(x)

📍 При x > 0: ∂f(x) = {1}
📍 При x < 0: ∂f(x) = {0}
📍 При x = 0: ∂f(0) = [0, 1]

# Субградиент ReLU
def subgradient_relu(x):
    if x > 0:
        return 1
    elif x < 0:
        return 0
    else:
        return random.uniform(0, 1)  # В PyTorch обычно 0

Пример 3: Максимум функций (SVM loss)

f(x) = max(x₁, x₂, x₃)

Если максимум достигается в одной точке - субградиент единственный.
Если в нескольких - берём их выпуклую комбинацию!

🎮 Практика

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

Задание 1: Найди субградиент функции f(x) = |x - 2| в точке x = 2

Задание 2: Реализуй субградиентный спуск для f(x) = |x| с начальной точки x₀ = 5

def subgradient_descent_abs(x0, learning_rate=0.1, iterations=10):
    x = x0
    for i in range(iterations):
        if x > 0:
            g = 1
        elif x < 0:
            g = -1
        else:
            g = 0  # или случайное из [-1,1]
        x = x - learning_rate * g
        print(f"Iteration {i+1}: x = {x}")
    return x

Задание 3: Для функции f(x) = max(x, 2x, 3x) найди субградиент в точке x = 0

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

Задание 4: Докажи, что для выпуклой функции f субградиентный метод сходится к глобальному минимуму

Задание 5: Реализуй субградиентную оптимизацию для L1-регуляризованной линейной регрессии:

# Loss = ||Ax - b||² + λ||x||₁
def l1_regularized_subgradient(A, b, lambda_reg, x0):
    # Твоя реализация
    pass

Задание 6: Объясни, почему в PyTorch для ReLU в точке 0 используется субградиент 0, а не случайный?

Челлендж 🔴

Задание 7: Докажи теорему: если f выпукла и непрерывна, то ∂f(x) ≠ ∅ для всех x

Задание 8: Реализуй проксимальный градиентный метод для задачи: minimize f(x) + g(x), где f гладкая, g негладкая

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

❌ Ошибка: “Субградиент = производная для негладких функций”
✅ Правильно: Субградиент - это множество, производная - единственный вектор
💡 Почему: В негладких точках может быть много “направлений спуска”

❌ Ошибка: Использовать слишком большой learning rate в субградиентном методе
✅ Правильно: lr должен убывать как 1/√t для гарантированной сходимости
💡 Почему: Субградиенты могут быть “зашумлёнными” по сравнению с точными градиентами

❌ Ошибка: Думать, что субградиентный метод сходится так же быстро, как градиентный
✅ Правильно: Скорость O(1/√T) против O(1/T) для гладких функций
💡 Почему: Отсутствие гладкости замедляет сходимость

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

✅ Суть: Субградиент обобщает производную для негладких функций
✅ Формула: f(y) ≥ f(x) + g^T(y-x) для всех y
✅ Применение: ReLU, L1-регуляризация, SVM, робастные функции потерь

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

Назад: Градиентный спуск (урок 289) дал нам интуицию оптимизации
Вперёд: Проксимальные методы, зеркальный спуск, онлайн-обучение
Практика: Adam, AdaGrad адаптируют идеи субградиентов для стохастической оптимизации