neuler_variance_reduction_papers
Neuler: Variance Reduction Methods — Key Papers
Ключевые статьи по variance reduction для стохастической оптимизации.
Дополняет коллекцию operator splitting papers в Neuler library.
1. SVRG — Stochastic Variance Reduced Gradient
Johnson, R. & Zhang, T. (2013).
Accelerating Stochastic Gradient Descent using Predictive Variance Reduction.
NeurIPS 2013, pp. 315–323.
- arXiv: нет (proceedings only: papers.nips.cc)
- Идея: периодически вычислять полный градиент (snapshot), использовать его для коррекции стохастического градиента → дисперсия → 0 при сходимости
- Теория: линейная сходимость для сильно выпуклых функций
- Почему важна: первая работа, показавшая что VR даёт линейную сходимость SGD-класса методов без уменьшения шага
2. SAGA
Defazio, A., Bach, F. & Lacoste-Julien, S. (2014).
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives.
NeurIPS 2014.
- arXiv: 1407.0202
- Идея: хранит таблицу последних градиентов по каждому примеру, использует несмещённый estimator с variance reduction
- Теория: линейная сходимость, поддержка non-strongly convex случая (в отличие от SVRG)
- Преимущество: online updates (не нужен двойной проход как в SVRG)
3. SARAH — Stochastic Recursive Gradient
Nguyen, L.M., Liu, J., Scheinberg, K. & Takáč, M. (2017).
SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient.
ICML 2017.
- arXiv: 1703.00102
- Идея: рекурсивное обновление estimatora: $v_t = \nabla f_{i_t}(x_t) - \nabla f_{i_t}(x_{t-1}) + v_{t-1}$ — смещённый, но малодисперсный
- Теория: сублинейная для невыпуклых, линейная для сильно выпуклых
- Особенность: смещённый estimator (в отличие от SVRG/SAGA) — но практически работает лучше
4. SPIDER — Stochastic Path-Integrated Differential EstimatoR
Fang, C., Li, C.J., Lin, Z. & Zhang, T. (2018).
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator.
NeurIPS 2018.
- arXiv: 1807.01695
- Идея: двухуровневый recursive gradient estimator (как SARAH), но с адаптивным периодом snapshot
- Теория: near-optimal сложность $O(\epsilon^{-3})$ для невыпуклых задач — лучше, чем SGD ($O(\epsilon^{-4})$)
- Почему важна: доказала оптимальность класса VR-методов для невыпуклой оптимизации
5. L-SVRG — Loopless SVRG
Kovalev, D., Horváth, S. & Richtárik, P. (2020).
Don’t Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop.
ALT 2020 (Algorithmic Learning Theory).
- arXiv: 1901.01555
- Идея: убирает внешний цикл SVRG → snapshot обновляется случайно с вероятностью $p$ на каждой итерации
- Теория: та же сходимость, но анализ чище; легче параллелизовать
- Связь с Neuler: авторы — Richtárik (наш коллаборатор по некоторым работам)
6. PAGE — Probabilistic Gradient Estimator
Li, Z., Bao, H., Zhang, X. & Richtárik, P. (2021).
PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization.
ICML 2021.
- arXiv: 2008.10898
- DOI: 10.48550/arXiv.2008.10898
- Идея: на каждой итерации с вероятностью $p$ вычисляет mini-batch gradient, с вероятностью $1-p$ делает дешёвое VR-обновление (как SPIDER)
- Теория: near-optimal для невыпуклых задач, унифицирует SPIDER/SGD
- Почему важна: простейший near-optimal estimator для невыпуклой оптимизации
7. SpiderBoost
Wang, Z., Ji, K., Zhou, Y., Liang, Y. & Tarokh, V. (2019).
SpiderBoost and Momentum: Faster Stochastic Variance Reduction Algorithms.
NeurIPS 2019.
- arXiv: 1910.10948
- Идея: улучшает SPIDER: использует larger step sizes, совместим с моментом
- Теория: улучшает константы в оценках сложности SPIDER
Сводная таблица
| Метод | Год | Тип задачи | Сложность | Тип estimator |
|---|---|---|---|---|
| SVRG | 2013 | Сильно выпуклая | $O(n + n^{2/3}\epsilon^{-1})$ | Несмещённый |
| SAGA | 2014 | Выпуклая/СВ | $O((n+L/\mu)\log(1/\epsilon))$ | Несмещённый |
| SARAH | 2017 | Невыпуклая/СВ | $O(n + n^{1/2}\epsilon^{-2})$ | Смещённый |
| SPIDER | 2018 | Невыпуклая | $O(n^{1/2}\epsilon^{-3})$ | Смещённый |
| L-SVRG | 2020 | Сильно выпуклая | то же что SVRG | Несмещённый |
| PAGE | 2021 | Невыпуклая | $O(n^{1/2}\epsilon^{-3})$ | Вероятностный |
| SpiderBoost | 2019 | Невыпуклая | $O(n^{1/2}\epsilon^{-3})$ | Смещённый |
Сгенерировано worker 2026-04-10. Для добавления в Neuler library через neuler_library_batch_add с проверкой по DOI.