Review of Mathematical Optimization in Federated Learning

Shusen Yang, Fangyuan Zhao, Zihao Zhou, Liang Shi, Xuebin Ren, and Zongben Xu · 2024

Read Review of Mathematical Optimization in Federated Learning by Shusen Yang, Fangyuan Zhao, Zihao Zhou, Liang Shi, Xuebin Ren, and Zongben Xu (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01630.txt.

Introduction

Shusen Yang and co-authors checked the math of federated learning in 2024, the setting where phones, hospitals, or banks jointly train one model without pooling their data. Optimization is the field's engine room: the partners must minimize a shared objective while obeying privacy rules and coping with quirks no normal distributed system faces. Above all data that differ wildly between people and noise on purpose injected for differential privacy.

The review systematically walks the current optimization literature, setting up it by starting claims, problem forms, method groups, and the convergence theory backing each. That form exposes where proofs lean on unrealistic starting claims and where forms still mismatch practice. A closing discussion of future directions makes the paper a map for mathematicians entering the field and a checklist for practitioners choosing a method whose guarantees survive contact with real federated data.

Catalog record

CREATORShusen Yang, Fangyuan Zhao, Zihao Zhou, Liang Shi, Xuebin Ren, and Zongben Xu
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01630

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Review of Mathematical Optimization in Federated Learning Shusen Yang, Fangyuan Zhao, Zihao Zhou, Liang Shi, Xuebin Ren, and Zongben Xu Abstract Federated Learning (FL) has been becoming a popular interdisciplinary research area in both applied mathematics and information sciences. Mathematically, FL aims to collaboratively optimize aggregate objective functions over distributed datasets while satisfying a variety of privacy and system constraints. Different from conventional distributed optimization methods, FL needs to address several specific issues (e.g., non-i.i.d. data distributions and differential private noises), which pose a set of new challenges in the problem formulation, algorithm design, and convergence analysis. In this paper, we will systematically review existing FL optimization research including their assumptions, formulations, methods, and theoretical results. Potential future directions are also discussed. \emails [email protected] (S. Yang), chan@email (F. Zhao), zhao@email (Z. Zhou) \ams 90C26, 90C31, 68W15, 68T05 keywords Federated Learning, distributed optimization, convergence analysis, error bounds. 1 Introduction With the increasingly stringent privacy regulations [ 1 , 2 ] , data isolation has been becoming the key bottleneck of data sciences and artificial intelligence. To address this issue, Federated learning (FL) emerges as a popular privacy-preserving distributed Machine Learning (ML) paradigm, which enables multiple data owners to jointly train ML models without sharing the raw data [ 3 , 4 , 5 ] . It has gained extensive interests from both academia and industry, and demonstrated great success across multiple domains, including medicine [ 6 ] , finance [ 7 ] , and industry [ 8 ] , etc. Mathematically, FL training tasks are essentially distributed optimization problems, which aim to minimize aggregate global objectives (e.g., the mean empirical loss), across a set of distributed data owners by exchanging model parameters trained on their local datasets [ 9 , 10 , 11 ] . Despite being similar in essence, FL optimization has many distinct characteristics from traditional distributed optimization. Their main difference lies in the communication environment. Specifically, traditional distributed optimization, mainly in the form of distributed ML [ 12 , 13 , 14 ] (some used in distributed resource allocation [ 15 , 16 , 17 ] ), is often used for high-throughput ML speedup in data centers. Here, multiple homogeneous computing nodes with uniformly distributed data partitions are connected by reliable networks with Gigabytes of bandwidth. However, FL is often applied to achieve collaborative and privacy-preserving ML in wide-area networks, where geographically distributed clients with naturally generated data collaborate to train ML models over bandwidth-constrained communication channels. Due to the drastic differences, FL needs to address a variety of specific and complicated issues in optimization. For example, naturally generated data at the FL clients are commonly heterogeneous, i.e., non-balanced and non-i.i.d. distributed, which leads to biased model aggregation. Considering limited communication bandwidth, FL often performs multiple local updates before the global aggregation, further amplifying the model bias caused by data heterogeneity. Furthermore, model dissemination and aggregation give rise to concerns of private information leakage and falsification. The decentralized communication architecture also leads to partially local approximations of global objective functions. These issues pose new challenges in optimization in FL, including problem formulation, algorithm design, and convergence analysis. In particular, typical challenges are summarized as follows: • Biased local objectives from non-i.i.d. datasets. The potentially unknown and non-i.i.d. data distributions among distributed nodes 1 1 1 The terms ”node”, ”client” and ”data owner” are used interchangeably within this survey. could result in biased local objectives [ 18 , 5 ] . Thus, the global objective function in FL optimization cannot be decomposed into trainable local objectives without bias. This means that the gradients of local models may largely deviate from the steepest descent direction of the global objective, leading to significant degradation of convergence speed and model accuracy [ 19 ] . • Perturbed gradients with DP noises. The Differential Privacy (DP) mechanisms [ 20 ] are commonly adopted in the FL optimization process to protect exchanged parameters or gradients, by introducing statistically unbiased noises (e.g., Gaussian [ 21 ] or Laplacian [ 22 ] noises). Despite the statistical unbiasedness, random noises may overwhelm the useful gradient information, causing unstable and slow convergence towards sub-optimal solutions [ 23 , 24 , 25 ] . • Partially approximated objectives under decentralized topologies. In FL systems with decentralized typologies, the model exchange has to rely on limited peer-to-peer neighborhood communication. The global objective for each data owner is thus partially approximated by consolidating the local objectives of their adjacent neighbors [ 26 ] . Consequently, the aggregated gradient in each step is also a partial approximation to that of the global objective. The approximation error can lead to significantly slower convergence [ 27 , 3 ] , especially in non-i.i.d. scenarios. • Obsolete solutions in online settings. Online FL optimization aims to learn a series of global functions with minimized cumulative losses from distributed sequential data [ 28 , 29 , 30 , 31 ] . However, the coming data may have a time-evolving distribution, resulting in inevitable generalization errors and instability of models on new data. Meanwhile, the inherent time-varying and cumulative constraints, e.g. communication, computing, and memory capabilities, may also complicate the problem modeling and solving [ 32 ] . Figure 1: The overview of the survey. This paper presents a systematic survey of the mathematical optimization in FL, summarizing the assumptions, problem formulations, optimization methods, and theoretical results. It is worth noting that although there exist several FL surveys [ 33 , 34 , 5 , 35 , 36 , 37 ] , all of them are presented from the perspective of information sciences, including the FL architectures [ 33 ] , algorithms [ 34 ] , and applications [ 38 ] , rather than mathematical optimizations like our survey. Fig. 1 illustrates the overview of this survey. We first review typical optimization methods in FL in Section 2 . The optimization challenges and solutions when dealing with non-i.i.d. data, DP noises, decentralized network topologies, and online FL optimizations are presented in Sections 3 - 6 , respectively. We then summarize other important works in Section 7 and discuss possible future directions in Section 8 . Finally, we conclude the survey in Section 9 . 2 Basic optimization methods in Federated Learning The common FL optimization is mostly studied in the context of horizontal FL (HFL) where participants possess the same feature space but different samples [ 39 , 5 ] . We will use HFL as the default FL setting 2 2 2 Another important category of FL is vertical FL (VFL), where participants share the same sample space but different features. More details can be referred to in [ 40 , 41 , 42 ] . to introduce the general workflow of FL optimization. Figure 2: General framework and workflow of FL. Algorithm 1 Algorithmic procedures of FL optimization 0: Client number N , objective function f(x)=\frac{1}{N}\sum_{i=1}^{N}f_{i}(x) , initialized x_{0} , total communication rounds T , local learning rate \eta_{l} , global learning rate \eta_{g} , number of local updates E in one round, distributed dataset \{\xi_{1},\ldots,\xi_{N}\} . 0: x^{T+1} . 1: for t\in\{1,\dots,T\} do 2: Server samples a subset S^{t} of K clients and server sends x^{t} to these clients; 3: for each client i\in

Read the complete text