2025-11-10T03:06:05.923380

Revisit First-order Methods for Geodesically Convex Optimization

Shu, Jiang, Shi et al.
In a seminal work of Zhang and Sra, gradient descent methods for geodesically convex optimization were comprehensively studied. In particular, Zhang and Sra derived a comparison inequality that relates the iterative points in the optimization process. Since their seminal work, numerous follow-ups have studied different downstream usages of their comparison lemma. In this work, we introduce the concept of quasilinearization to optimization, presenting a novel framework for analyzing geodesically convex optimization. By leveraging this technique, we establish state-of-the-art convergence rates -- for both deterministic and stochastic settings -- under weaker assumptions than previously required. The technique of quasilinearization may prove valuable for other non-Euclidean optimization problems.
academic

Переосмотр методов первого порядка для геодезически выпуклой оптимизации

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

  • ID статьи: 2504.06814
  • Название: Revisit First-order Methods for Geodesically Convex Optimization
  • Авторы: Yunlu Shu, Jiaxin Jiang, Lei Shi, Tianyu Wang (Фуданьский университет)
  • Классификация: math.OC (математическая оптимизация и управление)
  • Дата публикации: 16 октября 2025 г. (версия arXiv v4)
  • Ссылка на статью: https://arxiv.org/abs/2504.06814

Аннотация

В данной статье переосмотрены методы первого порядка для геодезически выпуклой оптимизации. Чжан и Сра в своей новаторской работе всесторонне исследовали методы градиентного спуска для геодезически выпуклой оптимизации, в частности вывели сравнительные неравенства для итерационных точек в процессе оптимизации. В статье вводится концепция квазилинеаризации в область оптимизации и предлагается новая схема анализа геодезически выпуклой оптимизации. Используя эту технику, авторы устанавливают современные скорости сходимости для детерминированного и стохастического случаев при более слабых предположениях, чем ранее. Техника квазилинеаризации может быть полезна для других задач оптимизации в неевклидовых пространствах.

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

Определение задачи

В статье рассматривается задача оптимизации на многообразиях Адамара: min⁡x∈Mf(x)\min_{x \in M} f(x) где M — многообразие Адамара, оснащённое римановой метрикой g.

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

  1. Ограничения существующих методов: Классический подход Чжана и Сра опирается на два сильных предположения:
    • (A1) Равномерная нижняя граница секционной кривизны (условие CBB)
    • (A2) Априорная верхняя граница диаметра траектории
  2. Практические проблемы: Многие важные многообразия Адамара не удовлетворяют условию CBB, например искривленные произведения многообразий, кривизна которых может стремиться к минус бесконечности.
  3. Основная задача: Как сохранить современные скорости сходимости при устранении предположений (A1) и (A2)?

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

  1. Введение схемы квазилинеаризации: Впервые применена концепция квазилинеаризации Берга и Николаева к анализу задач оптимизации
  2. Устранение сильных предположений: Установлены гарантии сходимости без требования нижней границы кривизны и предположения об ограниченной области
  3. Детерминированная оптимизация: Достигнута скорость сходимости O(1/t) для геодезически выпуклых функций
  4. Стохастическая оптимизация: Достигнута скорость сходимости Õ(1/√t) для гладких геодезически выпуклых функций
  5. Теоретический прорыв: Получен положительный ответ на вопрос (Q), то есть возможно сохранить оптимальные скорости сходимости при более слабых предположениях

Описание методов

Квазилинейное внутреннее произведение

Для любых двух упорядоченных геодезических сегментов xy→\overrightarrow{xy} и zw→\overrightarrow{zw} на многообразии M квазилинейное внутреннее произведение определяется как:

⟨xy→,zw→⟩=∣xy→∣∣zw→∣cos⁡q(xy→,zw→)\langle\overrightarrow{xy}, \overrightarrow{zw}\rangle = |\overrightarrow{xy}||\overrightarrow{zw}|\cos_q(\overrightarrow{xy}, \overrightarrow{zw})

где: cos⁡q(xy→,zw→)=∣xw→∣2+∣yz→∣2−∣xz→∣2−∣yw→∣22∣xy→∣∣zw→∣\cos_q(\overrightarrow{xy}, \overrightarrow{zw}) = \frac{|\overrightarrow{xw}|^2 + |\overrightarrow{yz}|^2 - |\overrightarrow{xz}|^2 - |\overrightarrow{yw}|^2}{2|\overrightarrow{xy}||\overrightarrow{zw}|}

Определение квазивыпуклости

Функция f является q-выпуклой, если: f(x)≥f(y)+⟨yExpy(gradf(y))→,yx→⟩+μ2d2(x,y)f(x) \geq f(y) + \langle\overrightarrow{y\text{Exp}_y(\text{grad}f(y))}, \overrightarrow{yx}\rangle + \frac{\mu}{2}d^2(x,y)

Проксимальный градиентный алгоритм

Основной алгоритм использует неявное проксимальное обновление: xt=Expxt+1(ηgradf(xt+1))x_t = \text{Exp}_{x_{t+1}}(\eta \text{grad}f(x_{t+1}))

что эквивалентно решению: xt+1=arg⁡min⁡z{f(z)+12ηd(xt,z)2}x_{t+1} = \arg\min_z \left\{f(z) + \frac{1}{2\eta}d(x_t, z)^2\right\}

Теоретический анализ

Основные теоремы

Теорема 1 (детерминированный случай): Пусть f — геодезически выпуклая функция на многообразии Адамара M. Проксимальный градиентный алгоритм удовлетворяет: f(xt)−f(x∗)≤∣x0x∗→∣2ηtf(x_t) - f(x^*) \leq \frac{|\overrightarrow{x_0x^*}|^2}{\eta t}

Теорема 2 (стохастический случай): При предположении ограниченной дисперсии стохастический проксимальный градиентный алгоритм с шагом ηt=12Lt\eta_t = \frac{1}{2L\sqrt{t}} удовлетворяет: 1∑t=1Tαt∑t=1Tαt(EF(xt)−F(x∗))≤∣x0x∗→∣22∑t=1Tαt+σ2log⁡(T+1)∑t=1Tαt\frac{1}{\sum_{t=1}^T \alpha_t}\sum_{t=1}^T \alpha_t(\mathbb{E}F(x_t) - F(x^*)) \leq \frac{|\overrightarrow{x_0x^*}|^2}{2\sum_{t=1}^T \alpha_t} + \frac{\sigma^2 \log(T+1)}{\sum_{t=1}^T \alpha_t}

Ключевые технические идеи

  1. Преимущества квазилинеаризации:
    • Применима ко всем многообразиям Адамара без требования нижней границы кривизны
    • Сохраняет алгебраические свойства, аналогичные евклидову пространству
    • Естественно совместима с геодезической выпуклостью
  2. Методы доказательства:
    • Использование леммы 2 для установления связи между квазилинейным и стандартным внутренним произведением
    • Применение техники телескопического суммирования для обработки итерационных неравенств
    • Умелое избежание ограничений традиционной теоремы о сравнении треугольников

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

Сравнительный анализ

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

МетодТребует нижней границы кривизны?Требует ограниченной области?Требует решения сложных уравнений?Скорость сходимости
Чжан и СраДаДаНетO(t⁻¹)
Liu et al.НетДаДаO†(t⁻²)
Данный методНетНетНетO(t⁻¹)

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

Статья предоставляет эффективные методы реализации проксимального оператора:

  • Решение сильно геодезически выпуклых подзадач методом градиентного спуска
  • Стратегия «теплого старта» для повышения вычислительной эффективности
  • Гарантия сходимости: f(zt)−f(z∗)≤(1−μ4L0)t(f(z0)−f(z∗))f(z_t) - f(z^*) \leq (1-\frac{\mu}{4L_0})^t(f(z_0) - f(z^*))

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

Историческое развитие

  1. Классические работы: Bonnabel (2013) и Zhang & Sra (2016) установили основную схему анализа
  2. Последующие исследования: Множество работ пытались ослабить предположения, но ни одна полностью не решила вопрос (Q)
  3. Техническое направление: Традиционные методы опираются на теорему сравнения треугольников Топоногова; данная статья открывает новый путь квазилинеаризации

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

  • Традиционные методы: Зависят от нижней границы секционной кривизны, сложный анализ
  • Данный метод: Использует квазилинеаризацию, более слабые предположения, более простой анализ
  • Вычислительная сложность: Избегает решения сложных уравнений, содержащих Exp⁻¹ и Γ

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

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

  1. Успешно решена открытая проблема вопроса (Q), стоявшая десять лет
  2. Установлены оптимальные скорости сходимости при минимальных предположениях
  3. Предоставлены новые инструменты анализа для оптимизации в неевклидовых пространствах

Ограничения

  1. По-прежнему требуется структура многообразия Адамара (неположительная кривизна)
  2. Проксимальный оператор может требовать численного решения
  3. Постоянные множители могут быть неоптимальными

Направления будущих исследований

  1. Расширение на задачи негладкой оптимизации
  2. Исследование возможности ускоренных методов
  3. Применение к конкретным задачам машинного обучения

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

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

  1. Теоретический прорыв: Решение важной открытой проблемы в области
  2. Методологическое новшество: Введение техники квазилинеаризации является новаторским
  3. Минимальные предположения: Достижение оптимальных скоростей сходимости при наименьших предположениях
  4. Простота анализа: Доказательства более прямолинейны по сравнению с традиционными методами

Недостатки

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

Влияние

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

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

  1. Оптимизация с ограничениями на многообразиях в машинном обучении
  2. Геодезические задачи в вычислительной геометрии
  3. Численное решение дифференциальных уравнений в частных производных
  4. Вычисление равновесия в экономике

Список литературы

Статья цитирует 61 связанную работу, включая:

  • Berg & Nikolaev (2008): исходная работа по квазилинеаризации
  • Zhang & Sra (2016): классический анализ геодезически выпуклой оптимизации
  • Bonnabel (2013): стохастический градиентный спуск на римановых многообразиях
  • Множество недавних работ по оптимизации на многообразиях Адамара

Общая оценка: Это высококачественная теоретическая статья, которая успешно решает важную открытую проблему в области геодезически выпуклой оптимизации путём введения техники квазилинеаризации. Несмотря на отсутствие численных экспериментов, её теоретический вклад значителен, и она предоставляет новую схему анализа и инструменты для оптимизации в неевклидовых пространствах.