统一分析随机梯度下降中任意数据打乱的收敛性，涵盖各类打乱策略。
A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond
- 提出通用假设，刻画跨轮次数据打乱的依赖关系。
- 首次实现对依赖型打乱方法的统一收敛分析。
- 可推广至联邦学习中的客户端任意排序场景。
本文旨在为基于数据打乱的随机梯度下降（SGD）提供统一收敛分析，其中数据在每轮前被重新排列。通过分析打乱方式之间的关系，我们将现有方法分为四类：任意打乱、独立打乱（含随机重排）、单次打乱（含增量梯度、Shuffle One 和 Nice Permutation）以及依赖型打乱（如 GraBs Lu et al., 2022；Cooper et al., 2023）。现有统一分析无法涵盖依赖型打乱，因其存在跨轮次的打乱依赖。本文提出一个通用假设以捕捉此类依赖关系，构建了一个涵盖所有代表性算法的统一框架。进一步，将该框架拓展至联邦学习中的客户端排序问题，提出了带正则化参与的联邦学习中任意客户端顺序的统一分析框架。
原文摘要 · Abstract (English)
We aim to provide a unified convergence analysis for permutation-based Stochastic Gradient Descent (SGD), where data examples are permuted before each epoch. By examining the relations among permutations, we categorize existing permutation-based SGD algorithms into four categories: Arbitrary Permutations, Independent Permutations (including Random Reshuffling), One Permutation (including Incremental Gradient, Shuffle One and Nice Permutation) and Dependent Permutations (including GraBs Lu et al., 2022; Cooper et al., 2023). Existing unified analyses failed to encompass the Dependent Permutations category due to the inter-epoch dependencies in its permutations. In this work, we propose a general assumption that captures the inter-epoch permutation dependencies. Using the general assumption, we develop a unified framework for permutation-based SGD with arbitrary permutations of examples, incorporating all the aforementioned representative algorithms. Furthermore, we adapt our framework on example ordering in SGD for client ordering in Federated Learning (FL). Specifically, we develop a unified framework for regularized-participation FL with arbitrary permutations of clients.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。