Federated Learning: From Theory to Practice
Full text
Federated Learning From Theory to Practice Alexander Jung October 19, 2025 please cite as: A. Jung, Federated Learning: From Theory to Practice. Espoo, Finland: Aalto University, 2025. 1
Preface This book offers a hands-on introduction to building and understanding federated learning (FL) systems. FL enables multiple devices – such as smartphones, sensors, or local computers – to collaboratively train machine learning (ML) models, while keeping their data private and local. It is a powerful solution when data cannot or should not be centralized due to privacy, regulatory, or technical reasons. The book is designed for students, engineers, and researchers who want to learn how to design scalable, privacy-preserving FL systems. Our main focus is on personalization: enabling each device to train its own model while still benefiting from collaboration with relevant devices. This is achieved by leveraging similarities between the learning tasks associated with devices. We represent these similarities as weighted edges of a federated learning network (FL network). The key idea is to represent real-world FL systems as networks of devices, where nodes correspond to device and edges represent communication links and data similarities between them. The training of personalized models for these devices can be naturally framed as a distributed optimization problem. This optimization problem is referred to as generalized total variation minimization (GTVMin) and ensures that devices with similar learning tasks learn similar model parameters. Our approach is both mathematically principled and practically motivated. While we introduce some advanced ideas from optimization theory and graphbased learning, we aim to keep the book accessible. Readers are guided through the core ideas step-by-step, with intuitive explanations. Throughout, 2
we maintain a focus of building FL systems that are trustworthy—robust against attacks, privacy-friendly, and secure. Audience. We assume a basic background in undergraduate-level mathematics, including calculus and linear algebra. Familiarity with concepts such as convergence, derivatives, and norms will be helpful but not strictly necessary. No prior experience with ML or optimization is required, as we build up most concepts from first principles. The book is intended for advanced undergraduates, graduate students, and practitioners who are looking for a practical, principled, and privacy-friendly approach to decentralized ML. Structure. The book begins by introducing the key motivations and challenges of FL. We then move on to introduce the notion of an FL network and explain how they capture the structure of distributed ML applications. The core chapters develop the GTVMin formulation and explore how to solve it using various distributed optimization techniques. Later chapters focus on practical concerns such as robustness and privacy protection of GTVMinbased systems. A comprehensive glossary is also included to better support the reader. Acknowledgements. The development of this book has greatly benefited from feedback and insights gathered during the course CS-E4740 Federated Learning at Aalto University, taught between 2023 and 2025. I am grateful to Bo Zheng, Olga Kuznetsova, Diana Pfau, and Shamsiiat Abdurakhmanova for their thoughtful comments on early drafts. Special thanks go to Ekkehard Schnoor and Mikko Seesto for their careful proofreading of the manuscript and to Konstantina Olioumtsevits for her meticulous revision of the glossary. 3
Some of the figures in the glossary have been prepared with the help of Salvatore Rastelli and Juliette Gronier. This work was supported by: •the Research Council of Finland (grants 331197, 363624, 349966), •the European Union (grant 952410), •the Jane and Aatos Erkko Foundation (grant A835), and • Business Finland, as part of the project Forward-Looking AI Governance in Banking and Insurance (FLAIG). 4
Contents 1 Introduction to Federated Learning 1 1.1 Core Techniques in Federated Learning . . . . . . . . . . . . . 3 1.2 Book Structure and Roadmap . . . . . . . . . . . . . . . . . . 4 1.3 Exercises.............................. 6 2 Machine Learning Foundations for FL 8 2.1 Components of ML Systems: A Design Framework . . . . . . 8 2.2 Computational Aspects of empirical risk minimization (ERM) 13 2.3 Statistical Aspects of ERM . . . . . . . . . . . . . . . . . . . . 14 2.4 Validation and Diagnosis of ML . . . . . . . . . . . . . . . . . 19 2.5 Regularization........................... 23 2.6 From ML to FL via Regularization . . . . . . . . . . . . . . . 27 2.7 Exercises.............................. 29 3 A Design Principle for FL 31 3.1 FLNetworks ........................... 31 3.2 Generalized Total Variation . . . . . . . . . . . . . . . . . . . 35 3.3 Generalized Total Variation Minimization . . . . . . . . . . . 42 3.3.1 Computational Aspects of GTVMin . . . . . . . . . . . 45 3.3.2 Statistical Aspects of GTVMin . . . . . . . . . . . . . 48 3.4 Non-Parametric Models in FL Networks . . . . . . . . . . . . 51 3.5 Interpretations .......................... 52 3.6 Exercises.............................. 56 3.7 Proofs ............................... 63 3.7.1 Proof of Proposition 3.1 . . . . . . . . . . . . . . . . . 63 5
4 Gradient Methods for Federated Optimization 64 4.1 GradientDescent ......................... 65 4.2 How to Choose the Learning Rate . . . . . . . . . . . . . . . . 68 4.3 WhentoStop? .......................... 70 4.4 Perturbed Gradient Step . . . . . . . . . . . . . . . . . . . . . 74 4.5 Handling Constraints - Projected Gradient Descent . . . . . . 75 4.6 Extended Gradient Methods for Federated Optimization . . . 78 4.7 Gradient Methods as Fixed-Point Iterations . . . . . . . . . . 81 4.8 Exercises.............................. 85 5 FL Algorithms 88 5.1 Gradient Descent for GTVMin . . . . . . . . . . . . . . . . . . 89 5.2 Message Passing Implementation . . . . . . . . . . . . . . . . 92 5.3 FedSGD.............................. 98 5.4 FedAvg...............................101 5.5 FedProx ..............................107 5.6 FedRelax..............................109 5.7 A Unified Formulation . . . . . . . . . . . . . . . . . . . . . . 113 5.8 Asynchronous FL Algorithms . . . . . . . . . . . . . . . . . . 115 5.9 Exercises..............................122 5.10Proofs ...............................125 5.10.1 Proof of Proposition 5.1 . . . . . . . . . . . . . . . . . 125 5.10.2 Proof of Proposition 5.2 . . . . . . . . . . . . . . . . . 126 6 Key Variants of Federated Learning 129 6.1 Single-ModelFL .........................130 6
6.2 ClusteredFL ...........................132 6.3 HorizontalFL...........................136 6.4 VerticalFL ............................138 6.5 Personalized Federated Learning . . . . . . . . . . . . . . . . . 139 6.6 Few-Shot Learning . . . . . . . . . . . . . . . . . . . . . . . . 143 6.7 Exercises..............................144 6.8 Proofs ...............................145 6.8.1 Proof of Proposition 6.1 . . . . . . . . . . . . . . . . . 145 7 Graph Learning for FL Networks 147 7.1 Edges as Design Choice . . . . . . . . . . . . . . . . . . . . . . 148 7.2 Measuring (Dis-)Similarity Between Datasets . . . . . . . . . . 154 7.3 Graph Learning Methods . . . . . . . . . . . . . . . . . . . . . 157 7.4 Exercises..............................160 8 Trustworthy FL 161 8.1 Human Agency and Oversight . . . . . . . . . . . . . . . . . . 162 8.2 Technical Robustness and Safety . . . . . . . . . . . . . . . . . 163 8.2.1 Sensitivity Analysis . . . . . . . . . . . . . . . . . . . . 164 8.2.2 Estimation Error Analysis . . . . . . . . . . . . . . . . 166 8.2.3 Robustness of FL Algorithms . . . . . . . . . . . . . . 169 8.2.4 Network Resilience . . . . . . . . . . . . . . . . . . . . 175 8.3 Privacy and Data Governance . . . . . . . . . . . . . . . . . . 176 8.4 Transparency ...........................177 8.5 Diversity, Non-Discrimination and Fairness . . . . . . . . . . . 182 8.6 Societal and Environmental Well-Being . . . . . . . . . . . . . 183 7
8.7 Exercises..............................185 9 Privacy Protection in FL 186 9.1 Measuring Privacy Leakage . . . . . . . . . . . . . . . . . . . 186 9.2 Ensuring Differential Privacy . . . . . . . . . . . . . . . . . . . 194 9.3 Private Feature Learning . . . . . . . . . . . . . . . . . . . . . 197 9.4 Exercises..............................201 10 Cybersecurity in FL: Attacks and Defenses 205 10.1 A Simple Attack Model . . . . . . . . . . . . . . . . . . . . . . 206 10.1.1 Model Poisoning . . . . . . . . . . . . . . . . . . . . . 208 10.1.2 Data Poisoning . . . . . . . . . . . . . . . . . . . . . . 208 10.2AttackTypes ...........................210 10.3 Making FL Robust Against Attacks . . . . . . . . . . . . . . . 212 10.4Exercises..............................216 8
Lists of Symbols Sets and Functions a∈ A The object ais an element of the set A. a:= b Depending on the context, we use the symbol := either to mean a definition or to mean an assignment (e.g., within a pseudocode for an algorithm. A ⊆ B A is a subset of B. A ⊂ B A is a strict subset of B. NThe natural numbers 1,2, . . .. RThe real numbers x[1]. R+The non-negative real numbers x≥0. R++ The positive real numbers x > 0. |x|The absolute value of a real number x∈R. 9
Rh A regularizer that assigns a hypothesis h a measure for the anticipated increase in average loss when h is applied to data points outside the training set. Ev The validation error of a hypothesis h , which is its average loss incurred over a validation set. b Lh|D The empirical risk or average loss incurred by the hypothesis hon a dataset D. Et The training error of a hypothesis h , which is its average loss incurred over a training set. t A discrete-time index t = 0 , 1 , . . . used to enumerate sequential events (or time instants). α A regularization parameter that controls the amount of regularization. w A parameter vector w= w1, . . . , wdT of a model, e.g., the weights of a linear model or in an artificial neural network (ANN). h(w)(·) A hypothesis map that involves tunable model parameters w1, . . . , wdstacked into the vector w=w1, . . . , wdT. Φ(·)A feature map Φ:X → X′:x7→ x′:= ϕx∈ X′. 16
X The feature matrix X= x (1),..., x (m)T∈Rm×d of a dataset, consisting of m data points each characterized by a feature vector x(r), for r= 1, . . . , m. y The label vector y= y(1), . . . , y(m)T∈Rm of a dataset, consisting of mdata points each characterized by a label y(r), for r= 1, . . . , m. 17
Federated Learning G= (V,E) An undirected graph whose nodes i∈ V represent devices within an FL network. The undirected edges {i, i′} ∈ E , each having a positive weight Ai,i′ , represent either some form of connectivity between devices or statistical similarities between their local datasets. i∈ V A node that represents some device within an FL network. The device can access a local dataset and train a local model. C Given a graph we denote by C ⊆ V a subset (or cluster) of nodes which are connected by many edges with large weights. |∂C| The boundary of a cluster, which is the sum Pi∈C,i′/∈C Ai,i′ . G(C)The induced subgraph of Gusing the nodes in C ⊆ V. L(G)The Laplacian matrix of a graph G. L(C)The Laplacian matrix of the induced graph G(C). N(i)The neighborhood of a node iin a graph G. d(i) The weighted degree d(i) := Pi′∈N(i)Ai,i′ of a node i in a graph G. d(G) max The maximum weighted node degree of a graph G. 18
D(i) The local dataset D(i) carried by node i∈ V of an FL network. mi The number of data points (i.e., sample size) contained in the local dataset D(i)at node i∈ V. x(i,r) The features of the r -th data point in the local dataset D(i). y(i,r)The label of the r-th data point in the local dataset D(i). w(i) The local model parameters of device i within an FL network. Li(w) The local loss function used by device i to measure the usefulness of some choice wfor the local model parameters. R(i)h A regularizer used for model training by device i within a FL network. This regularizer typically depends on the model parameters of other devices i′∈ V \{i}. d(i,i′) A quantitative measure for the variation (or discrepancy) between trained local models at nodes i, i′. stackw(i)n i=1 The vector w (1)T,..., w (n)TT ∈Rdn that is obtained by vertically stacking the local model parameters w(i)∈Rd. 19
1 Introduction to Federated Learning We are surrounded by devices, such as smartphones and wearables, that generate decentralized collections of local datasets [5 – 9]. These local datasets often exhibit an intrinsic network structure, arising from functional dependencies or statistical similarities (see Chapter 7.3). For example, contact networks underpin pandemic modeling, network medicine maps disease relationships via co-morbidities [10], and social sciences leverage social graphs to relate the data of connected individuals [11]. Similarly, weather stations of the Finnish Meteorological Institute (FMI) produce local datasets with statistical properties influenced by geographic proximity. Federated learning (FL) is an umbrella term for distributed optimization methods that train machine learning (ML) models directly at the locations of data generation [12 – 16]. Unlike traditional ML workflows that centralize data before training, FL leverages in-situ computations. Figure 1.1 contrasts these approaches. From an engineering perspective, this book is about building federated learning systems by formulating them as network-based optimization problems. The core idea is to represent a real-world FL setup via an federated learning network (FL network), where nodes correspond to devices with local datasets and models, and edges reflect communication capabilities or statistical similarity. We then pose FL as an optimization problem over this FL network, which we call generalized total variation minimization (GTVMin). GTVMin balances local model performance with smoothness of model parameters across connected nodes. Different choices for how to measure model variation across the FL network 1
Fig. 1.1. Left: A basic ML method uses a single dataset to train a single model. Right: Decentralized collection of devices with the ability to access data and train models locally. lead to different flavors of FL methods. The overarching goal is to derive these methods in a principled way by applying distributed optimization methods. All FL algorithms we study can be seen as fixed-point iterations for solving an instance of GTVMin. Beyond methodology, FL is also driven by several practical motivations: • Privacy. By exchanging only updates to model parameters, FL avoids raw data transmission and thus mitigates privacy risks (see Chapter 9). • Robustness. FL systems can tolerate stragglers and are more resilient to cyber-attacks, such as data poisoning (see Chapter 10). • Parallelism. We can interpret the interconnected devices of a FL network as a parallel computer. One example of such a parallel computer is a mobile network constituted by smartphones that can communicate 2
via radio links. This parallel computer allows to speed up computations required for the training of ML models (see Chapter 4). • Democratization. FL enables collective learning using low-cost, widely available devices – rather than relying on centralized high-end hardware [17,18]. • Communication Efficiency. In remote or bandwidth-limited scenarios, training locally can be cheaper than transmitting raw datasets [19]. • Personalization. FL naturally supports training personalized models that adapt to device-specific data distributions (see Chapter 6). 1.1 Core Techniques in Federated Learning To build and analyze FL algorithms, this book draws on core mathematical concepts: Euclidean space. Our main mathematical structure for the study and design of FL systems is the Euclidean space Rd . We expect familiarity with the algebraic and geometric structure of Rd [20,21]. For example, we often use the spectral decomposition of positive semi-definite (psd) matrices that naturally arise in the formulation of FL applications. We will also use the geometric structure of Rd , which is defined by the inner-product w T w ′ := Pd j=1 wjw′ j between two vectors w , w ′∈Rd and the induced norm ∥w∥2:= √wTw=qPd j=1 w2 j. Calculus. A main toolbox for the design the FL algorithms are variants of gradient descent (GD). The common idea of gradient-based methods is to approximate a function f (w)locally by a linear function. This local linear 3
approximation is determined by the gradient ∇f (w). We, therefore, expect some familiarity with multivariable calculus [2]. Fixed-Point Iterations. Each algorithm that we discuss in this book can be interpreted as a fixed-point iteration of some operator P : Rd→Rd . These operators depend on the local datasets and personal models used within an FL system. A prime example of such an operator is the gradient step of gradient-based methods (see Chapter 4). The computational properties of these FL algorithms are determined by the contraction properties of the underlying operator [22]. 1.2 Book Structure and Roadmap This book is organized into three parts: • Part I: ML Refresher. Chapters 2 and 4 review basic ML concepts and optimization methods. These chapters serve both to refresh prerequisite knowledge and to highlight techniques like regularization and gradient descent that underpin FL. • Part II: FL Theory and Methods. Chapter 3 introduces the FL network and formulates the core optimization principle, i.e., GTVMin. Chapters 4 and 5 show how to apply optimization methods to derive scalable and personalized FL algorithms. Chapter 6 explores main FL variants as special cases of GTVMin, and Chapter 7 discusses methods for constructing meaningful edge structures in FL networks. • Part III: trustworthy artificial intelligence (trustworthy AI). Chapters 8–10 explore key requirements for trustworthy AI systems, 4
including privacy protection and robustness against data poisoning. These chapters link FL methodology to emerging ethical and regulatory demands in AI deployment. 5
1.3 Exercises 1.1. Complexity of Matrix Inversion. Choose your favourite computer architecture (represented by a mathematical model) and think about how much computation is required - in the worst case - by the most efficient algorithm that can invert any given invertible matrix Q ∈Rd×d ? Try also to reflect on how practical your chosen computer architecture is, i.e., is it possible to buy such a computer in your nearest electronics shop? 1.2. Vector Spaces and Euclidean Norm. Consider data points, each characterized by a feature vector x∈Rdwith entries x1, x2, . . . , xd. • Show that the set of all feature vectors forms a vector space under standard addition and scalar multiplication. •Calculate the Euclidean norm of the vector x= (1,−2,3)T. •If x(1) = (1,2,3)Tand x(2) = (−1,0,1)T, compute 3x(1) −2x(2). 1.3. Matrix Operations in Linear Models. Linear regression methods learn model parameters b w∈Rdvia solving the optimization problem: b w= arg min w∈Rd∥y−Xw∥2 2, with some matrix X∈Rm×d, and some vector y∈Rm. • Derive a closed-form expression for b w that is valid for arbitrary matrix X, and vector y. •Discuss the conditions under which XTXis invertible. 6
• Statistical aspects. How useful is the solution ˆ h to (1) in general, i.e., how accurate is the prediction ˆ h (x)for the label y of an arbitrary data point with features x? 2.2 Computational Aspects of ERM A principled approach to design ML methods is to apply some optimization method to solve (1) [27]. Most of these optimization methods operate in an iterative fashion: Starting from an initial choice h(0) , they construct a sequence h(0), h(1), h(2),..., which are hopefully increasingly accurate approximations to a solution ˆ h of (1) . The computational complexity of such a ML method can be measured by the number of iterations required to guarantee some prescribed level of approximation. For a parametric model and a smooth loss function, we can solve (2) by gradient-based methods: Starting from an initial parameters w (0) , we iterate the gradient step: w(k):= w(k−1) −η∇fw(k−1) (3) =w(k−1) + (2η/m) m X r=1 x(r)y(r)−w(k−1)Tx(r).(8) This gradient update can be compactly expressed using the feature matrix 13
(4) and label vector (5) as1 w(k)=w(k−1) +η·2 mXTy−Xw(k−1). How much computation do we need for one iteration of (8) ? How many iterations do we need? We will try to answer the latter question in Chapter 4. The first question can be answered more easily for a typical computational infrastructure (e.g., “Python running on a commercial Laptop”). The evaluation of (8) then typically requires around m arithmetic operations (addition, multiplication). It is instructive to consider the special case of a linear model that does not use any feature, i.e., h (x) = w . For this extreme case, the ERM (2) has a simple closed-form solution: bw= (1/m) m X r=1 y(r).(9) Thus, for this special case of the linear model, solving (9) is to sum m numbers y(1), . . . , y(m) . The amount of computation, measured by the number of elementary arithmetic operations, required by (9) is proportional to m. 2.3 Statistical Aspects of ERM We can train a linear model on a given training set as ERM (2) . But how useful is the solution b w of (2) for predicting the labels of data points outside 1The gradient of the objective function (3) can be expressed as ∇f(w) = −2 mXT(y−Xw). 14
the training set? Consider applying the learned hypothesis h(b w) to an arbitrary data point not contained in the training set. What can we say about the resulting prediction error y−h(b w) (x)in general? In other words, how well does h(b w)generalize beyond the training set. A widely used approach to study the generalization of ML methods uses a simple probabilistic models: The idea is to interpret data points as independent and identically distributed (i.i.d.) random variables (RVs) with common probability distribution p (x , y ). Under this independent and identically distributed assumption (i.i.d. assumption), we can evaluate the overall performance of a hypothesis h∈ H via the expected loss (or risk) E{L((x, y), h)}.(10) One example of a probability distribution p (x , y )relates the label y with the features xof a data point as y=wTx+εwith x∼N(0,I), ε∼N(0, σ2),E{εx}=0.(11) A simple calculation reveals the expected squared error loss of a given linear hypothesis h(x) = xTb was E{(y−h(x))2}=∥w−b w∥2+σ2.(12) Strictly speaking, (12) only holds for constant model parameters b w . However, the learned model parameters b w are often the output of a ML method that is applied to a dataset D . If we interpret the data points in D as i.i.d. realizations from some underlying probability distribution, we can replace the expectation on the LHS of (12) with the conditional expectation E(y−h(x))2D[28]. 15
The first component in (12) is the estimation error ∥w−b w∥2 of a ML method that reads in the training set and delivers an estimate b w (e.g., via (2) ) for the parameters of a linear hypothesis. The second component σ2 in (12) can be interpreted as the intrinsic noise level of the label y . We cannot hope to find a hypothesis with an expected loss below σ2. We next study the estimation error w−b w incurred by the specific estimate b w = b w(LR) (6) delivered by linear regression methods. To this end, we first use the probabilistic model (11) to decompose the label vector yin (5) as y=Xw +n, with n:= ε(1), . . . , ε(m)T.(13) Inserting (13) into (6) yields b w(LR) ∈argmin w∈Rd wTQw +wTq′+wTe(14) with Q:=(1/m)XTX,q′:=−(2/m)XTXw, and e:=−(2/m)XTn.(15) Figure 2.2 depicts the objective function of (14) . It is a perturbation of the convex quadratic function w T Qw +w T q ′ , which is minimized at w= w . In general, the minimizer b w(LR) delivered by linear regression is different from wdue to the perturbation term wTein (14). The following result bounds the deviation between b w(LR) and w under the assumption that the matrix Q= (1/m)XTXis invertible.2 Proposition 2.1. Consider a solution b w(LR) to the ERM instance (14) that is applied to the dataset (13) . If the matrix Q= (1 /m )X T Xis invertible, 2 Can you think of sufficient conditions on the feature matrix of the training set that ensure Q= (1/m)XTXis invertible? 16
w a w b w(LR) wTQw+wTq′ wTQw+wT(q′+e) wTe Fig. 2.2. The estimation error of linear regression is determined by the effect of the perturbation term w T eon the minimizer of the convex quadratic function wTQw +wTq′. 17
with minimum eigenvalue λ1(Q)>0, b w(LR) −w 2 2≤∥e∥2 2 λ2 1 (15) =4 m2 XTn 2 2 λ2 1 .(16) Proof. Let us rewrite (14) as b w(LR) ∈argmin w∈Rd f(w)with f(w) := w−wTQw−w+eTw−w.(17) Clearly fw = 0 and, in turn, f ( b w ) = minw∈Rdf (w) ≤ 0. On the other hand, f(w)(17) =w−wTQw−w+eTw−w (a) ≥w−wTQw−w−∥e∥2∥w−w∥2 (b) ≥λ1∥w−w∥2 2−∥e∥2∥w−w∥2.(18) Step ( a )used Cauchy–Schwarz inequality and ( b )used the EVD (7) of Q. Evaluating (18) for w=b wand combining with fb w≤0yields (16). The bound (16) suggests that the estimation error bw(LR) −w is small if λ1 (Q)is large. This smallest eigenvalue of the matrix Q= (1 /m )X T Xcould be controlled by a suitable choice (or transformation) of features xof a data point. Trivially, we can increase λ1 (Q)by a factor of 100 if we scale each feature by a factor of 10. However, this approach would also scale the error term XTn 2 2 in (16) by a factor of 100. For some applications, we can find feature transformations that increase λ1 (Q)but do not increase XTn 2 2 . We finally note that the error term XTn 2 2 in (16) vanishes if the noise vector n is orthogonal to the columns of the feature matrix X. 18
It is instructive to evaluate the bound (16) for the special case where each data point has the same feature value x = 1. Here, the probabilistic model (13) reduces to a “signal in noise” model [29], y(r)=x(r)w+ε(r)with x(r)= 1,(19) with some true underlying parameter w . The noise terms ε(r) , for r = 1 , . . . , m , are realizations of i.i.d. RVs with probability distribution N (0 , σ2 ). The feature matrix then becomes X=1and, in turn, Q= 1, λ1 (Q) = 1. Inserting these values into (16) results in the bound bw(LR) −w2≤4∥n∥2 2/m2. For the labels and features in (19), the solution of (14) is given by bw(LR) = (1/m) m X r=1 y(r)(19) =w+ (1/m) m X r=1 ε(r). 2.4 Validation and Diagnosis of ML The above analysis of the generalization error started from postulating the probabilistic model (11) for the generation of data points. Strictly speaking, if the data points are not generated according to the probabilistic model the bound (16) does not apply. Thus, we might want to use a more data-driven approach for assessing the usefulness of a learned hypothesis ˆ h obtained, e.g., from solving ERM (1). Loosely speaking, validation tries to find out if a learned hypothesis ˆ h performs similarly well inside and outside the training set. A basic form of validation is to compute the average loss of a learned hypothesis ˆ h on some 19
data points not included in the training set. We refer to these data points as the validation set. Algorithm 1 summarizes a single iteration of a prototypical ML workflow that consists of model training and validation. The workflow starts with an initial choice of a dataset D , model H , and loss function L(·,·) . We then repeat Algorithm 1 several times. After each repetition, based on the resulting training error and validation error, we modify the some of the design choices for the dataset, the model and the loss function. Algorithm 1 One Iteration of ML Training and Validation Input: dataset D, model H, loss function L(·,·) 1: split Dinto a training set D(train) and a validation set D(val) 2: learn a hypothesis via solving ERM b h∈argmin h∈H X (x,y)∈D(train) L((x, y), h)(20) 3: compute resulting training error Et:= (1/|D(train)|)X (x,y)∈D(train) L(x, y),b h 4: compute validation error Ev:= (1/|D(val)|)X (x,y)∈D(val) L(x, y),b h Output: learned hypothesis (or trained model) b h , training error Et and validation error Ev We can diagnose an ERM-based ML method, such as Algorithm 1, by 20
comparing its training error with its validation error. This diagnosis is further enabled if we know a baseline E(ref) . One important source for a baseline E(ref) are probabilistic models for the data points. Given a probabilistic model p (x , y ), we can compute the minimum achievable risk (10) . Indeed, the minimum achievable risk is precisely the expected loss of the Bayes estimator b h (x)of the label y , given the features xof a data point. The Bayes estimator b h (x)is fully determined by the probability distribution p(x, y)[30, Chapter 4]. A further potential source for a baseline E(ref) is an existing, but for some reason unsuitable, ML method. This existing ML method might be computationally too expensive to be used for the ML application at hand. However, we might still use its statistical properties as a baseline. We can also use the performance of human experts as a baseline. For example,if we develop a ML method to detect skin cancer from images, a possible baseline is the classification accuracy achieved by experienced dermatologists [31]. We can diagnose a ML method by comparing the training error Et with the validation error Evand the baseline E(ref). •Et≈Ev≈E(ref) : The training error is on the same level as the validation error and the baseline. There seems to be little point in trying to improve the method further since the validation error is already close to the baseline. Moreover, the training error is not much smaller than the validation error which indicates that there is no overfitting. •Ev≫Et : The validation error is significantly larger than the training error, which hints at overfitting. We can address overfitting either by 21
reducing the effective dimension of the hypothesis space or by increasing the size of the training set. To reduce the effective dimension of the hypothesis space, we can use fewer features (in a linear model), a smaller maximum depth of decision trees or fewer layers in an artificial neural network (ANN). Instead of this coarse-grained discrete model pruning, we can also reduce the effective dimension of a hypothesis space continuously via regularization (see [23, Ch. 7]). •Et≈Ev≫E(ref) : The training error is on the same level as the validation error and both are significantly larger than the baseline. Thus, the learned hypothesis seems to not overfit the training set. However, the training error achieved by the learned hypothesis is significantly larger than the baseline. There can be several reasons for this to happen. First, it might be that the hypothesis space is too small, i.e., it does not include a hypothesis that provides a satisfactory approximation for the relation between the features and the label of a data point. One remedy to this situation is to use a larger hypothesis space, e.g., by including more features in a linear model, using higher polynomial degrees in polynomial regression, using deeper decision trees or ANNs with more hidden layers (deep net). Second, besides the model being too small, another reason for a large training error could be that the optimization algorithm used to solve ERM (20) is not working properly (see Chapter 4). •Et≫Ev : The training error is significantly larger than the validation error. The idea of ERM (20) is to approximate the risk (10) of a 22
2.7 Exercises 2.1. Fundamental Limits for Linear regression. Linear regression learns model parameters of a linear model to minimize the risk Ey− w T x 2 where (x, y) is a RV. In practice, we do not observe the RV (x, y) itself but a (realization of a) sequence of i.i.d. RVs x(t), y(t) , for t = 1 , 2 , . . . . The minimax risk is a lower bound on the risk achievable by any learning method [33, Ch. 15]. Determine the minimax risk in terms of the probability distribution of (x, y). 2.2. Uniqueness of Eigenvectors. Consider the EVD Q= Pd j=1 λj u (j) u (j)T of a psd matrix Q. The EVD consists of orthonormal eigenvectors u (j) and non-negative eigenvalues λj , with Qu (j) = λj u (j) , for j = 1 , . . . , d . Can you provide conditions on the eigenvalues λ1≤. . . ≤λd such that the (unit-norm) eigenvectors are unique? 2.3. Penalty Term as Data augmentation. Consider a ML method that trains a model with model parameters w. The training uses ERM with squared error loss. Show that regularization of the model training via adding a penalty term α∥w∥2 2 is equivalent to a specific form of data augmentation. What is the augmented training set? 2.4. Data Augmentation via Linear Interpolation. Consider a ML method that trains a model, with model parameters w, from a training set D . Each data point z ∈ D is characterized by a feature vector x ∈Rd and label y∈R , i.e., z= (x, y) . We augment the training set by adding, for each pair of two different data points z , z ′∈ D , synthetic data points ˜ z(r) := z+ (z ′− z) r/ 100 and , for r = 0 ,..., 99. Does this augmentation typically increase the training error? 29
2.5. Ridge Regression via Deterministic Data Augmentation. Ridge regression is obtained from linear regression by adding the penalty term α∥w∥2 2 to the average squared error loss incurred by the hypothesis h(w) on the training set D, min w(1/m) m X r=1 y(r)−hx(r)2+α∥w∥2 2.(26) Construct an augmented training set D′ such that the objective function of (26) coincides with the objective function of plain linear regression using D′ as training set. To construct D′ , add carefully chosen data points to the original training set D = y(1),x(1),...,y(m),x(m) . Generalize the construction of D′to implement a generalized form of ridge regression, min w(1/m) m X r=1 y(r)−hx(r)2+α∥w−e w∥2 2.(27) Here, we used some prescribed reference model parameters e w . Note that (27) reduces to basic ridge regression (26) for the specific choice e w=0. 30
3 A Design Principle for FL Chapter 2 reviewed ERM as a central design principle for traditional, centralized ML systems that rely on a single dataset to train a single model. This chapter extends these foundations to the distributed setting of FL, where learning takes place over a network of devices, each having their own datasets and models. We begin in Section 3.1 by introducing the notion of an FL network – a mathematical abstraction for FL systems. Each node of an FL network represents a device that collects a local dataset and trains a local model, while the edges encode communication links and statistical similarities between local datasets. Section 3.2 introduces the concept of GTV as a measure of discrepancy between local model parameters at connected nodes. This notion leads directly to Section 3.3, where we develop GTVMin as a principled regularization framework for training parametric local models in a federated setting. We then generalize this approach in Section 3.4 to accommodate non-parametric local models, broadening its applicability. Finally, Section 3.5 offers several interpretations of GTVMin that connect it to broader themes in applied mathematics and statistics, highlighting its conceptual and practical significance in FL design. 3.1 FL Networks Consider a FL system consisting of a collection of devices, indexed by i = 1 , . . . , n . The number n of devices can be arbitrarily large—potentially on 31
the order of billions—as encountered in internet-scale FL applications.Each device i can access a local dataset D(i) and train a personalized model H(i) . These devices collaborate over a communication network to learn a local hypothesis h(i)∈ H(i) . The quality of each local hypothesis is assessed using a loss function Lih(i). We now introduce the concept of an FL network as a mathematical model for FL applications. An FL network consists of an undirected weighted graph G = (V,E) with nodes V := { 1 , . . . , n} and undirected edges E between pairs of different nodes. The nodes V represent devices with varying amounts of computational resources. An undirected edge {i, i′}∈E in an FL network represents a form of similarity between device i and device i′ . The amount of similarity is represented by an edge weight Ai,i′ . We can collect edge weights into an adjacency matrix A ∈Rn×n , with Ai,i′ = Ai′,i . Figure 3.1 depicts an example of an FL network. D(i),H(i) D(i′),H(i′) Ai,i′ Fig. 3.1. Example of an FL network whose nodes i∈ V represent different devices. Each device i generates a local dataset D(i) and trains a local model H(i) . Some devices i, i′ are connected by an undirected edge {i, i′} with a positive edge weight Ai,i′. Note that the undirected edges E of an FL network encode a symmetric notion of similarity between devices: If the device i is similar to the device 32
i′, i.e., {i, i′}∈E, then also the device i′is similar to the device i. For some FL applications, an asymmetric notion of similarity, represented by directed edges, could be more accurate. However, the generalization of an FL network to directed graphs is beyond the scope of this book. It can be convenient to replace a given FL network G with an equivalent fully connected FL network G′ (see Figure 3.2). The fully connected graph G′ contains an edge between every pair of two different nodes i, i′, E′={i, i′}:i, i′∈ V, i =i′. The edge weights are chosen A′ i,i′ = Ai,i′ for any edge {i, i′} ∈ E and A′ i,i′ = 0 if the original FL network Gdoes not contain an edge between nodes i, i′. 1 2 3 4 1 2 3 4 Fig. 3.2. Left: An FL network G consisting of n = 4 nodes. Right: Equivalent fully connected FL network G′ with the same nodes and non-zero edge weights A′ i,i′=Ai,i′for {i, i′}∈Eand A′ i,i′= 0 for {i, i′}/∈ E. An FL network is more than the undirected weighted graph G : It also includes the local dataset D(i) and the local model H(i) (or its model parameters w (i) )for each device i∈ V . The details of the generation and the format of a local dataset will not be important in what follows. A local dataset is just one possible means to construct a loss function in order to evaluate model parameters. However, to build intuition, we can think of a local dataset D(i) 33
as a labelled dataset D(i):= x(i,1), y(i,1),...,x(i,mi), y(i,mi).(28) Here, x (i,r) and y(i,r) denote, respectively, the features and the label of the r th data point in the local dataset D(i) . Note that the size mi of the local dataset can vary between different nodes i∈ V. It is convenient to collect the feature vectors x (i,r) and labels y(i,r) into a feature matrix X(i)and label vector y(i), respectively, X(i):= x(i,1),...,x(i,mi)T, and y(i):= y(i,1), . . . , y(i,mi)T.(29) The local dataset D(i) can then be represented compactly by the feature matrix X(i)∈Rmi×dand the vector y(i)∈Rmi. Besides the local dataset D(i), each node i∈ G also carries a local model H(i) . Our focus is on parametric local models with by model parameters w (i)∈Rd , for i = 1 , . . . , n . The usefulness of a specific choice of the local model parameter w (i) is then measured by a local loss function Liw(i) , for i = 1 , . . . , n . Note that we can use different local loss functions Li(·) = Li′(·) at different nodes i, i′∈ V. We now have introduced all the components of an FL network. Strictly speaking, an FL network is a tuple G,{H(i)}i∈V,{Li(·)}i∈V consisting of an undirected weighted graph G , a local model H(i) and local loss function Li(·) for each node i∈ V . In principle, all of these components are design choices that influence the computational and statistical properties of the FL algorithms presented in Chapter 5. To some extend, also the edges E in the FL network are a design choice. 34
The role (or meaning) of an edge {i, i′} in an FL network is two-fold: First, it represents a communication link that allows to exchange messages between devices i, i′ . Second, an edge {i, i′} indicates similar statistical properties of local datasets generated by devices i, i′ . It then seems natural to learn similar hypothesis maps h(i), h(i′) . This is actually the main idea behind all the FL algorithms that we will discuss in the rest of this book. To make this idea precise, we next discuss how to obtain quantitative measures for how much local hypothesis maps h(i) vary across the edges {i, i′}∈E of an FL network. 3.2 Generalized Total Variation Consider an FL network with nodes i = 1 , . . . , n , undirected edges E with edge weights Ai,i′> 0for each {i, i′} ∈ E . For each edge {i, i′} ∈ E , we want to couple the training of the corresponding local models H(i),H(i′) . The strength of this coupling is determined by the edge weight Ai,i′ . We implement the coupling by penalizing the variation (or discrepancy)between the model parameters w(i),w(i′). We can measure the variation between two trained local models h(i), h(i′) across an edge {i, i′} ∈ E in different ways. For example, we can compare their predictions on a common test set Dby computing d(i,i′):= (1/|D|)X x∈D h(i)(x)−h(i′)(x)2.(30) In principle, we can use a different test set in (30) for each edge {i, i′} of G . For example, the test set could be obtained by merging randomly selected data points from each local dataset D(i),D(i′). Our main focus will be FL applications that use parametric local models, 35
i.e., each node learns local model parameters w (i)∈Rd , for i = 1 , . . . , n . Here, we can measure the variation between h(w(i)) and h(w(i′)) directly in terms of the model parameters w (i), w (i′) at the nodes of an edge {i, i′} . In particular, we use a regularizer ϕ : Rd→R that measures the difference between the model parameters, d(i,i′):= ϕw(i)−w(i′).(31) The penalty function ϕ will be mainly a design choice. Our main requirement is that ϕ is monotonically increasing 5 with respect to some norm in the Euclidean space Rd [16, 34]. This requirement ensures symmetry, i.e., ϕ w (i)− w (i′) = ϕ w (i′)− w (i) , allowing its use as a measure of variation across an undirected edge {i, i′}∈E. Summing up the edge-wise variations (weighted by the edge weights) yields the GTV of a collection of local model parameters, X {i,i′}∈E Ai,i′ϕw(i)−w(i′).(32) Our main focus will be on the special case of (32) , obtained for ϕ ( · ) := ∥·∥2 2 , X {i,i′}∈E Ai,i′ w(i)−w(i′) 2 2.(33) The choice of penalty ϕ ( · )has a crucial impact on the computational and statistical properties of the FL algorithms presented in Chapter 5. Our main choice during the rest of this book will be the penalty function ϕ ( · ) := ∥·∥2 2 . This choice often allows to formulate FL as the minimization of a smooth convex function, which can be done via simple gradient-based methods (see 5 A function f : R→R is monotonically increasing if f ( x ) ≤f ( y )whenever x≤y . This means that larger argument values never result in smaller function values. 36
Chapter 7). On the other hand, choosing ϕ to be a norm results in FL algorithms that require more computation but less training data [34]. The connectivity of an FL network G can be characterized locally - around a node i∈ V - by its node degree d(i):= X i′∈N(i) Ai,i′.(34) Here, we used the neighborhood N(i) := {i′∈ V : {i, i′} ∈ E} of node i∈ V . A global characterization for the connectivity of G is the maximum node degree d(G) max := max i∈V d(i)(34) = max i∈V X i′∈N(i) Ai,i′.(35) Besides inspecting the node degrees, we can study the connectivity of G also via the eigenvalues and eigenvectors of its Laplacian matrix L (G)∈Rn×n . 6 The Laplacian matrix of an undirected weighted graph G is defined elementwise as L(G) i,i′:= −Ai,i′for i=i′,{i, i′}∈E Pi′′=iAi,i′′ for i=i′ 0else. (36) Figure 3.3 illustrates the Laplacian matrix of a small graph. The Laplacian matrix is symmetric and psd, which follows from the 6 The study of graphs via the eigenvalues and eigenvectors of associated matrices is the main subject of spectral graph theory [35,36]. 37
1 2 3 L(G)= 2−1−1 −1 1 0 −1 0 1 Fig. 3.3. Left: Example of an FL network G with three nodes i = 1 , 2 , 3 that are connected via two edges with unit weight A1,2 = A1,3 = 1. Right: Laplacian matrix L(G)∈R3×3of G. identity wT(L(G)⊗I)w=X {i,i′}∈E Ai,i′ w(i)−w(i′) 2 2 for any d∈N,w:= w(1)T,...,w(n)TT | {z } =:stackw(i)n i=1 ∈Rdn.(37) As a psd matrix, L(G)possesses an EVD L(G)= n X i=1 λiu(i)u(i)T,(38) with orthonormal eigenvectors u (1),..., u (n) and corresponding list of eigenvalues 0 = λ1L(G)≤λ2L(G)≤. . . ≤λnL(G).(39) We just write λi instead of λi L (G) if the Laplacian matrix L (G) is clear from context. The eigenvalue λi L (G) corresponds to the eigenvector u (i) , i.e., L(G)u(i)=λiL(G)u(i)for i= 1, . . . , n. It is important to note that the ordered list of eigenvalues (39) is uniquely 38
The identity (37) allows to rewrite (51) using the Laplacian matrix L(G)as b w(i)∈argmin w=stackw(i)X i∈V (1/mi) y(i)−X(i)w(i) 2 2+αwTL(G)⊗Idw.(52) Let us rewrite the objective function in (52) as wT Q(1) ··· 0 . . ..... . . 0··· Q(n) +αL(G)⊗I w+q(1)T,...,q(n)Tw(53) with Q(i)=(1/mi)X(i)TX(i)and q(i):= (−2/mi)X(i)Ty(i). Thus, like linear regression (6) and ridge regression (24) , GTVMin (52) (for local linear models H(i)) minimizes a convex quadratic function, b w(i)n i=1 ∈argmin w=stackw(i)n i=1 wTQw +qTw.(54) Here, we used the psd matrix Q:= Q(1) ··· 0 . . ..... . . 0··· Q(n) +αL(G)⊗Iwith Q(i):=(1/mi)X(i)TX(i)(55) and the vector q:= q(1)T,...,q(n)TT, with q(i):= (−2/mi)X(i)Ty(i).(56) 3.3.1 Computational Aspects of GTVMin Chapter 5 will apply optimization methods to solve GTVMin (48) , resulting in practical FL algorithms. Different instances of GTVMin favour different 45
classes of optimization methods. For example, using a differentiable loss function Li(·) and penalty function ϕ ( · )allows to apply gradient-based methods (see Chapter 4) to solve GTVMin. Another important class of loss functions are those for which we can efficiently compute the proximal operator [38,39] proxLi(·),ρ(w) := argmin w′∈Rd Li(w′)+(ρ/2) ∥w−w′∥2 2for some ρ > 0.(57) We refer to functions Li(·) for which (57) can be computed easily as simple or proximable [40]. GTVMin (49) with proximable loss functions can be solved via proximal algorithms [39]. Besides influencing the choice of optimization method, the design choices underlying GTVMin also determine the amount of computation that is required by a given optimization method. Chapter 5 discusses FL algorithms that are obtained by applying fixedpoint iterations to solve GTVMin. These fixed-point iterations repeatedly apply a fixed-point operator which is determined by the FL network (including the choice for the local loss functions, local models and edges in the FL network). The computational complexity of the resulting iterative method has two factors: (i) the amount of computation required by a single iteration (i.e., the per-iteration complexity) and (ii) the number iterations required by the method to achieve a sufficiently accurate approximate solution of GTVMin. The fixed-point iterations used in Chapter 5 to design FL algorithms can be implemented as message passing over the FL network. These algorithms require an amount of computation that is proportional to the number of edges of the FL network. Clearly, using an FL network with few edges (i.e., using a sparse graph) results in a smaller per-iteration complexity. 46
The number of iterations required by an FL algorithm employing a fixedpoint operator F depends on the contraction properties of F . These contraction properties can be influenced through design choices for the FL network, such as selecting local loss functions that are strongly convex. In addition to affecting the iteration count, the contraction properties of F also play a crucial role in determining whether the FL algorithm can tolerate asynchronous execution. It is instructive to study the computational aspects of the special case of GTVMin (51) for local linear models. As discussed above, this instance is equivalent to solving (54) . Any solution b w of (54) (and, in turn, (51) ) is characterized by the zero-gradient condition Qb w=−(1/2)q,(58) with Q , qas defined in (55) and (56) . If the matrix Qin (58) is invertible, the solution to (58) and, in turn, to the GTVMin instance (51) is unique and given by b w= (−1/2)Q−1q. The size of the matrix Q(see (55) ) is proportional to the number of nodes in the FL network G which might be in the order of millions (or even billions) for internet-scale applications. For such large systems, we typically cannot use direct matrix inversion methods (such as Gaussian elimination) to compute Q−1.10 Instead, we typically need to resort to iterative methods [41,42]. One important family of such iterative methods are the gradient-based methods which we will discuss in Chapter 4. Starting from an initial choice of the local model parameters b w0 = b w(1) 0,...,b w(n) 0 , these methods repeat 10 How many arithmetic operations (addition, multiplication) do you think are required to invert an arbitrary matrix Q∈Rd×d? 47
variants of a gradient step, b wk+1 := b wk−η2Qb wk+qfor k= 0,1,.... The gradient step results in the updated local model parameters b w(i) which we stacked into b wk+1 := b w(1)T,...,b w(n)TT . We repeat the gradient step for a sufficient number of times, according to some stopping criterion (see Chapter 4). 3.3.2 Statistical Aspects of GTVMin How useful are the solutions of GTVMin (49) as a choice for the local model parameters? To answer this question, we use - as for the statistical analysis of ERM in Chapter 2 - a probabilistic model for the local datasets. In particular, we use a variant of an i.i.d. assumption: Each local dataset D(i) consists of data points whose features and labels are realizations of i.i.d. RVs y(i)=x(i,1),...,x(i,mi)T | {z } local feature matrix X(i) w(i)+ε(i)(59) with x(i,r)i.i.d. ∼ N(0,I), for r= 1, . . . , mi, i = 1, . . . , n, and ε(i)∼N(0, σ2I), for i= 1, . . . , n. In contrast to the probabilistic model (11) (which we used for the analysis of ERM), the probabilistic model (59) allows for different node-specific parameters w(i) , for i∈ V . In particular, the entire dataset obtained from pooling all local datasets does not conform to an i.i.d. assumption. In what follows, we focus on the GTVMin instance (51) to learn the parameters w (i) of a local linear model for each node i∈ V . For a reasonable 48
choice of FL network, the parameters w(i),w(i′) at connected nodes {i, i′}∈E should be similar. We cannot choose the edge weights based on parameters w(i) as they are unknown. However, we can still use estimates of w(i) that are computed from the available local datasets (see Chapter 7). Consider an FL network with nodes carrying local datasets generated from the probabilistic model (59) with true model parameters w(i) . For ease of exposition, we assume that w(i)=c, for some c∈Rdand all i∈ V.(60) To study the deviation between the solutions b w(i) of (51) and the true underlying parameters w(i), we decompose it as b w(i)=e w(i)+b c, with b c:= (1/n) n X i′=1 b w(i′).(61) The component b c is identical at all nodes i∈ V and obtained as the orthogonal projection of b w = stackb w(i)}n i=1 on the subspace (45) . The component e w(i) := b w(i)− (1 /n ) Pn i′=1 b w(i′) consists of the deviations, for each node i , between the GTVMin solution b w(i) and their average over all nodes. Trivially, the average of the deviations e w(i) across all nodes is the zero vector, (1/n)Pn i=1 e w(i)=0. The decomposition (61) entails an analogous (orthogonal) decomposition of the error b w(i)−w(i) . Indeed, for identical true underlying model parameters (60) (which makes wan element of the subspace (45)), we have n X i=1 b w(i)−w(i) 2 2 (60),(61) = n X i=1 ∥c−b c∥2 2 | {z } n∥c−b c∥2 2 + n X i=1 e w(i) 2 2.(62) 49
The following proposition provides an upper bound on the second error component in (62). Proposition 3.1. Consider a connected FL network, i.e., λ2> 0(see (39) ), and the solution (61) to GTVMin (51) for the local datasets (59) . If the true local model parameters in (59) are identical (see (60) ), we can upper bound the deviation e w(i) := b w(i)− (1 /n ) Pn i=1 b w(i) of learned model parameters b w(i) from their average, as n X i=1 e w(i) 2 2≤1 λ2α n X i=1 (1/mi) ε(i) 2 2.(63) Proof. See Section 3.7.1. Note that Proposition 3.1 only applies to GTVMin over a FL network with a connected graph G . A necessary and sufficient condition for G to be connected is that the second smallest eigenvalue is positive, λ2> 0. However, for an FL network with a graph G that is not connected, we can still apply Proposition 3.1 separately to each connected component of G. The upper bound (63) involves three components: •the properties of local datasets, via the noise terms ε(i)in (59), •the FL network via the eigenvalue λ2L(G)(see (39)), •the GTVMin parameter α. According to (63) , we can ensure a small error component e w(i) of the GTVMin solution by choosing a large value α . Thus, by (62) , for sufficiently large α , the local model parameters b w(i) delivered by GTVMin are approximately identical for all nodes i∈ V of a connected FL network (where λ2 L (G)> 0). 50
Enforcing identical local model parameters at all nodes of a FL network is desirable for FL applications that require to learn a common (global) model parameters for all nodes [12]. However, some FL applications involve heterogeneous devices that generate local datasets with significantly different statistics [34]. For such applications it is detrimental to enforce common model parameters at all nodes (see Chapter 6). Instead, we should enforce common model parameters only for nodes with local datasets having similar statistical properties. This is exactly the objective of clustered FL which we discuss in Section 6.2. 3.4 Non-Parametric Models in FL Networks In its basic form (49) , GTVMin can only be applied to parametric local models with model parameters belonging to the same Euclidean space Rd . Some FL applications involve non-parametric local models (such as decision trees) or parametric local models with varying parametrizations (e.g., nodes use different deep net architectures). Here, we cannot use the difference between model parameters as a measure for the discrepancy between h(i) and h(i′)across an edge {i, i′}∈E. One way to measure the discrepancy between two hypothesis maps h(i), h(i′) is to compare their predictions on a dataset D{i,i′}=nx(1),...,x(m′)o. For each edge {i, i′} , the connected nodes need to agree on dataset D{i,i′} . Note that the dataset D{i,i′} can be different for different edges. Examples for constructions of D{i,i′} include i.i.d. realizations of some probability 51
distribution or by using subsets of D(i)and D(i′)(see Exercise 3.8). We compare the predictions delivered by h(i) and h(i′) on D{i,i′} using some loss function L. In particular, we define the discrepancy measure d(i,i′):= (1/m′)X x∈D{i,i′} (1/2)Lx, h(i)x, h(i′) +Lx, h(i′)x, h(i).(64) Different choices for the loss function in (64) result in different computational and statistical properties of the resulting FL algorithms. For real-valued predictions we can use the squared error loss in (64), yielding d(i,i′):= (1/m′)X x∈D{i,i′}h(i)x−h(i′)x2.(65) We can generalize GTVMin by replacing w(i)−w(i′) 2 2 in (49) with the discrepancy d(h(i),h(i′))(64) (or the special case (65)). This results in b h(i)n i=1 ∈argmin h(i)∈H(i) i∈V X i∈V Lih(i)+αX {i,i′}∈E Ai,i′d(h(i),h(i′)).(66) 3.5 Interpretations We next discuss some interpretations of GTVMin (48). Empirical Risk Minimization. GTVMin (49) is obtained as a special case of ERM (1) for specific choices for the model H and loss function L . The model (or hypothesis space) used by GTVMin is a product space generated by the local models at the nodes of an FL network. The loss function of GTVMin consists of two parts: the sum of loss functions at each node and a penalty term that measures the variation of local models across the edges of the FL network. 52
Generalized Convex Clustering. One important special case of GTVMin (48) is convex clustering [43, 44]. Indeed, convex clustering is obtained from (48) using the local loss function Liw(i)=∥w(i)−a(i)∥2,for all nodes i∈ V (67) and the GTV penalty function ϕ (u) = ∥u∥p with some p≥ 1. 11 The vectors a (i) , for i = 1 , . . . , n , are the features of data points that we wish to cluster in (67) . Thus, we can interpret GTVMin as a generalization of convex clustering: we replace the terms ∥w(i)−a(i)∥2with a more general local loss function. Dual of Minimum-Cost Flow Problem. The optimization variables of GTVMin (48) are the local model parameters w (i) , for each node i∈ V in an FL network G . The optimization of node-wise variables w (i) , for i = 1 , . . . , n , is naturally associated with a dual problem [45]. This dual problem optimizes edge-wise variables u({i,i′}), one for each edge {i, i′}∈Eof G, max u(e),e∈E w(i),i∈V −X i∈V L∗ iw(i)−αX e∈E Aeϕ∗u(e)/(αAe)(68) subject to −w(i)=X e∈E e+=i u(e)−X e∈E e−=i u(e)for each i∈ V.(69) Here, we have introduced an orientation for each edge e := {i, i′} , by defining the head e− := min{i, i′} and the tail e+ := max{i, i′} . 12 Moreover, we used 11Here, we used the p-norm ∥u∥p:= Pd j=1 |uj|p1/p of a vector u∈Rd. 12 We use this orientation only for notational convenience to formulate the dual of GTVMin. The orientation of an edge (by choosing a head and tail) has no practical meaning in terms of GTVMin-based FL algorithms. After all, GTVMin (48) and its dual (68) are defined for an FL network with undirected edges E. 53
i w(i) i′ w(i′) u(e) e={i, i′} Fig. 3.5. Two nodes of an FL network that are connected by an edge e = {i, i′} . GTVMin (48) optimizes local model parameters w (i) for each node i∈ V in the FL network. The dual (68) of GTVMin optimizes local model parameter u(e)for each edge e∈ E in the FL network. the convex conjugates L∗ i(·), ϕ∗ of the local loss function Li(·) and GTV penalty function ϕ.13 The dual optimization problem (68) generalizes the optimal flow problem [45, Sec. 1J] to vector-valued flows. The special case of (68) , obtained when the GTV penalty function ϕ is a norm, is equivalent to a generalized minimumcost flow problem [47, Sec. 1.2.1]. Indeed, the maximization problem (68) is equivalent to the minimization min u(e),e∈E w(i),i∈V X i∈V L∗ iw(i) subject to −w(i)=X e∈E e+=i u(e)−X e∈E e−=i u(e)for each node i∈ V ∥u(e)∥∗≤αAefor each edge e∈ E.(71) The optimization problem (71) reduces to the minimum-cost flow problem [47, 13The convex conjugate of a function f:Rd→Ris defined as [46] f∗(x) := sup z∈Rd xTz−f(z).(70) 54
i Fig. 3.9. An FL network containing a node i with node degree d(i) = 3, like all its neighbors i′∈ N(i) . We use an FL algorithm to learn local model parameters w(i) . If the algorithm employs message passing, the first iteration provides access only to the local datasets of the neighbors in N(i) (located along the inner dashed circle). In the second iteration, the algorithm gains access to the local datasets of the neighbors N(i′) of each i′∈ N(i) . These second-hop neighbors are located along the outer dashed circle. 61
3.15. Proximal operator of a quadratic function. Study the proximal operator (57) for a quadratic function, Liw(i)=w(i)TQw(i)+qTw(i)+q, with some matrix Q∈Rd×d, vector q∈Rdand number q∈R. 62
3.7 Proofs 3.7.1 Proof of Proposition 3.1 Let us introduce the shorthand f w (i) for the objective function of the GTVMin instance (51) . We verify the bound (63) by showing that if it does not hold, the choice of the local model parameters w (i) := w(i) (see (59) ) results in a smaller objective function value, fw(i)< fb w(i) . This would contradict the fact that b w(i)is a solution to (51). First, note that fw(i)=X i∈V (1/mi) y(i)−X(i)w(i) 2 2+αX {i,i′}∈E Ai,i′ w(i)−w(i′) 2 2 (60) =X i∈V (1/mi) y(i)−X(i)w(i) 2 2 (59) =X i∈V (1/mi) X(i)w(i)+ε(i)−X(i)w(i) 2 2 =X i∈V (1/mi) ε(i) 2 2.(74) Inserting (61) into (51), fb w(i)=X i∈V (1/mi) y(i)−X(i)b w(i) 2 2 | {z } ≥0 +αX {i,i′}∈E Ai,i′ b w(i)−b w(i′) 2 2 | {z } (61) =∥e w(i) −e w(i′)∥2 2 ≥αX {i,i′}∈E Ai,i′ e w(i)−e w(i′) 2 2 (44) ≥αλ2 n X i=1 e w(i) 2 2.(75) If the bound (63) would not hold, then by (75) and (74) we would obtain fb w(i)> fw(i). This is a contradiction to the fact that b w(i)solves (51). 63
. 4 Gradient Methods for Federated Optimization Chapter 3 introduced GTVMin as a central design principle for FL algorithms. Many important instances of GTVMin require the minimization of a smooth objective function f (w)over a continuous parameter space. This chapter investigates how gradient-based methods –a broadly used family of iterative optimization methods – can be employed to solve such problems. These methods rely on local approximations of f(w)using its gradient. Section 4.1 introduces the basic gradient step and explains how it updates model parameters in the direction of steepest descent. Key considerations such as the choice of the learning rate are discussed in Section 4.2, along with stopping criteria in Section 4.3 that help determine when to terminate the optimization process. Section 4.4 studies how perturbations affect the convergence of gradient steps, which is particularly relevant in FL applications that involve unreliable communication or partial data access. When optimization problems include explicit constraints on the model parameters, projected gradient descent (projected GD) presented in Section 4.5 provides a principled solution. Section 4.6 then extends gradient-based methods to non-parametric models, using proximal operators and test datasets to generalize the notion of a gradient step. Finally, Section 4.7 interprets gradient-based methods as a special case of fixed-point iterations. This perspective allows for a unified understanding of FL algorithms as convergent 64
processes driven by contraction operators. 4.1 Gradient Descent Gradient-based methods are iterative algorithms for finding the minimum of a differentiable objective function f (w)of a vector-valued argument w. One example of such an optimization problem is the ERM instance (2) . Unless stated otherwise, we consider an objective function of the form: f(w) := wTQw +qTw.(76) Although restricting our discussion to objective functions of the form (76) may seem limiting, this formulation allows for a straightforward analysis and generalization to larger classes of differentiable functions. Moreover, we can use (76) also as an approximation for broader families of objective functions. Note that (76) defines an entire family of convex quadratic functions f (w). Each member of this family is specified by a psd matrix Q ∈Rd×d and a vector q ∈Rd . We have already encountered some ML and FL methods that minimize an objective function of the form (76) : Linear regression (2) and ridge regression (24) in Chapter 2 as well as GTVMin (51) for local linear models in Chapter 3. Moreover, (76) is a useful approximation for the objective functions arising in other ML methods [49–51]. Given a current choice of model parameters w (k) , we want to update them towards a minimum of (76) . To this end, we use the gradient ∇f w (k) to locally approximate f (w)(see Figure 4.1). The gradient ∇f w (k) indicates the direction in which the function f (w)maximally increases. Therefore, it 65
seems reasonable to update w(k)in the opposite direction of ∇fw(k), w(k+1) := w(k)−η∇fw(k) (76) =w(k)−η2Qw(k)+q.(77) The gradient step (77) involves the positive factor η > 0which we refer to as step size or learning rate. Algorithm 2 summarizes the most basic variant of gradient-based methods, which simply iterates (77) until a predefined stopping criterion is met. f(w) fw(k)+w−w(k)T∇fw(k) fw(k)n Fig. 4.1. We can approximate a differentiable function f (w)locally around a point w (k)∈Rd using the linear function f w (k) + w − w (k)T∇f w (k) . Geometrically, we approximate the graph of f (w)by a hyperplane with normal vector n= ( ∇f w (k),− 1) T∈Rd+1 of this approximating hyperplane is determined by the gradient ∇fw(k)[2]. The usefulness of gradient-based methods crucially depends on the computational complexity of evaluating the gradient ∇f (w). Modern software libraries for automatic differentiation enable the efficient evaluation of the gradients arising in widely-used ERM-based methods [52]. Besides the actual computation of the gradient, it might already be challenging to gather the required data points which define the objective 66
function f (w)(e.g., being the average loss over a large training set). Indeed, the matrix Qand vector qin (76) are constructed from the features and labels of data points in the training set. For example, the gradient of the objective function in ridge regression (24) is ∇f(w) = −(2/m) m X r=1 x(r)y(r)−wTx(r)+ 2αw. Evaluating this gradient requires roughly d×m arithmetic operations such as adding and multiplying numbers. Algorithm 2 A blueprint for gradient-based methods Input: some objective function f (w)(e.g., the average loss of a hypothesis h(w)on a training set); learning rate η > 0; some stopping criterion. Initialize: set w(0) :=0; set iteration counter k:=0 1: repeat 2: k:= k+1 (increase iteration counter) 3: w(k):= w(k−1) −η∇fw(k−1)(do a gradient step (77)) 4: until stopping criterion is met Output: learned model parameters b w := w (k) (hopefully fb w≈ minwf(w)) Like most other gradient-based methods, Algorithm 2, involves two hyperparameters: (i) the learning rate η used for the gradient step and (ii) a stopping criterion to decide when to stop repeating the gradient step. We next discuss how to choose these hyper-parameters. Note that we can apply Algorithm 2 to find the minimum of any differentiable objective function f (w). Indeed, Algorithm 2 only needs to be able 67
to access the gradient ∇f w (k−1) . In particular, we an apply Algorithm 2 to objective functions that do not belong to the family of convex quadratic functions (76). 4.2 How to Choose the Learning Rate The learning rate must be chosen carefully: if it is too large, the gradient step may overshoot and diverge from the solution of (76) ; if it is too small, each step makes only negligible progress. Note that practical FL systems can only afford to compute a finite number gradient steps. Therefore, we must ensure that each gradient step makes a sufficiently large progress towards the optimum of the objective function. Figure 4.2 illustrates both extremes. f(w(k)) f(w(k+1)) f(w(k+2)) (77) (77) (a) f(w(k)) f(w(k+1))f(w(k+2)) (b) Fig. 4.2. Effect of inadequate learning rates η in the gradient step (77) . (a) If η is too large, the gradient steps might “overshoot” such that the iterates w (k) might diverge from the optimum, i.e., f (w (k+1) ) > f (w (k) )! (b) If η is too small, the gradient steps make very little progress towards the optimum or even fail to reach the optimum at all. One approach to choosing the learning rate is to start with some initial value (first guess) and monitor the decrease in the objective function. If 68
this decrease does not agree with the decrease predicted by the (local linear approximation using the) gradient, we decrease the learning rate by a constant factor. After we decrease the learning rate, we re-consider the decrease in the objective function. We repeat this procedure until a sufficient decrease in the objective function is achieved [53, Sec 6.1]. Alternatively, we can use a prescribed sequence (schedule) ηk , for k = 1 , 2 ,..., of learning rates that vary across successive gradient steps [54]. For example, we could require the learning rate ηk to satisfy the following conditions [53, Sec. 6.1], [55] lim k→∞ηk= 0,∞ X k=1 ηk=∞, and ∞ X k=1 η2 k<∞.(78) Running the gradient step (77) with a learning rate schedule ηk that satisfies (78) ensures convergence to a minimum of f(w)if •the iterates w(k) 2are bounded, i.e., supk=1,... w(k) 2is finite, and •the gradients ∇fw(k) 2, for k= 1,2, . . ., are also bounded. A detailed convergence proof can be found in [53, Sec. 3]. It is instructive to discuss the meanings of the individual conditions in (78) . The first condition (78) requires that the learning rate eventually become sufficiently small to avoid overshooting. The third condition (78) ensures that this required decay of the learning rate does not take “forever”. Note that the first and third condition in (78) could be satisfied by the trivial learning rate schedule ηk = 0 which is clearly not useful as the gradient step has no effect. The trivial schedule ηk = 0 is ruled out by the middle condition of (78) . This middle condition ensures that the learning rate ηk is large enough such 69
that the gradient steps make sufficient progress towards a minimizer of the objective function. We emphasize that the conditions in (78) are independent of any properties of the matrix Qin (76) . The matrix Qis determined by data points (see, e.g., (2) ), whose statistical properties can typically be controlled only to a limited extent, such as through data normalization. 4.3 When to Stop? For the stopping criterion, we may use a fixed number of iterations, kmax . This hyper-parameter can be determined by constraints on computational resources. We can optimize the number of iterations also via meta-learning, i.e., trying to predict the optimal kmax based on key characteristics (or features) of the objective function [56]. Another stopping criterion can be obtained by monitoring the decrease in the objective function f w (k) . Specifically, we stop repeating the gradient step (77) when f w (k)−f w (k+1)≤ε(tol) for a given tolerance ε(tol) . As before, we can optimize the tolerance level ε(tol) via meta-learning techniques [56]. For an objective function of the form (76) , we can use information about the psd matrix Qto construct a stopping criterion. 14 Indeed, the choice of the 14 For linear regression (6) , the matrix Qis determined by the features of the data points in the training set. We can influence the properties of Qto some extent by feature transformation methods. One important example of such a transformation is the normalization of features. 70
f(w) w(k) (77) w(k)−η∇fw(k)PS·w(k+1) S Fig. 4.4. Projected GD augments a basic gradient step with a projection back onto the constraint set S. The approaches for choosing the learning rate η and stopping criterion for basic gradient step (77) explained in Sections 4.2 and 4.3 work also for the projected gradient step (91) . In particular, the convergence speed of the projected gradient step is also characterized by (80) [53, Ch. 6]. This follows from the fact that the concatenation of a contraction (such as the gradient step (77) for sufficiently small η ) and a projection (such as PS· ) results again in a contraction with the same contraction factor. Thus, the convergence speed of projected GD, in terms of number of iterations required to ensure a given level of optimization error, is essentially the same as that of basic GD. However, the bound (80) is only telling about the number of projected gradient steps (91) required to achieve a guaranteed level of sub-optimality f w (k)−f∗ . The iteration (91) of projected GD might require significantly more computation than the basic gradient step, as it requires to compute the projection (90). 77
4.6 Extended Gradient Methods for Federated Optimization The gradient-based methods discussed so far can be used to learn a hypothesis from a parametric model. Let us now sketch one possible generalization of the gradient step (77) for a model Hwithout a parametrization. We start with rewriting the gradient step (77) as the optimization w(k+1) =argmin w∈Rd (1/(2η)) w−w(k) 2 2+fw(k)+w−w(k)T∇fw(k) | {z } ≈f(w) . (92) The objective function in (92) includes the first-order approximation f(w)≈fw(k)+w−w(k)T∇fw(k) of the function f(w)around the location w=w(k)(see Figure 4.1). Let us modify (92) by using f(w)itself (instead of an approximation), w(k+1) = argmin w∈Rdf(w)+(1/(2η)) w−w(k) 2 2.(93) Like the gradient step, also (93) maps a given vector w (k) to an updated vector w (k+1) . Note that (93) is nothing but the proximal operator of the function f (w)[39]. Similar to the role of the gradient step as the main building block of gradient-based methods, the proximal operator (93) is the main building block of proximal algorithms [39]. To obtain a version of (93) for a non-parametric model, we need to be able to evaluate its objective function directly in terms of a hypothesis h instead of its parameters w. The objective function (93) consists of two components. 78
The first component f ( · ), which is the function we want to minimize, is obtained from a training error incurred by a hypothesis, which might be parametric h(w) . Thus, we can evaluate the function f ( h )by computing the training error for a given hypothesis. The second component of the objective function in (93) uses w−w(k) 2 2 to measure the difference between the hypothesis maps h(w) and h(w(k)) . Another measure for the difference between two hypothesis maps can be obtained by using some test dataset D′ = x (1),..., x (m′) : The average squared difference between their predictions, (1/m′) m′ X r=1 hx(r)−h(k)x(r)2 ,(94) is a measure for the difference between h and h(k) . Note that (94) only requires the predictions delivered by the hypothesis maps h, h(k) on D′ - no other information is needed about these maps. It is interesting to note that (94) coincides with w−w(k) 2 2 for the linear model h(w) (x) := w T xand a specific construction of the dataset D′ . This construction uses the realizations x (1), x (2), . . . of i.i.d. RVs with a common 79
probability distribution x∼ N(0,I). Indeed, by the law of large numbers lim m′→∞(1/m′) m′ X r=1 h(w)x(r)−h(w(k))x(r)2 = lim m′→∞(1/m′) m′ X r=1 w−w(k)Tx(r)2 = lim m′→∞(1/m′) m′ X r=1 w−w(k)Tx(r)x(r)Tw−w(k) =w−w(k)Tlim m′→∞(1/m′) m′ X r=1 x(r)x(r)T | {z } =I w−w(k) = w−w(k) 2 2.(95) Finally, we arrive at a generalized gradient step for the training of a non-parametric model H by replacing w−w(k) 2 2 in (93) with (94) . In other words, h(k+1) = argmin h∈H (1/(2ηm′)) m′ X r=1 hx(r)−h(k)x(r)2 +f(h).(96) We can turn gradient-based methods for the training of parametric models into corresponding training methods for non-parametric models by replacing the gradient step with the update (96) . For example, we obtain Algorithm 3 from Algorithm 2 by modifying step 3 suitably. 80
Algorithm 3 A blueprint for generalized gradient-based methods Input: some objective function f : H → R (e.g., the average loss of a hypothesis h∈ H on a training set); learning rate η > 0; some stopping criterion; test dataset D′={x(1),...,x(m′)} Initialize: set h(0) :=0; set iteration counter k:=0 1: repeat 2: k:=k+1 (increase iteration counter) 3: do a generalized gradient step (96), h(k)=argmin h∈H (1/(2ηm′)) m′ X r=1 hx(r)−h(k−1)x(r)2 +f(h) 4: until stopping criterion is met Output: learned hypothesis b h:= h(k)(hopefully fb h≈minh∈H f(h)) 4.7 Gradient Methods as Fixed-Point Iterations The iterative optimization methods discussed in the previous sections are all special cases of a fixed-point iteration, w(k)=Fw(k−1),for k= 1,2,.... (97) Different optimization methods use different choices for the operator F whose fixed points are solutions of the underlying optimization problem. For example, the gradient step (77) is obtained from (97) with the operator F(GD) :w 7→ w −η∇f (w). For a differentiable and convex objective function f(w), every minimizer b wis a fixed point of F(GD). The fixed-point iteration (97) will be the core computational step of every FL algorithm discussed in Chapter 5. These algorithms use (97) with an 81
operator F determined by an instance of GTVMin. More precisely, any fixed point of Fmust be an GTVMin-solution b w∈Rdn, Fb w=b w.(98) Given an instance of GTVMin, there are many different operators F that satisfy (98) . We obtain different FL algorithms by using different choices for F in (97) . Clearly, we should use an operator F in (97) that reduces the distance to a solution, w(k+1) −b w 2 | {z } (97),(98) =∥Fw(k)−Fb w∥2 ≤ w(k)−b w 2. Thus, we require F to be at least non-expansive, i.e., the iteration (97) should not result in worse model parameters that have a larger distance to the GTVMin solution. Moreover, each iteration (97) should also make some progress, i.e., reduce the distance from a GTVMin solution. This requirement can be made precise using the notion of a contraction operator [58,59]. The operator Fis a contraction operator if, for some κ∈[0,1), ∥Fw−Fw′∥2≤κ∥w−w′∥2holds for any w,w′∈Rdn. For a contraction operator F , the fixed-point iteration (97) generates a sequence w (k) that converges to a GTVMin solution b w quite rapidly. In particular [2, Theorem 9.23], w(k)−b w 2≤κk w(0) −b w 2. Here, w(0) −b w 2 is the distance between the initialization w (0) and the solution b w. 82
A well-known example of a fixed-point iteration (97) using a contraction operator is GD (77) for a smooth and strongly convex objective function f (w). 16 In particular, (77) is obtained from (97) using F := G(η) with the “gradient step operator” G(η):w7→ w−η∇f(w).(99) Note that the operator (99) is parametrized by the learning rate η. It is instructive to study the operator G(η) for an objective function of the form (76). Here, G(η):w7→ w−η2Qw +q |{z } (76) =∇f(w) .(100) For η := 1 / (2 λmax (Q)), the operator G(η) is contractive with κ = 1 − λmin (Q) /λmax (Q). Note that κ < 1only when λmin (Q) > 0, i.e., only when the matrix Qin (76) is invertible. The gradient step operator (100) is not contractive for the objective function (76) with a singular matrix Q(for which λmin = 0). However, even then G(η) is still firmly non-expansive [22]. We refer to an operator F:Rdn →Rdn as firmly non-expansive if ∥Fw−Fw′∥2 2≤Fw−Fw′Tw−w′, for any w,w′∈Rdn. It turns out that a fixed-point iteration (97) with a firmly non-expansive operator F is guaranteed to converge to a fixed-point of F [58, Cor. 5.16]. Figure 4.5 depicts examples of a firmly non-expansive operator, a non-expansive 16 The objective function in (76) is convex and smooth for any choice of psd matrix Q and vector q. Moreover, it is strongly convex whenever Qis invertible. 83
w(k) w(k+1) F(3) F(1) F(2) 1 −1 Fig. 4.5. Example of a non-expansive operator F(1) , a firmly non-expansive operator F(2) and a contractive operator F(3). operator and a contraction operator. All these operators are defined on the one-dimensional space R . Another example of a firmly non-expansive operator is the proximal operator (93) of a convex function [39,58]. 84
4.8 Exercises 4.1. Learning Rate Schedule. Consider the gradient step method applied to a differentiable objective function f(w), w(k+1) =w(k)−ηk∇fw(k),for k= 1,2,.... where the learning rate schedule is defined as ηk:= 1 k. 1. Verify that this learning rate schedule satisfies the standard conditions in (78). 2. Construct a differentiable, convex function f (w)and an initialization w (0) such that the gradient step iteration fails to converge to a minimizer of f(w). 4.2. Learning Rate Schedule II. Consider the generic gradient step w(k+1) =w(k)−ηk∇fw(k),for k= 1,2,.... with a learning rate schedule of the form ηk := 1 kp with some p > 0. For which values of p > 0does this schedule satisfy the conditions in (78)? 4.3. Online Gradient Descent. Linear regression methods learn model parameters of a linear model with minimum risk Ey− w T x 2 where (x, y) is a RV. In practice, we do not observe the RV (x, y) itself but a (realization of a) sequence of i.i.d. samples x(t), y(t) , for t = 1 , 2 , . . . . Online GD is an online learning method that updates the current model parameters w (t) , after observing x(t), y(t), w(t+1) := w(t)+2ηtx(t)y−w(t)Tx(t)at time t= 1,2,.... 85
Starting with initialization w (1) := 0, we run online gradient descent (online GD) for M time steps, resulting in the learned model parameters w (M+1) . Develop upper bounds on the risk Ey− w (M)T x 2 for two choices for the learning rate schedule: ηt:= 1/(t+ 5) or ηt:= 1/√t+ 5. 4.4. Computing the Average - I. Consider an FL network with graph G and its Laplacian matrix L (G) . Each node carries a local dataset which consists of a single measurement y(i)∈R . To compute their average (1 /n ) Pn i=1 y(i) we try an iterative method that, starting from the initialization u (0) := y(1), . . . , y(n)T∈Rn, repeats the update u(k+1) =u(k)−ηL(G)u(k)for k= 1,2,.... (101) Can you find a choice for η such that (101) becomes a fixed-point iteration (97) with a contractive operator F . Given such a choice of η , how is the limit limk→∞ u(k+1) related to the average (1/n)Pn i=1 y(i)? 4.5. Computing the Average - II. Consider the FL network from Problem 4.4. Try to construct an instance of GTVMin for learning scalar local model parameters w(i) which coincide, for each node i = 1 , . . . , n with the average (1 /n ) Pn i′=1 y(i′) . If you find such an instance of GTVMin, solve it using GD. 4.6. How to Quantize the Gradients? Any ML and FL application that uses a digital computer to implement a gradient step (77) must quantize the gradient ∇f (w)of the objective function f (w). The quantization process introduces perturbations to the gradient step. Given a fixed total budget of bits available for quantization, a key question arises: Should we allocate more bits (reducing quantization noise) during the initial gradient steps or during the final gradient steps in gradient-based methods? Hint: See Section 4.4. 86
The iterate w(k)contains local model parameters w(i,k), w(k)=: stackw(i,k)n i=1. Inserting (102) into (108), we obtain the gradient step w(i,k+1) :=w(i,k)−η(2/mi)X(i)TX(i)w(i,k)−y(i) | {z } (I) + 2αX i′∈N(i) Ai,i′w(i,k)−w(i′,k) | {z } (II) .(109) We slightly modify this gradient step by allowing for different learning rates ηk,i at different nodes iand iterations k, w(i,k+1) :=w(i,k)−ηk,i(2/mi)X(i)TX(i)w(i,k)−y(i) | {z } (I) + 2αX i′∈N(i) Ai,i′w(i,k)−w(i′,k) | {z } (II) .(110) The update (110) consists of two components, denoted (I) and (II). Component (I) reflects the local loss function at node i while component (II) couples node i with its neighbors i′∈ N(i) . In particular, component (I) is the gradient ∇Liw(i,k) of the local loss Liw(i) := (1 /mi ) y(i)−X(i)w(i) 2 2 . Component (I) drives the updated local model parameters w (i,k+1) towards the minimum of Li(·) , i.e., having a small deviation between labels y(i,r) and the predictions w (i,k+1)T x (i,r) . Note that we can rewrite the component (I) in (110), as (2/mi) mi X r=1 x(i,r)y(i,r)−x(i,r)Tw(i,k).(111) 93
The component (II) in (110) The purpose of component (II) in (110) is to force the local model parameters to be similar across an edge {i, i′} with large weight Ai,i′ . We control the relative importance of (II) and (I) using the GTVMin parameter α : Choosing a large value for α puts more emphasis on enforcing similar local model parameters across the edges. Using a smaller α puts more emphasis on learning local model parameters delivering accurate predictions (incurring a small loss) on the local dataset. w(1,k) w(2,k) w(3,k) A1,2 A1,3 Fig. 5.1. At the beginning of iteration k , node i = 1 collects the current local model parameters w (2,k) and w (3,k) from its neighbors. Then, it computes the gradient step (110) to obtain the new local model parameters w (1,k+1) . These updated parameters are then used in the next iteration for the local updates at the neighbors i= 2,3. The execution of the gradient step (110) requires only local information at node i . Indeed, the update (110) at node i depends only on its current model parameters w (i,k) , the local loss function Li(·) , the neighbors’ model parameters w (i′,k) , for i′∈ N(i) , and the corresponding edge weights Ai,i′ (see Figure 5.1). In particular, the update (110) does not depend on any properties kor edge weights) of the FL network beyond the neighbors N(i). We obtain Algorithm 4 by repeating the gradient step (110) , simultaneously for each node i∈ V , until a stopping criterion is met. Algorithm 4 allows for 94
potentially different learning rates ηk,i at different nodes i and iterations k . It Algorithm 4 FedGD for Local Linear Models Input: FL network G; GTV parameter α; learning rate ηk,i; local dataset D(i) = x(i,1), y(i,1);. . . , x(i,mi), y(i,mi) for each i ; some stopping criterion. Output: linear model parameters b w(i)for each node i∈ V Initialize:k:=0;w(i,0) :=0 1: while stopping criterion is not satisfied do 2: for all nodes i∈ V (simultaneously) do 3: share local model parameters w(i,k)with neighbors i′∈N(i) 4: update local model parameters via (110) 5: end for 6: increment iteration counter: k:=k+1 7: end while 8: b w(i):= w(i,k)for all nodes i∈ V is important to note that Algorithm 4 requires a synchronous (simultaneous) execution of the updates (110) at all nodes i∈ V [17,18]. Loosely speaking, all nodes i rely on a single global clock that maintains the current iteration counter k[62]. At the beginning of iteration k , each node i∈ V sends its current model parameters w (i,k) to their neighbors i′∈N(i) . Then, each node i∈ V updates their model parameters according to (110) , resulting in the updated model parameters w (i,k+1) . As soon as these local updates are completed, the global clock increments the counter k7→ k + 1 and triggers the next iteration to be executed by all nodes. Figure 5.2 illustrates the alternating execution of 95
i i′ w(i,k) w(i′,k) i i′ compute w(i,k+1) compute w(i′,k+1) Ai,i′ i i′ w(i,k+1) w(i′,k+1) Fig. 5.2. Algorithm 4 alternates between message passing across the edges of the FL network (left and right) and updates of local model parameters (centre). message passing and local updates of Algorithm 4. The implementation of Algorithm 4 in real-world computational infrastructures might incur deviations from the exact synchronous execution of (110) [63, Sec. 10]. This deviation can be modelled as a perturbation of the gradient step (108) and therefore analyzed using the concepts of Section 4.4 on perturbed GD. Section 8.2 will also discuss the effect of imperfect computation in the context of key requirements for trustworthy FL. We close this section by generalizing Algorithm 4 which is limited to FL networks using local linear models. This generalization, summarized in Algorithm 5, can be used to train parametric local models H(i) with a differentiable loss function Liw(i), for i= 1, . . . , n. 96
Algorithm 5 FedGD for Parametric Local Models Input: FL network G; GTV parameter α; learning rate ηk,i local loss function Liw(i)for each i= 1, . . . , n; some stopping criterion. Output: linear model parameters b w(i)for each node i∈ V Initialize:k:=0;w(i,0) :=0 1: while stopping criterion is not satisfied do 2: for all nodes i∈ V (simultaneously) do 3: share local model parameters w(i,k)with neighbors i′∈N(i) 4: update local model parameters via w(i,k+1) :=w(i,k)−ηk,i∇Liw(i,k)+2αX i′∈N(i) Ai,i′w(i,k)−w(i′,k). 5: end for 6: increment iteration counter: k:=k+1 7: end while 8: b w(i):= w(i,k)for all nodes i∈ V 97
5.3 FedSGD Consider Algorithm 4 for training local linear models h(i) (x) = x T w (i) for each node i = 1 , . . . , n of an FL network. Note that step 4 of Algorithm 4 requires to compute the sum (111) . It might be infeasible to compute this sum exactly, e.g., when local datasets are generated by remote devices with limited connectivity. It is then useful to approximate the sum by (2/B)X r∈B x(i,r)y(i,r)−x(i,r)Tw(i,k) | {z } ≈(111) .(112) The approximation (112) uses a subset (so-called batch) B=x(r1), y(r1),...,x(rB), y(rB) of B randomly chosen data points from D(i) . While (111) requires summing over m data points, the approximation requires to sum over B (typically B≪m) data points. Inserting the approximation (112) into the gradient step (110) yields the approximate gradient step w(i,k+1) :=w(i,k)−ηk,i(2/B)X r∈B x(i,r)x(i,r)Tw(i,k)−y(i,r) | {z } ≈(111) + 2αX i′∈N(i) Ai,i′w(i,k)−w(i′,k).(113) We obtain Algorithm 6 from Algorithm 4 by replacing the gradient step (110) with the approximation (113). We close this section by generalizing Algorithm 6 which is limited FL networks using local linear models. This generalization, summarized in Algorithm 98
Algorithm 6 FedSGD for Local Linear Models Input: FL network G; GTV parameter α; learning rate ηk,i; local datasets D(i) = x(i,1), y(i,1),...,x(i,mi), y(i,mi) for each node i ; batch size B; some stopping criterion. Output: linear model parameters b w(i)at each node i∈ V Initialize:k:=0;w(i,0) :=0 1: while stopping criterion is not satisfied do 2: for all nodes i∈ V (simultaneously) do 3: share local model parameters w(i,k)with all neighbors i′∈ N(i) 4: draw fresh batch B(i):= {r1, . . . , rB} 5: update local model parameters via (113) 6: end for 7: increment iteration counter k:=k+1 8: end while 9: b w(i):= w(i,k)for all nodes i∈ V 99
7, can be used to train parametric local models H(i) with a differentiable loss function Liw(i), for i= 1, . . . , n. Algorithm 7 does not require these local loss function themselves, but only an oracle g (i) ( · )for each node i = 1 , . . . , n . For a given vector w (i) , the oracle at node i delivers an approximate gradient (or estimate) g (i) (w (i) ) ≈ ∇Liw(i) . The analysis of Algorithm 7 can be facilitated by a probabilistic model which interprets the oracle output g (i) (w (i) ) as the realization of a RV. Under such a probabilistic model, we refer to an oracle as unbiased if Eg(i)(w(i))=∇Liw(i). Algorithm 7 FedSGD for Parametric Local Models Input: FL network G; GTV parameter α; learning rate ηk,i gradient oracle g(i)·for each node i= 1, . . . , n; some stopping criterion. Output: linear model parameters b w(i)for each node i∈ V Initialize:k:=0;w(i,0) :=0 1: while stopping criterion is not satisfied do 2: for all nodes i∈ V (simultaneously) do 3: share local model parameters w(i,k)with neighbors i′∈N(i) 4: update local model parameters via w(i,k+1) :=w(i,k)−ηk,ig(i)w(i,k)+2αX i′∈N(i) Ai,i′w(i,k)−w(i′,k). 5: end for 6: increment iteration counter: k:=k+1 7: end while 8: b w(i):= w(i,k)for all nodes i∈ V 100
5.4 FedAvg Consider an FL method that learns model parameters b w∈Rd of a single (global) linear model from a de-centralized collection of local datasets D(i) , i = 1 , . . . , n . 18 How can we learn b w without exchanging local datasets, but instead only exchanging updates for the model parameters? One approach is to apply Algorithm 4 to GTVMin (102) with a sufficiently large α . According to our analysis in Chapter 3 (specifically Proposition 3.1), if α is sufficiently large, then the GTVMin solutions b w(i) are almost identical across all nodes i∈ V . We can interpret the local model parameters delivered by GTVMin as a local copy of the global model parameters. Note that the bound in Proposition 3.1 only applies if the FL network (used in GTVMin) is connected. One example of a connected FL network is the star as depicted in Figure 5.3. Here, we choose one node i = 1 as a centre node that is connected by an edge with weight A1,i to the remaining nodes i = 2 , . . . , n . The star graph uses the minimum number of edges required to connect all nnodes [64]. Instead of using GTVMin with a connected FL network and a large value of α, we can also enforce identical local copies b w(i)via a constraint: b w∈arg min w∈S X i∈V (1/mi) y(i)−X(i)w(i) 2 2 with S=w= stack{w(i)}n i=1 :w(i)=w(i′)for any i, i′∈ V.(114) Here, we use as constraint set the subspace S defined in (45) . The projection of a given collection of local model parameters w= stack{ w (i)} on S is given 18 This setting is a special case of horizontal federated learning (HFL) which we discuss in Section 6.3. 101
D(i) A1,i Fig. 5.3. Star-shaped graph G(star) with a centre node i = 1 representing a server that trains a (global) model which is shared with peripheral nodes. These peripheral nodes represent clients generating local datasets. The training process at the server is facilitated by receiving updates on the model parameters from the clients. by PSw=vT,...,vTTwith v:= (1/n)X i∈V w(i). We can solve (114) using projected GD from Chapter 4. The resulting projected gradient step for solving (114) is b w(i) k+1/2:=w(i,k)−ηi,k(2/mi)X(i)TX(i)w(i,k)−y(i) | {z } (local gradient step) (115) w(i,k+1) := (1/n)X i′∈V b w(i′) k+1/2(projection) .(116) We can implement (116) conveniently in a server-client system with each node ibeing a client: • First, each node computes the update (115) , i.e., a gradient step towards a minimum of the local loss Liw(i):= y(i)−X(i)w(i) 2 2. 102
Li(v), •using the regularizer Rv:= v−b w(global) 2 2,(121) •and the regularization parameter α:= 1/η. Note that Algorithms 10 and 9 provide only an abstract description of a practical FL system. The details of their actual implementation, such as the synchronization between the server and all clients (see steps 4 and 3 in Algorithm 10) is beyond the scope of this book. Instead, we refer the reader to relevant literature on the implementation of distributed computing systems [18,66]. 5.6 FedRelax We now apply a simple block-coordinate minimization method [17] to solve GTVMin (49). To this end, we rewrite (49) as b w∈arg min w∈Rdn X i∈V f(i)(w) | {z } =:f(GTV)(w) with f(i)(w) := Liw(i)+ (α/2) X i′∈N(i) Ai,i′ w(i)−w(i′) 2 2, and the stacked model parameters w=w(1),...,w(n)T.(122) According to (122) , the objective function of (49) decomposes into components f(i)(w) , one for each node V of the FL network. Moreover, the local model parameters w (i) influence the objective function only via the components 109
at the nodes i∪ N(i) . We exploit this structure of (122) to decouple the optimization of the local model parameters b w(i)i∈V as described next. Consider some local model parameters w (i,k) , for i = 1 , . . . , n , at time k . We then update (in parallel) each w (i,k) by minimizing f(GTV) ( · )along w (i) with the other local model parameters w (i′) := w (i′,k) held fixed for all i′ = i , w(i,k+1) ∈argmin w(i)∈Rd f(GTV)w(1,k),...,w(i−1,k),w(i),w(i+1,k), . . . (122) = argmin w(i)∈Rd f(i)w(1,k),...,w(i−1,k),w(i),w(i+1,k), . . . (122) = argmin w(i)∈Rd Liw(i)+αX i′∈N(i) Ai,i′ w(i)−w(i′,k) 2 2.(123) The update rule in (123) can be viewed as a non-linear Jacobi method applied to (122) [17, Sec. 3.2.4]. It also admits an interpretation as a form of blockcoordinate optimization [67]. By iterating this update sufficiently many times, we arrive at Algorithm 11. There is an interesting connection between the Algorithm 11 FedRelax for Parametric Models Input: FL network Gwith local loss functions Li(·), GTV parameter α Initialize:k:=0;w(i,0) :=0 1: while stopping criterion is not satisfied do 2: for all nodes i∈ V in parallel do 3: compute w(i,k+1) via (123) 4: share w(i,k+1) with neighbors N(i) 5: end for 6: k:=k+1 7: end while update (123) and the basic gradient steps used by FedGD and FedSGD (see 110
Algorithm 5 and 7). Indeed, we obtain step 4 in Algorithm 5 from (123) by replacing the loss function Liw(i)with the approximation Liw(i,k)+∇Liw(i,k)w(i)−w(i,k)+ (1/(2η)) w(i)−w(i,k) 2 2. A Model-Agnostic Method. The applicability of Algorithm 11 is limited to FL networks with parametric local models (such as linear regression or ANNs with a common structure). We can generalize Algorithm 11 to non-parametric local models by applying the non-linear Jacobi method to the GTVMin variant (66). This results in the update b h(i) k+1 ∈argmin h(i)∈H(i) Lih(i)+αX i′∈N(i) Ai,i′d(h(i), b h(i′) k) | {z } see (64) .(124) We obtain Algorithm 12 as a model-agnostic variant of Algorithm 11 by replacing the update (123) in its step 3 with the update (124). Algorithm 12 is model-agnostic as it allows devices of an FL network to train different types of local models. The only restriction for the local models is that the update (124) can be computed efficiently. For some choices of local models and loss function, the update (124) can be implemented by basic data augmentation (see Exercise 5.3). 111
Algorithm 12 Model Agnostic FedRelax Input: FL network with G , local models H(i) , loss functions Li(·) , GTV parameter α, loss L(·,·)used in (64). Initialize:k:=0;b h(i) 0:=0 1: while stopping criterion is not satisfied do 2: for all nodes i∈ V in parallel do 3: compute b h(i) k+1 via (124) 4: end for 5: k:=k+1 6: end while 112
5.7 A Unified Formulation The previous sections have presented some widely-used FL algorithms. These algorithms are obtained by applying distributed optimization methods to solve GTVMin. Despite their different formulations they share a common underlying structure. In particular, they can all be expressed as synchronous fixed-point iterations: b h(i) k+1 =F(i)b h(1) k,...,b h(n) k, for i= 1, . . . , n. (125) h(1), . . . , h(n) h(i) F(i)h(1), . . . , h(n) Fig. 5.4. A key computational step in many FL algorithms is the evaluation of an operator F(i)at each node i= 1, . . . , n of the FL network. Each operator F(i) : H(1) ×. . . ×H(n)→ H(i) represents a local update rule at the i = 1 , . . . , n (see Figure 5.4). Some algorithms use time-varying update rules, b h(i) k+1 =F(i)b h(1) k,...,b h(n) k.(126) 113
with operators F(i,k) that can vary across nodes i = 1 , . . . , n and time instants k = 1 , 2 , . . . . One example of (126) is used in Algorithm 5 for a time-varying learning rate. Clearly, any FL algorithm of the form 125 is fully specified by the operators F(1),...,F(n) . This - rather trivial - observation implies that we can study the behaviour of FL algorithms via analyzing the properties of the operators F(i) , for i = 1 , . . . , n . In particular, the robustness of FL algorithms crucially depends on the shape of F(i). For parametric local models, we can re-formulate the fixed-point iteration (125) directly in terms of the model parameters w(i,k+1) =F(i)w(1,k),...,w(n,k), for k= 0,1,..., (127) with operators F(i) : Rnd →Rd , for i = 1 , . . . , n . One example of (127) is the update 123 used by FedRelax (see Algorithm 11). 114
5.8 Asynchronous FL Algorithms The FL algorithms presented so far rely on synchronous coordination among devices i = 1 , . . . , n within an FL network [18, Ch. 6]. A new iteration is only initiated once all devices have completed their local updates (125) and communicated them to their neighbors [68, Sec. 10], [17, Sec. 1.4]. The implementation of synchronous FL algorithms can be difficult (or impossible) in practice. As highlighted in Chapter 8, trustworthy FL systems should tolerate unreliable or failing devices. Synchronous methods lack this robustness—any device failure or dropout can cause the entire algorithm execution to stall. Moreover, synchronous execution is inefficient in heterogeneous FL systems. Devices often vary in computational power or communication bandwidth, leading to the straggler problem: faster devices are forced to wait idly for slower ones [69,70]. Having devices to wait idly for slower devices results in a waste of their computational resources. To address the limitations of synchronous FL algorithms, we now show how to build asynchronous variants of the FL algorithms discussed in Section 5.7. We focus here on parametric local models, each represented by their own model parameters w (i) . The basic idea is to let each device i = 1 , . . . , n execute the update (127) independently, using potentially out-dated updates from its neighbors N(i). An asynchronous FL algorithm consists of a sequence of update events, which we index by k = 0 , 1 , 2 , . . . (see Figure 5.5). During each event k , a subset A(k)⊆ V of devices performs updates: w(i,k+1) =F(i)w(1,ki,1),...,w(n,ki,n).(128) 115
Here, ki,i′≤k is event index of the latest available model parameters of device i′at device i. i= 1 i= 2 k= 1 k= 2 k= 3 k= 4 (128) (128) (128) (128) (128) (128) (128) Fig. 5.5. The execution of an asynchronous FL algorithm consists of a sequence of update events, indexed by k = 0 , 1 , 2 , . . . . During each event k , the active nodes i∈ A(k)⊆ V of an FL network update their local model parameters w(i)by computing (128). Active nodes are depicted as filled circles. The set of nodes performing the update (128) during event k is denoted as the active set A(k)⊆ V . It is convenient to summarize the resulting asynchronous algorithm as w(i,k+1) = F(i)w(1,ki,1),...,w(n,ki,n)for k∈T(i) w(i,k)otherwise. (129) Here, we used the set T(i):= k∈ {0,1,...,}:i∈ A(k), which consists, for each i = 1 , . . . , n , of those clock ticks during which node i is active. Note that (129) reduces to the synchronous algorithm (127) for the extreme case when T(i)= 0,1,2,..., for all i= 1, . . . , n. Like the synchronous algorithm (127) , also the asynchronous variant 129 uses an iteration counter k . However, the practical meaning of k in the 116
asynchronous variant is fundamentally different: Instead of representing a global clock tick (or wall-clock time), the counter k in (129) indexes some update event during which at least one node is active and computes a local update. We denote the set of active nodes (or devices) during event k by A(k)⊆ V . The inactive nodes i /∈ A(k) leave their current model parameters unchanged, i.e., w(i,k+1) =w(i,k). For each active node i∈ A(k) , the local update (129) uses potentially outdated model parameters w (i′,ki,i′) from its neighbors i′∈ N(i) . Indeed, some of the neighbors might have not been in the active sets A(k−1),A(k−2), . . . of the most recent iterations. In this case, the update (129) does not have access to w (i′,k) . Instead, we can only use w (i′,ki,i′) that has been produced obtained during some previous iteration ki,i′< k. The update (128) involves an operator F(i) : Rdn →Rd that determines the resulting FL algorithm. We can interpret (128) as an asynchronous variant of the synchronous algorithm (127) obtained for the same F(i) . For example, an asynchronous variant of Algorithm 5 (with a fixed learning rate) can be obtained for the choice F(i)w(1),...,w(n)=w(i)−η∇Liw(i)+X i′∈N(i) 2Ai,i′w(i)−w(i′).(130) Note that the choice (130) involves the local loss functions and the weighted edges of an FL network. The update (128) , at an active node i∈ A(k) , involves potentially outdated local model parameters w (i′,ki,i′) , with ki,i′≤k , for i′ = 1 , . . . , n . The quantity ki,i′ represents the most recent update event during which node i′ has shared its updated local model parameters with node i . We can, in turn, 117
interpret the difference k−ki,i′ as a measure of the communication delay between node i′and node i. Depending on the extent of the delays k−ki,i′ in the update (128) , we distinguish between [17] • Totally asynchronous algorithms. These are algorithms of the form (129) with unbounded delays k−ki,i′ , i.e., they can can become arbitrarily large. Moreover, we require that no device stops updating, i.e., the set T(i)is infinite for each i= 1, . . . , n. • Partially asynchronous algorithms. These are algorithms of the form (129) with bounded delays k−ki,i′≤B , with some fixed (but possibly unknown) maximum delay B∈N . Moreover, each device updates at least once during B consecutive clock ticks, i.e., T(i)∩{t, t +1 , t + B− 1 } = ∅for each t= 1,2,..., and i= 1, . . . , n. For some choices of F(i) in (128) , a partially asynchronous algorithm can converge for any value of B . However, there also choices of F(i) , for which a partially asynchronous algorithm will only converge if B is sufficiently small [17, Ch. 7]. Convergence Guarantees. There is an elegant characterization of the convergence of totally and partially asynchronous FL algorithms of the form (129) . This characterization applies whenever the operators F(i) , for i= 1, . . . , n, in (129) form a pseudo-contraction [71] max i=1,...,n F(i)w(1),...,w(n)−F(i)b w(1),...,b w(n) ≤κ·max i=1,...,n w(i)−b w(i) , (131) with some contraction rate κ∈[0,1) and some fixed-point b w(1),...,b w(n). 118
5.10 Proofs 5.10.1 Proof of Proposition 5.1 The first inequality in (106) follows from well-known results on the eigenvalues of a sum of symmetric matrices (see, e.g., [3, Thm 8.1.5]). In particular, λmaxQ≤max max i=1,...,n λdQ(i) | {z } (105) =λmax , λmaxαL(G)⊗I.(135) The second inequality in (106) uses the following upper bound on the maximum eigenvalue λnL(G)of the Laplacian matrix: λnL(G)(a) = max v∈S(n−1) vTL(G)v (37) = max v∈S(n−1) X {i,i′}∈E Ai,i′vi−vi′2 (b) ≤max v∈S(n−1) X {i,i′}∈E 2Ai,i′v2 i+v2 i′ (c) = max v∈S(n−1) X i∈V 2v2 iX i′∈N(i) Ai,i′ (35) ≤max v∈S(n−1) X i∈V 2v2 id(G) max = 2d(G) max.(136) Here, step ( a )uses the CFW of eigenvalues [3, Thm. 8.1.2.] and step ( b ) uses the inequality ( u + v ) 2≤ 2( u2 + v2 )for any u, v ∈R . For step ( c )we use the identity Pi∈V Pi′∈N(i)f ( i, i′ ) = P{i,i′}f ( i, i′ ) + f ( i′, i ) (see Figure 5.7). The bound (136) is essentially tight.21 21Consider an FL network being a chain (or path). 125
0 1 2 3 A1,22w2 1+w2 2 A1,32w2 1+w2 3 Fig. 5.7. Illustration of step (c)in (136). 5.10.2 Proof of Proposition 5.2 Similar to the upper bound (136) we also start with the CFW for the eigenvalues of Qin (103). In particular, λ1= min ∥w∥2 2=1 wTQw.(137) We next analyze the right-hand side of (137) by partitioning the constraint set { w: ∥w∥2 2 = 1 } of (137) into two complementary regimes for the optimization variable w= stack{ w (i)} . To define these two regimes, we use the orthogonal decomposition w=PSw |{z} =:w +PS⊥w |{z} =: e w for subspace Sin (45).(138) Explicit expressions for the orthogonal components w , e w are given by (46) and (47). In particular, the component wsatisfies w=cT,...,cTTwith c:= avgw(i)n i=1. Note that ∥w∥2 2=∥w∥2 2+∥e w∥2 2.(139) 126
Regime I. This regime is obtained for ∥e w∥2≥ρ∥w∥2 . Since ∥w∥2 2 = 1, and due to (139), we have ∥e w∥2 2≥ρ2/(1 + ρ2).(140) This implies, in turn, via (44) that wTQw (103) ≥αwTL(G)⊗Iw (37),(44) ≥αλ2L(G)∥e w∥2 2 (140) ≥αλ2L(G)ρ2/(1 + ρ2).(141) Regime II. This regime is obtained for ∥e w∥2< ρ ∥w∥2 . Here we have ∥w∥2 2>(1/ρ2)1−∥w∥2 2and, in turn, n∥c∥2 2=∥w∥2 2>1/(1 + ρ2).(142) We next develop the right-hand side of (137) according to wTQw (103) ≥ n X i=1 w(i)TQ(i)w(i) (138) ≥ n X i=1 c+e w(i)TQ(i)c+e w(i) (142) ≥ ∥w∥2 2λ1(1/n) n X i=1 Q(i) | {z } ¯ λmin + n X i=1 2e w(i)TQ(i)c+e w(i)TQ(i)e w(i) | {z } ≥0 ≥ ∥w∥2 2¯ λmin + n X i=1 2e w(i)TQ(i)c.(143) To develop (143) further, we note that n X i=1 2e w(i)TQ(i)c (a) ≤2λmax ∥e w∥2∥w∥2 ∥e w∥2<ρ∥w∥2 ≤2λmaxρ∥w∥2 2.(144) 127
Here, step ( a )follows from max∥y∥2=1,∥x∥2=1 y T Qx = λmax . Inserting (144) into (143) for ρ=¯ λmin/(4λmax), wTQw ≥ ∥w∥2 2¯ λmin/2(142) ≥(1/(1 + ρ2))¯ λmin/2(145) For each wwith ∥w∥2 2= 1, either (141) or (145) must hold. 128
6 Key Variants of Federated Learning Chapter 3 discussed GTVMin as a main design principle for FL algorithms. GTVMin learns local model parameters that optimally balance the individual local loss with their variation across the edges of an FL network. Chapter 5 discussed how to obtain practical FL algorithms. These algorithms solve GTVMin using distributed optimization methods, such as those from Chapter 4. This chapter discusses important special cases (or “main flavors”) of GTVMin obtained for specific construction of local datasets, choices of local models, measures for their variation and the weighted edges of the FL network. We next briefly summarize the resulting main flavors of FL discussed in the following sections. Section 6.1 discusses single-model FL that learns model parameters of a single (global) model from local datasets. This single-model flavor can be obtained from GTVMin using a connected FL network with large edge weights or, equivalently, a sufficient large value for the GTVMin parameter. Section 6.2 discusses how CFL is obtained from GTVMin over FL networks with a cluster structure. CFL exploits the presence of clusters (subsets of local datasets) which can be approximated using an i.i.d. assumption. GTVMin captures these clusters if they are well-connected by many (large weight) edges of the FL network. Section 6.3 discusses horizontal federated learning (HFL) which is obtained from GTVMin over an FL network whose nodes carry different subsets of a single underlying global dataset. Loosely speaking, HFL involves local datasets characterized by the same set of features but obtained from different 129
data points from an underlying dataset. Section 6.4 discusses vertical federated learning (VFL), which arises from applying GTVMin to a FL network where each node holds data on the same individuals but with different sets of features. A representative example involves public institutions such as tax authorities, social insurance agencies, and healthcare providers. While these organizations each collect distinct types of information, they all refer to the same underlying population, e.g., individuals identified by a Finnish social security number. Section 6.5 shows how personalized FL can be obtained from GTVMin by using specific measures for the GTV of local model parameters. For example, using deep ANNs as local models, we might only use the model parameters corresponding to the first few input layers to define the GTV. 6.1 Single-Model FL Some FL use cases require to train a single (global) model H from a decentralized collection of local datasets D(i) , i = 1 , . . . , n [13,73]. In what follows we assume that the model H is parametrized by a vector w ∈Rd . Figure 6.1 depicts a server-client architecture for an iterative FL algorithm that generates a sequence of (global) model parameters w(k),k= 1, . . .. After computing the new model parameters w (k+1) , the server broadcasts it to the devices i = 1 , . . . , i and increments the clock k := k + 1. In the next iteration, each device i uses the current global model parameters w (k) to compute a local update w (i,k) based on its local dataset D(i) . The precise implementation of this local update step depends on the choice of the global model H (trained by the server). One example of such a local update has 130
been discussed in Chapter 5 (see (119)). server global model parameters w(k)at time k 1 D(1) 2 D(2) 3 compute w(3,k)based on w(k) and local dataset D(3) w(1,k) w(2,k) w(3,k) w(k) w(k) w(k) Fig. 6.1. Illustration of a server-based (centralized) FL system during iteration k . The server begins by broadcasting the current global model parameters w (k) to each device i∈ V . Each device i then computes an update w (i,k) based on its local dataset D(i) and the received model parameters w (k) . These local updates w (i,k) are sent back to the server, which aggregates them to obtain the updated global model parameters w(k+1). Chapter 5 already hinted at an alternative to the server-based system in Figure 6.1. Indeed, we might learn local model parameters w (i) for each client i using a distributed optimization of GTVMin. We can force the resulting model parameters w (i) to be (approximately) identical by using a connected FL network and a sufficiently large GTVMin parameter α. To minimize the computational complexity of the resulting single-model FL system, we prefer FL networks with a small number of edges such as the star graph in Figure 5.3 [64]. However, to increase the robustness against 131
node/link failures we should use an FL network with more edges. This redundancy helps to ensure that the FL network is connected even after removing some of its edges [74]. Much like the server-based system from Figure 6.1, GTVMin-based methods using a star graph offers a single point of failure which is the server in Figure 6.1 or the centre node in Figure 5.3. Chapter 8 will discuss the robustness of GTVMin-based FL systems in slightly more detail. 6.2 Clustered FL Single-model FL systems require the local datasets to be well approximated as i.i.d. realizations from a common underlying probability distribution. However, requiring homogeneous local datasets, generated from the same probability distribution, might be overly restrictive. Indeed, the local datasets might be heterogeneous and need to be modelled using different probability distribution [16,34]. CFL relaxes the requirement of a common probability distribution underlying all local datasets. Instead, we approximate subsets of local datasets as i.i.d. realizations from a common probability distribution. In other words, CFL assumes that local datasets form clusters. Each cluster C ⊆ V has a cluster-specific probability distribution p(C). The idea of CFL is to pool the local datasets D(i) in the same cluster C to obtain a training set to learn cluster-specific b w(C) . Each node i∈ C then uses these learned model parameters b w(C) . A main challenge in CFL is that the cluster assignments of the local datasets are unknown in general. To determine a cluster C , we can apply standard clustering techniques (such 132
as k -means or Gaussian mixture model (GMM)) to a vector representation of the local datasets [23, Ch. 5]. These vector representations can be constructed in various ways. One option is to use the model parameters b w of a parametric ML model trained on D(i) . Alternatively, we can represent each local dataset D(i)using the gradient of its local loss function Liw(i)(see Section 7.2). We can also implement CFL via GTVMin with a suitably chosen FL network. In particular, the FL network should contain many edges (with large weight) between nodes in the same cluster and few edges (with a small weight) between nodes in different clusters. To fix ideas, consider the FL network in Figure 6.2, which contains a cluster C={1,2,3}. Cw(1) w(2) w(3) w(4) w(5) ∂C Fig. 6.2. The solution of GTVMin (49) are local model parameters that are approximately identical for all nodes in a tight-knit cluster C. Chapter 3 discussed how the eigenvalues of the Laplacian matrix can be used to measure the connectivity of G . Similarly, we can measure the connectivity of a cluster C via the eigenvalue λ2 L (C) of the Laplacian matrix L(C)of the induced sub-graph G(C):22 The larger λ2 L (C) , the better the connectivity among the nodes in C . 22The graph G(C)consists of the nodes in Cand the edges {i, i′}∈Efor i, i′∈ C. 133
While λ2 L (C) describes the intrinsic connectivity of a cluster C , we also need to characterize its connectivity with the other nodes in the FL network. To this end, we use the cluster boundary |∂C| := X {i,i′}∈∂C Ai,i′with ∂C:= {i, i′} ∈ E :i∈ C, i′/∈ C. Note that for a single-node cluster C = {i} , the cluster boundary coincides with the node degree, |∂C| =d(i)(see (34)). Intuitively, GTVMin tends to deliver (approximately) identical model parameters w (i) for nodes i∈ C if λ2 L (C) is large and the cluster boundary |∂C| is small. The following result makes this intuition more precise for the special case of GTVMin (102) for local linear models. Proposition 6.1. Consider an FL network G which contains a cluster C of local datasets with labels y(i)and feature matrix X(i)related via y(i)=X(i)w(C)+ε(i),for all i∈ C.(146) We learn local model parameters b w(i) via solving GTVMin (102) . If the cluster is connected, the error component e w(i):= b w(i)−(1/|C|)X i∈C b w(i)(147) is upper bounded as X i∈C e w(i) 2 2≤1 αλ2L(C)X i∈C 1 mi ε(i) 2 2+α|∂C|2 w(C) 2 2+R2.(148) Here, we used R:= maxi′∈V\C b w(i′) 2. Proof. See Section 6.8.1. 134
[138] P. R. Halmos, Measure Theory. New York: Springer, 1974. [139] C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,” Foundations and Trends®in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014. [Online]. Available: http://dx.doi.org/10.1561/0400000042 [140] U. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’14. New York, NY, USA: Association for Computing Machinery, 2014, p. 1054–1067. [Online]. Available: https://doi.org/10.1145/2660267.2660348 [141] Apple Machine Learning Research, “Understanding aggregate trends for apple intelligence using differential privacy,” https://machinelearning. apple.com/research/differential-privacy-aggregate-trends, April 2025, accessed: 2025-05-20. [142] J. M. Abowd, “The u.s. census bureau adopts differential privacy,” in Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, ser. KDD ’18. New York, NY, USA: Association for Computing Machinery, 2018, p. 2867. [Online]. Available: https://doi.org/10.1145/3219819.3226070 [143] J. P. Near, D. Darais, N. Lefkovitz, and G. S. Howarth, “Guidelines for evaluating differential privacy guarantees,” National Institute of Standards and Technology, Gaithersburg, MD, NIST 237
Special Publication NIST SP 800-226, 2025. [Online]. Available: https://doi.org/10.6028/NIST.SP.800-226 [144] S. Asoodeh, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar, “A Better Bound Gives a Hundred Rounds: Enhanced Privacy Guarantees via f-Divergences,” arXiv e-prints, p. arXiv:2001.05990, Jan. 2020. [145] I. Mironov, “Rényi differential privacy,” in 2017 IEEE 30th Computer Security Foundations Symposium (CSF), 2017, pp. 263–275. [146] S. M. Kay, Fundamentals of statistical signal processing. Vol. 2., Detection theory, ser. Prentice-Hall signal processing series. Upper Saddle River, NJ: Prentice-Hall PTR, 1998. [147] P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” in Proceedings of the 32nd International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, F. Bach and D. Blei, Eds., vol. 37. Lille, France: PMLR, 07–09 Jul 2015, pp. 1376–1385. [Online]. Available: https://proceedings.mlr.press/v37/kairouz15.html [148] Q. Geng and P. Viswanath, “The optimal noise-adding mechanism in differential privacy,” IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 925–951, 2016. [149] M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” ser. CCS ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 308–318. [Online]. Available: https://doi.org/10.1145/2976749.2978318 238
[150] L. Chua, B. Ghazi, P. Kamath, R. Kumar, P. Manurangsi, A. Sinha, and C. Zhang, “How private are DP-SGD implementations?” in Proceedings of the 41st International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, Eds., vol. 235. PMLR, 21–27 Jul 2024, pp. 8904–8918. [Online]. Available: https://proceedings.mlr.press/v235/chua24a.html [151] H. Shu and H. Zhu, “Sensitivity analysis of deep neural networks,” in Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, ser. AAAI’19/IAAI’19/EAAI’19. AAAI Press, 2019. [Online]. Available: https://doi.org/10.1609/aaai.v33i01.33014943 [152] R. Busa-Fekete, A. Munoz-Medina, U. Syed, and S. Vassilvitskii, “Label differential privacy and private training data release,” in Proceedings of the 40th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 202. PMLR, 23–29 Jul 2023, pp. 3233–3251. [Online]. Available: https://proceedings.mlr.press/v202/busa-fekete23a.html [153] B. Balle, G. Barthe, and M. Gaboardi, “Privacy amplification by subsampling: tight analyses via couplings and divergences,” in Proceedings of the 32nd International Conference on Neural Information Processing Systems, ser. NIPS’18. Red Hook, NY, USA: Curran Associates Inc., 2018, pp. 6280–6290. [154] P. Cuff and L. Yu, “Differential privacy as a mutual information constraint,” in Proceedings of the 2016 ACM SIGSAC Conference on 239
Computer and Communications Security, ser. CCS ’16. New York, NY, USA: Association for Computing Machinery, 2016, pp. 43–54. [Online]. Available: https://doi.org/10.1145/2976749.2978308 [155] A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Médard, “From the information bottleneck to the privacy funnel,” in 2014 IEEE Information Theory Workshop (ITW 2014), 2014, pp. 501–505. [156] M. Mohamed, B. Shrestha, and N. Saxena, “Smashed: Sniffing and manipulating android sensor data for offensive purposes,” IEEE Transactions on Information Forensics and Security, vol. 12, no. 4, pp. 901–913, 2017. [157] A. Turner, D. Tsipras, and A. Madry, “Clean-label backdoor attacks,” 2019. [Online]. Available: https://openreview.net/forum?id= HJg6e2CcK7 [158] A. Vassilev, A. Oprea, A. Fordyce, and H. Anderson, “Adversarial machine learning: A taxonomy and terminology of attacks and mitigations,” National Institute of Standards and Technology, Gaithersburg, MD, NIST Artificial Intelligence (AI) Report NIST AI 100-2e2023, 2024. [Online]. Available: https://doi.org/10.6028/NIST.AI. 100-2e2023 [159] P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer, “Machine learning with adversaries: Byzantine tolerant gradient descent,” in Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and 240
R. Garnett, Eds., vol. 30. Curran Associates, Inc., 2017. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/2017/file/ f4b9ec30ad9f68f89b29639786cb62ef-Paper.pdf [160] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov, “How to backdoor federated learning,” in Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, S. Chiappa and R. Calandra, Eds., vol. 108. PMLR, 26–28 Aug 2020, pp. 2938–2948. [Online]. Available: https://proceedings.mlr.press/v108/bagdasaryan20a.html [161] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’15. New York, NY, USA: Association for Computing Machinery, 2015, p. 1322–1333. [Online]. Available: https://doi.org/10.1145/2810103.2813677 [162] G. Lugosi and S. Mendelson, “Robust multivariate mean estimation: The optimality of trimmed mean,” Annals of Statistics, vol. 49, no. 1, pp. 393–410, Feb. 2021, publisher Copyright: ©Institute of Mathematical Statistics, 2021. [163] X. Cao, M. Fang, J. Liu, and N. Gong, “Fltrust: Byzantine-robust federated learning via trust bootstrapping,” in Network and Distributed Systems Security (NDSS) Symposium 2021, 01 2021. [164] S. M. Stigler, “The Asymptotic Distribution of the Trimmed Mean,” 241
The Annals of Statistics, vol. 1, no. 3, pp. 472 – 477, 1973. [Online]. Available: https://doi.org/10.1214/aos/1176342412 [165] S. Shen, S. Tople, and P. Saxena, “Auror: defending against poisoning attacks in collaborative deep learning systems,” in Proceedings of the 32nd Annual Conference on Computer Security Applications, ser. ACSAC ’16. New York, NY, USA: Association for Computing Machinery, 2016, p. 508–519. [Online]. Available: https://doi.org/10.1145/2991079.2991125 [166] N. Wang, Y. Xiao, Y. Chen, Y. Hu, W. Lou, and Y. T. Hou, “Flare: Defending federated learning against model poisoning attacks via latent space representations,” in Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, ser. ASIA CCS ’22. New York, NY, USA: Association for Computing Machinery, 2022, p. 946–958. [Online]. Available: https://doi.org/10.1145/3488932.3517395 [167] M. Fang, Z. Zhang, Hairi, P. Khanduri, J. Liu, S. Lu, Y. Liu, and N. Gong, “Byzantine-robust decentralized federated learning,” in Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’24. New York, NY, USA: Association for Computing Machinery, 2024, p. 2874–2888. [Online]. Available: https://doi.org/10.1145/3658644.3670307 [168] D. Yin, Y. Chen, R. Kannan, and P. Bartlett, “Byzantine-robust distributed learning: Towards optimal statistical rates,” in Proceedings of the 35th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 80. PMLR, 10–15 Jul 2018, pp. 5650– 5659. [Online]. Available: https://proceedings.mlr.press/v80/yin18a.html 242
[169] K. Chaudhuri, C. Monteleoni, and A. Sarwate, “Differentially private empirical risk minimization,” J. Mach. Learn. Res., vol. 12, pp. 1069–1109, Mar. 2011. [170] C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and differential privacy,” in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 51–60. 243