2025-11-10T02:38:56.409187

Re$^3$MCN: Cubic Newton + Variance Reduction + Momentum + Quadratic Regularization for Finite-sum Non-convex Problems

Pasechnyuk-Vilensky, Kamzolov, Takáč
We analyze a stochastic cubic regularized Newton method for finite sum optimization $\textstyle\min_{x\in\mathbb{R}^d} F(x) \;=\; \frac{1}{n}\sum_{i=1}^n f_i(x)$, that uses SARAH-type recursive variance reduction with mini-batches of size $b\sim n^{1/2}$ and exponential moving averages (EMA) for gradient and Hessian estimators. We show that the method achieves a $(\varepsilon,\sqrt{L_2\varepsilon})$-second-order stationary point (SOSP) with total stochastic oracle calls $n + \widetilde{\mathcal{O}}(n^{1/2}\varepsilon^{-3/2})$ in the nonconvex case (Theorem 8.3) and convergence rate $\widetilde{\mathcal{O}}(\frac{L R^3}{T^2} + \frac{σ_2 R^2}{T^2} + \frac{σ_1 R}{\sqrt{T}})$ in the convex case (Theorem 6.1). We also treat the matrix-free variant based on Hutchinson's estimator for Hessian and present a fast inner solver for the cubic subproblem with provable attainment of the required inexactness level.
academic

Re³MCN: Кубический метод Ньютона + Редукция дисперсии + Момент + Квадратичная регуляризация для конечносуммовых невыпуклых задач

Основная информация

  • ID статьи: 2510.08714
  • Название: Re³MCN: Cubic Newton + Variance Reduction + Momentum + Quadratic Regularization for Finite-sum Non-convex Problems
  • Авторы: Dmitry Pasechnyuk-Vilensky (MBZUAI), Dmitry Kamzolov (TSE, France), Martin Takáč (MBZUAI)
  • Классификация: math.OC (математическая оптимизация)
  • Дата публикации: 9 октября 2025 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2510.08714

Аннотация

В статье предложен стохастический метод кубической регуляризации Ньютона для задач оптимизации конечной суммы min⁡x∈RdF(x)=1n∑i=1nfi(x)\min_{x\in\mathbb{R}^d} F(x) = \frac{1}{n}\sum_{i=1}^n f_i(x), использующий технику рекурсивной редукции дисперсии типа SARAH с малыми мини-батчами размером b∼n1/2b \sim n^{1/2} и экспоненциальным скользящим средним (EMA) для оценки градиентов и матриц Гессе. Показано, что метод достигает точки второго порядка стационарности (SOSP) типа (ε,L2ε)(\varepsilon,\sqrt{L_2\varepsilon}) в невыпуклом случае с числом обращений к стохастическому оракулу n+O~(n1/2ε−3/2)n + \tilde{O}(n^{1/2}\varepsilon^{-3/2}), а в выпуклом случае — скорость сходимости O~(LR3T2+σ2R2T2+σ1RT)\tilde{O}(\frac{LR^3}{T^2} + \frac{\sigma_2 R^2}{T^2} + \frac{\sigma_1 R}{\sqrt{T}}).

Исследовательский контекст и мотивация

Основная проблема

Поиск точек второго порядка стационарности в невыпуклой оптимизации машинного обучения является центральной задачей. Обучение глубоких нейронных сетей, разложение тензоров и байесовский вывод обычно включают целевые функции, в которых методы первого порядка могут застревать в седловых точках.

Значимость проблемы

  • Выход из седловых точек: методы второго порядка используют информацию о кривизне для потенциального выхода из седловых точек
  • Вычислительные узкие места: вычислительная стоимость работы с точной матрицей Гессе слишком высока, особенно для крупномасштабных задач минимизации эмпирического риска с сложностью O(nd2)O(nd^2)
  • Теоретические гарантии: методы кубической регуляризации Ньютона (CRN) обеспечивают сильные гарантии сходимости для выхода из седловых точек на траектории оптимизации

Ограничения существующих методов

Существующие методы кубического Ньютона с редукцией дисперсии имеют следующие проблемы:

  1. Плохая зависимость сложности: некоторые методы имеют неудовлетворительную зависимость от размерности и целевой точности
  2. Неоптимальная сложность оракула: сложность обращений к оракулу градиента или Гессе не является оптимальной
  3. Ограничения практичности: отсутствует анализ эффективных практических версий

Исследовательская мотивация

Интеграция техник редукции дисперсии с обновлениями второго порядка для разработки алгоритмов, обладающих как теоретическими гарантиями, так и практической эффективностью, особенно в высокомерных сценариях, избегая узкого места O(d2)O(d^2).

Основные вклады

  1. Разработка алгоритма: предложен алгоритм Re³MCN, объединяющий EMA-SARAH оценители для градиентов и Гессе, а также решатель подзадач без матриц на основе оценителя Хатчинсона
  2. Теоретические гарантии: доказано, что Re³MCN достигает точку (ε,Lε)(\varepsilon,\sqrt{L\varepsilon})-SOSP в невыпуклом случае с числом обращений к оракулу O~(n+n1/2ε−3/2)\tilde{O}(n+n^{1/2}\varepsilon^{-3/2}), а в выпуклом случае — скорость сходимости O~(LR3T2+σ2R2T2+σ1RT)\tilde{O}(\frac{LR^3}{T^2} + \frac{\sigma_2R^2}{T^2} + \frac{\sigma_1R}{\sqrt{T}})
  3. Практическая эффективность: разработка алгоритма, применимого к высокомерным задачам, с решателем внутренних подзадач без матриц, избегающим узкого места O(d2)O(d^2)
  4. Реализуемость: проведены численные эксперименты сравнения существующих методов кубического Ньютона с редукцией дисперсии, реализованные как часть пакета OPTAMI

Подробное описание метода

Постановка задачи и предположения

Задача оптимизации: F(x)=1n∑i=1nfi(x)F(x) = \frac{1}{n}\sum_{i=1}^n f_i(x)

Основные предположения:

  • (A1) Гладкость второго порядка: матрица Гессе липшицева непрерывна с константой L2>0L_2 > 0
  • (A2) Ограниченность: матрица Гессе равномерно ограничена на траектории алгоритма
  • (A3-A5) Ограниченность дисперсии: стохастические оракулы имеют ограниченную дисперсию

Архитектура алгоритма

Основные компоненты алгоритма Re³MCN:

  1. График весов EMA: αt=c(t+1)−1/2\alpha_t = c(t+1)^{-1/2}, где c∈(0,1/2]c \in (0,1/2]
  2. Обновление SARAH:
    • Градиент: Δgt:=1b∑i∈It[∇fi(xt)−∇fi(xt−1)]\Delta g_t := \frac{1}{b}\sum_{i \in I_t}[\nabla f_i(x_t) - \nabla f_i(x_{t-1})]
    • Гессе: ΔHt:=1b∑i∈It[∇2fi(xt)−∇2fi(xt−1)]\Delta H_t := \frac{1}{b}\sum_{i \in I_t}[\nabla^2 f_i(x_t) - \nabla^2 f_i(x_{t-1})]
  3. Агрегация EMA:
    • gt←(1−αt)gt−1+αtg^tg_t \leftarrow (1-\alpha_t)g_{t-1} + \alpha_t \hat{g}_t
    • Ht←(1−αt)Ht−1+αtH^tH_t \leftarrow (1-\alpha_t)H_{t-1} + \alpha_t \hat{H}_t
  4. Кубическая подзадача: mt(s)=gtTs+12sTHts+βt2∥s∥2+M6∥s∥3m_t(s) = g_t^T s + \frac{1}{2}s^T H_t s + \frac{\beta_t}{2}\|s\|^2 + \frac{M}{6}\|s\|^3

Технические инновации

  1. Комбинация EMA-SARAH: впервые объединены экспоненциальное скользящее среднее и техника редукции дисперсии SARAH для более стабильных оценок
  2. Адаптивная квадратичная регуляризация:
    • Выпуклый случай: βt=2max⁡{C4σ2b,C5L2R}(t+1)\beta_t = 2\max\{\frac{C_4\sigma_2}{\sqrt{b}}, C_5L_2R\}(t+1)
    • Невыпуклый случай: введение фиксированного проксимального квадратичного члена для улучшения агрегации шума
  3. Реализация без матриц: использование оценителя Хатчинсона для произведения Гессе на вектор, избегая явного хранения матрицы Гессе

Теоретическая схема анализа

Граница одношагового спуска: E[F(xt+1)−F(xt)∣Gt]≤−L28E[∥st∥3]+23M−1/2E[∥ϵt∥3/2]+M−1/2E[∥Σt∥op3/2]E[F(x_{t+1}) - F(x_t) | \mathcal{G}_t] \leq -\frac{L_2}{8}E[\|s_t\|^3] + \frac{2}{3}M^{-1/2}E[\|\epsilon_t\|^{3/2}] + M^{-1/2}E[\|\Sigma_t\|_{op}^{3/2}]

Главное неравенство: агрегация членов дисперсии через неравенство BDG дает: L28E[ST]≤ΔF+C∗b3/4T9/8E[ST1/6]\frac{L_2}{8}E[S_T] \leq \Delta F + \frac{C_*}{b^{3/4}}T^{9/8}E[S_T^{1/6}]

Экспериментальная установка

Теоретическая верификация

Статья в основном предоставляет теоретический анализ, проверяемый следующим образом:

  1. Анализ сложности: детальный вывод границ сложности оракула
  2. Доказательство сходимости: строгое доказательство свойств сходимости алгоритма
  3. Выбор параметров: теоретическое руководство по оптимальному выбору параметров

Детали реализации

Размер батча: b=⌈n1/2⌉b = \lceil n^{1/2} \rceil

Длина эпохи:

  • Без регуляризации: Tmax=Θ(n1/3)T_{max} = \Theta(n^{1/3})
  • С регуляризацией: Tmax=Θ(n3/5)T_{max} = \Theta(n^{3/5})

Внутренний решатель: использование метода секущих с бинарным поиском + усеченный метод сопряженных градиентов для решения кубической подзадачи

Результаты экспериментов

Основные теоретические результаты

Теорема 8.3 (сложность в невыпуклом случае): При предположениях (A1)-(A5) алгоритм Re³MCN возвращает (ε,L2ε)(\varepsilon,\sqrt{L_2\varepsilon})-SOSP с общей сложностью оракула: G=H≤n+O~(n1/2ε−3/2)G = H \leq n + \tilde{O}(n^{1/2}\varepsilon^{-3/2})

Теорема 6.1 (скорость сходимости в выпуклом случае): Предположим, что FF — выпуклая функция, алгоритм достигает скорость сходимости: E[F(xT)−F∗]≤C1L2R3+Cββ0R2(T+1)2+C3σ1RT+1E[F(x_T) - F^*] \leq \frac{C_1L_2R^3 + C_\beta\beta_0R^2}{(T+1)^2} + \frac{C_3\sigma_1R}{\sqrt{T+1}}

Сравнение сложности

По сравнению с существующими методами:

  • Улучшенная зависимость от nn: улучшение с n5/6n^{5/6} или n4/5n^{4/5} до n1/2n^{1/2}
  • Оптимальная зависимость от ε\varepsilon: достижение оптимальной скорости ε−3/2\varepsilon^{-3/2}
  • Единая схема: одновременная обработка выпуклых и невыпуклых случаев

Связанные работы

Методы кубической регуляризации Ньютона

  • Nesterov & Polyak (2006): детерминированный метод CRN
  • Различные стохастические варианты: развитие методов SCRN

Техники редукции дисперсии

  • Метод SARAH: основа рекурсивной редукции дисперсии
  • Методы типа SPIDER: оценители разностей интегральных путей

Стохастические методы второго порядка

  • Применение методов редукции дисперсии Ньютона для сильно выпуклых функций
  • Применение VR-CN в оптимизации стратегий

Заключение и обсуждение

Основные выводы

  1. Теоретический прорыв: впервые достигнута сложность оракула n+O~(n1/2ε−3/2)n + \tilde{O}(n^{1/2}\varepsilon^{-3/2}) в невыпуклой оптимизации конечной суммы
  2. Технические инновации: комбинация EMA-SARAH обеспечивает более стабильную редукцию дисперсии
  3. Практичность: оценитель Хатчинсона делает метод применимым к высокомерным задачам

Ограничения

  1. Теоретические предположения: требуется липшицева непрерывность и ограниченность матрицы Гессе
  2. Настройка параметров: требуется надлежащий выбор нескольких гиперпараметров
  3. Экспериментальная верификация: в основном предоставляется теоретический анализ, отсутствует крупномасштабная эмпирическая верификация

Будущие направления

  1. Адаптивный выбор параметров: разработка методов адаптивного выбора весов EMA и параметров регуляризации
  2. Более слабые предположения: ослабление предположений о свойствах матрицы Гессе
  3. Практические приложения: верификация эффективности метода на практических задачах, таких как глубокое обучение

Глубокая оценка

Преимущества

  1. Теоретическая строгость: полный анализ сходимости и границы сложности
  2. Технические инновации: комбинация EMA и SARAH является новым техническим вкладом
  3. Практические соображения: оценитель Хатчинсона и быстрый внутренний решатель повышают практичность
  4. Единая схема: одновременная обработка выпуклых и невыпуклых случаев

Недостатки

  1. Отсутствие экспериментов: недостаток эмпирического сравнения с существующими методами
  2. Ограничения предположений: некоторые предположения могут не выполняться на практических задачах
  3. Зависимость от констант: константы в теоретических границах могут быть значительными

Влияние

  1. Теоретический вклад: значительный прогресс в теории стохастической оптимизации второго порядка
  2. Методологическая ценность: техника EMA-SARAH может вдохновить разработку других алгоритмов
  3. Практический потенциал: предоставляет новые инструменты для крупномасштабной невыпуклой оптимизации

Применимые сценарии

  • Крупномасштабное машинное обучение: особенно невыпуклые задачи, требующие выхода из седловых точек
  • Глубокое обучение: оптимизация второго порядка при обучении нейронных сетей
  • Научные вычисления: задачи оптимизации, требующие высокой точности решения

Библиография

Статья цитирует 15 связанных работ, охватывающих основные исследования в области методов кубической регуляризации, техник редукции дисперсии и стохастической оптимизации второго порядка, обеспечивая прочную теоретическую основу для данного исследования.

Общая оценка: это статья с важными теоретическими вкладами в область стохастической оптимизации второго порядка. Путем умелого объединения техник EMA и SARAH достигнуты лучшие на данный момент границы сложности оракула. Хотя отсутствует экспериментальная верификация, теоретический анализ строг, технические инновации явны, и работа оказывает важное влияние на развитие данной области.