Выпуклая оптимизация: методы первого порядка

Выпуклая оптимизация в машинном обучении

Многие задачи ML имеют выпуклую структуру: линейная регрессия, логистическая регрессия, SVM, LASSO, Ridge, метод опорных векторов. Для таких задач гарантирован глобальный оптимум, и существует богатая теория эффективных алгоритмов. Знание выпуклой оптимизации — фундамент понимания того, «почему работает» обучение ML-моделей.

Выпуклые функции и задачи

Определение выпуклости: Функция f: ℝⁿ → ℝ выпуклая, если для всех x, y ∈ dom(f) и α ∈ [0,1]:

f(αx + (1−α)y) ≤ αf(x) + (1−α)f(y)

Геометрически: хорда между любыми двумя точками лежит выше графика. Следствие: локальный минимум = глобальный.

L-гладкость: f дважды дифференцируема с ||∇²f(x)|| ≤ L (наибольшее собственное значение гессиана ограничено). Эквивалентно: ||∇f(x) − ∇f(y)|| ≤ L||x−y|| — градиент не меняется слишком быстро. Следствие (descent lemma):

f(y) ≤ f(x) + ∇f(x)ᵀ(y−x) + L/2||y−x||²

μ-сильная выпуклость: f(y) ≥ f(x) + ∇f(x)ᵀ(y−x) + μ/2||y−x||². Означает: функция «не слишком плоская» — квадратичная нижняя граница. Условное число задачи κ = L/μ — чем больше, тем сложнее оптимизировать.

Методы градиентного спуска

Градиентный спуск (GD): xₜ₊₁ = xₜ − (1/L)∇f(xₜ). Оптимальный шаг для L-гладкой: α = 1/L.

Теорема сходимости:

• Выпуклая, L-гладкая: f(x_T) − f* ≤ L||x₀−x*||²/(2T). Сходимость: O(1/T).
• μ-сильно выпуклая, L-гладкая: ||xₜ−x*||² ≤ (1−μ/L)ᵗ ||x₀−x*||². Сходимость: O(exp(−t/κ)).

Ускорение Нестерова (1983): добавляет «импульс» из предыдущей итерации:

yₜ = xₜ + (t−1)/(t+2)·(xₜ−xₜ₋₁) (momentum step) xₜ₊₁ = yₜ − (1/L)∇f(yₜ) (gradient step)

Сходимость: O(1/t²) для выпуклой — оптимально для методов первого порядка! Удвоение t уменьшает ошибку в 4 раза (vs 2 раза для GD).

Проксимальные методы

Многие задачи ML имеют вид: min_x f(x) + g(x), где f — гладкая выпуклая (например, MSE), g — негладкая выпуклая (например, λ||x||₁ для LASSO).

Проксимальный оператор: prox_{αg}(v) = argmin_x {(1/2)||x−v||² + αg(x)}. Имеет аналитическое решение для многих g:

• g(x) = λ||x||₁: prox = sign(v)·max(|v|−αλ, 0) (мягкое пороговое, soft-thresholding)
• g(x) = λ||x||₂: prox = max(1−αλ/||v||, 0)·v (проекция на шар)
• g = I_C (индикатор выпуклого множества C): prox = проекция на C

ISTA (Iterative Shrinkage-Thresholding Algorithm):

xₜ₊₁ = prox_{αg}(xₜ − α∇f(xₜ))

Шаг 1: градиентный шаг по f. Шаг 2: проксимальный шаг по g. Сходимость: O(1/t) для выпуклой.

FISTA: Нестеровское ускорение для ISTA → O(1/t²). Де-факто стандарт для LASSO с теоретическими гарантиями.

ADMM: декомпозиция задачи

Задача с ограничением: min f(x) + g(z), при Ax + Bz = c. Примеры: distributed ML, portfolio optimization.

Augmented Lagrangian: L_ρ(x,z,y) = f(x) + g(z) + yᵀ(Ax+Bz−c) + (ρ/2)||Ax+Bz−c||²

ADMM-шаги: x^{k+1} = argmin_x L_ρ(x, z^k, y^k) z^{k+1} = argmin_z L_ρ(x^{k+1}, z, y^k) y^{k+1} = y^k + ρ(Ax^{k+1} + Bz^{k+1} − c)

Каждый шаг — простая оптимизация (часто аналитическая). Параллелизируется: x-шаги независимы по блокам. Используется в распределённой оптимизации, portfolio selection с ограничениями.

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

Идея: вместо оптимизации по всем переменным сразу — оптимизируем по одной переменной, фиксируя остальные: min_{x_j} f(x₁,...,x_{j−1}, x_j, x_{j+1},...,x_n).

Для LASSO аналитически: x_j^* = (1/n)soft-thresh_{λ}(zⱼ), где zⱼ = xⱼ − (Aᵀ(Ax−y))ⱼ. Случайный координатный спуск (randomized CD): на каждой итерации выбираем j случайно → O(n/T) сходимость. Используется в liblinear (SVM), word2vec.

Численный пример

LASSO: y = Xβ* + ε, n=100 наблюдений, p=500 признаков, истинный β* — 10-разреженный. λ = 0.1·||Xᵀy||_∞.

ISTA: 1000 итераций, α=1/L, финальная MSE = 0.023. FISTA: те же 1000 итераций, MSE = 0.0018 (в 13 раз лучше). Координатный спуск (sklearn): 200 итераций, MSE = 0.0015 (быстрее на практике). ISTA находит 12 ненулевых коэффициентов (2 лишних), FISTA и CD — ровно 10.

Задание: Реализуйте ISTA и FISTA для LASSO на synthetically generated data (X ∈ ℝ^{100×500}, s=20 ненулевых). Постройте кривые сходимости (log(f(xₜ)−f*) vs t) для обоих методов. Теоретически FISTA сходится как O(1/t²), ISTA — O(1/t). Проверьте теоретические оценки эмпирически. Реализуйте ADMM для Ridge regression с sum ограничением Σxⱼ = 1.