Стохастический Градиентный Спуск (SGD) имеет достаточно простую запись:
Здесь — это некоторая аппроксимация градиента целевой функции в точке , называемая стохастическим градиентом (или просто стох. градиентом), — это размер шага (stepsize, learning rate) на итерации . Для простоты мы будем считать, что для всех . Обычно предполагается, что стох. градиент является несмещённой оценкой при фиксированном : .
Доказательство сходимости
Зададимся следующим вопросом: с какой скоростью и в каком смысле SGD сходится к решению и сходится ли? Во-первых, как и во многих работах по стохастической оптимизации, нас будет интересовать сходимость метода в среднем, т.е. оценки на или , где — решение задачи (для простоты будем считать, что оно единственное).
Во-вторых, чтобы SGD сходился в указанном смысле, необходимо ввести дополнительные предположения. Действительно, например, если дисперсия стох. градиента не ограничена , то и никаких разумных гарантий доказать не удаётся. Поэтому дополнительно к несмещённости часто предполагается, что дисперсия равномерно ограничена: предположим, что существует такое число , что для всех выполнено
Данное предположение выполнено, например, для задачи логистической регрессии (поскольку в данной задаче норма градиентов слагаемых ограничена), но в то же время является весьма обременительным. Его можно заменить на более реалистичные предположения, что мы немного затронем далее. Однако при данном предположении анализ SGD является очень простым и полезным для дальнейших обобщений и рассуждений.
Для простоты везде далее мы будем считать, что функция является -гладкой и -сильно выпуклой, т.е. для всех выполнены неравенства
Теорема. Предположим, что является -гладкой и -сильно выпуклой, стох. градиент имеет ограниченную дисперсию, и размер шага удовлетворяет . Тогда для всех выполняется неравенство
Доказательство. Используя выражение для , мы выводим
Далее мы берём условное матожидание от левой и правой частей и получаем:
Следующий шаг в доказательстве состоит в оценке второго момента . Используя предположение об ограниченности дисперсии стох. градиента, мы выводим:
Чтобы оценить сверху , мы используем следующий факт, справедливый для любой выпуклой -гладкой функции (см. книгу Ю. Е. Нестерова "Методы выпуклой оптимизации", 2010):
Беря в этом неравенстве , и используя , получаем
Далее мы подставляем эту оценку в выражение для :
Остаётся оценить скалярное произведение в правой части неравенства. Это можно сделать, воспользовавшись сильной выпуклостью функции : из
следует
Используя это неравенство в выведенной ранее верхней оценке на , мы приходим к следующему неравенству:
где в последнем неравенстве мы воспользовались неотрицательностью , что следует из и . Чтобы получить результат, заявленный в теореме, нужно взять полное мат. ожидание от левой и правой частей полученного неравенства (воспользовавшись при этом крайне полезным свойством условного мат. ожидания — tower property: )
а затем, применяя это неравенство для , , , , получим
что и требовалось доказать.
Данный результат утверждает, что SGD с потоянным шагом сходится линейно к окрестности решения, радиус которой пропорционален . Отметим, что чем больше размер шага , тем быстрее SGD достигает некоторой окрестности решения, в которой продолжает осциллировать. Однако чем больше размер шага, тем больше эта окрестность. Соответственно, чтобы найти более точное решение, необходимо уменьшать размер шага в SGD. Этот феномен хорошо проиллюстрирован здесь.
Теорема выше доказана при достаточно обременительных предположениях: мы предположили, что функция является сильно выпуклой, -гладкой и стох. градиент имеет равномерно ограниченную дисперсию. В практически интересных задачах данные условия (в данном виде) выполняются крайне редко. Тем не менее, выводы, которые мы сделали из доказанной теоремы, справедливы для многих задач, не удовлетворяющих введённым предположениям (во многом потому, что указанные свойства важны лишь на некотором компакте вокруг решения задачи, что в свою очередь не так и обременительно).
Более того, если мы сделаем немного другое предположение о стохастических градиентах, то сможем покрыть некоторые случаи, когда дисперсия не является равномерно ограниченной на всём пространстве. Предположим теперь, что , где просэмплировано из некоторого распределения независимо от предыдущих итераций, и является выпуклой и -гладкой для всех (данное предположение тоже можно ослабить, но для простоты изложения остановимся именно на такой формулировке). Будем называть данные условия предположением о выпуклых гладких стохастчиеских реализациях. Они выполнены, например, для задач линейно регрессии и логистической регрессии.
В таком случае, для точек, сгенерированных SGD, справедливо, что SGD с потоянным шагом сходится линейно к окрестности решения, радиус которой пропорционален . Отметим, что чем больше размер шага , тем быстрее SGD достигает некоторой окрестности решения, в которой продолжает осциллировать. Однако чем больше размер шага, тем больше эта окрестность. Соответственно, чтобы найти более точное решение, необходимо уменьшать размер шага в SGD. Этот феномен хорошо проиллюстрирован здесь.
Теорема. Предположим, что является -гладкой и -сильно выпуклой, стохастчиеские реализации являются выпуклыми и гладкими, и размер шага удовлетворяет , где . Тогда для всех выполняется неравенство
где .
Доказательство. Аналогично предыдущей доказательству предыдущей теоремы, получаем
Поскольку является выпуклой и -гладкой, имеем (см. книгу Ю. Е. Нестерова "Методы выпуклой оптимизации", 2010):
Применяя это неравенство для , , получаем
где во втором переходе мы воспользовались стандартным фактом: для любых . Подставим полученное неравенство в выражение для , доказанное ранее:
Остаётся оценить скалярное произведение в правой части неравенства. Это можно сделать, воспользовавшись сильной выпуклостью функции : из
следует
Используя это неравенство в выведенной ранее верхней оценке на , мы приходим к следующему неравенству:
где в последнем неравенстве мы воспользовались неотрицательностью , что следует из и . Действуя по аналогии с доказательством предыдущей теоремы, получаем требуемый результат.
Выводы, которые можно сделать из данной теоремы, очень похожи на те, что мы уже сделали из прошлой теоремы. Главные отличия заключаются в том, что может быть гораздо больше , т.е. максимальный допустимый размер шага в данной теореме может быть гораздо меньше, чем в предыдущей. Однако размер окрестности теперь зависит от дисперсии стох. градиента в решении , что может быть значительно меньше .
Рассмотрим важный частный случай — задачи минимизации суммы функций:
Обычно имеет смысл функции потерь на -м объекте датасета. Предположим, что — выпуклая и -гладкая функция. Тогда выполняется предположение о выпуклых гладких стохастчиеских реализациях: действительно, достаточно задать как случайное число из , имеющее равномерное распределение. Тогда справедлив результат предыдущей теоремы с и .
Для любого можно выбрать шаг в SGD следующим образом:
где . Тогда из доказанного выше результата следует (см. Лемму 3 из статьи С. Стиха), что после итераций
Таким образом, чтобы гарантировать , SGD требуется
итераций/подсчётов градиентов слагаемых. Чтобы гарантировать то же самое, градиентному спуску (GD) необходимо сделать
подсчётов градиентов слагаемых, поскольку каждая итерация GD требует подсчётов градиентов слагаемых (нужно вычислять полный градиент ). Можно показать, что , поэтому в худшем случае полученная оценка для SGD заведомо хуже, чем для GD. Однако в случае, когда , однозначного вывода сделать нельзя: при большом может доминировать первое слагаемое в оценке сложности SGD, поэтому в таком случае SGD будет доказуемо быстрее, чем GD (если пренебречь логарифмическими множителями).
Иными словами, чтобы достичь не очень большой точности решения, выгоднее использовать SGD, чем GD. В ряде ситуаций небольшой точности вполне достаточно, но так происходит не всегда. Поэтому возникает ествественный вопрос: можно ли так модифицировать SGD, чтобы полученный метод сходился линейно асимптотически к точному решению (а не к окрестности как SGD), но при этом стоимость его итераций была сопоставима со стоимостью итераций SGD? Оказывается, что да и соответствующие методы называются методами редукции дисперсии.
Методы редукции дисперсии
Перед тем, как мы начнём говорить о методах редукции дисперсии, хотелось бы раскрыть подробнее причину того, что SGD не сходится линейно асимптотически к точному решению. Мы рассмотрели анализ SGD в двух предположениях, и в обоих случаях нам требовалось вывести некоторую верхнюю оценку на второй момент стох. градиента, т.е. на . В обоих случаях эта оценка содержала некоторый константный член ( или — зависит от рассматриваемого предположения), который потом возникал и в финальной оценке на , препятствуя тем самым линейно сходимости метода. Конечно, это рассуждение существенно опирается на конкретный способ анализа метода, а потому не является строгим объяснением, почему SGD не сходится линейно.
Однако важно отметить, что оценка на достаточно точно отражает поведение метода вблизи решения: даше если точка оказалась по какой-то причине близка к решению (или даже просто совпала с решением), то и, в частности, будут порядка или . Следовательно, при следующем шаге метод с большой вероятностью отдалится от/выйдет из решения, поскольку или .
Из приведённых выше рассуждений видно, что дисперсия стох. градиента мешает методу сходится линейно к точному решению. Поэтому хотелось бы как-то поменять правило вычисления стох. градиента, чтобы выполнялись 3 важных свойства: (1) новый стох. градиент должен быть не сильно дороже в плане вычислений, чем подсчёт стох. градиента в SGD (градиента слагаемого), (2) новый стох. градиент должен быть несмещённой оценкой полного градиента , и (3) дисперсия нового стох. градиента должна уменьшаться в процессе работы метода. Например, можно рассмотреть следующий стох. градиент:
где выбирается случайно равновероятно из множества и . В таком случае, будет выполнено свойство (2) из списка выше. Чтобы достичь желаемой цели, необходимо как-то специфицировать выбор случайного вектора . Исторически одним из первых способов выбора был , где точка обновляется раз в итераций:
Данный метод называется Stochastic Variance Reduced Gradient (SVRG). Данный методы был предложен и проанализирован в NeurIPS статье Джонсона и Жанга в 2013 году. Теперь же убедимся, что метод удовлетворяет всем трём отмеченным свойствам. Начнём с несмещённости:
Далее, вычисление подразумевает 2 подсчёта градентов слагаемых при и подсчёта градентов слагаемых при . Таким образом, за последователльных итераций SVRG происходит вычисление градиентов слагаемых, в то время как SGD требуется подсчётов градиентов слагаемых. Если (стандартный выбор параметра ), то итераций SVRG лишь в 3 раза дороже, чем итераций SGD. Иными словами, в среднем итерация SVRG не сильно дороже итерации SGD.
Наконец, если мы предположим, что метод сходится (а он действительно сходится, см., например, доказательство вот тут), то получим, что , а значит и . Но тогда в силу Липшицевости градиентов для всех имеем:
а значит, дисперсия стремится к нулю.
Приведённые выше рассуждения не являются формальным доказательством сходимости метода, но частично объясняют, почему метод сходится и, самое главное, объясняют интуицию позади формул, задающих метод. Строгое доказательство можно прочитать вот тут. Мы же здесь приведём результат о сходимости немного другого метода — Loopless Stochastic Variance Reduced Gradient (L-SVRG), который был предложен в 2015 году и переоткрыт в 2019 году. Основное отличие от SVRG состоит в том, что точка теперь обновляется на каждой итерации с некоторой маленькой вероятностью :
Иными словами, L-SVRG имеет случайную длину цикла, в котором не обновляется. Вся интуиция и все наблюдения приведённые для SVRG выше, справедливы и для L-SVRG.
Можно доказать следующий результат.
Теорема. Предположим, что является -гладкой, -сильно выпуклой и имеет вид суммы, функции являются выпуклыми и -гладкими для всех , и размер шага удовлетворяет , где . Тогда для всех для итераций L-SVRG выполняется неравенство
где , .
Замечание. В частности, если и , то
Следовательно, чтобы гарантировать , L-SVRG требуется
итераций/подсчётов градиентов слагаемых (в среднем). Напомним, что чтобы гарантировать то же самое, градиентному спуску (GD) необходимо сделать
подсчётов градиентов слагаемых, поскольку каждая итерация GD требует подсчётов градиентов слагаемых (нужно вычислять полный градиент ). Можно показать, что , поэтому в худшем случае полученная оценка для L-SVRG не лучше, чем для GD. Однако в случае, когда , L-SVRG имеет сложность значительно лучше, чем GD (если пренебречь логарифмическими множителями).
В заключение этого раздела, хотелось бы отметить, что существуют и другие методы редукции дисперсии. Одним из самых популярных среди них является SAGA. В отличие от SVRG/L-SVRG, в методе SAGA хранится набор градиентов . Здесь точка обозначает точку, в которой в последний раз был подсчитан градиент функции до итерации . Формально это можно записать следующим образом:
Основное преимущество SAGA состоит в том, что не требуется вычислять полный градиент всей суммы по ходу работы метода, однако в начале требуется посчитать градиенты всех слагаемых (отмечаем здесь, что эта операция может быть гораздо дороже по времени, чем вычисление полного градиента) и, более того, требуется хранить векторов, что может быть недопустимо для больших датасетов. В плане теоретических гарантий SAGA и L-SVRG не отличимы.
Ниже приведён график с траекториями SGD (с постоянным шагом), L-SVRG и SAGA при решении задачи логистической регрессии. Как можно видеть из графика, SGD достаточно быстро достигает не очень высокой точности и начинает осциллировать вокруг решения. В то же время, L-SVRG и SAGA достигают той же точности медленнее, но зато не осциллируют вокруг решения, а продолжают сходится (причём линейно).
Сравнение работы SGD, L-SVRG и SAGA при решении задачи логистической регрессии на датасете gisette из библиотеки LIBVSM.
