Strategy/projects/files/neuler_variance_reduction_papers.md
+

neuler_variance_reduction_papers

Neuler: Variance Reduction Methods — Key Papers

Составлено: 2026-04-10. Дополнение к operator splitting papers.
Цель: добавить 5-7 ключевых статей по variance reduction в Neuler library.

Ключевые статьи

1. SVRG — Stochastic Variance Reduced Gradient

Johnson & Zhang (2013)
- Title: Accelerating Stochastic Gradient Descent using Predictive Variance Reduction
- Venue: NeurIPS 2013
- URL: https://papers.nips.cc/paper_files/paper/2013/hash/ac1dd209cbcc5e5d1c6e28598e8cbbe8-Abstract.html
- Идея: периодическое полное вычисление градиента как контрольная точка. Сложность O((n + κ) log(1/ε)) для strongly convex.
- Значимость: первая практически эффективная VR-схема, положила начало целому направлению.

2. SAGA

Defazio, Bach, Lacoste-Julien (2014)
- Title: SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- Venue: NeurIPS 2014
- URL: https://papers.nips.cc/paper_files/paper/2014/hash/ede7e2b6d13a41ddf9f4bdef84fdc737-Abstract.html
- DOI: (NeurIPS 2014 proceedings)
- Идея: хранит таблицу старых градиентов размера n, несмещённый оценщик. Работает для non-strongly convex.
- Значимость: практичная альтернатива SVRG без необходимости полного прохода.

3. SARAH — Stochastic Recursive Gradient Algorithm

Nguyen, Liu, Scheinberg, Takáč (2017)
- Title: SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
- Venue: ICML 2017
- arXiv: 1703.00102
- DOI: (ICML 2017 PMLR)
- Идея: рекурсивный оценщик градиента (не несмещённый, но с убывающей дисперсией).
- Значимость: достигает оптимальной сложности для finite-sum задач.

4. SPIDER — Stochastic Path-Integrated Differential Estimator

Fang, Li, Lin, Zhang (2018)
- Title: SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator
- Venue: NeurIPS 2018
- arXiv: 1807.01695
- Идея: оценщик аналогичен SARAH, но с адаптивным выбором размера шага. Near-optimal для nonconvex.
- Значимость: первый nearly optimal алгоритм для nonconvex finite-sum оптимизации.

5. L-SVRG / Loopless SVRG

Kovalev, Horváth, Richtárik (2020)
- Title: Don’t Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
- Venue: AISTATS 2020
- arXiv: 1901.01366
- DOI: (AISTATS 2020 PMLR)
- Идея: устраняет внешний цикл SVRG с вероятностным обновлением snapshot. Проще анализировать, не хуже.
- Значимость: упрощение практически важно для адаптации к распределённым/онлайн сеттингам.

6. PAGE — Probabilistic Gradient Estimator

Li, Bao, Zhao, Richtárik (2021)
- Title: PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
- Venue: ICML 2021
- arXiv: 2008.10898
- DOI: (ICML 2021 PMLR)
- Идея: с вероятностью p берёт полный градиент, с вер. (1-p) использует предыдущий + небольшой мини-batch.
- Значимость: оптимален для nonconvex задач, элегантное унифицирующее представление VR методов.

7. STORM — Stochastic Recursive Momentum

Cutkosky & Orabona (2019)
- Title: Momentum-Based Variance Reduction in Non-Convex SGD
- Venue: NeurIPS 2019
- arXiv: 1905.10018
- Идея: momentum-based VR без хранения n градиентов. Применима к online/streaming сеттингу.
- Значимость: расширяет VR на online оптимизацию (не только finite-sum).

Рекомендации по добавлению в Neuler

Приоритет добавления (высший сначала):
1. SVRG (основополагающая, много цитирований)
2. SAGA (несмещённый оценщик, nonconvex)
3. PAGE (ICML 2021, оптимальный, unifying view)
4. L-SVRG (arXiv доступен, современная интерпретация)
5. SARAH/SPIDER (для полноты раздела nonconvex)
6. STORM (если нужен online сеттинг)

Команды для добавления (через Neuler MCP):

# Пример — искать по arXiv ID или точному названию
neuler_add_paper(query="SVRG accelerating stochastic gradient descent variance reduction Johnson Zhang 2013")
neuler_add_paper(doi="arxiv:1703.00102")  # SARAH
neuler_add_paper(doi="arxiv:1807.01695")  # SPIDER

⚠️ Напоминание: после batch_add всегда проверять title результатов vs запрос (баг: OpenAlex может добавить нерелевантную статью). Неправильные удалять по DOI.

Феанор worker, 2026-04-10 23:05 MSK

Choose icon