Cheatsheet

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

Множество C ⊆ ℝⁿ называется выпуклым, если для любых двух точек x, y ∈ C и любого числа θ ∈ [0,1] выполняется:

Что это означает словами? Возьмите любые две точки множества. Соедините их отрезком. Если весь этот отрезок целиком лежит внутри множества — оно выпуклое. Параметр θ «пробегает» от 0 до 1, описывая все точки между x и y: при θ=1 получаем x, при θ=0 — y, при θ=0.5 — середину отрезка.

Геометрический тест: нарисуйте фигуру. Если можно найти две точки внутри неё, соединённые отрезком, частично выходящим за границу — фигура невыпуклая. Буква «C» — невыпуклая. Круг, квадрат, треугольник — выпуклые.

Главный практический факт: если функция выпуклая, то её любой локальный минимум является глобальным. Это колоссальное преимущество. В невыпуклой задаче у вас могут быть тысячи локальных минимумов, и алгоритм может «застрять» в плохом из них. В выпуклой задаче — только один минимум, и любой метод ...

Функция f: ℝⁿ → ℝ (или f: dom(f) → ℝ, где dom(f) — выпуклое множество) называется выпуклой, если для любых x, y ∈ dom(f) и любого λ ∈ [0,1]:

Геометрический смысл: рассмотрим две точки на графике функции: A = (x, f(x)) и B = (y, f(y)). Правая часть λf(x) + (1−λ)f(y) — это точка на хорде AB, соответствующая параметру λ. Левая часть f(λx + (1−λ)y) — это значение функции в той же точке по горизонтали. Выпуклость означает: график функции л...

Если выполняется строгое неравенство (< вместо ≤) при x ≠ y и λ ∈ (0,1) — функция строго выпуклая. У строго выпуклой функции минимум единственен.

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

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

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

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

Иногда решить задачу оптимизации напрямую сложно, но существует «переформулировка», которая решается проще. Лагранжева двойственность — это систематический способ построить такую двойственную задачу. Оказывается, у каждой задачи минимизации есть «двойственная задача максимизации», оптимальное зна...

Лагранжиан: «смягчаем» ограничения, перемещая их в целевую функцию со штрафами λᵢ и νⱼ:

где λᵢ ≥ 0 — «двойственные переменные» (множители Лагранжа) для неравенств, νⱼ — для уравнений (могут быть любого знака).

Физический смысл λᵢ: цена нарушения i-го ограничения. Если gᵢ(x) > 0 (нарушение), за это платим λᵢ gᵢ(x) > 0. При λᵢ = 0 — штрафа нет. При больших λᵢ — нарушение «дорогое».

Представьте, что вы хотите охарактеризовать выпуклую функцию не через её значения в точках, а через поддерживающие её гиперплоскости. Каждая касательная линия к выпуклой функции задаётся своим наклоном y и «точкой перехвата». Сопряжённая функция f*(y) фиксирует это «пересечение» для гиперплоскост...

Ключевое свойство: f* — всегда выпуклая функция, даже если исходная f — невыпуклая! (Как супремум аффинных функций по y.)

Биполярная теорема: если f — замкнутая выпуклая функция, то f = f (двойная сопряжённая совпадает с исходной). Для невыпуклых f: f = cl(conv(f)) — замыкание выпуклой оболочки.

Вычисление: если |yᵢ| > 1 для некоторого i, берём xᵢ → ±∞ → супремум = +∞. Если |yᵢ| ≤ 1 для всех i, то yᵀx ≤ ‖y‖_∞ ‖x‖₁ ≤ ‖x‖₁ → yᵀx − ‖x‖₁ ≤ 0, максимум = 0 (при x = 0).

Definitions

Formulas

Выпуклое программирование — это «семейство» задач оптимизации различной сложности. Линейное программирование (ЛП) — простейшее: линейная цель, линейные ограничения. Квадратичное (КП) — квадратичная цель. Программирование второго порядка (SOCP) — конические ограничения. Полуопределённое (SDP) — ма...

Здесь c ∈ ℝⁿ — вектор коэффициентов цели, A ∈ ℝ^{m×n} — матрица ограничений, b ∈ ℝᵐ — правые части.

Геометрия: область допустимых решений — выпуклый многогранник (политоп). Линейная целевая функция достигает минимума в вершине многогранника. Симплекс-метод (Данциг, 1947) «ходит» по вершинам, пока не найдёт оптимальную. Метод внутренней точки — движется через внутренность.

Двойственность ЛП: примальная задача min cᵀx при Ax ≥ b, x ≥ 0 имеет двойственную max bᵀy при Aᵀy ≤ c, y ≥ 0. Сильная двойственность выполнена всегда (при допустимости обеих задач).

Методы второго порядка (метод Ньютона) очень быстрые, но требуют вычисления и обращения матрицы Гессе — O(n³) операций за шаг. При n = 10⁶ параметров (нейросеть среднего размера) это просто невозможно. Методы первого порядка используют только градиент — O(n) операций. Они медленнее на итерацию, н...

Здесь α > 0 — размер шага (learning rate). При слишком большом α — алгоритм расходится. При слишком малом — очень медленная сходимость.

Класс L-гладких функций: f называется L-гладкой, если ‖∇f(x) − ∇f(y)‖ ≤ L‖x − y‖ для всех x, y. Константа L — «степень гладкости» (наибольшее собственное значение матрицы Гессе).

Это скорость O(1/k): чтобы уменьшить ошибку вдвое, нужно удвоить число итераций.

Formulas

Задача LASSO: min (1/2)‖Ax−b‖² + λ‖x‖₁. Первый член — гладкий (можно дифференцировать), второй — нет (|x|₁ недифференцируема в нуле). Применить градиентный спуск нельзя напрямую. Субградиентный метод — слишком медленный (O(1/√k)). Прокс-алгоритмы решают эту проблему элегантно: «расщепляют» функци...

Это «мягкий шаг в сторону минимума f». При τ → 0: prox ≈ x (не двигаемся). При τ → ∞: prox → argmin f (идём в минимум).

1. f(x) = ‖x‖₁: prox_{τf}(x) = sign(x) · max(|x| − τ, 0) — мягкое пороговое (soft thresholding)

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

Задача с ограничениями: min f(x) при gᵢ(x) ≤ 0. Один из подходов — «забыть» про ограничения, но добавить большой штраф за их нарушение. Логарифмический барьер делает это изящно: он уходит в +∞ при приближении x к границе допустимого множества. Метод внутренней точки (МВТ) систематически используе...

Смысл: когда gᵢ(x) → 0 (приближаемся к границе ограничения), −gᵢ(x) → 0⁺ → log → −∞ → φ(x) → +∞. Барьер «отталкивает» от границы.

При gᵢ(x) = −t (x строго внутри, зазор = t): φ(x) = − log t. При удвоении зазора барьер уменьшается на log 2.

Параметр t > 0 — «точность». При t → ∞ барьерный член (1/t)φ(x) → 0, и решение сходится к оригинальному.

Представьте, что вы строите модель прогнозирования цен на квартиры по 1000 признакам, имея только 100 наблюдений. Без ограничений модель может «запомнить» обучающие данные (переобучение), показав нулевую ошибку на них, но ужасную — на новых данных. Регуляризация — это добавление штрафного члена к...

Здесь A ∈ ℝ^{m×n} — матрица признаков, b ∈ ℝᵐ — отклики, λ > 0 — параметр регуляризации.

Важно: матрица AᵀA + λI всегда обратима при λ > 0, даже если AᵀA вырождена! Это решает проблему мультиколлинеарности.

Эффект: все коэффициенты сжимаются к нулю пропорционально, но ни один не обнуляется точно. Это хорошо для «стабилизации» (уменьшения дисперсии), но плохо для «отбора признаков».

Задача классификации: дано N точек (xᵢ, yᵢ), где xᵢ ∈ ℝⁿ и yᵢ ∈ {−1, +1} — метки классов. Нужно найти гиперплоскость, разделяющую два класса. Таких гиперплоскостей бесконечно много — любая разделяющая подойдёт. SVM (Support Vector Machine) выбирает «наилучшую» — ту, которая максимально удалена от...

Зазор (margin) = 2/‖w‖ (расстояние между двумя параллельными гиперплоскостями wᵀx + b = ±1).

Задача SVM (hard margin): максимизировать зазор при правильной классификации:

Это выпуклое квадратичное программирование! Уникальное решение (строго выпуклая цель).

Formulas

Машинное обучение кажется эмпирической дисциплиной: попробовал — получилось. Но за кулисами существует математическая теория, объясняющая, почему и когда обучение даёт обобщение на новые данные. VC-теория и PAC-обучаемость — это строгие рамки. Выпуклые задачи имеют особые гарантии: независящие от...

Разбиение (shattering): набор точек S «разбит» гипотезным классом H, если для любой разметки точек ∈ {−1, +1} существует гипотеза h ∈ H, правильно классифицирующая все точки.

Основная теорема VC: конечная vc(H) ↔ PAC-обучаемость (Probably Approximately Correct). Число примеров для (ε, δ)-обучения: N = O((vc(H) + log(1/δ)) / ε²).

Следствие: обобщение ≤ O(Bρ/√N) — не зависит от размерности пространства! Только маржа (1/B) и норма данных (ρ) имеют значение.