Метод обратного отслеживания в математической оптимизации

Введение

Метод математической оптимизации

В (неограниченной) математической оптимизации, поиск с возвратом (backtracking line search) — это метод поиска вдоль прямой, предназначенный для определения величины шага в заданном направлении поиска. Для его применения необходимо, чтобы целевая функция была дифференцируема и известен её градиент. Метод заключается в начале с относительно большой оценки размера шага для движения вдоль направления поиска, и последующем итеративном уменьшении этого размера шага (то есть, "возврате") до тех пор, пока не будет наблюдаться снижение значения целевой функции, которое в достаточной мере соответствует ожидаемому снижению, исходя из размера шага и локального градиента целевой функции. Распространённым критерием остановки является условие Армихо — Гольдштейна. Поиск с возвратом обычно используется в методе градиентного спуска (GD), но может применяться и в других случаях. Например, его можно использовать с методом Ньютона, если матрица Гессе положительно определена.

Нижняя граница для показателей обучения

Это отвечает на вопрос, существует ли систематический способ найти положительное число, зависящее от функции f, точки и направления спуска, так, чтобы все шаги обучения (или скорости обучения) удовлетворяли условию Армихо. Когда , мы можем выбрать в порядке , где является локальной константой Липшица для градиента в окрестности точки (см. непрерывность по Липшицу). Если функция , то она приближается к гессиану функции в этой точке. Подробнее см. в [указание на источник].

Верхняя граница для показателей обучения

В той же ситуации, где , возникает интересный вопрос о том, насколько большими могут быть выбраны скорости обучения в условиях Армихо (то есть, когда нет ограничения на , как определено в разделе "Минимизация функции с использованием обратного поиска линии на практике"), поскольку большие скорости обучения, когда ближе к предельной точке (если она существует), могут ускорить сходимость. Например, в условиях Вольфа не упоминается , но вводится другое условие, называемое условием выпуклости. Показано, что существует верхняя граница для скоростей обучения, если требуется, чтобы построенная последовательность сходилась к невырожденной критической точке, см.: Скорости обучения должны быть ограничены сверху приблизительно следующим образом: Здесь H — гессиан функции в предельной точке, — ее обратная, а — норма линейного оператора. Таким образом, этот результат применим, например, при использовании обратного поиска линии для функций Морзе. Следует отметить, что в одномерном случае является числом, и, следовательно, эта верхняя граница сопоставима по порядку величины с нижней границей, указанной в разделе "Нижняя граница для скоростей обучения". С другой стороны, если предельная точка вырождена, то скорости обучения могут быть неограниченными. Например, модификация обратного поиска линии, известная как неограниченный градиентный спуск с возвратом (см.), позволяет скорости обучения быть вдвое меньше , где — константа. Эксперименты с простыми функциями, такими как , показывают, что неограниченный градиентный спуск с возвратом сходится значительно быстрее, чем базовая версия, описанная в разделе "Минимизация функции с использованием обратного поиска линии на практике".

Эффективность времени

Аргумент против использования поиска с возвратом (Backtracking line search), особенно в крупномасштабной оптимизации, заключается в том, что проверка условия Армихо вычислительно затратна. Существует способ (так называемый двусторонний поиск с возвратом) обойти это ограничение, обладающий хорошими теоретическими гарантиями и успешно протестированный на глубоких нейронных сетях, см. (Там же можно найти хорошие/стабильные реализации условия Армихо и его комбинации с популярными алгоритмами, такими как Momentum и NAG, на наборах данных Cifar10 и Cifar100). Можно заметить, что если последовательность сходится (что желательно при использовании итеративного метода оптимизации), то последовательность шагов обучения должна мало изменяться при достаточно большом n. Следовательно, при поиске оптимального шага обучения, если всегда начинать с текущего значения, можно потерять много времени, если последовательность остается далеко от нуля. Вместо этого, поиск следует начинать с текущего значения. Второе наблюдение состоит в том, что оптимальный шаг обучения может быть больше текущего, и, следовательно, следует допускать увеличение шага обучения (а не только уменьшение, как описано в разделе «Алгоритм»). Вот подробное описание алгоритма двустороннего поиска с возвратом: на шаге n

Установить набор и счетчик итераций . (Увеличить шаг обучения, если условие Армихо выполнено). Если , то, пока это условие и условие выполняются, многократно устанавливать и увеличивать j. (В противном случае, уменьшить шаг обучения, если условие Армихо не выполнено). Если же , то, пока условие не будет выполнено, многократно увеличивать и устанавливать .
Вернуть для шага обучения.
(В можно найти описание алгоритма, включающего пункты 1), 3) и 4), который до появления упомянутой статьи не был протестирован на глубоких нейронных сетях). Можно дополнительно сэкономить время, используя гибридный подход, сочетающий двусторонний поиск с возвратом и базовый алгоритм градиентного спуска. Эта процедура также имеет хорошие теоретические гарантии и демонстрирует хорошие результаты на практике. Грубо говоря, мы выполняем двусторонний поиск с возвратом несколько раз, а затем используем полученный шаг обучения без изменений, за исключением случаев, когда значение функции увеличивается. Вот как это делается. Заранее выбираем число и число , устанавливаем счетчик итераций j=0. На шагах используем двусторонний поиск с возвратом. На каждом шаге k в наборе : Установить . Если , то выбираем и (в этом случае используем шаг обучения без изменений). В противном случае, если , используем двусторонний поиск с возвратом. Увеличиваем k на 1 и повторяем. Увеличиваем j на 1.

Теоретическая гарантия (для спуска по наклонной полосе)

По сравнению с условиями Вулфа, которые более сложны, условие Армихо имеет более строгую теоретическую гарантию. Действительно, на сегодняшний день обратный поиск по линии и его модификации являются наиболее теоретически обоснованными методами среди всех алгоритмов численной оптимизации в отношении сходимости к критическим точкам и избежания седловых точек, см. ниже. Критические точки – это точки, в которых градиент целевой функции равен 0. Локальные минимумы являются критическими точками, но существуют критические точки, которые не являются локальными минимумами. Примером служат седловые точки. Седловые точки – это критические точки, в которых существует по крайней мере одно направление, вдоль которого функция достигает (локального) максимума. Следовательно, эти точки далеки от локальных минимумов. Например, если функция имеет хотя бы одну седловую точку, то она не может быть выпуклой. Важность седловых точек для алгоритмов оптимизации заключается в том, что при оптимизации в больших масштабах (то есть в пространствах высокой размерности) вероятность встретить больше седловых точек, чем минимумов, выше, см. Таким образом, хороший алгоритм оптимизации должен уметь избегать седловых точек. В контексте глубокого обучения седловые точки также распространены, см. Следовательно, для применения в глубоком обучении необходимы результаты для невыпуклых функций. Относительно сходимости к критическим точкам: например, если функция потерь является вещественно-аналитической функцией, то показано в , что сходимость гарантирована. Основная идея заключается в использовании неравенства Лояшевича, которым обладает вещественно-аналитическая функция. Для негладких функций, удовлетворяющих неравенству Лояшевича, вышеуказанная гарантия сходимости расширяется, см. В приведено доказательство того, что для любой последовательности, построенной методом обратного поиска по линии, предельная точка кластера (то есть предел одной подпоследовательности, если подпоследовательность сходится) является критической точкой. В случае функции с не более чем счетным числом критических точек (например, функции Морса) и компактными подуровнями, а также с градиентом, удовлетворяющим условию Липшица, при использовании стандартного градиентного спуска с шагом обучения <1/L (см. раздел "Стохастический градиентный спуск"), сходимость гарантирована, см., например, главу 12 в . Предположение о компактных подуровнях необходимо для обеспечения работы только с компактными множествами евклидова пространства. В общем случае, когда предполагается только, что имеет не более чем счетное число критических точек, сходимость гарантирована, см. В той же работе аналогично гарантируется сходимость для других модификаций обратного поиска по линии (таких как неограниченный градиентный спуск, упомянутый в разделе "Верхняя граница для шага обучения"), и даже если функция имеет несчетное число критических точек, все равно можно вывести некоторые нетривиальные факты о поведении сходимости. В стохастической постановке, при том же предположении, что градиент удовлетворяет условию Липшица, и используется более ограничительная версия схемы убывающего шага обучения (требующая, чтобы сумма шагов обучения была бесконечной, а сумма квадратов шагов обучения была конечной) (см. раздел "Стохастический градиентный спуск"), и, кроме того, функция строго выпукла, то сходимость устанавливается в известном результате , см. для обобщений на менее ограничительные версии схемы убывающего шага обучения. Ни один из этих результатов (для невыпуклых функций) пока не доказан для какого-либо другого алгоритма оптимизации. Относительно избежания седловых точек: например, если градиент функции потерь удовлетворяет условию Липшица и выбран стандартный градиентный спуск с шагом обучения <1/L, то при случайном выборе начальной точки (точнее, вне множества меры Лебега, равной нулю) построенная последовательность не будет сходиться к невырожденной седловой точке (доказано в ), и в более общем случае также верно, что построенная последовательность не будет сходиться к вырожденной седловой точке (доказано в ). При том же предположении, что градиент удовлетворяет условию Липшица и используется схема убывающего шага обучения (см. раздел "Стохастический градиентный спуск"), избежание седловых точек устанавливается в .

Compared with Wolfe's conditions, which is more complicated, Armijo's condition has a better theoretical guarantee. Indeed, so far backtracking line search and its modifications are the most theoretically guaranteed methods among all numerical optimization algorithms concerning convergence to critical points and avoidance of saddle points, see below. Critical points are points where the gradient of the objective function is 0. Local minima are critical points, but there are critical points which are not local minima. An example is saddle points. Saddle points are critical points, at which there are at least one direction where the function is (local) maximum. Therefore, these points are far from being local minima. For example, if a function has at least one saddle point, then it cannot be convex. The relevance of saddle points to optimisation algorithms is that in large scale (i. e. high dimensional) optimisation, one likely sees more saddle points than minima, see Hence, a good optimisation algorithm should be able to avoid saddle points. In the setting of deep learning, saddle points are also prevalent, see Thus, to apply in deep learning, one needs results for non convex functions. For convergence to critical points: For example, if the cost function is a real analytic function, then it is shown in that convergence is guaranteed. The main idea is to use Łojasiewicz inequality which is enjoyed by a real analytic function. For non smooth functions satisfying Łojasiewicz inequality, the above convergence guarantee is extended, see In , there is a proof that for every sequence constructed by backtracking line search, a cluster point (i. e. the limit of one subsequence, if the subsequence converges) is a critical point. For the case of a function with at most countably many critical points (such as a Morse function) and compact sublevels, as well as with Lipschitz continuous gradient where one uses standard GD with learning rate <1/L (see the section "Stochastic gradient descent"), then convergence is guaranteed, see for example Chapter 12 in Here the assumption about compact sublevels is to make sure that one deals with compact sets of the Euclidean space only. In the general case, where is only assumed to be and have at most countably many critical points, convergence is guaranteed, see In the same reference, similarly convergence is guaranteed for other modifications of Backtracking line search (such as Unbounded backtracking gradient descent mentioned in the section "Upper bound for learning rates"), and even if the function has uncountably many critical points still one can deduce some non trivial facts about convergence behaviour. In the stochastic setting, under the same assumption that the gradient is Lipschitz continuous and one uses a more restrictive version (requiring in addition that the sum of learning rates is infinite and the sum of squares of learning rates is finite) of diminishing learning rate scheme (see section "Stochastic gradient descent") and moreover the function is strictly convex, then the convergence is established in the well known result , see for generalisations to less restrictive versions of a diminishing learning rate scheme. None of these results (for non convex functions) have been proven for any other optimization algorithm so far. For avoidance of saddle points: For example, if the gradient of the cost function is Lipschitz continuous and one chooses standard GD with learning rate <1/L, then with a random choice of initial point (more precisely, outside a set of Lebesgue measure zero), the sequence constructed will not converge to a non degenerate saddle point (proven in ), and more generally it is also true that the sequence constructed will not converge to a degenerate saddle point (proven in ). Under the same assumption that the gradient is Lipschitz continuous and one uses a diminishing learning rate scheme (see the section "Stochastic gradient descent"), then avoidance of saddle points is established in .

Специальный случай: (стандартное) спуск стохастического градиента (SGD)

Хотя это тривиально упомянуть, если градиент функции потерь является липшицево-непрерывным, с константой Липшица L, то при выборе постоянной скорости обучения размера , мы имеем частный случай поиска линии с возвратом (для градиентного спуска). Однако эта схема требует хорошей оценки L, иначе, если скорость обучения слишком велика (по сравнению с 1/L), схема не гарантирует сходимость. Можно увидеть, что произойдет, если функция потерь является сглаживанием (вблизи точки 0) функции f(t) = |t|. Однако такая хорошая оценка затруднительна и трудоемка в больших размерностях. Кроме того, если градиент функции не является глобально липшицево-непрерывным, эта схема также не гарантирует сходимость. Например, это аналогично упражнению в , для функции потерь и для любой выбранной постоянной скорости обучения, последовательность, построенная этой схемой, не сходится к глобальному минимуму 0, начиная со случайной начальной точки. Если не учитывать требование, чтобы скорость обучения была ограничена 1/L, то эта схема использовалась гораздо раньше, по крайней мере с 1847 года, Коши, и может быть названа стандартным градиентным спуском (не путать со стохастическим градиентным спуском, который здесь обозначается как SGD). В стохастической постановке (например, в постановке мини-пакетов в глубоком обучении) стандартный градиентный спуск называется стохастическим градиентным спуском или SGD. Даже если функция потерь имеет глобально непрерывный градиент, хорошая оценка константы Липшица для функций потерь в глубоком обучении может быть невозможна или нежелательна, учитывая очень высокие размерности глубоких нейронных сетей. Следовательно, существует метод тонкой настройки скорости обучения при применении стандартного градиентного спуска или SGD. Один из способов — выбрать множество скоростей обучения из сетки, в надежде, что некоторые из них дадут хорошие результаты. (Однако, если функция потерь не имеет глобально липшицево-непрерывного градиента, то пример с выше показывает, что поиск по сетке не поможет.) Другой способ — так называемый адаптивный стандартный градиентный спуск или SGD, некоторые представители — Adam, Adadelta, RMSProp и т. д., см. статью о стохастическом градиентном спуске. В адаптивном стандартном градиентном спуске или SGD скорость обучения может меняться на каждом шаге итерации n, но иначе, чем при поиске линии с возвратом для градиентного спуска. Очевидно, что использование поиска линии с возвратом для градиентного спуска будет более затратным, поскольку необходимо выполнять поиск в цикле, пока не будет выполнено условие Армихо, в то время как для адаптивного стандартного градиентного спуска или SGD поиск в цикле не требуется. Большинство из этих адаптивных стандартных градиентных спусков или SGD не обладают свойством убывания , для всех n, в отличие от поиска линии с возвратом для градиентного спуска. Лишь немногие обладают этим свойством и имеют хорошие теоретические свойства, но они оказываются частными случаями поиска линии с возвратом или, в более общем смысле, условием Армихо. Первый случай — когда скорость обучения выбирается постоянной <1/L, как упоминалось выше, если можно получить хорошую оценку L. Второй — так называемая убывающая скорость обучения, используемая в известной работе , если функция снова имеет глобально липшицево-непрерывный градиент (но константа Липшица может быть неизвестна), и скорости обучения стремятся к 0.

While it is trivial to mention, if the gradient of a cost function is Lipschitz continuous, with Lipschitz constant L, then with choosing learning rate to be constant and of the size , one has a special case of backtracking line search (for gradient descent). This has been used at least in This scheme however requires that one needs to have a good estimate for L, otherwise if learning rate is too big (relative to 1/L) then the scheme has no convergence guarantee. One can see what will go wrong if the cost function is a smoothing (near the point 0) of the function f(t)=|t|. Such a good estimate is, however, difficult and laborious in large dimensions. Also, if the gradient of the function is not globally Lipschitz continuous, then this scheme has no convergence guarantee. For example, this is similar to an exercise in , for the cost function and for whatever constant learning rate one chooses, with a random initial point the sequence constructed by this special scheme does not converge to the global minimum 0. If one does not care about the condition that learning rate must be bounded by 1/L, then this special scheme has been used much older, at least since 1847 by Cauchy, which can be called standard GD (not to be confused with stochastic gradient descent, which is abbreviated herein as SGD). In the stochastic setting (such as in the mini batch setting in deep learning), standard GD is called stochastic gradient descent, or SGD. Even if the cost function has globally continuous gradient, good estimate of the Lipschitz constant for the cost functions in deep learning may not be feasible or desirable, given the very high dimensions of deep neural networks. Hence, there is a technique of fine tuning of learning rates in applying standard GD or SGD. One way is to choose many learning rates from a grid search, with the hope that some of the learning rates can give good results. (However, if the loss function does not have global Lipschitz continuous gradient, then the example with above shows that grid search cannot help.) Another way is the so called adaptive standard GD or SGD, some representatives are Adam, Adadelta, RMSProp and so on, see the article on Stochastic gradient descent. In adaptive standard GD or SGD, learning rates are allowed to vary at each iterate step n, but in a different manner from Backtracking line search for gradient descent. Apparently, it would be more expensive to use Backtracking line search for gradient descent, since one needs to do a loop search until Armijo's condition is satisfied, while for adaptive standard GD or SGD no loop search is needed. Most of these adaptive standard GD or SGD do not have the descent property , for all n, as Backtracking line search for gradient descent. Only a few has this property, and which have good theoretical properties, but they turn out to be special cases of Backtracking line search or more generally Armijo's condition The first one is when one chooses learning rate to be a constant <1/L, as mentioned above, if one can have a good estimate of L. The second is the so called diminishing learning rate, used in the well known paper by , if again the function has globally Lipschitz continuous gradient (but the Lipschitz constant may be unknown) and the learning rates converge to 0.

Резюме

В целом, поиск по линии с возвратом (и его модификации) – это метод, который легко реализовать, применим к очень широкому классу функций, обладает сильной теоретической гарантией (как в отношении сходимости к критическим точкам, так и в отношении избежания седловых точек) и хорошо работает на практике. Другие методы, обладающие хорошей теоретической гарантией, такие как убывающие скорости обучения или стандартный градиентный спуск со скоростью обучения <1/L, требуют, чтобы градиент целевой функции был липшицево непрерывным, и оказываются частным случаем поиска по линии с возвратом или удовлетворяют условию Армихо. Несмотря на то, что априори для применения этого метода требуется непрерывная дифференцируемость целевой функции, на практике его можно успешно применять и к функциям, непрерывно дифференцируемым на плотном открытом множестве, например, или .