Выпуклые функции 🥣

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

Этот урок — один из самых важных в курсе именно потому, что он объясняет, где проходит граница между «простым» и «сложным» в машинном обучении. Функция потерь линейной регрессии (среднеквадратичная ошибка, MSE) и функция потерь логистической регрессии (кросс-энтропия) — выпуклые функции своих параметров. Это значит, что у них попросту не существует «ловушек»: любая точка, где градиентный спуск остановится, гарантированно окажется наилучшей из всех возможных, а не просто наилучшей по соседству. А вот функция потерь нейросети с несколькими слоями — невыпуклая. Её поверхность в пространстве весов испещрена холмами, оврагами и — что важнее всего, как ты увидишь в конце этого урока — седловыми точками, которых в выпуклой задаче не может быть в принципе.

Сегодня мы дадим выпуклости строгое определение через неравенство Йенсена, разберём геометрический смысл этого определения — график функции лежит не выше любой хорды, — получим удобный практический критерий через вторую производную и гессиан, а затем докажем главную теорему всего урока: у выпуклой функции любой локальный минимум является глобальным. Именно эта теорема — не эмпирическое наблюдение, а строго доказуемый факт — и есть причина, по которой градиентный спуск для линейной и логистической регрессии гарантированно сходится к наилучшему возможному решению, вне зависимости от того, с какой точки он стартовал.

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

История

Формальное определение выпуклой функции и неравенство, которое сегодня носит его имя, дал датский математик Йохан Людвиг Вильям Вальдемар Йенсен в 1906 году в статье «Sur les fonctions convexes et les inégalités entre les valeurs moyennes» («О выпуклых функциях и неравенствах между средними значениями»). Примечательная деталь: Йенсен не был профессиональным академическим математиком. Он всю жизнь проработал инженером на Копенгагенской телефонной компании, дослужился там до технического директора, а математикой занимался как страстным увлечением по вечерам и выходным. Тем не менее именно его формулировка — не отдельные частные неравенства для конкретных функций, а общее определение через $f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y)$ — оказалась настолько удачной, что стала стандартом на следующие более чем сто лет.

До Йенсена математики прекрасно знали и доказывали отдельные неравенства, которые сегодня мы понимаем как частные случаи выпуклости: неравенство между средним арифметическим и средним геометрическим, неравенство Коши — Буняковского, различные неравенства для средних степенных. Но каждое из них доказывалось своим отдельным трюком, специфичным для конкретной функции. Йенсен заметил общую структуру, стоящую за всеми этими результатами, и дал ей имя и строгое определение. После этого десятки ранее разрозненных неравенств оказались просто следствиями одного общего факта — неравенства Йенсена для соответствующей выпуклой (или вогнутой) функции. Это тот редкий случай в математике, когда абстрактное обобщение не усложнило картину, а радикально её упростило.

В XX веке теория выпуклых функций и выпуклых множеств срослась в отдельную дисциплину — выпуклый анализ, систематизированную окончательно в классической монографии Ральфа Рокафеллара «Convex Analysis» (1970). А во второй половине века выпуклость превратилась из красивой математической теории в рабочий инструмент прикладной статистики и машинного обучения: метод опорных векторов (SVM) Владимира Вапника в 1990-х годах был построен именно как выпуклая задача квадратичного программирования специально для того, чтобы гарантировать единственность и глобальность решения; логистическая регрессия как метод максимального правдоподобия оказалась выпуклой задачей ещё раньше; а книга Стивена Бойда и Ливена Ванденберга «Convex Optimization» (2004) стала настольной для целого поколения специалистов по машинному обучению — именно потому, что умение распознать выпуклость задачи означает умение заранее, до единой строчки кода, знать, что оптимизация сработает надёжно.

Определение через неравенство Йенсена и геометрический смысл

Интуиция

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

Это же можно сформулировать через случайную величину: если ты подбрасываешь монетку и в зависимости от исхода оказываешься либо в точке $x$, либо в точке $y$, то для выпуклой функции «среднее значение функции» (то есть $\lambda f(x) + (1-\lambda) f(y)$ при вероятности $\lambda$ попасть в $x$) всегда не меньше, чем «функция от среднего значения» (то есть $f(\lambda x + (1-\lambda) y)$, значение функции в средней взвешенной точке). Этот же факт в общем виде для произвольного распределения, а не только для двух точек, — и есть неравенство Йенсена в его полной формулировке, которое ты позже встретишь в теории вероятностей и в вычислении границ правдоподобия.

Определение

Определение. Пусть $D \subseteq \mathbb{R}^n$ — выпуклое множество (в смысле прошлого урока: для любых $x, y \in D$ и $\lambda \in [0,1]$ точка $\lambda x + (1-\lambda) y$ тоже лежит в $D$). Функция $f: D \to \mathbb{R}$ называется выпуклой, если для любых $x, y \in D$ и любого $\lambda \in [0, 1]$ выполняется неравенство Йенсена:

$$f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y)$$

Если неравенство строгое для всех $x \ne y$ и $\lambda \in (0,1)$, функция называется строго выпуклой. Функция $f$ называется вогнутой, если $-f$ выпукла (неравенство меняет знак на противоположный).

Обрати внимание на требование «$D$ — выпуклое множество» — это прямое продолжение прошлого урока, и оно не формальность. Определение выпуклости функции опирается на то, что точка $\lambda x + (1-\lambda) y$ вообще лежит в области определения — иначе левая часть неравенства попросту не имеет смысла. Именно поэтому выпуклость множества-области определения — обязательное предварительное условие, без которого понятие выпуклой функции не определено.

Есть и второй, эквивалентный способ увидеть то же самое определение — через надграфик (эпиграф): $\operatorname{epi}(f) = \{(x, t) \in D \times \mathbb{R} : t \ge f(x)\}$, то есть множество всех точек, лежащих на графике функции или выше него. Можно строго доказать, что функция $f$ выпукла тогда и только тогда, когда её надграфик $\operatorname{epi}(f)$ является выпуклым множеством в смысле прошлого урока. Это красивый мост между двумя соседними темами курса: выпуклость функции — это в точности выпуклость множества точек «на графике и выше него».

Примеры

Пример 1: $f(x) = x^2$. Проверим неравенство Йенсена напрямую, раскрыв разность правой и левой части:

После раскрытия скобок и приведения подобных эта разность точно равна $\lambda(1-\lambda)(x-y)^2$. Поскольку $\lambda \in [0,1]$, множитель $\lambda(1-\lambda) \ge 0$, а $(x-y)^2 \ge 0$ всегда — значит, вся разность неотрицательна, то есть неравенство Йенсена выполняется для любых $x, y, \lambda$. Более того, разность равна нулю только при $x = y$ или при $\lambda \in \{0, 1\}$ — значит, $x^2$ строго выпукла.

Пример 2: линейная функция потерь MSE в одномерном случае. Пусть у тебя есть точки данных $(x_i, y_i)$, и функция потерь одного параметра $w$: $L(w) = \sum_i (y_i - w x_i)^2$. Каждое слагаемое $(y_i - w x_i)^2$ — это композиция $x^2$ с линейной по $w$ функцией $y_i - w x_i$, а сдвиг и умножение аргумента на константу внутри выпуклой функции выпуклость сохраняет (это мы строго докажем как отдельное правило в разделе с практикой). Сумма выпуклых слагаемых — снова выпуклая функция. Уже здесь, на геометрической интуиции, видно: график $L(w)$ — это парабола, «чаша» в пространстве одного параметра, и у такой чаши физически не может быть второго дна где-то в стороне.

Пример 3: невыпуклая функция. Возьми $f(x) = x^3$ на всей числовой прямой. При $x < 0$ график этой функции локально вогнутый (выпуклый вниз в бытовом смысле, «горб» смотрит вверх), а при $x > 0$ — выпуклый в нашем строгом смысле. Проверим неравенство Йенсена в точках $x = -3$, $y = -1$, $\lambda = 0{,}5$: середина отрезка — точка $-2$, и $f(-2) = -8$. Правая часть неравенства: $0{,}5 \cdot f(-3) + 0{,}5 \cdot f(-1) = 0{,}5 \cdot (-27) + 0{,}5 \cdot (-1) = -14$. Неравенство Йенсена требует $f(-2) \le -14$, но $-8 > -14$ — неравенство нарушено. Значит, $x^3$ на всей числовой прямой не выпукла (хотя на луче $x \ge 0$, если рассматривать его как отдельную область определения, она выпукла).

Почему это важно

Определение через неравенство Йенсена не требует ни производных, ни дифференцируемости — оно проверяется прямым вычислением значений функции в трёх точках. Это критично для функций потерь, которые не всюду гладкие: например, $\operatorname{ReLU}(x) = \max(0, x)$ или хинж-лосс SVM $\max(0, 1 - y w^\top x)$ не дифференцируемы в отдельных точках, но определение через неравенство Йенсена прекрасно к ним применимо и подтверждает их выпуклость (это ты докажешь сам в задании из блока практики). Там же, где функция дважды дифференцируема — а это подавляющее большинство функций потерь классического машинного обучения, — гораздо удобнее пользоваться критерием через вторую производную, к которому мы сейчас и переходим.

Критерий выпуклости через вторую производную и гессиан

Интуиция

Вторая производная измеряет кривизну графика — насколько быстро меняется наклон касательной. У выпуклой функции наклон касательной может расти или падать по величине, но он никогда не «заворачивает» график вниз относительно любой хорды — а это ровно то же самое, что «кривизна везде неотрицательна». Для функции многих переменных прямого аналога одного числа «вторая производная» нет — вместо него используется гессиан, матрица вторых частных производных, с которой ты уже встречался в университетском курсе (урок 213) при поиске экстремумов функций нескольких переменных. Там гессиан помогал классифицировать отдельную найденную критическую точку — минимум она, максимум или седло. Здесь задача сложнее и одновременно проще: нам нужно знать не про одну точку, а сразу про весь график функции целиком — и критерий именно такой: гессиан должен быть «неотрицательным» в каждой точке области определения, без единого исключения.

Формальный критерий

Критерий выпуклости через вторую производную. Пусть $f$ дважды дифференцируема на выпуклом интервале $I \subseteq \mathbb{R}$. Тогда $f$ выпукла на $I$ тогда и только тогда, когда $f''(x) \ge 0$ для всех $x \in I$. Если $f''(x) > 0$ для всех $x \in I$, то $f$ строго выпукла (обратное в общем случае неверно — строгая выпуклость может допускать отдельные точки с $f''(x) = 0$).

Критерий выпуклости через гессиан (многомерный случай). Пусть $f: D \to \mathbb{R}$ дважды дифференцируема на выпуклом множестве $D \subseteq \mathbb{R}^n$. Тогда $f$ выпукла на $D$ тогда и только тогда, когда гессиан $\nabla^2 f(x)$ положительно полуопределён для каждого $x \in D$, то есть $v^\top \nabla^2 f(x)\, v \ge 0$ для любого вектора $v \in \mathbb{R}^n$. Если гессиан положительно определён ($v^\top \nabla^2 f(x)\, v > 0$ для всех $v \ne 0$) во всех точках $D$, функция строго выпукла.

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

Примеры

Пример 1: строгая выпуклость MSE через гессиан. Возьмём линейную регрессию в матричной записи: $L(w) = \frac{1}{2n}\|y - Xw\|^2$, где $X$ — матрица признаков размера $n \times d$, $y$ — вектор целевых значений, $w \in \mathbb{R}^d$ — веса. Градиент этой функции равен $\nabla L(w) = \frac{1}{n} X^\top X w - \frac{1}{n} X^\top y$, а гессиан — вторая производная от градиента по $w$ — оказывается константной матрицей, не зависящей от $w$ вообще:

Проверим положительную полуопределённость напрямую: для любого вектора $v \in \mathbb{R}^d$

Сумма квадратов координат вектора $Xv$ не может быть отрицательной ни при каких $X$ и $v$ — значит, $X^\top X$ положительно полуопределена для абсолютно любой матрицы данных $X$, безо всяких условий на сами данные. Вывод: MSE выпукла всегда, для любого датасета, — это не эмпирическое наблюдение, а строгая теорема. Строгая же выпуклость (и, как следствие, единственность решения) требует, чтобы $X^\top X$ была положительно определена, а это равносильно тому, что столбцы $X$ линейно независимы — признаки не дублируют друг друга и их не больше, чем наблюдений.

Пример 2: выпуклость кросс-энтропии логистической регрессии. Функция потерь логистической регрессии — это $L(w) = -\frac{1}{n}\sum_i \big[y_i \log \sigma(x_i^\top w) + (1-y_i)\log(1-\sigma(x_i^\top w))\big]$, где $\sigma(z) = \frac{1}{1+e^{-z}}$ — сигмоида. Прямое вычисление (его стоит проделать самостоятельно как упражнение, оно встретится в блоке практики) даёт гессиан вида

Это в точности взвешенная матрица Грама: для любого $v$, $v^\top X^\top S X\, v = \sum_i p_i(1-p_i) (x_i^\top v)^2$. Поскольку сигмоида принимает значения строго между 0 и 1, каждый вес $p_i(1-p_i)$ строго положителен, а каждое слагаемое суммы — неотрицательный квадрат, умноженный на положительный вес. Вся сумма неотрицательна — значит, гессиан положительно полуопределён, а кросс-энтропия логистической регрессии тоже выпукла всегда, для любых данных и любого текущего значения весов $w$. Обрати внимание на тонкость: сама сигмоида $\sigma(z)$ как функция от $z$ выпуклой не является (она S-образная, выпукла при $z<0$ и вогнута при $z>0$) — но составленная с логарифмом функция потерь как функция от $w$ всё равно оказывается выпуклой. Это иллюстрация того, что выпуклость итоговой функции потерь — отдельный факт, который нужно доказывать именно для неё, а не для отдельных «строительных блоков» внутри.

Пример 3: невыпуклость минимальной модели нейросети. Рассмотрим предельно упрощённую «двухслойную сеть» без нелинейностей — просто произведение двух скалярных весов, $f(w_1, w_2) = w_1 w_2$, с квадратичной функцией потерь относительно цели, равной 1: $L(w_1, w_2) = (w_1 w_2 - 1)^2$. Вычислим гессиан в точке $(0, 0)$. Частные производные: $\partial L/\partial w_1 = 2w_2(w_1w_2 - 1)$, $\partial L/\partial w_2 = 2w_1(w_1w_2-1)$ — в точке $(0,0)$ обе равны нулю, значит, это критическая точка. Вторые частные производные в этой же точке дают гессиан

Собственные значения этой матрицы равны $+2$ и $-2$ — матрица неопределена (не положительно и не отрицательно полуопределена), значит, критерий выпуклости нарушен уже в этой единственной точке, и функция $L(w_1, w_2)$ не выпукла. Точка $(0,0)$ — это ровно седловая точка в смысле университетского урока 213: вдоль одних направлений функция в этой точке ведёт себя как минимум, вдоль других — как максимум. Это не какой-то экзотический пример, а миниатюрная модель того, что происходит в любой многослойной нейросети: там, где слои перемножаются или комбинируются нелинейно, гессиан функции потерь почти неизбежно теряет положительную полуопределённость хотя бы в части точек пространства весов.

Почему это важно

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

Главная теорема: у выпуклой функции любой локальный минимум — глобальный

Интуиция

Представь, что ты стоишь в самой нижней точке своей окрестности внутри выпуклой «чаши». Может ли где-то ещё в этой же чаше найтись точка ниже той, где ты стоишь? Если бы такая точка существовала, то отрезок, соединяющий тебя с ней, по определению выпуклости обязан лежать не выше хорды между двумя значениями функции — а значит, двигаясь по этому отрезку от более низкой точки к тебе, значение функции должно было бы монотонно приближаться к твоему значению, оставаясь по пути строго ниже него на всех промежуточных точках, сколь угодно близких к тебе. Но тогда рядом с тобой, в твоей же собственной «локальной» окрестности, нашлись бы точки со значением функции ниже твоего — противоречие с тем, что ты стоишь в точке локального минимума. Форма чаши физически не оставляет места для второго, более глубокого дна где-то в стороне, отделённого от первого возвышенностью.

Формулировка теоремы

Теорема. Пусть $f: D \to \mathbb{R}$ — выпуклая функция на выпуклом множестве $D$. Если $x^*$ — точка локального минимума $f$ (то есть существует окрестность $x^*$, в которой $f(x^*) \le f(x)$ для всех $x$ из этой окрестности), то $x^*$ — точка глобального минимума $f$ на всём $D$ (то есть $f(x^*) \le f(x)$ для любого $x \in D$, а не только для соседей).

Доказательство от противного

Предположим обратное: пусть $x^*$ — локальный минимум, но существует точка $x' \in D$, для которой $f(x') < f(x^*)$. Рассмотрим отрезок между $x^*$ и $x'$: для любого $\lambda \in (0, 1]$ точка $z_\lambda = \lambda x' + (1-\lambda) x^*$ лежит в $D$ (множество выпукло), и по неравенству Йенсена

Поскольку $f(x') < f(x^*)$ по предположению, правая часть строго меньше, чем $\lambda f(x^*) + (1-\lambda) f(x^*) = f(x^*)$, для любого $\lambda \in (0,1]$. Значит, $f(z_\lambda) < f(x^*)$ для всех $\lambda \in (0,1]$. Но при $\lambda \to 0^+$ точка $z_\lambda$ стремится к $x^*$ — а значит, для достаточно малого $\lambda$ точка $z_\lambda$ попадает внутрь любой наперёд заданной окрестности $x^*$, в том числе и той, в которой $x^*$ был объявлен локальным минимумом. Мы нашли точку сколь угодно близко к $x^*$ со значением функции строго меньше $f(x^*)$ — это прямо противоречит тому, что $x^*$ был локальным минимумом. Значит, исходное предположение неверно: такой точки $x'$ не существует, и $x^*$ — глобальный минимум. $\blacksquare$

Примеры

Пример 1: линейная регрессия. MSE выпукла всегда (мы доказали это в прошлом разделе через $X^\top X \succeq 0$). Значит, по только что доказанной теореме любая точка, в которой градиентный спуск остановился с нулевым (или близким к нулю) градиентом, — это не просто «неплохое» решение по соседству, а гарантированно наилучшее из всех возможных наборов весов. Именно поэтому две реализации линейной регрессии — через градиентный спуск и через прямое решение нормальных уравнений $w^* = (X^\top X)^{-1} X^\top y$ — при отсутствии численных ошибок всегда сходятся к одному и тому же ответу, вне зависимости от того, с какой точки стартовал градиентный спуск.

Пример 2: логистическая регрессия. То же рассуждение применимо к кросс-энтропии: она выпукла (мы доказали это через $S = \operatorname{diag}(p_i(1-p_i)) \succeq 0$), поэтому решатель sklearn.linear_model.LogisticRegression при разных начальных приближениях, разных решателях (lbfgs, newton-cg, liblinear) и даже на разных запусках надёжно приходит к одним и тем же весам с точностью до численной погрешности — теорема гарантирует это заранее, ещё до запуска кода.

Пример 3: нейросеть — контрпример. Возьмём функцию потерь многослойной нейросети как функцию весов всех слоёв. Она не выпукла (мы это видели уже на минимальном примере $(w_1 w_2 - 1)^2$ — а в реальной сети таких «перемножений» и нелинейных композиций сотни тысяч). Теорема про локальный-минимум-равный-глобальному здесь просто неприменима: запусти обучение одной и той же архитектуры дважды с разной случайной инициализацией — стохастический градиентный спуск вполне может остановиться в двух разных точках с разными значениями функции потерь, скажем $0{,}23$ в одном запуске и $0{,}19$ в другом, и обе точки будут добросовестными локальными минимумами (или, что бывает чаще в многомерном пространстве, точками рядом с плоским седловым плато) — просто не глобальными. Более того, как показывает урок 213, в пространствах с миллионами параметров подавляющее большинство критических точек (мест, где градиент обнуляется) — это вообще не минимумы, а именно седловые точки: вероятность того, что все собственные значения гессиана окажутся неотрицательными одновременно в случайно устроенной невыпуклой задаче, экспоненциально падает с ростом числа параметров. Отсюда и вся инженерная возня вокруг обучения нейросетей: разумная инициализация весов, расписание скорости обучения (learning rate schedule), тёплые перезапуски (warm restarts), множественные прогоны и выбор лучшего по валидации — всё это компенсирует отсутствие теоретической гарантии, которую выпуклые модели получают бесплатно из одной теоремы.

Почему это важно

Эта теорема — не абстрактная красота, а причина, по которой целые классы моделей машинного обучения (линейная регрессия, логистическая регрессия, линейный SVM, Lasso, Ridge) называют «просто оптимизируемыми»: для них можно математически доказать, что обучение сойдётся к наилучшему возможному решению, а не просто понадеяться на удачу эксперимента. Понимание того, где проходит граница этой гарантии — выпуклая задача или нет, — прямо определяет, чего разумно ожидать от конкретной модели: воспроизводимости и математической гарантии оптимальности от одних моделей и практической, эмпирически подтверждаемой, но теоретически негарантированной работоспособности от других.

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

Интуиция

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

Определение и теорема

Определение. Функция $f$ строго выпукла, если неравенство Йенсена строгое: $f(\lambda x + (1-\lambda) y) < \lambda f(x) + (1-\lambda) f(y)$ для всех $x \ne y$ из области определения и всех $\lambda \in (0,1)$.

Теорема о единственности минимума. Если $f$ строго выпукла на выпуклом множестве $D$ и достигает на нём минимума, то точка минимума единственна.

Доказательство. Предположим, что существуют две различные точки глобального минимума $x_1 \ne x_2$ с $f(x_1) = f(x_2) = m$, где $m$ — минимальное значение функции. Возьмём $\lambda = 0{,}5$: по строгому неравенству Йенсена

Мы получили точку со значением функции строго меньше $m$ — но $m$ по предположению было минимальным значением. Противоречие. Значит, двух различных точек минимума быть не может. $\blacksquare$

Примеры

Пример 1: MSE при линейно независимых признаках. Если столбцы матрицы $X$ линейно независимы (признаки не дублируют друг друга и наблюдений не меньше, чем признаков), то $X^\top X$ положительно определена, MSE строго выпукла, и по только что доказанной теореме существует ровно один набор весов $w^*$, минимизирующий ошибку, — это и есть классический случай линейной регрессии с единственным решением $w^* = (X^\top X)^{-1} X^\top y$.

Пример 2: MSE при мультиколлинеарности — контрпример. Пусть в данных есть два абсолютно идентичных признака: столбец $X_1$ полностью совпадает со столбцом $X_2$ (например, «рост в сантиметрах» и «рост в сантиметрах», продублированный по ошибке при склейке датасетов). Тогда $X^\top X$ вырождена (имеет нулевое собственное значение вдоль направления $v = (1, -1, 0, \dots, 0)$, потому что $Xv = 0$), MSE выпукла, но не строго. Минимальное значение ошибки при этом всё ещё единственно (это гарантирует уже доказанная главная теорема — все локальные минимумы равны по значению), но сама точка минимума — нет: любое перераспределение общего веса между двумя идентичными признаками, при котором их сумма сохраняется, даёт одно и то же предсказание и одну и ту же ошибку. Получается целая прямая эквивалентных решений вместо одной точки.

Пример 3: Ridge-регрессия чинит проблему. Добавь к MSE регуляризационное слагаемое $L2$: $L_{\text{ridge}}(w) = \frac{1}{2n}\|y - Xw\|^2 + \frac{\lambda}{2}\|w\|^2$ с любым $\lambda > 0$. Гессиан такой функции — $\frac{1}{n}X^\top X + \lambda I$. Даже если исходная $X^\top X$ вырождена, добавление $\lambda I$ сдвигает все собственные значения матрицы вверх ровно на $\lambda > 0$ — а значит, итоговый гессиан положительно определён при любой матрице данных, без каких-либо условий на неё. Ridge-регуляризация строго выпукла всегда, и решение у неё всегда единственно — это не побочный эффект борьбы с переобучением, а прямое, математически точное следствие добавления квадратичного штрафа к гессиану.

Почему это важно

Строгая выпуклость — ответ на вопрос «а единственно ли решение вообще?», который отдельная от главной теоремы, но не менее практичная проблема. Мультиколлинеарность признаков — частая реальная ситуация (коррелирующие финансовые показатели, дублирующиеся по смыслу признаки после one-hot-кодирования, избыточные инженерные фичи) — превращает формально выпуклую, но не строго выпуклую задачу в задачу с бесконечным множеством одинаково хороших решений, что делает интерпретацию весов моделей ненадёжной (разные библиотеки или разные случайные перезапуски выдадут разный, но одинаково «правильный» набор коэффициентов). Осознанное добавление L2-регуляризации — это не только защита от переобучения, но и прямой инструмент восстановления строгой выпуклости и единственности решения.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Проверь неравенство Йенсена для $f(x) = x^2$ в точках $x=1$, $y=3$, $\lambda = 0{,}5$.

Задание 2: Докажи, что $f(x) = x^3$ не выпукла на всей числовой прямой, найдя явный контрпример к неравенству Йенсена.

Задание 3: Докажи выпуклость $f(x) = e^x$ через вторую производную.

Задание 4: Докажи выпуклость $f(x) = -\log(x)$ на области $x > 0$ через вторую производную. Где в машинном обучении используется эта функция?

Задание 5: Найди гессиан $f(x,y) = x^2 + y^2$ и определи его знакоопределённость.

Задание 6: Найди гессиан $f(x,y) = x^2 - y^2$ и определи, выпукла ли эта функция.

Задание 7: Функция $f(x) = x^4$ имеет $f''(0) = 0$. Означает ли это, что $x^4$ не строго выпукла?

Задание 8: Для данных $(x_1,y_1)=(1,2)$, $(x_2,y_2)=(2,5)$, $(x_3,y_3)=(3,6)$ и модели $y = wx$ запиши $L(w) = \sum_i (y_i - wx_i)^2$ и докажи выпуклость через $L''(w)$.

Задание 9: Проверь неравенство Йенсена для $f(x) = |x|$ в точках $x=-2$, $y=4$, $\lambda=0{,}25$.

Задание 10: Является ли константная функция $f(x) = 5$ выпуклой? Строго выпуклой?

Средние задания (11–20)

Задание 11: Докажи, что MSE в матричном виде $L(w) = \frac{1}{2n}\|y-Xw\|^2$ выпукла для любой матрицы $X$, вычислив гессиан.

Задание 12: Приведи пример матрицы $X$ (2 наблюдения, 2 признака), при которой $X^\top X$ вырождена, и объясни последствия для MSE.

Задание 13: Докажи, что гессиан кросс-энтропии логистической регрессии $\nabla^2 L(w) = \frac{1}{n}X^\top S X$, где $S=\operatorname{diag}(p_i(1-p_i))$, положительно полуопределён.

Задание 14: Сигмоида $\sigma(z)$ сама по себе не выпукла (выпукла при $z<0$, вогнута при $z>0$). Покажи, что log-loss как функция от логита $z$ всё же выпукла, вычислив $d^2L/dz^2$ для $L(z) = -\log\sigma(z)$ (случай $y=1$).

Задание 15: Рассмотрим упрощённую двухпараметрическую «нейросеть» $f(w_1,w_2)=(w_1w_2-1)^2$. Проверь, выпукла ли она, исследовав поведение вдоль пути $w_1=w_2=t$.

Задание 16: Вычисли гессиан $f(w_1,w_2) = (w_1w_2-1)^2$ в точке $(0,0)$ и классифицируй эту критическую точку.

Задание 17: Докажи главную теорему урока (локальный минимум выпуклой функции — глобальный) самостоятельно, восстановив шаги доказательства от противного.

Задание 18: Объясни, почему для строго выпуклой дифференцируемой функции условие $\nabla f(x^*)=0$ гарантирует, что $x^*$ — единственный глобальный минимум.

Задание 19: Покажи, что Ridge-функция $L_{\text{ridge}}(w)=\frac{1}{2n}\|y-Xw\|^2+\frac{\lambda}{2}\|w\|^2$ строго выпукла при любом $\lambda>0$, даже если $X^\top X$ вырождена.

Задание 20: Функция $f(x,y)=x^2$ (не зависит от $y$) выпукла на $\mathbb{R}^2$. Строго ли она выпукла? Сколько у неё точек глобального минимума?

Продвинутые задания (21–30)

Задание 21: Докажи, что сумма двух выпуклых функций $f+g$ выпукла.

Задание 22: Докажи, что если $f$ выпукла и $a \ge 0$ — константа, то $af$ тоже выпукла.

Задание 23: Докажи, что поточечный максимум двух выпуклых функций $h(x) = \max(f(x), g(x))$ выпукл.

Задание 24: Используя результат предыдущего задания, докажи, что хинж-лосс SVM $L(w) = \max(0,\ 1-yw^\top x)$ выпукл по $w$.

Задание 25: Докажи, что если $f$ выпукла на $\mathbb{R}^m$, то $g(w) = f(Aw+b)$ выпукла по $w$ для любой матрицы $A$ и вектора $b$ (композиция с аффинным преобразованием).

Задание 26: Функции $f(t)=t^2$ и $g(x)=x^2-4$ обе выпуклы. Проверь, выпукла ли их композиция $h(x)=f(g(x))=(x^2-4)^2$, вычислив $h''(x)$, и объясни, почему общее правило «композиция выпуклых функций выпукла» здесь не работает.

Задание 27: Своими словами объясни, почему композиция линейных слоёв с нелинейными функциями активации в многослойной нейросети почти неизбежно даёт невыпуклую функцию потерь, опираясь на результат заданий 25–26.

Задание 28: Выпуклость — достаточное, но не необходимое условие того, что «любой локальный минимум является глобальным». Объясни своими словами разницу и почему это важно для интерпретации современных исследований о ландшафте функции потерь глубоких сетей.

Задание 29: Для строго выпуклой функции $L(w) = 3w^2-12w+15$ найди минимум аналитически, затем сделай три шага градиентного спуска с $\alpha=0{,}1$, начиная с $w_0=0$, и убедись, что шаги монотонно приближаются к аналитическому минимуму.

Задание 30: Мини-модель «глубокой линейной сети»: два данных $(x_1,y_1)=(1,2)$, $(x_2,y_2)=(2,5)$, предсказание $\hat y = w_1w_2x$ (произведение двух весов вместо одного). Запиши $L(w_1,w_2)$ через $u=w_1w_2$, покажи, что она выпукла по $u$, но объясни, почему это не делает исходную функцию выпуклой по $(w_1,w_2)$.

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

Ошибка 1. Путают «выпуклую функцию» (график не выше хорды) с «выпуклым множеством» из прошлого урока (область без вмятин).

Как выглядит: фраза вида «эта задача выпуклая, потому что допустимая область — круг» без единого слова про саму оптимизируемую функцию.

Почему возникает: оба понятия называются одним словом «выпуклость» и тесно связаны через эпиграф, из-за чего кажется, что выпуклость множества автоматически что-то говорит о функции.

Как правильно: для выпуклости задачи оптимизации нужны оба условия одновременно — выпуклая функция потерь и выпуклое допустимое множество; выпуклость одного без другого гарантий не даёт.

Ошибка 2. Считают, что $f''(x) \ge 0$ в нескольких проверенных точках достаточно, чтобы объявить функцию выпуклой.

Как выглядит: «я подставил три значения $x$, везде вторая производная положительна — функция выпукла».

Почему возникает: по аналогии с проверкой гипотез на конечном наборе примеров, что нормально работает в программировании при тестировании кода, но не является математическим доказательством.

Как правильно: критерий требует $f''(x)\ge0$ для всех $x$ из области определения без исключения — это аналитическое утверждение, а не то, что можно подтвердить конечной выборкой точек; нужно либо доказать неравенство для произвольного $x$, либо привести общее алгебраическое выражение (как в примере с $X^\top X$).

Ошибка 3. Путают выпуклость с монотонностью — считают, что если функция где-то убывает, а где-то возрастает, она не может быть выпуклой.

Как выглядит: «$f(x)=x^2$ сначала убывает, потом возрастает — какая же это выпуклая функция, она же не монотонная».

Почему возникает: интуитивно кажется, что «стабильное» поведение функции должно означать одно направление изменения.

Как правильно: выпуклость — свойство кривизны (график не выше хорды), а не направления изменения; классический пример $x^2$ убывает на $(-\infty,0)$ и возрастает на $(0,+\infty)$, оставаясь при этом строго выпуклой на всей числовой прямой.

Ошибка 4. Считают, что «у функции только один минимум» (унимодальность) автоматически означает выпуклость.

Как выглядит: «график поднимается по обе стороны от единственной низшей точки — значит, функция выпуклая».

Почему возникает: геометрически унимодальный график интуитивно напоминает чашу, и разница между «унимодальность» и «выпуклость» кажется несущественной.

Как правильно: контрпример — $f(x)=\sqrt{|x|}$: у неё единственный минимум в точке $x=0$, но при $x>0$ вторая производная $f''(x) = -\tfrac{1}{4}x^{-3/2} < 0$ — функция вогнута на каждой из половин, то есть не выпукла, несмотря на единственный минимум. Унимодальность — необходимое, но не достаточное условие выпуклости.

Ошибка 5. Забывают, что определение выпуклой функции вообще требует, чтобы область определения была выпуклым множеством, и пытаются говорить о «выпуклости» функции на заведомо невыпуклой (например, состоящей из двух несвязных кусков) области.

Как выглядит: обсуждение выпуклости $f(x)=1/x$ на области $x \ne 0$ (объединение двух лучей) как единой функции на всей этой области.

Почему возникает: каждый отдельный кусок графика может выглядеть локально «выпукло устроенным», и не сразу очевидно, что само требование $\lambda x+(1-\lambda)y \in D$ вообще может не выполняться, если $x$ и $y$ взяты из разных кусков.

Как правильно: прежде чем проверять выпуклость функции, убедиться, что область определения — выпуклое множество в смысле прошлого урока; если нет — вопрос о выпуклости функции на всей такой области попросту некорректно поставлен, и стоит говорить только о выпуклости на каждом связном выпуклом куске отдельно.

Ошибка 6. Считают, что если около найденного решения нейросети локально «всё выглядит гладко и по-чашечьи», то это автоматически глобальный минимум.

Как выглядит: «лосс почти не меняется вокруг текущей точки, наверное, мы нашли лучшее решение».

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

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

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

• Функция $f$ выпукла на выпуклом множестве $D$, если для любых $x,y \in D$ и $\lambda \in [0,1]$ выполняется неравенство Йенсена $f(\lambda x+(1-\lambda)y) \le \lambda f(x)+(1-\lambda)f(y)$ — график лежит не выше любой хорды.

• Выпуклость функции эквивалентна выпуклости её надграфика (эпиграфа) как множества — прямой мост к прошлому уроку про выпуклые множества.

• Для дважды дифференцируемой функции одной переменной критерий выпуклости — $f''(x) \ge 0$ на всём интервале; для функции многих переменных — положительная полуопределённость гессиана $\nabla^2 f(x) \succeq 0$ в каждой точке области определения.

• MSE линейной регрессии всегда выпукла, поскольку её гессиан $\frac{1}{n}X^\top X$ положительно полуопределён при любой матрице данных $X$; кросс-энтропия логистической регрессии выпукла по той же логике, через взвешенную матрицу Грама $X^\top \operatorname{diag}(p_i(1-p_i))X$.

• Главная теорема урока: у выпуклой функции любой локальный минимум является глобальным — доказывается от противного через движение по отрезку к предполагаемой более низкой точке.

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

• Строгая выпуклость (строгое неравенство Йенсена) гарантирует единственность точки минимума, если она существует; обычная (нестрогая) выпуклость гарантирует лишь единственность минимального значения, но не точки.

• Мультиколлинеарность признаков делает MSE выпуклой, но не строго выпуклой (бесконечно много эквивалентных решений); добавление L2-регуляризации (Ridge) восстанавливает строгую выпуклость и единственность решения при любых данных.

• Композиция аффинного преобразования с выпуклой функцией сохраняет выпуклость, сумма и поточечный максимум выпуклых функций тоже выпуклы, а вот произвольная композиция двух выпуклых функций — нет; именно нелинейные композиции слоёв делают функцию потерь многослойной нейросети невыпуклой.

• Функции потерь многослойных нейросетей типично невыпуклы, и их критические точки в высокоразмерном пространстве весов чаще оказываются седловыми точками, чем истинными локальными минимумами.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок напрямую опирается на прошлый урок 277 про выпуклые множества: сама область определения выпуклой функции обязана быть выпуклым множеством, а эпиграф функции связывает оба понятия напрямую. Не менее важен университетский урок 213 «Экстремумы функций нескольких переменных» — именно там впервые появился гессиан и критерий положительной/отрицательной определённости для классификации отдельной критической точки как минимума, максимума или седла. Сегодняшний урок использует тот же самый математический аппарат, но с принципиально иной задачей: не классифицировать одну точку, а проверить свойство всей функции сразу — гессиан должен быть положительно полуопределён не в одной точке, а в каждой точке области определения без исключения. Понимание того, что такое седловая точка из урока 213, напрямую объясняет, почему невыпуклые функции потерь нейросетей в примерах этого урока ведут себя именно так.

Что изучить дальше

Следующий урок 279 разбирает условия оптимальности Каруша — Куна — Таккера (KKT) — обобщение условия «градиент равен нулю» на задачи с ограничениями; для выпуклых задач KKT-условия оказываются не просто необходимыми, а достаточными для глобальной оптимальности — ровно благодаря теореме, доказанной сегодня. Позже, в уроке 285 про градиентный спуск, ты увидишь количественные оценки скорости сходимости, которые для выпуклых (и тем более строго выпуклых) функций формулируются и доказываются намного точнее и увереннее, чем для произвольных невыпуклых функций потерь.

Где это нужно в жизни

🤖 Классическое машинное обучение. Линейная регрессия, логистическая регрессия, линейный SVM (через хинж-лосс из задания 24), Lasso и Ridge — все эти модели обучаются надёжно и воспроизводимо именно потому, что их функции потерь выпуклы; это прямо объясняет, почему scikit-learn для этих моделей не требует случайных перезапусков «на удачу».

🧠 Глубокое обучение. Понимание невыпуклости функции потерь многослойных сетей объясняет всю инженерную культуру вокруг их обучения: подбор инициализации весов, батч-нормализация (batch normalization), планировщики скорости обучения (learning rate), несколько прогонов обучения с выбором лучшего по валидации — всё это компенсирует отсутствие теоретической гарантии, которую выпуклые модели получают бесплатно.

💰 Экономика и финансы. Портфельная оптимизация Марковица формулируется как выпуклая квадратичная задача (минимизация дисперсии портфеля при ограничении на ожидаемую доходность) именно для того, чтобы гарантировать единственное, надёжно вычислимое оптимальное распределение активов.

🏭 Исследование операций. Многие задачи распределения ресурсов и планирования из урока 276 про введение в оптимизацию надёжно решаются в промышленных масштабах именно потому, что их удаётся сформулировать как выпуклые задачи — тогда даже очень большая по размеру задача остаётся вычислительно предсказуемой.

Интересные факты

• Йохан Йенсен, чьё имя носит неравенство, лежащее в основе всей теории выпуклых функций, не был профессиональным университетским математиком — он проработал всю карьеру инженером и техническим директором Копенгагенской телефонной компании, а свою знаменитую статью 1906 года написал как математик-любитель в свободное от основной работы время.

• Современные библиотеки дисциплинированного выпуклого программирования (например, CVXPY) умеют автоматически доказывать выпуклость сложного составного выражения функции потерь, просто проверяя его структуру по конечному набору правил композиции — тем самым правилам «сумма выпуклых выпукла», «максимум выпуклых выпукл», «аффинная композиция сохраняет выпуклость», которые ты доказал в заданиях 21–25, — без символьного вычисления единой производной.

• Эмпирическое и теоретическое наблюдение из статьи Dauphin, Pascanu, Gulcehre, Cho, Ganguli и Bengio (2014), разобранной подробнее в университетском уроке 213, состоит в том, что в задачах невыпуклой оптимизации высокой размерности (как обучение глубоких сетей) вероятность того, что случайно найденная критическая точка окажется истинным локальным минимумом (а не седловой точкой), экспоненциально убывает с ростом числа параметров — просто из комбинаторики знаков собственных значений гессиана.

• В начале 1990-х годов метод опорных векторов Владимира Вапника отчасти обязан своей популярностью тому, что был сознательно сконструирован как выпуклая задача квадратичного программирования — в противовес нейросетям того времени, которые считались капризными и ненадёжными в обучении именно из-за невыпуклости; исторический парадокс в том, что полвека спустя те же самые невыпуклые нейросети вернулись на первый план благодаря вычислительной мощности и инженерным приёмам, компенсирующим отсутствие теоретических гарантий.

Лайфхаки

• Если нужно быстро проверить выпуклость незнакомой или самописной функции потерь без вычисления производных вручную, просто просэмплируй много случайных пар точек $x,y$ и случайных $\lambda \in [0,1]$ и проверь неравенство Йенсена численно — единственное найденное нарушение сразу доказывает невыпуклость, хотя отсутствие нарушений на конечной выборке доказательством выпуклости, конечно, не является.

• Для проверки выпуклости многомерной функции потерь вычисли собственные значения её гессиана численно в нескольких случайных точках (например, через автоматическое дифференцирование и numpy.linalg.eigvalsh); хотя бы одно отрицательное собственное значение хоть в одной точке — однозначное доказательство невыпуклости всей функции.

• Держи в голове маленький «свод правил» из заданий 21–25: сумма выпуклых выпукла, неотрицательная константа умноженная на выпуклую — выпукла, максимум выпуклых выпукл, аффинная композиция с выпуклой функцией сохраняет выпуклость. Эти правила позволяют доказать выпуклость сложной составной функции потерь за несколько строк, вместо вычисления гессиана целиком с нуля.

• При проектировании собственной функции потерь для новой задачи старайся сначала проверить, можно ли обойтись выпуклым суррогатом (квадратичная ошибка, логистическая/кросс-энтропийная ошибка, хинж-лосс) — обучение станет предсказуемым и воспроизводимым; если без нелинейной сети никак не обойтись, заранее закладывай в план эксперимента несколько прогонов с разной инициализацией и выбор лучшего по валидации именно потому, что теоретической гарантии единственного результата у тебя не будет.

• Добавляй L2-регуляризацию не только как защиту от переобучения, но и как общий рецепт от вырожденного, не положительно определённого гессиана в любой задаче наименьших квадратов — она гарантированно восстанавливает строгую выпуклость и единственность решения при любых данных, включая мультиколлинеарные признаки.

• Если два, казалось бы, идентичных запуска обучения «выпуклой» модели вдруг дают заметно разные результаты — в первую очередь подозревай не случайность, а либо численную неустойчивость близкой к вырожденной матрицы $X^\top X$, либо случайно добавленный невыпуклый член в функцию потерь (например, нелинейное преобразование весов): теорема этого урока обещает одинаковый результат для истинно выпуклой задачи, поэтому расхождение — сигнал искать ошибку, а не «шум эксперимента».

Выпуклость — это, пожалуй, самая практичная теорема из всех, что встретятся тебе в курсе оптимизации: она не просто описывает красивую геометрическую форму, а буквально проводит границу между моделями, которые обучаются с математической гарантией, и моделями, которые обучаются на честном слове инженерной практики. Каждый раз, когда ты в следующий раз запустишь LogisticRegression().fit() и получишь один и тот же результат на любом железе и с любой случайной инициализацией, — вспомни, что за этой скучной воспроизводимостью стоит ровно та теорема, которую ты только что доказал сам. А каждый раз, когда придётся перезапускать обучение нейросети с новым случайным зерном (random seed) в надежде на чуть лучший результат, — будешь точно понимать, почему это вообще нужно делать, и что именно из-за отсутствия делает эту практику необходимой.