🔥 Делимся с вами разбором еще одной нашей статьи

Unified Theory of Adaptive Variance Reduction

[статья]

Стохастические методы — сердце современной оптимизации. Не теряют в скорости сходимости, но требуют гораздо меньше ресурсов, к тому же просты в имплементации: итерация имеет вид x(t+1) = xᵗ − γ gᵗ, где gᵗ - стохастический градиент.

Один из способов улучшить стохастические методы — редукция дисперсии (variance reduction, VR) — прием, позволяющий снизить разброс стохастических градиентов за счет коррекции новых аппроксимаций градиента прошлыми. Такого рода подходы перекочевали и в распределенную оптимизацию с координатными методами, где комбинируя достаточно грубые оценка градиента можно улучшать их точность. Тем не менее, теоретические значения параметров для таких методов, в первую очередь шага, используют константу гладкости задачи, которая обычно неизвестна. А для лучшего качества необходимо дополнительно настраивать шаг. В этой работе мы справляемся с этими недостатками, предлагая настройку метода в режиме реального времени, в зависимости от свойств задачи.

🧠 Что мы предлагаем?
1) Единый анализ VR без требования несмещенности. Это позволяет описать методы как для минимизации функций в виде конечных сумм, так и для распределенной оптимизации, вместе с координатными методами.
2) Parameter-free адаптивный шаг, который подбирается “на лету” по подсчитанной сумме стохастических градиентов без дополнительной настройки:

γₜ ∝ (∑_{i<t} ∥gᵢ∥²)⁻ᵅ

3) Теоремы, доказывающие сходимость данных методов. На практике оказывается, что такой адаптивный подбор шага всегда лучше, чем константный, который следует брать по теории. Более того, сходимость метода с parameter-free адаптивным шагом будет практически идентична сходимости этого же метода с затюненным параметрами.

⚙️ Где это применимо?
Единая теория и адаптивные шаги покрывают три большие семейства методов (с конкретными рецептами выбора батчей/параметров):
• Функции в виде конечной суммы: используйте L-SVRG, SAGA, PAGE, ZeroSARAH и их адаптивные версии;
• Распределенная оптимизация: правильно имплементированная компрессия градиентов удовлетворяет нашему анализу. Применяйте EF-21, DIANA, DASHA;
• Координатные методы: берите не весь градиент, а только некоторые частные производные и накапливайте ошибку с прошлых итераций. Вам помогут SEGA и JAGUAR

Смотри детали нашей работы в комментариях ⬇️