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

При обучении модели мы пытаемся минимизировать среднее значение функций потерь модели по обучающим выборкам:

Для каждого i, f_i в приведенной выше сумме - это потери, понесенные обучающей выборкой iᵗʰ как функция вектора параметров модели w. Для задачи минимизации потерь мы используем варианты метода стохастического градиента: на шаге k мы случайным образом выбираем функцию f из {f_1, …, f_n}, и вычислим:

Существует множество вариантов метода, таких как мини-пакетирование, Ада-Град и Адам, но у всех них есть одна общая черта: каждая потеря f задается как «черный ящик» - ничего нет. предполагается, за исключением возможности вычислить его градиент.

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

Разминка - вид проксимальный

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

Давайте упростим приведенную выше формулу "волосатости". Синий член - это касательная, или приближение первого порядка на w_k, а красный член - это мера близости к w_k. Следовательно, согласно проксимальному виду,

на каждой итерации мы минимизируем функцию, которая балансирует между спуском по касательной и близостью к w_k .

Баланс между двумя конфликтующими силами определяется 1 / η - весом члена близости. Сумма касательной и члена близости дает «касательную параболу» в w_k, минимум которой является следующей итерацией.

Таким образом, интуитивно ближний вид интерпретирует шаг градиента как минимизатор касательной параболы, которая локально аппроксимирует нашу функцию потерь, как показано ниже. Чем больше η, тем более «плоская» парабола, и поэтому мы отдаляемся от нашей текущей итерации w_k.

Формально, чтобы убедиться, что приведенная выше формула действительно является замаскированным шагом градиента, давайте решим задачу минимизации. Взяв градиент w.r.t w члена внутри argmin и приравняв его к нулю, получаем:

Умножение обеих сторон на η и извлечение w восстанавливает шаг градиента.

Примечание: приблизительный взгляд на градиентный метод давно известен специалистам по оптимизации, и его можно найти в книге Бориса Поляка «Введение в оптимизацию» 1987 года.

Тепло - регуляризация

Касательная - это, конечно, разумное приближение функций, о которых мы ничего не знаем. Но что, если мы действительно что-то знаем? Можем ли мы заменить синюю часть (касательную) на лучшее приближение?

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

где lᵢ - (возможно, взвешенный) «чистый» убыток, к которому мы добавляем термин регуляризации. В этом случае мы могли бы аппроксимировать lᵢ его касательной, оставляя член регуляризации как есть. Зачем нам? Благодаря следующему интуитивно понятному практическому правилу:

Чем меньше мы приближаемся, тем больше информации о функции потерь сохраняется и используется, и, таким образом, получается лучший алгоритм.

Исходный шаг градиента в нашем примере заменен на

Посмотрим, сможем ли мы получить явную формулу w_ {k + 1}. Взяв градиент w.r.t w и приравняв его к нулю, получаем:

Извлекая w, получаем

Мы получили полностью новый алгоритм, который существенно отличается от метода стохастического градиента, применяемого непосредственно к потерям. Согласно нашему новому алгоритму, на каждой итерации мы применяем шаг стохастического градиента к «необработанным» потерям l, а затем делим результат на (2 η +1).

За пределами регуляризации L2

Что произойдет, если членом регуляризации будет не квадрат евклидовой нормы, а какая-то другая функция g? В явном виде потери равны

Ближайшая проблема становится

Получился хорошо известный проксимальный градиент. Чтобы реализовать на практике, нам нужна явная формула для следующей итерации w_ {k + 1}.

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

Следовательно, g должен быть «достаточно простым», чтобы можно было получить простую явную формулу, и поэтому эта схема применима только для таких «простых» функций g.

Дальнейшие темы

  • Другое приближение вместо касательной приводит к стабильному обучению - оно менее чувствительно к выбору размера шага и избавляет нас от дорогостоящей настройки размера шага. См. Пример [1].
  • Выход за рамки касательной параболы - с учетом неквадратичных условий близости. Примеры включают стохастический вариант известного алгоритма зеркального спуска [2], который выгоден для многих классов задач.

использованная литература

[1]: Хилал Аси, Джон Дучи (июль 2019 г.). Стохастические (приблизительные) методы проксимальной точки: сходимость, оптимальность и адаптивность. https://arxiv.org/abs/1810.05633

[2]: Амир Бек, Марк Тебулль (2003). Зеркальный спуск и методы нелинейного проецирования субградиентов для выпуклой оптимизации. https://www.sciencedirect.com/science/article/abs/pii/S0167637702002316