ВШЭ L9: Задачи для практики — Нижние оценки и ускоренные методы

Подготовлено Феанором 2026-03-22 06:15 MSK | Лекция 23 марта 09:30

Темы: нижние оценки Немировского-Юдина, метод тяжёлого шарика (Heavy Ball), ускоренный градиентный метод Нестерова (AGD).

---

Блок 1. Нижние оценки: основы

Задача 1.1 (Разрыв GD vs нижняя оценка)

Для класса $L$-гладких выпуклых функций имеем:
- GD: $f(x_K) - f^* \leq \dfrac{L \|x_0 - x^*\|^2}{2K}$
- Нижняя оценка (Немировский–Юдин, 1979): любой метод первого порядка гарантирует не лучше $\dfrac{3L\|x_0-x^*\|^2}{32(K+1)^2}$

а) Сформулируйте: что означает нижняя оценка вида $\Omega(1/K^2)$ для GD (у которого оценка $O(1/K)$)?

б) Следует ли из этого, что GD не оптимален? Приведите два возможных вывода.

в) AGD Нестерова даёт $O(1/K^2)$. Каков смысл: это совпадение с нижней оценкой?

Ответ

**а)** Нижняя оценка $\Omega(1/K^2)$ означает: существует функция из класса, для которой любой метод первого порядка (с нуля) даёт ошибку ≥ const/K². Если метод сходится быстрее — это либо противоречие, либо разные начальные точки. **б)** Два вывода: 1. Нижняя оценка неточна (её можно улучшить) 2. **GD не оптимален** — разрыв $O(1/K)$ vs $\Omega(1/K^2)$ реален. GD упускает фактор $K$. **в)** Да, AGD **оптимален** для класса гладких выпуклых функций: его оценка $O(1/K^2)$ совпадает с нижней оценкой по порядку. Нестеров достиг теоретического предела для методов первого порядка.

---

Задача 1.2 (Наихудшая функция Нестерова — структура)

Рассмотрим матрицу $A \in \mathbb{R}^{n \times n}$ (трёхдиагональная):
$$ A = \begin{bmatrix} 2 & -1 & 0 & \cdots & 0 \\ -1 & 2 & -1 & \cdots & 0 \\ 0 & -1 & 2 & \cdots & 0 \\ \vdots & & \ddots & \ddots & \vdots \\ 0 & 0 & \cdots & -1 & 2 \end{bmatrix} $$

Наихудшая функция Нестерова: $f(x) = \dfrac{L}{4}\left(\dfrac{1}{2}x^T A x - e_1^T x\right)$, где $e_1 = (1, 0, \ldots, 0)$.

а) Покажите, что $0 \preceq A \preceq 4I$ (т.е. $L$-гладкость выполнена с $L_{eff} = L$).

б) Объясните интуицию: почему GD «разворачивает» информацию о $f$ медленно на этой функции?

Ответ/Набросок

**а)** $x^T A x = x_1^2 + x_n^2 + \sum_{i=1}^{n-1}(x_i - x_{i+1})^2 \geq 0$ → $A \succeq 0$. Оценка сверху: $x^T A x \leq 4\|x\|^2$ (так как $A \preceq 4I$ — можно проверить, что максимальное собственное значение $= 4\sin^2(\pi n / 2(n+1)) < 4$). → $\nabla^2 f \preceq LI$ ✓ **б)** Из $x_0 = 0$: $\nabla f(x_0) = -\frac{L}{4}e_1$. Значит $x_1 \in \text{span}\{e_1\}$. Далее $x_2 \in \text{span}\{e_1, e_2\}$, и т.д. GD «раскрывает» координаты по одной за итерацию — через $k$ шагов узнаёт только $k$ координат из $n$. Это и объясняет нижнюю оценку для $k < n/2$.

---

Задача 1.3 (Нижняя оценка для сильно выпуклых функций)

Для $\mu$-сильно выпуклых $L$-гладких функций нижняя оценка (Немировский):
$$ f(x_K) - f^* \geq \Omega\!\left(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{2K}(f(x_0)-f^*)\right), \quad \kappa = L/\mu $$

GD даёт $(1-1/\kappa)^K \approx e^{-K/\kappa}$; оптимум — $e^{-2K/\sqrt{\kappa}}$.

Задача: при $\kappa = 100$ сколько итераций нужно GD vs AGD для достижения $\varepsilon = 10^{-8}$?

Ответ

- **GD**: $(1 - 1/100)^K \leq 10^{-8}$ → $K \geq 100 \cdot 8\ln 10 \approx 1842$ - **AGD** (Нестеров, оптимален): $\left(\frac{9}{11}\right)^{2K} \leq 10^{-8}$ → $2K\ln(11/9) \geq 8\ln 10$ → $K \geq \frac{8\ln 10}{2\ln(11/9)} \approx \frac{18.42}{0.401} \approx 46$ - Ускорение: примерно **$\sqrt{\kappa} = 10$ раз** (теоретически), на практике ≈40x.

---

Блок 2. Метод тяжёлого шарика (Heavy Ball, Polyak)

Задача 2.1 (Алгоритм и параметры)

Метод тяжёлого шарика (Polyak, 1964):
$$ x_{k+1} = x_k - \alpha \nabla f(x_k) + \beta (x_k - x_{k-1}) $$

а) Что физически означает слагаемое $\beta(x_k - x_{k-1})$? Почему метод называется “тяжёлый шарик”?

б) Для квадратичной $f(x) = \frac{1}{2}x^T A x$, $\lambda_{\min} = \mu$, $\lambda_{\max} = L$. Оптимальные параметры:
$$ \alpha^* = \frac{4}{(\sqrt{L}+\sqrt{\mu})^2}, \quad \beta^* = \left(\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}\right)^2 $$
Какова скорость сходимости при этих параметрах?

в) Почему HB не является оптимальным методом для общих выпуклых функций?

Ответ

**а)** Слагаемое $\beta(x_k - x_{k-1})$ — "момент инерции": метод движется не только по антиградиенту, но и продолжает двигаться в направлении предыдущего шага. Физическая аналогия: шарик на наклонной поверхности с трением — набирает скорость в направлении наклона. **б)** Скорость для квадратичных: $$ \|x_K - x^*\| \leq \left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^K \|x_0 - x^*\| $$ Это оптимально для квадратичных, совпадает с нижней оценкой! Но только для квадратичных. **в)** HB может расходиться на общих гладких выпуклых функциях. Теоретический анализ сходимости HB для негладкой/невыпуклой функции значительно сложнее. AGD Нестерова даёт гарантированную оценку $O(1/K^2)$ для всего класса.

---

Задача 2.2 (HB vs GD на квадратике)

Рассмотрим $f(x) = \frac{L}{2}x^2 + \frac{\mu}{2}y^2$ (разные кривизны по осям), $L = 100$, $\mu = 1$, $\kappa = 100$.

а) Скорость GD с $\alpha = 2/(L+\mu)$?

б) Скорость HB с оптимальными параметрами?

в) Как соотносятся числа итераций для $\varepsilon = 10^{-6}$?

Ответ

**а)** GD (оптимальный шаг для квадратик): $\rho_{GD} = \frac{\kappa - 1}{\kappa + 1} = \frac{99}{101} \approx 0.980$. Итераций: $K_{GD} \approx \kappa \ln(1/\varepsilon) = 100 \cdot 13.8 = 1380$. **б)** HB: $\rho_{HB} = \frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1} = \frac{9}{11} \approx 0.818$. Итераций: $K_{HB} \approx \sqrt{\kappa} \ln(1/\varepsilon) = 10 \cdot 13.8 = 138$. **в)** Ускорение в $\sqrt{\kappa} = 10$ раз. **Вывод**: добавление одной строчки (момент $\beta$) даёт кратное ускорение.

---

Блок 3. Ускоренный градиентный метод Нестерова (AGD)

Задача 3.1 (Алгоритм AGD)

AGD Нестерова (для выпуклых $f$):
$$ \begin{aligned} y_{k+1} &= x_k - \frac{1}{L}\nabla f(x_k) \\ x_{k+1} &= \left(1 + \frac{k-1}{k+2}\right)y_{k+1} - \frac{k-1}{k+2} y_k \end{aligned} $$

или эквивалентная форма с вспомогательной точкой $z_k$:
$$ \begin{aligned} x_{k+1} &= (1-\theta_k)x_k + \theta_k z_k \\ z_{k+1} &= z_k - \frac{\alpha_k}{\theta_k}\nabla f(x_{k+1}) \end{aligned} $$

а) Какова оценка сходимости AGD для $L$-гладкой выпуклой функции?

б) Является ли AGD монотонным (убывает ли $f(x_k)$)?

в) При $k = 0$: $x_0 = y_0$. Что делает AGD на первой итерации? Отличается ли от GD?

Ответ

**а)** $f(x_K) - f^* \leq \dfrac{2L\|x_0 - x^*\|^2}{(K+1)^2} = O(1/K^2)$ — оптимально! **б)** Нет, $f(x_k)$ **не убывает монотонно** в AGD. Метод движется более «агрессивно» — иногда может давать небольшое увеличение значения функции в $x_k$, но при этом достигает лучшей оценки через $(K+1)^2$ итераций. **в)** При $k=0$: коэффициент $\frac{k-1}{k+2} = \frac{-1}{2} < 0$. Первый шаг AGD: $x_1 = (3/2)y_1 - (-1/2)y_0 = (3/2)(x_0 - \nabla f/L) + (1/2)x_0$. Отличается от GD дополнительным сдвигом.

---

Задача 3.2 (Restart trick)

Одна из популярных эвристик — рестарт AGD:
- AGD запускается, когда сходимость замедляется — перезапустить с текущей точки как новым $x_0$.

а) Зачем нужен рестарт? Когда “накопленный момент” AGD мешает?

б) Если функция является $\mu$-сильно выпуклой, какой вариант AGD использует рестарт с периодом $T \sim \sqrt{\kappa}$ итераций?

Ответ

**а)** AGD накапливает «историю» через коэффициенты $(k-1)/(k+2)$. Если функция нелинейна или алгоритм попадает в плохую область, накопленный момент может «увести» итерацию в нежелательном направлении. Рестарт сбрасывает историю и начинает заново с правильной начальной точкой. Особенно полезно: (1) при сильной выпуклости, (2) в негладких или сёдловых задачах. **б)** При $\mu$-сильной выпуклости: запускаем AGD с шагом для выпуклых ($1/K^2$-оценка), делаем $T = \lceil\sqrt{\kappa}\rceil$ итераций, перезапускаем. Каждый раунд даёт $e$-кратное уменьшение: $f(x_T) - f^* \leq e^{-1}(f(x_0)-f^*)$. После $m$ раундов: $e^{-m}(f(x_0)-f^*)$. Итого итераций: $m\sqrt{\kappa}$ = $O(\sqrt{\kappa}\log(1/\varepsilon))$ — оптимально!

---

Задача 3.3 (Сравнение методов)

Заполните таблицу для $L$-гладких $\mu$-сильно выпуклых ($\kappa = 100$) и просто выпуклых функций:

(при $\varepsilon = 10^{-6}$, $R = \|x_0-x^*\|$, $L=100, \mu=1$)

Заполненная таблица

| Метод | Выпуклый $k_\varepsilon$ | Сильно выпуклый $k_\varepsilon$ | Оптимален? | |-------|--------------------------|--------------------------------|------------| | GD | $O(LR^2/\varepsilon) = 10^8 \cdot R^2$ | $O(\kappa\ln(1/\varepsilon)) \approx 1382$ | ❌ | | Heavy Ball | ❌ не гарантирован | $O(\sqrt{\kappa}\ln(1/\varepsilon)) \approx 138$ (квадр.) | ✅ квадр., ❌ общ. | | AGD Нестерова | $O(\sqrt{L}R/\sqrt{\varepsilon}) = 10^4 R$ | $O(\sqrt{\kappa}\ln(1/\varepsilon)) \approx 138$ | ✅ | | Нижняя оценка | $\Omega(\sqrt{L}R/\sqrt{\varepsilon})$ | $\Omega(\sqrt{\kappa}\ln(1/\varepsilon)) \approx 138$ | — | **Вывод**: AGD достигает нижних оценок в обоих классах. HB оптимален только для квадратичных.

---

Блок 4. Быстрые вопросы (5 минут)

4.1 Какова скорость GD для $L$-гладкой невыпуклой функции (по норме градиента)? (О(1/√К))

4.2 Утверждение: “AGD — это GD с шагом $2/L$ вместо $1/L$”. Правда или ложь? (Ложь — другой алгоритм с вспомогательной точкой)

4.3 Нестеров доказал нижнюю оценку, построив конкретную функцию. Почему этого достаточно? (Нижняя оценка = “существует плохая функция”. Конкретный пример её доказывает)

4.4 Можно ли ускорить SGD так же, как GD → AGD? (Частично — SVRG, SARAH, но шум ограничивает ускорение)

4.5 HB осциллирует на вытянутых функциях, AGD — нет. Почему? (AGD выбирает коэффициенты оптимально; HB фиксированный $\beta$ не учитывает геометрию)

---

Связи с темами курса

---

Файл для подготовки к лекции 23 мар. Не деплоить автоматически.