Strategy/projects/files/hse26_session_16mar_brief.md
+

hse26_session_16mar_brief

ВШЭ: Лекция 8 — 16 марта (понедельник, 09:30)

Подготовлено Феанором 2026-03-13 13:05 MSK

Тема: Градиентный спуск. Теоремы сходимости.

Материалы: lectures/8.pdf ✅ | seminars/8.pdf ✅ | test 8 — ждёт деплоя
Лекция: L8 (читано 1–7, следующая 8)

Содержание лекции

Градиентный спуск в гладком случае

  • Итерация: $x_{k+1} = x_k - \alpha \nabla f(x_k)$, шаг $\alpha \leq 1/L$
  • Выпуклый случай: $f(x_K) - f^* \leq \frac{L\|x_0 - x^*\|^2}{2K}$ — скорость $O(1/K)$
  • Сильно выпуклый случай: $\|x_k - x^*\|^2 \leq \left(1 - \frac{\mu}{L}\right)^k \|x_0 - x^*\|^2$ — скорость $O\left(\left(1-\kappa^{-1}\right)^K\right)$
  • PL-условие: аналогично сильной выпуклости, но для негладких задач

Верхние и нижние оценки

  • Верхние: из $L$-гладкости + (сильной) выпуклости
  • Нижние оценки (Немировский-Юдин): для методов 1-го порядка $\Omega(1/K^2)$ для выпуклого случая
  • Разрыв между GD ($O(1/K)$) и нижней оценкой ($\Omega(1/K^2)$) → мотивация ускоренных методов (AGD в L9)

Ключевые понятия

  • L-гладкость, μ-сильная выпуклость, число обусловленности κ = L/μ
  • PL-условие (Polyak-Łojasiewicz): $\|\nabla f(x)\|^2 \geq 2\mu(f(x) - f^*)$
  • Descent lemma: $f(y) \leq f(x) + \langle \nabla f(x), y-x\rangle + \frac{L}{2}\|y-x\|^2$

Семинар (параллельно или после)

Файл: seminars/8.md (Quarto, тема “Градиентный спуск и сходимость”) ✅
Семинаристы: Ребриков, Куйбида, Бородич, Забара, Муравьев, Максимов

Задачи семинара — практика теорем сходимости, подбор шага, PL-примеры.

Что нужно сделать до 16 мар

🔴 Срочно (нужен ОК Даниила)

  1. Задеплоить тесты L5-L9 → /review/inbox/hse26_tests_l5_l9_deploy.md
    - materials_template.ejs + materials.yml + tests/5-9.md готовы локально
    - git add tests/ materials.yml materials_template.ejs && git push — ~3 мин
    - ⚠️ Тест 8 тематически про Heavy Ball/Nesterov (!) — возможен оффсет нумерации между тестами и лекциями. Стоит проверить перед деплоем.

⚠️ Обратить внимание

  • Тест 8 vs Лекция 8: tests/8.md содержит задачи про Heavy Ball, AGD, FISTA — это темы L9/L10, но не L8 (GD convergence). Возможно, тест был создан “наперёд”. Нужно проверить, какой тест открывать студентам после L8.

Контекст МОМО

Sprint 1 итоги: дедлайн прошёл 11 мар, форков 0 (проверено 12:05). Степан Дергачев ждёт ответа (черновик в /review/inbox/stepan_dergachev_callback.md). Рекомендую ответить ДО или ПОСЛЕ лекции 16 мар.

Быстрая шпаргалка (для лекции)

Случай Шаг Скорость
Выпуклый α = 1/L O(1/K)
Сильно выпуклый α = 1/L O((1-μ/L)^K)
PL-условие α = 1/L O((1-μ/L)^K)
Нижняя оценка (выпуклый) — Ω(1/K²)
Нижняя оценка (σ-выпуклый) — Ω(e^{-K/√κ})

Разрыв O(1/K) vs Ω(1/K²) → ускоренные методы (тема L9).

Choose icon