2025-11-27T01:52:18.796624

On the Limits of Momentum in Decentralized and Federated Optimization

Zaccone, Karimireddy, Masone
Recent works have explored the use of momentum in local methods to enhance distributed SGD. This is particularly appealing in Federated Learning (FL), where momentum intuitively appears as a solution to mitigate the effects of statistical heterogeneity. Despite recent progress in this direction, it is still unclear if momentum can guarantee convergence under unbounded heterogeneity in decentralized scenarios, where only some workers participate at each round. In this work we analyze momentum under cyclic client participation, and theoretically prove that it remains inevitably affected by statistical heterogeneity. Similarly to SGD, we prove that decreasing step-sizes do not help either: in fact, any schedule decreasing faster than $Θ\left(1/t\right)$ leads to convergence to a constant value that depends on the initialization and the heterogeneity bound. Numerical results corroborate the theory, and deep learning experiments confirm its relevance for realistic settings.
academic

О пределах импульса в децентрализованной и федеративной оптимизации

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

  • ID статьи: 2511.20168
  • Название: On the Limits of Momentum in Decentralized and Federated Optimization
  • Авторы: Riccardo Zaccone (Политехнический университет Турина), Sai Praneeth Karimireddy (USC), Carlo Masone (Политехнический университет Турина)
  • Классификация: cs.LG (Машинное обучение), cs.AI
  • Дата публикации: Ноябрь 2025 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2511.20168

Аннотация

В данной статье глубоко исследуются теоретические ограничения импульса (momentum) в федеративном обучении и децентрализованной оптимизации. Хотя недавние исследования изучали использование импульса в локальных методах для улучшения распределённого SGD, особенно в федеративном обучении для смягчения влияния статистической гетерогенности, остаётся неясным, может ли импульс гарантировать сходимость при неограниченной гетерогенности в децентрализованных сценариях с частичным участием клиентов. Посредством теоретического анализа циклических моделей участия клиентов в статье доказывается, что импульс неизбежно подвержен влиянию статистической гетерогенности. Кроме того, убывающие размеры шагов не помогают: любое расписание с убыванием быстрее, чем Θ(1/t), приводит к сходимости к константе, зависящей от инициализации и границы гетерогенности. Численные эксперименты и эксперименты глубокого обучения подтверждают корректность теории и её релевантность в практических сценариях.

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

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

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

Важность проблемы

  1. Практические требования федеративного обучения: Современные приложения глубокого обучения требуют обучения на распределённых хранилищах данных или персональных устройствах, где клиенты часто не могут участвовать в каждом раунде (из-за сетевых сбоев, ограничений конфиденциальности или временной недоступности)
  2. Вызовы статистической гетерогенности: Неидентичное распределение данных клиентов (non-IID) приводит к дрейфу клиентов (client drift) и смещённым обновлениям сервера
  3. Недостаточное теоретическое понимание: Несмотря на широкое применение импульса в распределённых алгоритмах, теоретическое понимание его поведения в децентрализованной среде остаётся неполным

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

  • Алгоритмы на основе импульса (FedAvgM и FedCM) хорошо работают на практике, но не имеют теоретических гарантий при частичном участии
  • Существующие теоретические результаты:
    • 8 доказано, что при полном участии импульс может сходиться при неограниченной гетерогенности
    • 9 предложенный GHBM также обеспечивает аналогичные гарантии при циклическом частичном участии
    • Но теоретические свойства классического импульса при частичном участии остаются неясными

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

Посредством строгого теоретического анализа уточнить фундаментальные ограничения классических методов импульса и обеспечить теоретическое руководство для разработки алгоритмов федеративного обучения.

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

Основные вклады статьи включают:

  1. Теоретическое доказательство того, что импульс не может устранить влияние гетерогенности: При циклической выборке клиентов формально доказано, что импульс не может устранить влияние гетерогенности данных — центральной проблемы в децентрализованном и федеративном обучении
  2. Отрицательные результаты для убывающих размеров шагов: Доказано, что любое расписание размера шага с убыванием быстрее, чем Θ(1/t), приводит к сходимости к константе, зависящей от инициализации и границы гетерогенности, а не к оптимальному решению
  3. Систематическая аналитическая структура: Посредством моделирования динамики алгоритма как дискретной линейной системы обеспечивается чёткое разложение:
    • Нулевой входной отклик (zero-input response) захватывает общую цель всех клиентов
    • Нулевой состояний отклик (zero-state response) изолирует цели гетерогенности
  4. Экспериментальная верификация: Посредством численных экспериментов на теоретических задачах и экспериментов глубокого обучения (CIFAR-10) верифицируются теоретические находки в практических сценариях

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

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

Рассмотрим распределённую систему обучения, где множество клиентов S сотрудничают для решения задачи обучения, формализуемой как задача оптимизации конечной суммы:

θ∗=arg⁡min⁡θ∈Rd[f(θ):=1∣S∣∑i∈Sfi(θ)]\theta^* = \arg\min_{\theta \in \mathbb{R}^d} \left[ f(\theta) := \frac{1}{|S|} \sum_{i \in S} f_i(\theta) \right]

где:

  • fi(θ)f_i(\theta) — локальная целевая функция клиента ii
  • f(θ)f(\theta) — глобальная целевая функция
  • На каждом раунде tt участвует только подмножество St⊂SS_t \subset S клиентов (частичное участие)

Теоретическая аналитическая структура

1. Конструирование минимальной задачи гетерогенности

Для анализа поведения импульса при гетерогенности сконструирована наиболее благоприятная для импульса минимальная сценария:

  • Два клиента: f1(θ)=μ2θ2+Gθf_1(\theta) = \frac{\mu}{2}\theta^2 + G\theta, f2(θ)=μ2θ2−Gθf_2(\theta) = \frac{\mu}{2}\theta^2 - G\theta
  • Циклическая выборка: На каждом раунде поочередно выбирается один клиент
  • Глобальная цель: f(θ)=12(f1(θ)+f2(θ))=μ2θ2f(\theta) = \frac{1}{2}(f_1(\theta) + f_2(\theta)) = \frac{\mu}{2}\theta^2, оптимальное решение θ∗=0\theta^* = 0

Эта установка удовлетворяет:

  • μ\mu-сильной выпуклости (Предположение III.1)
  • Ограниченной разнице градиентов: 1∣S∣∑i=1∣S∣∥∇fi(θ)−∇f(θ)∥≤G\frac{1}{|S|}\sum_{i=1}^{|S|} \|\nabla f_i(\theta) - \nabla f(\theta)\| \leq G (Предположение III.2)
  • Циклическому участию (Предположение III.3)

2. Моделирование дискретной линейной системой (Лемма III.4)

Правила обновления FedAvgM и FedCM моделируются как дискретная линейная система:

z[t] = A[t]z[t-1] + Bu[t] \\ y[t] = Cz[t] \end{cases}$$ где: - Состояние: $z[t] = (\theta_t, \theta_{t-1})^T$ - Вход: $u[t] = ((-1)^t q_t^{(a)} G)$ (член, управляемый гетерогенностью) - Выход: $y[t] = \theta_t$ - Матрица состояния: $A[t] = \begin{pmatrix} p_t^{(a)} & -r_t^{(a)} \\ 1 & 0 \end{pmatrix}$ Для однократного локального обновления ($J=1$) FedAvgM и FedCM имеют одинаковое правило обновления: $$\theta_t = \theta_{t-1}(1 - \mu\tilde{\eta}_t + \beta) - \beta\theta_{t-2} + (-1)^t\tilde{\eta}_t G$$ где $\tilde{\eta}_t = \eta_t(1-\beta)$. #### 3. Разложение системного отклика Посредством развёртывания рекурсии системный выход может быть разложен как: $$y[t] = \underbrace{C\Psi(t,1)z[1]}_{\text{нулевой входной отклик}} + \underbrace{C\sum_{k=2}^t \Psi(t,k)Bu[k]}_{\text{нулевой состояний отклик}}$$ где матрица переходов состояния: $\Psi(t,k) := \prod_{s=k+1}^t A[s]$ **Физическая интерпретация**: - **Нулевой входной отклик**: Соответствует оптимизации общей цели $f_{hom}(\theta) = f(\theta)$, отражает влияние начальных условий - **Нулевой состояний отклик**: Соответствует членам гетерогенности $f_{het}(\theta) = \pm G\theta$ как внешним возмущениям ### Технические инновационные моменты #### 1. Системно-теоретический подход - Впервые моделируются алгоритмы импульса в федеративном обучении как дискретные линейные системы - Посредством разложения нулевого входного/состояний отклика чётко раскрывается механизм действия гетерогенности как "сигнала возмущения" #### 2. Техника диагонализации (доказательство Теоремы III.6) Для времязависимой системы матрица состояния разлагается как: $$A[t] = A_\infty + E[t]$$ где $A_\infty$ соответствует предельной матрице при $\eta_t \to 0$, затем посредством диагонализации: $$\bar{z}[t] = P^{-1}z[t] = (\Lambda + H[t])\bar{z}[t-1] + Wu[t]$$ получаются собственные значения $\lambda_1 = 1$ (маргинально устойчивое) и $\lambda_2 = \beta < 1$ (асимптотически устойчивое), соответствующие развязанным направлениям. #### 3. Метод самосогласованного анзаца (Self-consistent Ansatz) Для связанной системы предполагается асимптотическая форма $\bar{z}_1[t]$, проверяется, приводит ли выведённое из этого $\bar{z}_2[t]$ к согласованным выводам. ## Основные теоретические результаты ### Теорема III.5: Скорость сходимости при постоянном размере шага **Формулировка теоремы**: Для любых положительных констант $G, \mu$ существуют функции $\mu$-сильной выпуклости, удовлетворяющие Предположению III.2, такие что при надлежащем постоянном размере шага $\eta$ и произвольном коэффициенте импульса $\beta \in [0,1)$ асимптотическая ошибка FedCM и FedAvgM при циклическом частичном участии составляет: $$f(\theta_t) - f(\theta^*) = \Theta\left(\frac{G^2}{\mu T^2}\right)$$ **Ключевые идеи**: 1. **Нулевой входной отклик**: При выполнении условия на собственные значения $\eta \in (0, \frac{2(1+\beta)}{\mu(1-\beta)})$ сходится с экспоненциальной скоростью 2. **Нулевой состояний отклик**: Сходится к 2-периодическому предельному циклу с амплитудой: $$|\theta_\infty| = \frac{\eta(1-\beta)G}{2(1+\beta) - \mu\eta(1-\beta)}$$ 3. **Ограничение размера шага**: Для контроля ошибки сходимости необходимо выбрать $\eta = \Theta(1/T)$, приводя к линейной скорости сходимости $O(1/T^2)$ **Физический смысл**: Импульс не может устранить периодические колебания, вызванные гетерогенностью, необходимо контролировать амплитуду путём уменьшения размера шага. ### Теорема III.6: Скорость сходимости при убывающем размере шага **Формулировка теоремы**: Для полиномиально убывающего размера шага $\eta_t \sim O(1/t^\alpha)$, даже при инициализации из оптимального решения ($\theta_0 = \theta^*$), ошибка составляет: $$f(\theta_t) - f(\theta^*) = \begin{cases} \Theta\left(\frac{G^2}{\mu t^{2\alpha}}\right) & \text{если } 0 < \alpha < 1 \\ \Theta\left(\frac{G^2}{\mu t^{2\min(\mu\eta, 1)}}\right) & \text{если } \alpha = 1 \\ \Theta\left(\frac{G^2}{\mu}\right) & \text{если } \alpha > 1 \end{cases}$$ **Ключевые находки**: 1. **Медленное убывание ($0 < \alpha < 1$)**: - Нулевой входной отклик убывает с полиномиальной скоростью $O(t^{-\alpha})$ - Нулевой состояний отклик всё ещё убывает экспоненциально - Скорость сходимости $O(t^{-2\alpha})$ медленнее, чем $O(T^{-2})$ при постоянном размере шага 2. **Линейное убывание ($\alpha = 1$)**: - Скорость сходимости зависит от начального размера шага $\eta$ - При $\eta < 1/\mu$ скорость сходимости $O(t^{-\mu\eta})$ зависит от инициализации - При $\eta \geq 1/\mu$ скорость сходимости составляет $O(t^{-1})$ 3. **Быстрое убывание ($\alpha > 1$)**: - **Не может сходиться к оптимальному решению**, сходится к константе $\Theta(G/\mu)$ - Матрица переходов состояния больше не убывает к нулю - Как нулевой входной, так и нулевой состояний отклики сходятся к константе, зависящей от $G$ и $\theta_0$ **Математическая интуиция**: Посредством лемм B.2-B.9 установленные асимптотические границы матриц переходов состояния $\Psi_1(t,s,\alpha)$ и $\Psi_2(t,s,\alpha)$ точно характеризуют поведение сходимости в различных диапазонах $\alpha$. ## Экспериментальная установка ### Теоретические эксперименты **Целевые функции**: $f_1(\theta) = \frac{\mu}{2}\theta^2 + G\theta$, $f_2(\theta) = \frac{\mu}{2}\theta^2 - G\theta$ **Установка параметров**: - $\mu = 1$ (параметр сильной выпуклости) - $G \in \{0, 10, 100\}$ (уровень гетерогенности) - $\theta_0 \in \{0, 10\}$ (инициализация) - $\beta = 0.9$ (коэффициент импульса) - $T = 10^6$ (количество итераций) **Расписания размера шага**: 1. **Постоянный размер шага**: $\eta_t = \eta$ 2. **Полиномиальное убывание**: $\eta_t = \eta/t^\alpha$, $\alpha \in \{0.1, 0.5, 1, 2\}$ 3. **Экспоненциальное убывание**: $\eta_t = \eta\gamma^t$, $\gamma \in \{0.9999, 0.999, 0.99, 0.9\}$ ### Эксперименты глубокого обучения **Набор данных**: CIFAR-10 - Предварительная обработка обучающего набора: случайное обрезание, случайное горизонтальное отражение, нормализация - Количество клиентов: $|S| = 100$ - Разделение данных: согласно методу [19], моделирование максимального уровня гетерогенности (распределение Дирихле) **Архитектура модели**: 1. **CNN**: Архитектура, подобная LeNet-5 2. **ResNet-20**: Использование Group Normalization вместо Batch Normalization **Установка обучения**: - Коэффициент выборки клиентов: $C = 10\%$ (циклическая выборка) - Количество локальных шагов: $J = 1$ - Коэффициент импульса: $\beta = 0.9$ - Количество повторений: 5 независимых запусков **Поиск гиперпараметров**: - FedAvg: размер шага сервера $\eta \in \{2, 1.5, 1, 0.5, 0.1\}$, локальный размер шага $\eta_l \in \{0.1, 0.05, 0.01, 0.005\}$ - FedCM: аналогичный диапазон поиска ## Результаты экспериментов ### Результаты теоретических экспериментов (Таблица I) #### Ключевые находки: 1. **Линейное влияние гетерогенности**: - При $G = 100$: $\theta_t \approx 2.5 \times 10^{-5}$ (постоянный размер шага) - При $G = 10$: $\theta_t \approx 2.5 \times 10^{-6}$ (постоянный размер шага) - Пропорциональное соотношение верифицирует теоретическое предсказание $\Theta(G/\mu T)$ 2. **Влияние инициализации**: - Для медленного убывания ($\alpha < 1$) и постоянного размера шага конечные значения при $\theta_0 = 0$ и $\theta_0 = 10$ одинаковы - Верифицирует экспоненциальное убывание нулевого входного отклика 3. **Вред быстрого убывания** ($\alpha = 2$): - $G = 100, \theta_0 = 0$: $\theta_t = 4.8 \times 10^1$ - $G = 100, \theta_0 = 10$: $\theta_t = 5.7 \times 10^1$ - Не может сходиться к оптимальному решению $\theta^* = 0$ и зависит от инициализации 4. **Сравнение импульса и без импульса**: - Поведение сходимости с импульсом (слева) и без импульса (справа) подобно - Доказывает, что импульс не может принципиально улучшить зависимость от гетерогенности ### Эксперимент влияния размера шага (Таблица II) Верифицирует теоретическое предсказание Теоремы III.6 при $\alpha = 1$: | Начальный размер шага | $\theta_t$ ($\theta_0=0$) | $\theta_t$ ($\theta_0=10$) | |----------------------|--------------------------|---------------------------| | $\eta = \frac{1(1+\beta)}{\mu(1-\beta)} - \epsilon$ | $2.5 \times 10^{-6}$ | $2.5 \times 10^{-6}$ | | $\eta = \frac{1}{\mu} - \epsilon$ | $-3.9 \times 10^{-6}$ | $-1.2 \times 10^{-4}$ | При $\eta < 1/\mu$ конечное значение зависит от инициализации, верифицируя теоретическую скорость сходимости $O(t^{-\mu\eta})$. ### Результаты экспериментов глубокого обучения (Рисунок 1) **Экспериментальная установка**: CIFAR-10, циклическое участие клиентов, высокая гетерогенность **Наблюдения результатов**: 1. **FedAvg vs FedCM (ResNet-20)**: - Точность тестирования после 10000 раундов: примерно 60-70% - Эталон централизованного обучения: ≈89% - Значительный разрыв в производительности указывает на то, что импульс не может эффективно смягчить гетерогенность 2. **FedAvg vs FedCM (CNN)**: - Точность тестирования после 10000 раундов: примерно 50-60% - Эталон централизованного обучения: ≈86% - Производительность FedAvg и FedCM близка, без явного преимущества 3. **Ключевые идеи**: - При высокой гетерогенности и частичном участии методы федеративного обучения на основе классического импульса не могут обеспечить существенное улучшение - Результаты экспериментов согласуются с теоретическим анализом: импульс не может устранить фундаментальное влияние гетерогенности ## Связанные работы ### Оптимизация конечной суммы и варианты SGD 1. **SGD и методы случайного перемешивания**: - [12] Safran & Shamir 2020: исследование производительности SGD со случайным перемешиванием - [13] Koloskova et al. 2024: скорость сходимости IGD для неконвексных гладких функций - [14] Liu & Zhou 2024: сходимость последней итерации методов перемешивания градиентов 2. **Нижние границы для SGD**: - [15] Jentzen & von Wurstemberger 2020: нижние границы ошибок для алгоритма оптимизации стохастического градиентного спуска - [16] Nguyen et al. 2019: независимые от размерности нижние границы - [17] Kim et al. 2025: анализ IGD с малой эпохой для плохо обусловленных задач **Ключевое отличие**: Все вышеупомянутые работы не рассматривали импульс и требовали границы гетерогенности. В данной статье доказано, что даже при добавлении импульса эта фундаментальная зависимость сохраняется. ### Применение импульса в распределённом обучении 1. **Алгоритмы импульса в федеративном обучении**: - [2] FedAvgM (Hsu et al. 2019): импульс на стороне сервера - [4] FedCM (Xu et al. 2021): импульс на стороне клиента - [5] FedADC: ускоренное управление дрейфом - [6-7] Многошаговые методы инерционного импульса 2. **Теоретический прогресс**: - [8] Cheng et al. 2024: доказательство того, что при полном участии импульс может сходиться при неограниченной гетерогенности - [9] GHBM (Zaccone et al. 2025): обход ограничений посредством перспективы инкрементального агрегирования градиентов - [10] SlowMo: коммуникационно-эффективный распределённый SGD - [11] DiLoCo: распределённое обучение языковых моделей с низкой коммуникацией ### Уникальный вклад данной статьи Данная статья является **первой систематически анализирующей фундаментальные ограничения классического импульса при частичном участии** работой: - Чётко ответить на открытый вопрос "Может ли импульс устранить влияние гетерогенности при частичном участии" (ответ отрицательный) - Обеспечить полную аналитическую структуру (линейно-системный подход) - Доказать, что GHBM [9] в настоящее время единственный известный алгоритм импульса, который может обойти это ограничение ## Заключение и обсуждение ### Основные выводы 1. **Фундаментальные ограничения импульса**: При циклическом участии клиентов классический импульс (FedAvgM и FedCM) **не может устранить влияние статистической гетерогенности**, скорость сходимости остаётся зависимой от границы гетерогенности $G$ 2. **Отрицательные результаты для убывающих размеров шагов**: - Убывание медленнее, чем $\Theta(1/t)$: скорость сходимости замедляется - Убывание равно $\Theta(1/t)$: скорость сходимости зависит от начального размера шага - Убывание быстрее, чем $\Theta(1/t)$: **не может сходиться к оптимальному решению** 3. **Влияние количества локальных шагов**: Увеличение количества локальных шагов $J$ ухудшает зависимость от гетерогенности посредством эффекта дрейфа клиентов, но не изменяет асимптотическую скорость сходимости 4. **Особенность GHBM**: GHBM [9] в настоящее время единственный известный алгоритм импульса, который может обойти это ограничение при частичном участии ### Ограничения 1. **Область анализа**: - Анализируется только циклическая модель участия клиентов - Случайная равномерная выборка может иметь различное поведение (но эксперименты [9] показывают аналогичные результаты) 2. **Постановка задачи**: - Рассматриваются сильно выпуклые функции - Практическое глубокое обучение — это неконвексная оптимизация, полная применимость теоретических результатов требует дальнейшего исследования 3. **Упрощённый сценарий**: - Конструкция с двумя клиентами — наиболее благоприятный для импульса сценарий - Практические сценарии могут быть более сложными, но теоретическая нижняя граница уже раскрывает фундаментальное ограничение 4. **Масштаб экспериментов**: - Эксперименты глубокого обучения проводятся только на CIFAR-10 - Верификация на больших наборах данных и моделях требует дополнительных работ ### Направления будущих исследований 1. **Расширение на неконвексную оптимизацию**: Расширить теоретический анализ на неконвексные функции потерь, распространённые в глубоком обучении 2. **Анализ случайной выборки**: Анализ свойств сходимости при случайной равномерной выборке клиентов 3. **Улучшенная разработка алгоритмов**: - Исследование других возможных вариантов импульса, которые могут обойти ограничение помимо GHBM - Новые методы, объединяющие адаптивные скорости обучения и импульс 4. **Оптимизация практической системы**: Верификация теоретически обоснованной разработки алгоритмов в практических системах федеративного обучения ## Глубокая оценка ### Преимущества #### 1. Глубина теоретического вклада - **Строгие математические доказательства**: Посредством теории дискретных линейных систем обеспечивается полный анализ сходимости - **Точные границы скорости сходимости**: Не только предоставляются асимптотические сложности, но и анализируются постоянные множители - **Охват множественных сценариев**: Систематический анализ четырёх случаев: постоянный размер шага, медленное убывание, линейное убывание и быстрое убывание #### 2. Инновационность методологии - **Системно-теоретический подход**: Впервые моделируются алгоритмы федеративного обучения как линейные системы, обеспечивая совершенно новую аналитическую структуру - **Разложение нулевого входного/состояний отклика**: Чётко раскрывает взаимодействие между оптимизацией общей цели и возмущениями гетерогенности - **Техника диагонализации**: Ловко решает проблему анализа времязависимых систем #### 3. Достаточность экспериментов - **Полная теоретическая верификация**: Таблицы I и II точно верифицируют все ключевые теоретические предсказания - **Практическая релевантность**: Эксперименты CIFAR-10 демонстрируют применимость теоретических находок в практическом глубоком обучении - **Комплексные сравнения**: Одновременно сравниваются методы с импульсом и без импульса, различные расписания размера шага #### 4. Ясность изложения - **Пошаговое построение**: От конструирования задачи к системному моделированию и затем к теоретическому анализу, логика ясна - **Интуитивные объяснения**: Для каждого теоретического результата предоставляется физическая интуиция и математический смысл - **Подробное приложение**: Полные детали доказательства (25-страничное приложение) обеспечивают воспроизводимость ### Недостатки #### 1. Ограничения теоретического анализа - **Предположение сильной выпуклости**: Практическое глубокое обучение неконвексно, обобщаемость теоретических результатов ограничена - **Упрощённый сценарий**: Установка с двумя клиентами и одномерным параметром чрезмерно идеализирована - **Циклическая выборка**: Практические системы часто используют случайную выборку, применимость теоретических результатов требует дальнейшей верификации #### 2. Недостатки экспериментальной установки - **Единственный набор данных**: Верификация только на CIFAR-10, отсутствуют эксперименты на крупномасштабных наборах данных, таких как ImageNet - **Ограниченный масштаб модели**: ResNet-20 — относительно небольшая модель, поведение современных больших моделей (например, Transformer) неизвестно - **Недостаточные методы сравнения**: Отсутствует прямое сравнение с GHBM, невозможно количественно оценить разрыв в производительности #### 3. Практические соображения - **Отрицательные результаты**: Основное внимание уделяется доказательству "что не работает", руководство по "что работает" ограничено - **Чувствительность гиперпараметров**: Теория требует точного выбора размера шага (например, $\eta = \Theta(1/T)$), в практике сложно предварительно определить $T$ - **Стоимость коммуникации**: Не рассматривается компромисс между количеством коммуникационных раундов и вычислительными затратами #### 4. Глубина анализа - **Недостаточный анализ количества локальных шагов**: Хотя упоминается, что $J > 1$ ухудшает зависимость, отсутствует точное количественное исследование - **Влияние различных коэффициентов импульса**: В теории $\beta$ произвольный, но недостаточно подробно исследуется стратегия его выбора - **Постоянные сходимости**: Асимптотический анализ скрывает постоянные множители, фактическая скорость сходимости может существенно различаться ### Влияние #### 1. Вклад в область - **Теоретическая основа**: Обеспечивает строгую теоретическую основу для использования импульса в федеративном обучении - **Ответ на открытый вопрос**: Чётко отвечает на волнующий сообщество вопрос "Может ли импульс преодолеть гетерогенность" - **Направление исследований**: Указывает на важность новых методов импульса, таких как GHBM #### 2. Практическая ценность - **Руководство по разработке алгоритмов**: - Избегать расписаний размера шага с быстрым убыванием ($\alpha > 1$) - При высокой гетерогенности классический импульс может быть менее эффективным, чем ожидается - Рассмотреть использование альтернативных методов, таких как GHBM - **Настройка гиперпараметров**: - Размер шага должен быть выбран в масштабе $\Theta(1/T)$ - Выбор коэффициента импульса $\beta$ требует компромисса между скоростью сходимости и стабильностью #### 3. Воспроизводимость - **Отличные аспекты**: - Полные детали доказательства (приложения A-B) - Чёткая экспериментальная установка и гиперпараметры - Простая конструкция теоретической задачи - **Пространство для улучшения**: Код не опубликован (в статье не упоминается репозиторий кода) ### Применимые сценарии #### Сценарии, подходящие для применения 1. **Теоретические исследования**: - Анализ сходимости федеративного обучения - Исследование нижних границ оптимизационных алгоритмов - Количественный анализ влияния гетерогенности 2. **Руководство по выбору алгоритма**: - Сценарии федеративного обучения с высокой гетерогенностью и частичным участием - Критические приложения, требующие теоретических гарантий (например, здравоохранение, финансы) #### Менее подходящие сценарии 1. **Крупномасштабная неконвексная оптимизация**: Теория основана на предположении сильной выпуклости, применимость к глубокому обучению требует осторожности 2. **Сценарии полного участия**: Существующие работы [8] доказывают, что при полном участии импульс жизнеспособен, отрицательные результаты данной статьи неприменимы 3. **Сценарии с ограничениями коммуникации**: Не рассматривается стоимость коммуникации, может недооценивать практическую ценность импульса ### Общая оценка Это **теоретически строгая и с чёткими вкладами** отличная статья. Посредством инновационной аналитической структуры линейных систем впервые систематически раскрывает фундаментальные ограничения классического импульса в федеративном обучении. Несмотря на более сильные теоретические предположения и ограниченный масштаб экспериментов, её основные идеи — **импульс не может устранить влияние гетерогенности, и быстрое убывание размера шага вредно** — имеют важное значение для разработки алгоритмов федеративного обучения. Основная ценность статьи заключается в: 1. **Чётком определении теоретических границ**: Ясно определены границы применимости методов импульса 2. **Обеспечении аналитических инструментов**: Моделирование линейных систем может быть обобщено на анализ других распределённых алгоритмов 3. **Указании направления исследований**: Подчёркивает необходимость новых методов импульса, таких как GHBM Рекомендации для будущих работ: 1. Расширить на неконвексную оптимизацию и случайную выборку 2. Провести подробное теоретическое и экспериментальное сравнение с GHBM 3. Верифицировать теоретически обоснованное проектирование алгоритмов в крупномасштабных практических системах **Рекомендуемый индекс**: ★★★★☆ (4.5/5) - Теоретическая глубина: ★★★★★ - Практическая ценность: ★★★★☆ - Инновационность: ★★★★★ - Полнота: ★★★★☆ ## Ключевые ссылки [1] Polyak, B. (1964). Some methods of speeding up the convergence of iteration methods. USSR Computational Mathematics and Mathematical Physics. [2] Hsu et al. (2019). Measuring the effects of non-identical data distribution for federated visual classification. arXiv:1909.06335. [8] Cheng et al. (2024). Momentum benefits non-iid federated learning simply and provably. ICLR. [9] Zaccone et al. (2025). Communication-efficient heterogeneous federated learning with generalized heavy-ball momentum. Transactions on Machine Learning Research. [15] Jentzen & von Wurstemberger (2020). Lower error bounds for the stochastic gradient descent optimization algorithm. Journal of Complexity.