Перечислим несколько возможных способов выбора величины шага
.
Обозначим
направление минимизации. Существуют два основных способа, приводящих к снижению значения
на каждом шаге и к сходимости итеративного процесса.
1. Зададимся некоторым
. Дроблением шага добьемся того, чтобы
Поскольку
всегда
.
2. Длина шага определяется из условия
При таком выборе шага обычно говорят о «наискорейшем спуске». Экстремальная задача (9.7) чаще всего решается с помощью квадратичной аппроксимации по р.
Решение одномерной задачи минимизации вторым способом может оказаться чрезвычайно трудоемким. Дело может осложниться тем, что функция У (В) вдоль выбранного направления может быть мультимодальной. Поэтому первый способ нам кажется более предпочтительным. Описанные способы выбора шага могут применяться и в других методах минимизации (см. § 9.3-9.5).
Сравнение эффективности различных способов выбора длины шага применительно к задачам регрессии проведено в [159].
Алгоритмы типа (9.6) (см., например, [35, 107, 25]) обеспечивают при определенных ограничениях на функцию
сходимость последовательности
со скоростью геометрической прогрессии
В частности, такая скорость сходимости обеспечивается так называемой линейной сходимостью, при которой
где
— длина вектора
; С и q — константы, определяемые видом
.
Например, если помимо некоторых не очень существенных ограничений градиент удовлетворяет условию Липшица:
при всех
и функция
сильно выпукла с показателем
9.2.2. Замечание об эффективности алгоритма.
Одним из основных достоинств градиентного спуска является его простота. Однако реальная скорость его сходимости уменьшается при приближении
к точке
. Для функций овражного типа с сильно вытянутыми линиями уровня в окрестности
эффективность методов типа градиентного спуска особенно низка, так как обычно для таких функций
близко к нулю.
При решении статистических задач с помощью градиентного спуска приходится на заключительном этапе проводить дополнительные расчеты по отысканию оценок ковариационных матриц и прочих величин, описывающих статистические свойства оценок.
Обычно градиентный спуск целесообразно применять лишь на начальных этапах минимизации, используя найденные в результате сравнительно небольшого числа итераций величины
в качестве начального приближения для более сложных методов, обладающих большей скоростью сходимости.