Изучение градиентного спуска с ограниченными ошибками градиента

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

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

Как влияет на ошибку сходимости градиентный спуск с приближенными градиентами с ограниченными ошибками?

Это крутая проблема, над которой стоит подумать, с несколькими потенциальными областями полезности! Для тех, кто в восторге от этого материала, я расскажу о своем анализе и доказательстве ошибки сходимости градиентного спуска в этой ситуации с особенно хорошей целевой функцией. Время погрузиться в математику!

Итак, сначала давайте взглянем на рассматриваемый подход рекурсивного градиентного спуска. Рассмотрим метод наискорейшего спуска с ограниченной ошибкой:

где s — положительный постоянный размер шага, ε_k — член ошибки, удовлетворяющий ‖ε_k‖≤ δ для всех k, а f — положительно определенная квадратичная форма, определяемая как

Затем определим параметр q как

и предположим, что q ‹ 1. Используя описанный выше подход градиентного спуска, я покажу, что для всех k мы можем ограничить расстояние между k-й итерацией и локальным оптимумом следующим образом:

где x_0 — начальная точка последовательности итераций, а x* — локальные оптимумы. Я докажу этот результат, сначала доказав две полезные леммы, а затем используя их для доказательства основного результата.

Лемма 1

Учитывая значение 0 ≤ c ‹ 1 и что

мы можем найти границу для ‖x_k - x*‖, чтобы она была

Доказательство

Лемма 2

Для некоторой симметричной положительно определенной матрицы A и положительного скаляра s выполняется следующее неравенство:

Доказательство

Напомним, что некоторая положительно определенная квадратная матрица A = U^T Λ U, где U — унитарная матрица собственных векторов, а Λ — диагональная матрица с положительные собственные значения. Напомним также, что для матричной 2-нормы некоторой матрицы B имеем

После этого мы можем продолжить доказательство, выполнив следующие шаги:

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

Чтобы прийти к нашему окончательному результату, мы воспользуемся некоторыми типичными аналитическими неравенствами, которые дадут нам возможность использовать лемму 1 и лемму 2. С учетом сказанного мы можем продолжить это окончательное доказательство следующим образом:

Поскольку мы предполагаем, что s выбраны достаточно малыми, чтобы q ‹ 1, мы можем использовать лемму 1, чтобы дополнительно показать, что

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

В любом случае, теперь, когда теоретическая часть сделана, мы можем двигаться дальше, чтобы увидеть, насколько хорошо это неравенство соблюдается по сравнению с реальными численными экспериментами.. пришло время посчитать некоторые цифры!

Численные результаты

Я подумал, что было бы неплохо провести численный эксперимент, чтобы увидеть, как оценка соотносится со сходимостью на практике. Для проведения этого эксперимента вектор шума ε был добавлен к точному градиенту квадратичной формы для случайного положительно определенного Q, такого что ‖ε‖ ≤ δ для некоторого заданного δ ›0. Было запущено несколько последовательностей с разными начальными случайными начальными значениями, и приведенный ниже график представляет собой визуализацию результатов сходимости по отношению к границе.

Судя по приведенному выше рисунку, похоже, что привязка работает отлично! Это, конечно, немного консервативно по сравнению с реальными экспериментами, но это нормально. Следует отметить следующие наблюдения. При q → 1 связанный член, не зависящий от k в неравенстве, становится довольно большим, и сходимость члена q^k к 0 замедляется. Это означает, что спектр sQ находится в пределах единичного шара с центром вокруг значения 1 и что экстремальные значения s λ_{min} и s λ_{max} находятся вблизи границы этого шара. q → 1 также означает, что мы приближаемся к ситуации, когда мы будем расходиться по мере того, как число итераций приближается к бесконечности, поэтому имеет смысл, что вещи будут более ограничены и сходятся медленнее, когда q близко к 1.

Вывод

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

На основе статьи, первоначально опубликованной на https://christianjhoward.me 15 марта 2018 г.