Субградиенты и субдифференциал

Мотивация: что делать с недифференцируемыми функциями?

Многие важные выпуклые функции не имеют градиента в каждой точке. Абсолютное значение |x| не дифференцируемо в нуле. L1-норма ‖x‖₁ не дифференцируема, когда хотя бы одна компонента обращается в нуль. Максимум из нескольких функций не дифференцируем на множестве переключения. Если мы хотим решать задачи минимизации LASSO (‖Ax − b‖² + λ‖x‖₁), нам нужен инструмент, обобщающий градиент на негладкие функции. Это субдифференциал.

Определение субградиента

Вектор g ∈ ℝⁿ называется субградиентом выпуклой функции f в точке x, если:

f(y) ≥ f(x) + gᵀ(y − x) для всех y ∈ dom(f)

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

Субдифференциал ∂f(x) — множество всех субградиентов f в точке x:

∂f(x) = {g : f(y) ≥ f(x) + gᵀ(y − x) для всех y}

Это всегда замкнутое выпуклое множество.

Примеры субдифференциалов

Модуль |x| в одной переменной:

При x > 0: f'(x) = 1, поэтому ∂|x| = {1}
При x < 0: f'(x) = −1, поэтому ∂|x| = {−1}
При x = 0: субдифференциал ∂|0| = [−1, 1] — весь отрезок

Почему? При x = 0 нужно найти все g такие, что |y| ≥ |0| + g(y−0) = gy для всех y. Это выполняется при |y| ≥ gy для всех y, что означает g ∈ [−1, 1].

L1-норма ‖x‖₁ = Σᵢ|xᵢ| в ℝⁿ:

∂‖x‖₁ = {g : gᵢ = sign(xᵢ) при xᵢ ≠ 0, gᵢ ∈ [−1, 1] при xᵢ = 0}

Покоординатно: каждая компонента gi выбирается независимо из ∂|xᵢ|.

Максимум max(f₁, ..., fₘ)(x) (при условии, что fᵢ — гладкие):

∂ max(f₁,...,fₘ)(x) = conv{∇fᵢ(x) : i ∈ I(x)}

где I(x) = {i : fᵢ(x) = max_j fⱼ(x)} — множество «активных» функций, conv — выпуклая оболочка.

Индикаторная функция δ_C(x) = 0 если x ∈ C, иначе +∞:

∂δ_C(x) = N_C(x) = {g : gᵀ(y − x) ≤ 0 для всех y ∈ C} — нормальный конус к C в точке x.

Условие оптимальности через субдифференциал

Теорема: точка x* является глобальным минимумом выпуклой функции f тогда и только тогда, когда:

0 ∈ ∂f(x*)

Смысл: нуль должен быть субградиентом. Если f дифференцируема, это стандартное условие ∇f(x*) = 0. Для недифференцируемых функций: 0 должен лежать в «веере» субградиентов.

Пример: для f(x) = |x|: 0 ∈ ∂|x*| ⟺ x* = 0 (потому что только при x = 0 субдифференциал содержит 0).

Правила субдифференцирования

Сумма: ∂(f + g)(x) ⊇ ∂f(x) + ∂g(x). При условиях регулярности (например, одна из функций непрерывна): выполняется равенство.

Аффинная замена аргумента: если h(x) = f(Ax + b), то ∂h(x) = Aᵀ ∂f(Ax + b).

Прокс-оператор

Субградиент — это «направление» для движения. Но субградиентный метод медленный (O(1/√k)). Прокс-оператор даёт более эффективную альтернативу:

prox_{τf}(x) = argmin_y {f(y) + (1/2τ) ‖y − x‖²}

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

Примеры вычисления прокс-оператора:

Для f(x) = τ‖x‖₁ (мягкая пороговая функция): prox_{τ‖·‖₁}(x) = sign(x) · max(|x| − τ, 0) — поэлементно

Это «soft thresholding»: обнуляет компоненты |xᵢ| ≤ τ, сдвигает остальные к нулю на τ.

Для f(x) = δ_C(x) (индикатор): prox_{δ_C}(x) = P_C(x) — просто проекция на C.

Полный разбор примера: LASSO

Задача: min_{x ∈ ℝⁿ} F(x) = (1/2)‖Ax − b‖² + λ‖x‖₁

Условие оптимальности: 0 ∈ ∂F(x*) = ∂(1/2)‖Ax−b‖² + λ ∂‖x*‖₁

Первый субдифференциал — это градиент гладкой части: Aᵀ(Ax* − b). Второй — это λ · ∂‖x*‖₁.

Итого: −Aᵀ(Ax* − b) ∈ λ ∂‖x*‖₁

По компонентам: если xᵢ ≠ 0, то [Aᵀ(Ax − b)]ᵢ = −λ sign(xᵢ). Если xᵢ = 0, то |[Aᵀ(Ax* − b)]ᵢ| ≤ λ.

Алгоритм ISTA (мягкое пороговое: iterative shrinkage-thresholding):

x^{k+1} = prox_{τλ‖·‖₁}(x^k − τ Aᵀ(Ax^k − b)) = softthresh(x^k − τAᵀ(Ax^k − b), τλ)

На каждом шаге: градиентный шаг по гладкой части + прокс по негладкой.

Применения

Отбор признаков: LASSO-регрессия с L1-штрафом автоматически обнуляет ненужные коэффициенты. Это «автоматический отбор переменных». В медицинских данных с тысячами генов LASSO выбирает несколько десятков наиболее значимых.

Компрессированное восстановление сигналов: МРТ-сканер делает в 10 раз меньше измерений, используя L1-минимизацию для восстановления разреженного изображения. Субдифференциал L1-нормы — ключ к пониманию, почему это работает.