ВШЭ L8: Задачи для практики — Градиентный спуск. Теоремы сходимости.

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

Тема: $L$-гладкость, $\mu$-сильная выпуклость, сходимость GD, PL-условие, нижние оценки.

---

Блок 1. Оценки сходимости (базовые)

Задача 1.1 (классическая)

Функция $f: \mathbb{R}^d \to \mathbb{R}$ выпукла и $L$-гладкая. Градиентный спуск:
$$x_{k+1} = x_k - \frac{1}{L}\nabla f(x_k)$$

Доказать: $f(x_K) - f^* \leq \dfrac{L\|x_0 - x^*\|^2}{2K}$.

Подсказка: использовать Descent Lemma + суммирование телескопическим методом.

Решение (ключевые шаги)

1. Descent Lemma: $f(x_{k+1}) \leq f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2$ 2. Выпуклость: $f(x_k) - f^* \leq \langle \nabla f(x_k), x_k - x^* \rangle$ 3. Из п.1 и шага GD: $f(x_k) - f^* \leq \frac{L}{2}(\|x_k - x^*\|^2 - \|x_{k+1} - x^*\|^2)$ 4. Телескоп по $k = 0, \ldots, K-1$: $\sum_k (f(x_k)-f^*) \leq \frac{L}{2}\|x_0-x^*\|^2$ 5. Усредняем (или берём минимум): $f(x_K) - f^* \leq \frac{L\|x_0-x^*\|^2}{2K}$ ∎

---

Задача 1.2 (сильная выпуклость)

Функция $f$ является $\mu$-сильно выпуклой и $L$-гладкой. GD с шагом $\alpha = 1/L$.

Доказать: $\|x_{k+1} - x^*\|^2 \leq \left(1 - \dfrac{\mu}{L}\right)\|x_k - x^*\|^2$.

Следствие: $\|x_K - x^*\|^2 \leq \left(1 - \dfrac{1}{\kappa}\right)^K \|x_0 - x^*\|^2$, где $\kappa = L/\mu$.

Решение

Для $\mu$-сильной выпуклости: $f(y) \geq f(x) + \langle \nabla f(x), y-x\rangle + \frac{\mu}{2}\|y-x\|^2$. Обозначим $e_k = x_k - x^*$, $g_k = \nabla f(x_k)$. Из оптимальности: $\nabla f(x^*) = 0$, поэтому $\langle g_k, e_k \rangle \geq \frac{\mu}{2}\|e_k\|^2 + \frac{1}{2L}\|g_k\|^2$ (co-coercivity). $\|e_{k+1}\|^2 = \|e_k - \alpha g_k\|^2 = \|e_k\|^2 - 2\alpha\langle g_k, e_k\rangle + \alpha^2\|g_k\|^2$ При $\alpha = 1/L$: $\leq \|e_k\|^2 - \frac{2}{L}\cdot(\frac{\mu}{2}\|e_k\|^2 + \frac{1}{2L}\|g_k\|^2) + \frac{1}{L^2}\|g_k\|^2 = (1-\frac{\mu}{L})\|e_k\|^2$ ∎

---

Блок 2. Выбор шага и числа итераций

Задача 2.1 (практическая)

Требуется найти минимум функции $f(x) = \frac{1}{2}x^T A x - b^T x$ с $A \succ 0$, $\lambda_{\min}(A) = \mu = 0.1$, $\lambda_{\max}(A) = L = 10$.

а) Число обусловленности $\kappa = ?$

б) Сколько итераций GD нужно для $\|x_K - x^*\| \leq 10^{-6}\|x_0 - x^*\|$?

в) Как изменится ответ, если $\mu = 1$ (при том же $L$)?

Ответ

**а)** $\kappa = L/\mu = 100$. **б)** Нужно $(1 - 1/\kappa)^K \leq 10^{-12}$, т.е. $K \geq \frac{12\ln 10}{\ln(100/99)} \approx \frac{12 \cdot 2.303}{0.01005} \approx 2749$ итераций. **в)** При $\mu = 1$: $\kappa = 10$, $K \geq \frac{12\ln 10}{\ln(10/9)} \approx \frac{27.63}{0.1054} \approx 262$ итерации — в **10 раз быстрее**!

---

Задача 2.2 (accuracy vs step)

Функция $f$ выпукла и $L$-гладкая (не сильно выпуклая). Мы хотим $f(x_K) - f^* \leq \varepsilon$.

а) Какое минимальное $K$ гарантирует точность $\varepsilon$ при шаге $\alpha = 1/L$?

б) Что выгоднее для ускорения: уменьшить $L$ (лучшая предобусловка) или взять большее $K$?

Ответ

**а)** Из оценки $f(x_K) - f^* \leq \frac{L\|x_0-x^*\|^2}{2K} \leq \varepsilon$: $$K \geq \frac{L\|x_0-x^*\|^2}{2\varepsilon}$$ **б)** Уменьшить $L$ линейно снижает $K$ и время на вычисление одного шага (если предобусловка это позволяет). Большее $K$ только снижает погрешность, не меняет константы. **Лучше: улучшать предобусловку**. Мотивация: методы второго порядка (Newton), Quasi-Newton (L-BFGS).

---

Блок 3. PL-условие (Polyak-Łojasiewicz)

Задача 3.1 (PL vs сильная выпуклость)

Напомним: PL-условие: $\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f^*)$.

а) Покажите, что $\mu$-сильная выпуклость влечёт PL-условие.

б) Приведите пример функции, удовлетворяющей PL, но не являющейся сильно выпуклой.

Решение

**а)** $f(x) - f^* \leq \langle \nabla f(x), x - x^* \rangle - \frac{\mu}{2}\|x-x^*\|^2 \leq \frac{1}{2\mu}\|\nabla f(x)\|^2$ (по неравенству Young). Значит $\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f^*)$ ✓ **б)** $f(x, y) = (x^2 + y^2)\sin^2(x^2 + y^2)$ — ноль в начале координат, бесконечно много других нулей (не существует единственного минимума → не сильно выпукла), но $\|\nabla f\|^2 \sim 4r^2\sin^2(r^2) + ...\geq 2\mu f$ — выполняется PL. Более простой пример: $f(x) = (x_1^2 + x_2^2)^2$ — минимум на прямой $x_1=x_2=0$, но PL выполняется вблизи нуля.

---

Задача 3.2 (сходимость при PL)

Пусть $f$ является $L$-гладкой и удовлетворяет PL-условию с константой $\mu$.

Доказать: GD с шагом $1/L$ сходится со скоростью:
$$f(x_K) - f^* \leq \left(1 - \frac{\mu}{L}\right)^K (f(x_0) - f^*)$$

Решение

Из Descent Lemma: $f(x_{k+1}) \leq f(x_k) - \frac{1}{2L}\|\nabla f(x_k)\|^2$ Применяем PL: $\|\nabla f(x_k)\|^2 \geq 2\mu(f(x_k) - f^*)$ $f(x_{k+1}) - f^* \leq f(x_k) - f^* - \frac{\mu}{L}(f(x_k) - f^*) = (1 - \frac{\mu}{L})(f(x_k) - f^*)$ Применяем индукцию: $f(x_K) - f^* \leq (1 - \mu/L)^K (f(x_0) - f^*)$ ∎

---

Блок 4. Нижние оценки (мотивация для AGD)

Задача 4.1 (разрыв GD vs AGD)

Для класса $L$-гладких выпуклых функций:
- GD: $O\!\left(\dfrac{LR^2}{K}\right)$ (R = ‖x₀-x*‖)
- Нижняя оценка (Немировский-Юдин): $\Omega\!\left(\dfrac{LR^2}{K^2}\right)$

а) Насколько GD субоптимален относительно нижней оценки?

б) Нестеровский AGD достигает $O(LR^2/K^2)$. Какое ускорение это даёт при $K = 1000$ и $\varepsilon$-требовании?

Ответ

**а)** Разрыв в $K$ раз (квадратичный разрыв). GD требует $K \sim LR^2/\varepsilon$ итераций, нижняя оценка — $\sqrt{LR^2/\varepsilon}$. Разрыв: $\sim \sqrt{LR^2/\varepsilon}$ = $\sqrt{K_\text{GD}}$. **б)** При $\varepsilon = LR^2/K_\text{AGD}^2$: - AGD: $K_\text{AGD} = \sqrt{LR^2/\varepsilon}$ - GD: $K_\text{GD} = LR^2/\varepsilon = K_\text{AGD}^2$ - При $K_\text{AGD} = 1000$: GD нужно $1000^2 = 10^6$ итераций. Ускорение: **1000x**.

---

Задача 4.2 (сильно выпуклый случай)

Для $\mu$-сильно выпуклых $L$-гладких функций нижняя оценка:
$$\Omega\!\left(\exp\!\left(-\frac{K}{\sqrt{\kappa}}\right)\right)$$

GD даёт $(1 - 1/\kappa)^K \approx \exp(-K/\kappa)$.

При $\kappa = 100$: сколько итераций GD vs AGD для $10^{-6}$ точности?

Ответ

- **GD**: $K_\text{GD} \approx \kappa \cdot \ln(1/\varepsilon) = 100 \cdot 6\ln 10 \approx 1382$ - **AGD** (нижняя оценка достигается Nesterov): $K_\text{AGD} \approx \sqrt{\kappa} \cdot \ln(1/\varepsilon) = 10 \cdot 13.8 \approx 138$ - Ускорение: **~10x** (= $\sqrt{\kappa}$)

---

Блок 5. Quickfire (проверка понимания)

5.1 Если $\alpha > 2/L$ — что происходит с GD? (Дивергенция — шаг слишком большой)

5.2 Убывает ли $f(x_k)$ монотонно при $\alpha = 1/L$? (Да — из Descent Lemma)

5.3 Для квадратичной $f(x) = \frac{1}{2}\|Ax - b\|^2$ — чему равна $L$? (λ_max(A^T A) = σ_max(A)²)

5.4 Зачем нужна $L$-гладкость для анализа GD? (Descent Lemma = гарантированное убывание)

5.5 Можно ли применить GD к $f(x) = |x|$? (Нет — не дифференцируема в 0; нужен субградиентный метод или проксимальный)

---

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

---

Файл для использования на семинаре/лекции 16 мар. Не деплоить автоматически.