Овраги и осцилляция

В вытянутой долине градиентный спуск зигзагует между стенками вместо движения по дну — это главная слабость метода.

Овраг (ravine) — вытянутая долина, где функция круто меняется в одном направлении и почти плоская вдоль другого; градиентный спуск в ней мучительно медленный.

Откуда берутся овраги

Если кривизна функции по разным осям сильно различается, чаша вытягивается в длинный жёлоб. Возьмём $f(x,y)=x^2+100y^2$. По оси $y$ стенки в $100$ раз круче, чем по $x$. Градиент почти всегда смотрит поперёк оврага (в крутую стенку), а не вдоль него (к минимуму). Поэтому спуск прыгает от стенки к стенке, едва-едва продвигаясь по дну.

Число обусловленности

Степень «оврагистости» измеряет число обусловленности гессиана — отношение наибольшей кривизны к наименьшей:

$$\kappa=\frac{\lambda_{\max}}{\lambda_{\min}}.$$

Для $f=x^2+100y^2$ это $\kappa=100/1=100$. Скорость градиентного спуска падает с ростом $\kappa$: число итераций для заданной точности растёт примерно как $\kappa$. При $\kappa=10^6$ (типично для плохо масштабированных данных) спуск практически стоит на месте.

Зигзаг в коде

Запустим спуск на овраге и посмотрим на знаки координаты $y$ — они скачут, выдавая осцилляцию.

def grad(v):
    x, y = v
    return [2 * x, 200 * y]      # f = x^2 + 100 y^2

def f(v):
    return v[0] ** 2 + 100 * v[1] ** 2

x = [10.0, 1.0]
alpha = 0.009      # близко к критическому 2/200 = 0.01
for k in range(1, 31):
    g = grad(x)
    x = [x[0] - alpha * g[0], x[1] - alpha * g[1]]
    if k <= 6 or k % 6 == 0:
        print(f"шаг {k:2d}: x=({x[0]:.4f}, {x[1]:+.4f})  f={f(x):.4f}")

Вывод:

шаг  1: x=(9.8200, -0.8000)  f=160.4324
шаг  2: x=(9.6432, +0.6400)  f=133.9521
шаг  3: x=(9.4697, -0.5120)  f=115.8889
шаг  4: x=(9.2992, +0.4096)  f=103.2525
шаг  5: x=(9.1318, -0.3277)  f=94.1276
шаг  6: x=(8.9674, +0.2621)  f=87.2871
шаг 12: x=(8.0415, +0.0687)  f=65.1382
шаг 18: x=(7.2112, +0.0180)  f=52.0337
шаг 24: x=(6.4666, +0.0047)  f=41.8191
шаг 30: x=(5.7989, +0.0012)  f=33.6272

Координата $y$ меняет знак на каждом шаге (осцилляция между стенками оврага), а $x$ ползёт к нулю до обидного медленно: за $30$ шагов прошли лишь от $10$ до $5.8$. Узкое горлышко — именно пологое направление $x$, по которому информации о наклоне почти нет.

Лекарства

Масштабирование/нормировка. Привести переменные к одному масштабу — уменьшить $\kappa$, сделать чашу круглой.
Momentum. Накапливать скорость вдоль дна оврага, гасить поперечные колебания (следующий раздел).
Метод Ньютона. Учесть кривизну гессианом — он «выпрямляет» овраг (раздел про Ньютона).

Как работает под капотом

Корень проблемы — изотропность спуска: он применяет один шаг $\alpha$ ко всем координатам, хотя им нужны разные. По крутой оси шаг почти критический (отсюда осцилляция), а по пологой — мизерный (отсюда черепаший прогресс). Метод просто не умеет «смотреть в разные стороны разным глазом». Все продвинутые методы так или иначе вводят покоординатную или направленную адаптацию шага, чтобы вылечить эту болезнь.

Частые ошибки

Списывать медленность на малый $\alpha$. В овраге увеличение $\alpha$ вызовет взрыв по крутой оси раньше, чем ускорит движение по пологой.
Игнорировать масштаб признаков. Разные единицы измерения создают искусственные овраги.
Не считать $\kappa$. Большое число обусловленности — сигнал, что чистый спуск не подойдёт.

Итоги

Овраг — вытянутая долина с разной кривизной по осям; спуск зигзагует между стенками.
Число обусловленности $\kappa=\lambda_{\max}/\lambda_{\min}$ задаёт замедление (итераций $\sim\kappa$).
Лечится нормировкой, моментом или вторым порядком (Ньютон).