Когда гауссовский шум портит состояние Оракула.
Введение
В этой статье мы обсудим историю о набирающей популярность алгоритмической фигуре: Градиентном спуске. Для непосвященных градиентный спуск — это предпочтительный инструмент для волшебников машинного обучения, пытающихся понять и укротить темные искусства глубокого обучения, хотя он также находит применение в более простых областях, таких как линейная регрессия и тангенциальные области оптимизации.
Градиентный спуск похож на туриста, спускающегося с горы, покрытой густым туманом. Человек не может видеть очень далеко перед собой, но он может локально чувствовать, где он стоит, какие направления самые крутые и, в конечном счете, в каком направлении ему следует сделать шаг вниз, чтобы спуститься с горы как можно быстрее. В классической оптимизации важным вопросом является понимание того, как быстро можно сойтись к подножию горы.
Человек будет блуждать вечно? Смогут ли они добраться до дна до того, как закончатся закуски?
Важные вопросы в дикой природе, чтобы быть уверенным. Но что, если мы сделаем эту ситуацию немного более захватывающей?
Предположим, что турист на горе самопроизвольно потерял сознание; возможно, они были ослеплены признанием красоты (или ужаса) больших языковых моделей и ChatGPT.
Но не все потеряно, потому что у них есть, казалось бы, всеведущий (и дружелюбный!) Оракул, говорящий в их разуме! И этот Оракул там, шепчет из пустоты, говоря им, в каком направлении они должны спуститься, чтобы выбраться из этой горы как можно быстрее. Загвоздка только в том, что на самом деле этот Оракул не дает совершенно точных советов... а выплевывает на несчастного путешественника шумное состояние.
Учитывая, что шум имеет точное нормальное представление и у нас есть дополнительная информация о геометрии горы, что мы можем сказать о том, где в конечном итоге окажется турист?
Сможет ли этот Оракул привести путешественника в безопасное место? Или будущее путешественников всегда безрадостно?
Анализ
Некоторые говорят, что это эра математиков, и хотя я определенно не один из них, я могу сказать, что любые задроты, которые являются мазохистами в деталях, вероятно, получат некоторое удовольствие, проведя математический анализ ситуации этого бедного туриста. Точная формулировка этой задачи описана в следующей постановке задачи:
Итак, в этой формулировке образ нашей функции f — это наша гора, и мы предполагаем, что она выпукла для простоты, то есть имеет только один отчетливый локальный минимум; это означает, что глобальный минимум является единственным локальным минимумом. Таким образом, у горы есть ровно одна точка, которую мы называем «дно».
Как упоминалось ранее, шум в совете Оракула нормально распределен со средним значением 0 и постоянной дисперсией. В конечном счете, мы хотим решить, как далеко нужно спуститься с горы каждый раз, когда Оракул сообщает путешественнику, в каком направлении нужно спуститься, чтобы мы спустились с горы как можно скорее. Кроме того, мы хотим увидеть, сможем ли мы на самом деле с уверенностью достичь абсолютного подножия горы.
Чтобы помочь нам понять это, мы проанализируем ожидаемое расстояние между неизвестным местоположением подножия горы и i-м местоположением туриста, когда он спускается с горы. Полезная лемма, которую мы в конечном счете хотим доказать, сформулирована ниже:
Доказательство этой леммы проходит в два этапа: сначала находят удобную рекурсивную связь между текущей и предыдущей итерацией, затем по индукции показывают, что желаемая связь выполняется.
Теперь с помощью леммы 0.1 мы можем перейти к рассуждениям о размерах шагов α_i. В конечном счете, мы хотим уменьшить верхнюю границу итерационной ошибки до минимально возможного значения. Результат леммы 0.1 подразумевает, что мы хотим, чтобы все значения q_j были как можно меньше; точнее, мы хотим, чтобы все они были строго меньше 1 и как можно меньше. Прежде всего заметим, что если мы хотим добиться того, чтобы q_j ‹ 1, это означает, что мы должны выполнить оба приведенных ниже неравенства:
Мы можем добиться этого, сначала выбрав α_j достаточно маленьким, чтобы обе величины были меньше 1 без необходимости абсолютного значения. При этом обстоятельстве, поскольку a ≤ b, мы видим, что (1 - a * α_j) ≥ (1 - b * α_j). Таким образом, наибольший размер шага, который мы можем выбрать для α_j, который удовлетворяет различным неравенствам, равен α_j := 1/b. Поскольку это не зависит от индекса j, отсюда следует, что α_j := 1/b для всех j и, аналогично, все q_j := (1 - a/б). Эти наблюдения позволяют нам упростить ожидаемую ошибку нашей i-й итерации до:
Поскольку для всех действительных значений x мы знаем, что (1 - x) ≤ exp(-x), мы можем видеть, что ожидаемая ошибка как i стремится к бесконечности, будет сходиться к постоянной верхней границе (σ/a) экспоненциально быстро.
Это также говорит нам, возможно, к сожалению, что присущая Оракулу случайность может помешать нашему путешественнику в конечном итоге добраться до точного оптимального подножия горы. Это связано с тем, что все, что мы можем гарантировать, это то, что ожидаемое расстояние между туристом и минимальным местоположением будет не более (σ/a), а не не более 0, поскольку i уходит в бесконечность.
Комментарии и другие указания
Похоже, что наш путешественник может быть обречен из-за неточности Оракула, что, возможно, поставит этого путешественника в компанию каких-то древних греков. Я думаю, что голос в голове не всегда хорошо слушать..
Теперь, не обращая внимания на судьбу нашего путешественника, отметим, что этот анализ был сделан в ожидаемом смысле, но можно получить аналогичный результат, правильный с высокой вероятностью, но с большей ошибкой. Один из подходов состоит в том, чтобы изменить лемму 0.1 так, чтобы шум был ограничен некоторой предполагаемой константой, а затем использовать концентрацию нормальных случайных величин, чтобы показать, что с высокой вероятностью шум остается в пределах некоторого выбранного диапазона, что позволяет вам затем использовать модифицированную лемму 0.1. . Мы покажем, как это происходит, в следующем разделе.
Подтверждение судьбы путешественника с высокой вероятностью™
Для тех, кто работает с вероятностными или рандомизированными алгоритмами, стремление к гарантиям высокой вероятности часто является великой целью. В нашем контексте мы делаем это, сначала отметив следующую лемму, аналогичную лемме 0.1.
Лемма 0.2 очень похожа на лемму 0.1, за исключением того, что мы предполагаем, что величина шума детерминистически ограничена сверху некоторым параметром Δ. Мы не будем доказывать эту лемму, так как она очень похожа на работу, проделанную в лемме 0.1, но не стесняйтесь доказывать ее в качестве упражнения.
Теперь, чтобы использовать лемму 0.2, мы сначала заметим, что для одиночной субгауссовой случайной величины X с заместителем дисперсии σ² мы имеем это для фиксированной положительной константы γ, что
Оказывается, наша случайная величина ε ~ N(0, σ²) является субгауссовой, поэтому мы можем найти, что
Итак, если мы хотим гарантировать, что |ε| ≥ γ с вероятностью не выше δ, это означает, что мы должны выбрать γ равным
С этого момента мы предполагаем, что планируем запустить градиентный спуск не более чем для n итераций. При этом мы можем выбрать δ = 2/n², а это означает с вероятностью не менее 1–2/n, то есть с высокой вероятностью™, что наш шум будет удовлетворять |ε| ≤ 2σ sqrt(ln(n)) = ∆. Таким образом, по лемме 0.2 и выбирая все размеры шагов, как мы это делали ранее, мы находим, что с высокой вероятностью ошибка после i итераций равна
Таким образом, выбрав маршрут с высокой вероятностью, мы наблюдаем, что шар ошибок сойдется к немного большему радиусу, чем в нашем предыдущем анализе в ожидаемом случае. Конечно, это имеет смысл, потому что нам нужна более высокая уверенность в том, какую именно ошибку мы должны ожидать, а не ожидаемую ошибку, но немного прискорбно видеть, что это зависит от количества итераций, которые мы решили выполнить. Например, если n = 1 000 000 000, верхняя граница примерно в 9 раз больше, чем в анализе, который мы провели ранее для ожидаемого случая. Не страшно, учитывая значение для n... но и не идеально.
Короче говоря, путешественник обречен, с высокой вероятностью™.
Спасение путешественника с уменьшением дисперсии
А что, если бы мы захотели уменьшить радиус этой ошибки, чтобы спасти путешественника? Ну, мы могли бы настроить алгоритм так, чтобы мы запрашивали Oracle κ раз и усредняли результаты, используя вместо этого усредненный результат в градиентном спуске. Поскольку наш шум нормально распределен, усреднение κ независимых результатов на шаг градиентного спуска делает так, что каждая оценка градиента теперь имеет дисперсию (σ²/κ). Согласно нашему предыдущему результату, наша гарантия высокой вероятности ошибки становится равной
Таким образом, выбор κ = 4 ln(n) дает нам ту же гарантию ошибки с высокой вероятностью™, что и ожидаемый случай! Для n ≤ 1 000 000 000 это означает, что κ = 83, что может дать каждому шагу градиентного спуска заметно большую постоянную времени выполнения. Вы также можете сделать больше выборок для достижения точной допустимой ошибки τ (когда i стремится к бесконечности), где выбор κ = ln(n) (2σ/aτ) ² точно достигает этого результата. Очевидно, что выбор крошечного значения для τ может потребовать много запросов к Oracle и в некоторых ситуациях может оказаться нецелесообразным.
Тем не менее, если мы решим, что τ = (1/2)¹⁰⁰ является достаточно малой константой, чтобы достичь подножия горы, мы в конечном итоге обеспечим, чтобы турист мог достичь подножия горы, используя O( (σ/a)ln(n) ) Запросы Oracle на операцию градиентного спуска.. так что технически сублинейное количество запросов! Другими словами, путешественника можно (асимптотически) эффективно спасти с помощью Оракула!
Заключение
Таким образом, путешественник не был безнадежен, используя идею выборки для уменьшения дисперсии, но могли ли мы добиться большего? Точнее, можем ли мы использовать менее n ln(n) (2σ/aτ)² общих запросов Oracle за n итераций усредненного Oracle градиентный спуск и получить итерационную ошибку асимптотически не более τ?
Я оставляю это вам, читатель, чтобы попытаться улучшить результат. Прокомментируйте свой подход, если вам удастся это сделать! Давайте посмотрим, сможем ли мы сделать жизнь путешественника немного проще!
