hse26_l9_cheatsheet
ВШЭ L9: Шпаргалка лектора — Нижние оценки, HB, AGD Нестерова
Для использования во время лекции 23 марта 09:30 | Феанор 2026-03-22
1. Нижние оценки (Lower Bounds) для методов I порядка
| Класс функций | Нижняя оценка | GD даёт | Разрыв |
|---|---|---|---|
| Выпуклая негладкая | $\Omega(1/\sqrt{k})$ | $O(1/\sqrt{k})$ | ✅ оптимален |
| Гладкая невыпуклая | $\Omega(1/\sqrt{k})$ для $\|\nabla f\|$ | $O(1/\sqrt{k})$ | ✅ оптимален |
| Гладкая выпуклая | $\Omega(1/k^2)$ | $O(1/k)$ | ❌ GD в $k$ раз медленнее |
| Гладкая сильно выпуклая | $\Omega\!\left(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{2k}\right)$ | $O\!\left((1-\mu/L)^k\right)$ | ❌ GD в $\sqrt{\kappa}$ раз медленнее |
Доказательство нижней оценки = построить конкретную плохую функцию (наихудшая функция Нестерова).
Наихудшая функция: $f(x) = \frac{L}{4}\!\left(\frac{1}{2}x^TAx - e_1^Tx\right)$, $A$ — трёхдиагональная.
Ключ: из $x_0=0$ метод раскрывает по 1 координате за итерацию → за $k$ шагов знает лишь первые $k$ компонент из $n$.
2. Метод тяжёлого шарика (Heavy Ball, Polyak 1964)
$$ \boxed{x_{k+1} = x_k - \alpha \nabla f(x_k) + \beta (x_k - x_{k-1})} $$
Оптимальные параметры (для $\mu$-SC + $L$-smooth квадратик):
$$
\alpha^* = \frac{4}{(\sqrt{L}+\sqrt{\mu})^2}, \quad \beta^* = \left(\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}\right)^2
$$
Скорость (квадратичные SC):
$$
\|x_k - x^*\| \leq \left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k \|x_0 - x^*\| \quad \text{← оптимально для квадратичных}
$$
Сравнение при $\kappa=100$:
| GD | HB | AGD | |
|---|---|---|---|
| Скорость SC | $(1-0.01)^k \approx e^{-k/100}$ | $(9/11)^k \approx e^{-0.2k}$ | $(9/11)^{2k}$ |
| $k_\varepsilon$ ($\varepsilon=10^{-6}$) | ~1382 | ~138 | ~69 |
| Ускорение vs GD | — | $\sqrt{\kappa}=10$× | $\sqrt{\kappa}=10$× |
⚠️ HB ограничен квадратичными — для общих выпуклых сходимость не гарантирована!
3. Ускоренный градиентный метод Нестерова (AGD, 1983)
$$ \boxed{y_{k+1} = x_k - \frac{1}{L}\nabla f(x_k), \quad x_{k+1} = y_{k+1} + \frac{k-1}{k+2}(y_{k+1} - y_k)} $$
(Эквивалентная форма — через промежуточную точку $z_k$ с адаптивными $\theta_k$.)
Скорость сходимости:
| Класс | AGD оценка | Нижняя оценка | Оптимален? |
|---|---|---|---|
| Гладкий выпуклый | $f(x_K)-f^* \leq \dfrac{2L\|x_0-x^*\|^2}{(K+1)^2} = O(1/K^2)$ | $\Omega(1/K^2)$ | ✅ да |
| Гладкий SC | $O\!\left(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{2K}\right)$ | то же | ✅ да |
Ключевые свойства AGD:
- ❌ $f(x_k)$ не убывает монотонно (в отличие от GD)
- ✅ Использует 2 точки: $x_k$ (итерация) + $y_k$ (вспомогательная)
- ✅ Restart trick для SC: перезапуск каждые $T\sim\sqrt{\kappa}$ итераций → $O(\sqrt{\kappa}\log 1/\varepsilon)$
4. Итоговая таблица
| Метод | Выпуклый $k_\varepsilon$ | SC $k_\varepsilon$ ($\kappa=100$, $\varepsilon=10^{-6}$) | Оптимален? |
|---|---|---|---|
| GD | $O(LR^2/\varepsilon)$ | ~1382 | ❌ |
| Heavy Ball | ❌ не гарантирован | ~138 (квадрат.) | ✅ квадр. / ❌ общий |
| AGD Нестерова | $O(\sqrt{L}R/\sqrt{\varepsilon})$ | ~69 | ✅ всегда |
| Нижняя оценка | $\Omega(\sqrt{L}R/\sqrt{\varepsilon})$ | $\Omega(\sqrt{\kappa}\log 1/\varepsilon)\approx 69$ | — |
5. Быстрые факты для вопросов студентов
- “Почему нижняя оценка — это факт?” → нужна одна плохая функция, не все
- “HB vs AGD — что лучше на практике?” → AGD с гарантиями; HB быстрее на квадратиках но рискованен
- “SGD тоже можно ускорить?” → частично: SVRG, SARAH — но шум ограничивает до $O(1/K)$
- “Почему AGD немонотонен?” → он “прыгает вперёд” используя инерцию; в среднем сходится быстрее
Тест L9: https://docs.google.com/forms/d/e/1FAIpQLSc-xMxy1sqKQ509Iewz32psPfYEoOHdHesoBi6FpDdI9TS3FQ/viewform