9.2. Градиентный спуск

9.2.1. Описание общей схемы алгоритма.

При градиентном спуске движение осуществляется непосредственно в направлении антиградиента, т. е. (напомним, что — единичная матрица размерности . Итерационная процедура таким образом принимает вид:

где

Перечислим несколько возможных способов выбора величины шага .

Обозначим направление минимизации. Существуют два основных способа, приводящих к снижению значения на каждом шаге и к сходимости итеративного процесса.

1. Зададимся некоторым . Дроблением шага добьемся того, чтобы

Поскольку всегда .

2. Длина шага определяется из условия

При таком выборе шага обычно говорят о «наискорейшем спуске». Экстремальная задача (9.7) чаще всего решается с помощью квадратичной аппроксимации по р.

Решение одномерной задачи минимизации вторым способом может оказаться чрезвычайно трудоемким. Дело может осложниться тем, что функция У (В) вдоль выбранного направления может быть мультимодальной. Поэтому первый способ нам кажется более предпочтительным. Описанные способы выбора шага могут применяться и в других методах минимизации (см. § 9.3-9.5).

Сравнение эффективности различных способов выбора длины шага применительно к задачам регрессии проведено в [159].

Алгоритмы типа (9.6) (см., например, [35, 107, 25]) обеспечивают при определенных ограничениях на функцию сходимость последовательности со скоростью геометрической прогрессии

В частности, такая скорость сходимости обеспечивается так называемой линейной сходимостью, при которой

где — длина вектора ; С и q — константы, определяемые видом .

Например, если помимо некоторых не очень существенных ограничений градиент удовлетворяет условию Липшица:

при всех и функция сильно выпукла с показателем

9.2.2. Замечание об эффективности алгоритма.

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

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

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