Я. Гудфеллоу, И. Бенджио, А. Курвилль

ошибку превышения
J
(
θ
) – min
θ
J
(
θ
), т. е. величину, на которую текущая функция 
стоимости превышает минимально возможную стоимость. При применении СГС 
к выпуклой задаче ошибка превышения равна 
O
(1/
√
_
k
) после 
k
итераций, тогда как 
в строго выпуклом случае она составляет 
O
(1/
k
). Эти границы нельзя улучшить без 
дополнительных предположений. Теоретически у пакетного градиентного спуска 
скорость сходимости должна быть выше, чем у стохастического. Но из неравенства 
Крамера–Рао (Crame
�
r, 1946; Rao, 1945) следует, что ошибка обобщения не может 
убывать быстрее, чем 
O
(1/
k
). В работе Bottou and Bousquet (2008) утверждается, что 
в таком случае в задачах машинного обучения не имеет смысла искать алгоритм опти-
мизации, который сходится быстрее, чем 
O
(1/
k
), – более быстрая сходимость, скорее 
всего, приведет к переобучению. Кроме того, асимптотический анализ игнорирует 
многие преимущества стохастического градиентного спуска с небольшим числом 
шагов. На больших наборах способность СГС быстро достигать прогресса на началь-
ной стадии после обсчета небольшого числа примеров перевешивает его медленную 
асимптотическую сходимость. Большинство описываемых далее алгоритмов облада-
ет практически важными достоинствами, которые скрыты за постоянным множите-

---

Основные алгоритмы 

255
лем в асимптотической оценке 
O
(1/
k
). Можно также попытаться найти компромисс 
между пакетным и стохастическим градиентным спусками, постепенно увеличивая 
размер мини-пакета в процессе обучения.
Дополнительные сведения о СГС см. в работе Bottou (1998).