Krishna Pillutla

Yassine Laguel

Jérôme Malick

Zaid Harchaoui

Federated Learning with Heterogeneous Data: A Superquantile Optimization Approach

We present a federated learning framework that is designed to robustly deliver good predictive performance across individual clients with heterogeneous data. The proposed approach hinges upon a superquantile-based learning objective that captures the tail statistics of the error distribution over heterogeneous clients. We present a stochastic training algorithm which interleaves differentially private client reweighting steps with federated averaging steps. The proposed algorithm is supported with finite time convergence guarantees that cover both convex and non-convex settings. Experimental results on benchmark datasets for federated learning demonstrate that our approach is competitive with classical ones in terms of average error and outperforms them in terms of tail statistics of the error.

Introduction

Federated learning is a distributed machine learning framework where many clients (e.g. mobile devices) collaboratively train a model under the orchestration of a central server (e.g. service provider), while keeping the training data private and local to the client throughout the training process [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF][START_REF] Kairouz | Advances and Open Problems in Federated Learning[END_REF]. It has found widespread adoption across industry [START_REF] Bonawitz | Towards Federated Learning at Scale: System Design[END_REF][START_REF] Paulik | Federated Evaluation and Tuning for On-Device Personalization: System Design & Applications[END_REF] for applications ranging from applications on smart devices [START_REF] Yang | Applied Federated Learning: Improving Google Keyboard Query Suggestions[END_REF][START_REF] Hard | Federated Learning for Mobile Keyboard Prediction[END_REF] to healthcare [START_REF] Brisimi | Federated learning of predictive models from federated Electronic Health Records[END_REF][START_REF] Huang | Patient Clustering Improves Efficiency of Federated Machine Learning to Predict Mortality and Hospital stay time using Distributed Electronic Medical Records[END_REF].

A key feature of federated learning is statistical heterogeneity, i.e., client data distributions are not identically distributed [START_REF] Kairouz | Advances and Open Problems in Federated Learning[END_REF][START_REF] Li | Federated Learning: Challenges, Methods, and Future Directions[END_REF]. In typical cross-device federated learning scenarios, each client corresponds to a user. The diversity in the data they generate reflects the diversity in their unique personal, cultural, regional and geographical characteristics.

This data heterogeneity in federated learning manifests itself as a train-test distributional shift. Indeed, the usual approach minimizes the prediction error of the model on average over the population of clients available for training [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF], while at test time, the same model is deployed on individual clients. This approach can be liable to fail on clients whose data distribution is far from most of the population or who may have less data than most of the population. It is highly desirable, therefore, to have a federated learning method that can robustly deliver good predictive performance across a wide variety of natural distribution shifts posed by individual clients.

We present in this paper a robust approach to federated learning that guarantees a minimal level of predictive performance to all clients even in situations where the population is heterogeneous. The approach we develop addresses these issues by minimizing a learning objective based on the notion of a superquantile [START_REF] Rockafellar | Conditional Value-at-Risk for General Loss Distributions[END_REF][START_REF] Rockafellar | Risk tuning with generalized linear regression[END_REF], a risk measure that captures the tail behavior of a random variable.

Training models with a learning objective involving the superquantile raises challenges. The superquantile is a non-smooth functional with sophisticated properties. Furthermore, the superquantile function can be seen as a kind of nonlinear expectation that we would like to blend well with averaging mechanisms. We show how to address the former by leveraging the dual formulation and the latter by leveraging the tail-domain viewpoint. As a result, we can obtain an algorithm that can be implemented in a similar way to FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] yet offers important benefits to heterogeneous populations.

The approach we propose, ∆-FL, allows one to control higher percentiles of the distribution of errors over the heterogeneous population of clients. We show in the experiments that our approach is more efficient than a direct approach simply seeking to minimize the worst error over the population of clients. Compared to FedAvg, ∆-FL delivers improved prediction to data-poor or non-conforming clients. We present finite time theoretical convergence guarantees for the ∆-FL algorithm when used to train additive models or deep networks and show how to implement it in a way that is compatible and modular with secure aggregation and distributed differential privacy.

Contributions

We make the following concrete contributions.

• The ∆-FL Framework: We introduce the ∆-FL framework, summarized in Figure 1, which seeks to guarantee a minimal level of predictive performance on nonconforming clients. The framework relies on a nonsmooth superquantile-based objective to minimize the tail statistics of the prediction errors on the client data distributions. The objective is parameterized by the conformity level, which is a scalar summary of how closely a client conforms to the population.

• Optimization Algorithm, Convergence and Privacy Analysis: To optimize the ∆-FL objective, we present a federated optimization algorithm which interleaves differentially private client reweighting steps with federated averaging steps. We establish bounds on its rate of convergence in the convex and nonconvex cases. Further, we provided an analysis of the differential privacy of the proposed algorithm.

• Numerical Experiments: We perform numerical experiments using neural networks and linear models, on tasks including image classification, and sentiment analysis based on public datasets. The experiments demonstrate superior performance of ∆-FL over state-of-the-art baselines on the upper quantiles of the error on test clients, with particular improvements on data-poor clients, while being competitive on the mean error.

Outline. We start with Section 2 to describe the related work. Section 3 describes the general setup, recalls the FedAvg algorithm for federated learning, and formalizes the notions of conformity and heterogeneity. Section 4 presents a federated optimization algorithm for ∆-FL. We analyze its convergence in the convex and non-convex cases, as well as its differential privacy properties in Section 5. We discuss extension to other risk measures and relations to fair allocation in Section 6. Section 7 presents experimental results, comparing the proposed approach to existing ones, on benchmark datasets for federated learning. Detailed proofs and additional details are deferred to the supplement. The code and the scripts to reproduce results are made publicly available at https://github.com/krishnap25/ simplicial-fl.

An early version of this work was presented at IEEE CISS [START_REF] Laguel | A Superquantile Approach to Federated Learning with Heterogeneous Devices[END_REF]. This paper extends and improves upon it in several respects. First, we give an improved and sharp convergence analysis in both the general nonconvex as well as strongly convex cases. Second, we augment our algorithm with differential privacy and analyze its privacy and utility. Finally, we conduct an expanded numerical study, including comparing with baselines such as Tilted-ERM [START_REF] Li | Tilted Empirical Risk Minimization[END_REF] that were published after our conference paper.

Notation. The norm • denote the Euclidean norm • 2 in R d . We use ∆ N -1 = π ∈ R N + :

N k=1 π k = 1 to denote the probability simplex in R N .

Related Work

Federated learning was introduced by [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] to handle distributed on-client learning [START_REF] Kairouz | Advances and Open Problems in Federated Learning[END_REF][START_REF] Li | Federated Learning: Challenges, Methods, and Future Directions[END_REF][START_REF] Gafni | Federated Learning: A Signal Processing Perspective[END_REF]. A plethora of recent extensions have also been proposed [START_REF] Yurochkin | Bayesian Nonparametric Federated Learning of Neural Networks[END_REF][START_REF] Sattler | Clustered Federated Learning: Model-Agnostic Distributed Multitask Optimization Under Privacy Constraints[END_REF][START_REF] Mills | Communication-Efficient Federated Learning for Wireless Edge Intelligence in IoT[END_REF][START_REF] Wei | Federated Learning With Differential Privacy: Algorithms and Performance Analysis[END_REF][START_REF] Amiri | Machine Learning at the Wireless Edge: Distributed Stochastic Gradient Descent Over-the-Air[END_REF][START_REF] Shlezinger | UVeQFed: Universal Vector Quantization for Federated Learning[END_REF][START_REF] Jhunjhunwala | Adaptive Quantization of Model Updates for Communication-Efficient Federated Learning[END_REF][START_REF] Sery | Over-the-Air Federated Learning From Heterogeneous Data[END_REF][START_REF] Collins | Exploiting Shared Representations for Personalized Federated Learning[END_REF]. Our approach of addressing the statistical heterogeneity by proposing a new objective, which is broadly applicable in these settings.

Distributionally robust optimization [START_REF] Ben-Tal | Robust Solutions of Optimization Problems Affected by Uncertain Probabilities[END_REF], which aims train models that perform uniformly well across all subgroups instead of just on average, has witnessed a flurry of recent research [START_REF] Lee | Minimax statistical learning with Wasserstein distances[END_REF][START_REF] Duchi | Variance-based Regularization with Convex Objectives[END_REF][START_REF] Kuhn | Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning[END_REF]. This approach is closely related to the risk measures studied in economics and finance [START_REF] Artzner | Coherent Measures of Risk[END_REF][START_REF] Rockafellar | Optimization of Conditional Value-at-Risk[END_REF][START_REF] Ben-Tal | An Old-New Concept of Convex Risk Measures: The Optimized Certainty Equivalent[END_REF][START_REF] Föllmer | Stochastic Finance: An Introduction in Discrete Time[END_REF]. The recent works [START_REF] Laguel | First-Order Optimization for Superquantile-Based Supervised Learning[END_REF][START_REF] Levy | Large-Scale Methods for Distributionally Robust Optimization[END_REF][START_REF] Curi | Adaptive Sampling for Stochastic Risk-Averse Learning[END_REF] study optimization algorithms for risk measures. More broadly, risk measures have been successfully utilized in problems ranging from bandits [START_REF] Sani | Risk-Aversion in Multi-armed Bandits[END_REF][START_REF] Cassel | A General Approach to Multi-Armed Bandits Under Risk Criteria[END_REF], reinforcement learning [START_REF] Chow | Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach[END_REF][START_REF] Tamar | Policy Gradient for Coherent Risk Measures[END_REF][START_REF] Chow | Risk-Constrained Reinforcement Learning with Percentile Risk Criteria[END_REF], and fairness in machine learning [START_REF] Williamson | Fairness Risk Measures[END_REF][START_REF] Rezaei | Robust Fairness Under Covariate Shift[END_REF]. The federated learning method we here is based on the superquantile [START_REF] Rockafellar | Conditional Value-at-Risk for General Loss Distributions[END_REF], a popular risk measure. We propose a stochastic optimization algorithm adapted to the federated setting and prove the convergence.

Addressing statistical heterogeneity in federated learning has led to two lines of work. The first includes algorithmic advances to alleviate the effect of heterogeneity on convergence rates while still minimizing the classical expectationbased objective function of empirical risk minimization. These techniques include the use of proximal terms [START_REF] Li | Federated Optimization in Heterogeneous Networks[END_REF], control variates [START_REF] Karimireddy | SCAFFOLD: stochastic controlled averaging for federated learning[END_REF] or augmenting the server updates [START_REF] Wang | Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization[END_REF][START_REF] Reddi | Adaptive Federated Optimization[END_REF]; we refer to the recent survey [START_REF] Wang | A Field Guide to Federated Optimization[END_REF] for details. More generally, the framework of local SGD has been used to study federated optimization algorithms [START_REF] Stich | Local SGD Converges Fast and Communicates Little[END_REF][START_REF] Zhou | On the Convergence Properties of a K-step Averaging Stochastic Gradient Descent Algorithm for Nonconvex Optimization[END_REF][START_REF] Haddadpour | Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization[END_REF][START_REF] Dieuleveut | Communication Trade-offs for Local-SGD with Large Step Size[END_REF][START_REF] Li | On the Convergence of FedAvg on Non-IID Data[END_REF][START_REF] Khaled | Tighter Theory for Local SGD on Identical and Heterogeneous Data[END_REF][START_REF] Koloskova | A Unified Theory of Decentralized SGD with Changing Topology and Local Updates[END_REF]. Compared to these works which study federated optimization algorithms in the smooth case, we tackle in our analysis the added challenge of nonsmoothness of the superquantile-based objective in both the general nonconvex and strongly convex cases.

The second line of work addressing heterogeneity involves designing new objective functions by modeling statistical heterogeneity and designing optimization algorithms. The AFL framework to minimize the worst-case error across all training clients and associated generalization bounds were given in [START_REF] Mohri | Agnostic Federated Learning[END_REF]. The concurrent work of [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF] proposes the q-FFL framework whose objective is inspired by fair resource allocation to minimize the L p norm of the per-client losses. Several related works were also published following the initial presentation of the current work [START_REF] Laguel | Device Heterogeneity in Federated Learning: A Superquantile Approach[END_REF]. A federated optimization algorithm for AFL was proposed and its convergence was analyzed in [START_REF] Deng | Distributionally Robust Federated Averaging[END_REF]. Distributional robustness to affine shifts in the data was considered in [START_REF] Reisizadeh | Robust Federated Learning: The Case of Affine Distribution Shifts[END_REF] along with convergence guarantees. Finally, a classical risk measure, namely the entropic risk measure, was considered in [START_REF] Li | Tilted Empirical Risk Minimization[END_REF]. We note that no convergence guarantees are currently known for the stochastic optimization algorithms of [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF].

Problem Setup

We begin this section by recalling the standard setup of federated learning in Section 3.1. We then describe the standard approach to federated learning and its associated optimization, FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] in Section 3.2. We then describe the statistical heterogeneity in some detail in Section 3.3.

Federated Learning Setup

Federated learning consists of heterogeneous clients which collaboratively train a machine learning model under the orchestration of a central server. The model is then deployed on all clients, including those not seen during training.

Let the vector w ∈ R d denote the d model parameters. We assume that each client has a distribution q over some data space such that the data on the client is sampled i.i.d. from q. The loss incurred by the model w ∈ R d on this client is F (w; q) := E ξ∼q [f (w; ξ)], where f (w; ξ) is the chosen loss function, such as the logistic loss, on input-output pair ξ under the model w. The expectation above is assumed to be well-defined and finite. For a given distribution q, smaller values of F (•; q) denote a better fit of the model to the data.

There are N clients available for training. We number these clients as 1, . . . , N and denote the distribution on training client k by q k . We denote the loss on client k by F k (w) := F (w; q k ). The goal of federated learning is to train a model w so that it achieves good performance when deployed each test client, including those which are unseen during training. Owing to statistical heterogeneity of federated learning, the distribution p of a specific test client could be different from the average distribution (1/N ) N k=1 q k that the model is trained on. Each federated learning method is characterized by an objective function and the federated optimization algorithm used to minimize it. It is not possible to achieve good performance on each client simultaneously with a single model w, as it would be a difficult multiobjective optimization problem. The usual approach is combine the per-client losses into a scalar and minimize this objective. The choice of the objective function and optimization algorithm are primarily determined by the three key aspects of federated learning [START_REF] Kairouz | Advances and Open Problems in Federated Learning[END_REF][START_REF] Li | Federated Learning: Challenges, Methods, and Future Directions[END_REF]

Federated Learning and the FedAvg algorithm

Analogous to the classical expectation-based objective function in empirical risk minimization approach, the standard objective in federated learning is to minimize the average loss on the training clients

min w∈R d 1 N N k=1 F k (w) + λ 2 w 2 , (1)
where λ ≥ 0 is a regularization parameter. We will call this objective as the vanilla FL objective. The de facto standard training algorithm is FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]. Each round of the algorithm consists in following steps: (a) The server samples a set S of m clients from [N ] and broadcasts the current model w (t) to these clients. (b) Staring from w (t) k,0 = w (t) , each client k ∈ S makes τ local gradient or stochastic gradient descent steps1 with a learning rate γ: w

(t) k,j+1 = w (t) k,j -γ∇F k (w (t) k,j
) . (c) The models from the selected clients are sent to the server and aggregated to update the server model

w (t+1) = 1 m k∈S w (t) k,τ .
FedAvg addresses the communication bottleneck by using τ > 1 local computation steps as opposed to τ = 1 local steps in minibatch SGD. It also performs the averaging step (c) securely to enhance data privacy. However, the vanilla FL objective places a limit on how well statistical heterogeneity can be addressed. By minimizing the average training loss, the resulting model w can sacrifice performance on "difficult" clients in order to perform well on average. In other words, it is not guaranteed to perform well on individual test clients, whose distribution p might be quite different from the average training distribution (1/N ) N k=1 q k . Our goal in this work is to design an objective function, different from the vanilla FL objective (1) to better handle statistical heterogeneity and the associated train-test mismatch. We also design a federated optimization algorithm similar to FedAvg to optimize it.

0 1 1 1 E[Z] Q θ (Z) S θ (Z) = E[Z | Z > Q θ (Z)]

Problem Formulation: Conformity and Heterogeneity

In this work, we consider test clients whose distribution p can be written as a mixture p π := N k=1 π k q k of the training distribution q k of the clients with weights π ∈ ∆ N -1 . Here, ∆ N -1 denotes the probability simplex in R N . The test distribution p π is different from the average training distribution p train = (1/N ) N k=1 q k if the mixture weights π are different from 1/N at training time.

We now define conformity of a mixture p π to the training distribution p train , as a measure of the degree of similarity between p π and p train .

Definition 1. The conformity conf(p π ) ∈ [N -1 , 1] of a mixture p π with weights π is defined as N max k∈[N ] π k -1 .
The conformity of a client refers to the conformity of its data distribution.

When π and α coincide, we have that conf(p π ) = 1, and this is the largest possible value of conf(p π ). On the other extreme, suppose that π k = 1 for some k, so that π is very different from α. Here, conf(p π ) = 1/N , which is the smallest value it takes. In other words, the conformity measures how similar the mixture weights π of p π are to the original weights α.

More generally, a mixture distribution p π with conf(p π ) ≥ θ must satisfy π k ≤ 1/(θN ) for each k. In other words, the set of all mixture weights {π ∈ ∆ N -1 : conf(p π ) ≥ θ} lie in an axis-parallel box around (1/N, • • • , 1/N ), as shown in Figure 2 (left). We do not directly impose a lower bound on π k because it is not realistic to assume that the distribution on a test client must necessarily contain a component of every training distribution q k . Interpretation. Assuming that the training clients are a representative sample of the population of clients, every client's distribution can be well-approximated by a mixture p π for some π ∈ ∆ N -1 . The conformity of a client is a scalar summary of how close it is to the population. A test client with conformity θ ≈ 1 closely conforms to the population. Then, a model trained on the population p train is expected to have a high predictive power. In contrast, a test client with θ ≈ 0 would be vastly different from the population p train , and the predictive power of a model trained on p train could be poor. The inverse of the conformity 1/conf(p π ) is a measure of how much p π is shifted relative to p train .

There is a trade-off between the fitting to the population and supporting non-conforming test clients. The conformity θ presents a natural way to encapsulate this tradeoff in a scalar parameter. That is, given a conformity θ ∈ (0, 1), we choose to only support test distributions p π with conf(p π ) ≥ θ.

Handling Heterogeneity with ∆-FL

In this section, we introduce the ∆-FL framework in Section 4.1, and propose an algorithm to optimize in the federated setting in Section 4.2.

The ∆-FL Framework

The ∆-FL framework aims to address the train-test distributional mismatch by supplying each test client with a model appropriate to its conformity. Given a discretization {θ 1 , . . . , θ r } of (0, 1], ∆-FL maintains r models, one for each conformity level θ j . The local data is not allowed to leave a client due to privacy restrictions; hence, the conformity of a test client cannot be measured. Instead, we allow each test client to tune their conformity. See the schematic in Figure 1 for an illustration.

To train a model for a conformity level θ, we aim to do well on all distributions p π with conf(p π ) ≥ θ:

min w∈R d F θ (w) := max π∈P θ F (w; p π ) + λ 2 w 2
, where,

P θ := π ∈ ∆ N -1 : conf(p π ) ≥ θ . (2)
In contrast, the vanilla FL objective optimizes F (w; p train ), which is defined on the basis of the training distribution p train . We observe that ∆-FL is designed to be robust on all test clients with conformity at least θ.

Connection to the Superquantile. The objective function of (2) brings the notion of superquantile into play. For θ ∈ (0, 1), the (1θ)-superquantile S θ (Z) of a continuous random variable Z is simply its tail expectation

S θ (Z) = E[Z | Z > Q θ (Z)], where Q θ (Z) is the (1 -θ)-quantile of Z.
The superquantile, also known as the conditional value at risk (CVaR), thus quantifies the worst-case or tail behavior of a random variable Z; see Figure 2. More generally, the following definition is applicable to both discrete and continuous random variables [START_REF] Rockafellar | Optimization of Conditional Value-at-Risk[END_REF] S θ (Z) = min

η∈R η + 1 θ E [max{0, Z -η}] .
Next, we show that the ∆-FL objective is the superquantile of a discrete random variable with the per-client losses.

Property 1. Let Z(w) be a discrete random variable which takes the value F k (w) with probability 1/N for k = 1, . . . , N . Then, we have that

F θ (w) = S θ (Z(w)) + (λ/2) w 2 .
Proof. The proof follows from the following equality, which holds due to linear programming duality:

max π∈P θ N k=1 π k x k = min (η,µ)∈M η + 1 θ N k=1 µ k N with M = {(η, µ) ∈ R× R N + : µ k ≥ x k -η for k ∈ [N ]}.

Federated Optimization for ∆-FL

We now propose a federated optimization algorithm for the ∆-FL objective [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF]. While there could be many approaches to opimizing (2), we consider algorithms similar to FedAvg for their ability to avoid communication bottlenecks and preserve the privacy of user data. The objective function ( 2) is effectively the average loss of the clients in the tail, as visualized in Figure 2. Therefore, a natural algorithm to minimize it first evaluates the loss on all the clients, and only performs gradient updates on those clients in the tail above the (1θ)-quantile. However, a practical algorithm cannot assume that all the clients are available at a given point of time. Therefore, we perform the same operation on a subsample of clients.

Concretely, the optimization algorithm for the ∆-FL objective (2) is given in Algorithm 1. It has four steps: (a) Model Broadcast (line 2): The server samples a set S of m clients from [N ] and sends the current model w (t) . (b) Quantile Computation and Reweighting (lines 3 and 5): Selected clients k ∈ S and the server collaborate to estimate the (1θ)-quantile of the losses F k (w (t) ) with differential privacy. The clients then update their weights to be zero if their loss is smaller than the estimated quantile, and leave them unchanged otherwise. This ensures that model updates are only aggregated from the tail clients; cf. Estimate the (1θ)-quantile of F k (w (t) ) for k ∈ S with distributed differential privacy (Algorithm 2); call this Q (t)

4:

for each selected client k ∈ S in parallel do

5: Set π(t) k = I F k (w (t) ) ≥ Q (t) 6:
Initialize w

(t) k,0 = w (t)
7:

for j = 0, • • • , τ -1 do 8: w (t) k,j+1 = (1 -γλ)w (t) k,j -γ∇F k (w (t) k,j ) 9:
end for 10:

end for 11: The models from the selected clients are sent to the server and aggregated to update the server model, with weights from line 5). Compared to FedAvg, ∆-FL has the additional step of computing the quantile and new weights π(t) k for each selected client k ∈ S in lines 3 and 5. Let us consider ∆-FL in relation to the three keys aspects of federated learning which we introduced in Section 3.1.

w (t+1) = k∈S π(t) k w (t) k,τ / k∈S π(t)
(1) Communication Bottleneck: Identical to FedAvg, ∆-FL algorithm performs multiple computation rounds per communication round. (2) Statistical Heterogeneity: The ∆-FL objective (2) is designed to better handle the statistical heterogeneity by minimizing the worst-case over all test distributions with conformity at least θ, while the vanilla FL objective cannot handle non-conforming clients. (3) Privacy: Identical to FedAvg, ∆-FL does not require any data transfer and the aggregation of line 11 can be securely performed using secure multiparty communication. The extra step of quantile computation is also performed with distributed differential privacy, as we describe next.

Quantile Estimation with Distributed Differential Privacy. The naïve way to compute the quantile of the per-client losses in line 3 of Algorithm 1 is to have the clients send their losses to the server. To avoid the privacy risk of leakage of information about the clients to the server, we compute the quantile with distributed differential privacy [START_REF] Kairouz | The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation[END_REF] using the discrete Gaussian mechanism [START_REF] Canonne | The Discrete Gaussian for Differential Privacy[END_REF]. The key idea behind differential privacy [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF][START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF] is to ensure that the addition or removal of the data from one client does not lead to a substantial change in the output of an algorithm. A large change in the output would give a privacy adversary enough signal to learn about the client which was added or removed.

Our algorithm is given in Algorithm 2. All computations are performed on the ring

Z M of integers modulo M . 2 Each client k first computes a local histogram x k on [0, B] based on edges 0 ≤ l 0 < l 1 < • • • < l n = B,
where the losses assumed to bounded as F k (w) ∈ [0, B]. Each client then adds random discrete Gaussian 3 noise ξ k ∼ N Z (0, σ 2 I n ) with scale parameter σ 2 , and finally sums them up using secure multiparty computation [START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF]. We abstract out the details of the secure summation oracle and only require that it return the sum k∈S x k mod M without revealing any further information to a privacy adversary.

At the end of all these steps, the server has a histogram ĥ ∈ R n which approximates the true histogram h = k∈S x k of per-client losses. Finally, Algorithm 2 returns the bin edge l j * θ ( ĥ) nearest to the (1θ)-quantile of the histogram ĥ 2 For ease of handling negative integers, we perform modular arithmetic over the ring

{-M/2 + 1, • • • , -1, 0, 1, 2, • • • , M/2} rather than {0, 1, • • • , M -1}.
3 See Appendix B for a formal definition.

Algorithm 2 Quantile Computation with Distributed Differential Privacy

Input: Ring size M , set S of clients where each client k has a scalar k ∈ [0, B], target quantile 1θ ∈ (0, 1),

discretization l 0 , l 1 , • • • , l n of [0, B], variance proxy σ 2 , scaling factor c ∈ Z + 1: Each client k computes local histogram x k = I(l j-1 ≤ k < l j ) n j=1 2: Each client k samples ξ k ∼ N Z (0, σ 2 I n ) and sets xk = (cx k + ξ k ) mod M 3: Compute s = ( k∈S xk ) mod M securely 4:
Set histogram ĥ = s/c 5: return Quantile estimate l j * θ ( ĥ) corresponding to index j * θ ( ĥ); cf. Eq. ( 3) as:

j * θ ( ĥ) = arg min j∈[n] j i=1 ĥi n i=1 ĥi -(1 -θ) . (3)

Theoretical Analysis

In this section, we analyze the convergence analysis of ∆-FL (Section 5.1) and study the differential privacy properties of the quantile computation (Section 5.2).

Convergence Analysis

We study the convergence of Algorithm 1 with respect to the objective (2) in two cases: (i) the general non-convex case, and, (ii) when each F k (w) is convex.

Assumptions. We make some assumptions on the per-client losses F k , which are assumed to hold throughout this section. For each client k ∈

[N ], the objective F k is (a) B-bounded, i.e., 0 ≤ F k (w) ≤ B for all w ∈ R d , (b) G-Lipschitz, i.e., |F k (w) -F k (w )| ≤ G w -w for all w, w ∈ R d ,
and, (c) L-smooth, i.e., F k is continuously differentiable and its gradient ∇F k is L-Lipschitz.

Equivalent Algorithm. Algorithm 1 is not amenable to theoretical analysis as it is stated because the quantile function of discrete random variables computed in line 3 is piecewise constant and discontinuous. To overcome this obstacle, we introduce a near-equivalent algorithm in Algorithm 3, which replaces the reweighting step of Algorithm 1 (lines 3 and lines 5) with the ideal reweighting suggested by the objective (2). Let us start with the case of S = [N ]. Ideally, we wish the weights π (t) to achieve the maximum over π in the objective [START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF]. It then follows by the chain rule [START_REF] Rockafellar | Variational analysis[END_REF]Thm. 10.6] that

N k=1 π (t) k ∇F k (w (t) ) ∈ ∂F θ (w (t) )
, where ∂F θ is the regular subdifferential of F θ . This allows us to derive convergence guarantees.

Algorithm 3 extends this intuition to the setting where only a subsample S ⊂ [N ] of clients are available in each round. We define the counterpart of the constraint set P θ from (2) defined on a subset S ⊂ [N ] of m clients as:

P θ,S = π ∈ ∆ |S|-1 : π k ≤ 1 θm , for k ∈ S , (4)
where we denote (π k ) k∈S ∈ R |S| by π with slight abuse of notation. With this notation, Algorithm 3 computes the new weights of the clients as

π (t) = arg max π∈P θ,S k∈S π k F k (w (t) ) .
We now analyze how close Algorithm 3 is to Algorithm 1. Let Z(w) be a discrete random variable which takes the value F k (w) with probability 1/N for k = 1, . . . , N , and let Q θ (Z(w)) denote its (1θ)-quantile. The weights Algorithm 3 The ∆-FL Algorithm with Exact Reweighting

Input: Same as Algorithm 1 1: for t = 0, 1, • • • , T -1 do 2: Sample m clients from [N ] without replacement in S 3: Compute π (t) = arg max π∈P θ,S k∈S π k F k (w (t) ) 4:
for each selected client k ∈ S in parallel do Initialize w

(t) k,0 = w (t)
6:

for j = 0, • • • , τ -1 do 7: w (t) k,j+1 = (1 -γλ)w (t) k,j -γ∇F k (w (t) k,j ) 8:
end for 9:

end for 10:

w (t+1) = k∈S π (t) k w (t) k,τ 11: end for 12: return w T π ∈ ∆ N -1 considered in Algorithm 1 (assuming that Q (t)
is the exact quantile of {F k (w (t) ) : k ∈ S}) are given by a hard-thresholding based on whether F k (w) is larger than its (1θ)-quantile:

πk = I F k (w) ≥ Q θ (Z(w)) , and, πk = πk N k =1 πk . ( 5
)
The objective defined by these weights is

Fθ (w) = N k=1 πk F k (w) + (λ/2) w 2 .
The next proposition shows that Fθ (w) = F θ (w) under certain conditions, or is a close approximation, in general.

Proposition 2. Assume F 1 (w) < • • • < F N (w) and let k = θN . Then, we have, (a) π = arg max π∈P θ N k=1 π k F k (w) is unique, (b) Q θ (Z(w)) = F k (w), (
c) if θN is an integer, then π = π so that Fθ (w) = F θ (w), and, (d) if θN is not an integer, then

0 ≤ F θ (w) -Fθ (w) ≤ B θN .
Proof. We assume w.l.o.g. that λ = 0. We apply the property that the superquantile is a tail mean (cf. Figure 2) for discrete random variables [START_REF] Rockafellar | Conditional Value-at-Risk for General Loss Distributions[END_REF]Proposition 8] to get

F θ (w) = 1 θN N k=k +1 F k (w) + 1 - θN θN F k (w) .
Comparing with (2), this gives a closed-form expression for π , which is unique because

F k -1 (w) < F k (w) < F k +1 (w). For (b), note that Q θ (Z(w)) = inf{η ∈ R : P(Z(w) > η) ≤ θ} equals F k (w) by definition of k . Therefore, if A = θ, π coincides exactly with π. When A = θ, we have Fθ (w) = 1 N -k + 1 N k=k F k (w) .
The bound on Fθ (w) -F θ (w) follows from elementary manipulations together with 0 ≤ F k (w) ≤ B.

Proposition 2 shows that when θm is an integer, Algorithm 3 is identical to Algorithm 1 where line 5 exactly computes the quantile of the per-client losses. We record another consequence of Proposition 2, namely, that the reweighting π (t) is sparse.

Remark 1. Proposition 2 shows that ∆-FL's reweighting π (t) (line 3 of Algorithm 3) is sparse. That is, π (t)
k is non-zero only for exactly θm clients with the largest losses.

Bias due to Partial Participation. Note that we define the objective (2) as the maximum over all distributions in P θ , but Algorithm 3 only maximizes weights over a set S of m clients in each round (line 3). Therefore, the updates performed by Algorithm 3 are not unbiased. In particular, Algorithm 3 minimizes the objective:

F θ (w) := E S∼Um [F θ,S (w)] , where F θ,S (w) = max π∈P θ,S k∈S π k F k (w) + λ 2 w 2
is the analogue of ( 2

sup w∈R d F θ (w) -F θ (w) ≤ B √ θm . (6)
Our general strategy will be to study the convergence (near-stationarity or near-optimality) in terms of the objective F θ which Algorithm 3 actually minimizes, and then translate that a convergence result on the original objective F θ using the bias bound [START_REF] Bonawitz | Towards Federated Learning at Scale: System Design[END_REF].

Convergence: Nonconvex Case. We start with the convergence analysis in the nonconvex case with no regularization (i.e., λ = 0). Since F θ is nonsmooth and nonconvex, we state the convergence guarantee in terms of the Moreau envelope of F θ [START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms I: Fundamentals[END_REF] following the idea of [START_REF] Drusvyatskiy | Efficiency of minimizing compositions of convex functions and smooth maps[END_REF][START_REF] Davis | Stochastic Model-Based Minimization of Weakly Convex Functions[END_REF]. Given a parameter µ > 0, we define the Moreau envelope of F θ as

Φ µ θ (w) = inf z∈R d F θ (z) + µ 2 w -z 2 . (7)
The Moreau envelope satisfies a number of remarkable properties for µ > L [22, Lemma 4.3]. It is well-defined, and the infimum on the right hand side admits a unique minimizer, called the proximal point of w, and denoted prox F θ /µ (w).

Second, the Moreau envelope is continuously differentiable with ∇Φ µ θ (w) = µ(wprox F θ /µ (w)). Finally, the stationary points of Φ µ θ and F θ coincide. Interestingly, the bound ∇Φ µ θ (w) ≤ ε directly implies a near-stationarity on F θ in the following variational sense: the proximal point z = prox F θ /µ (w) satisfies [START_REF] Drusvyatskiy | Efficiency of minimizing compositions of convex functions and smooth maps[END_REF]Sec. 4.1]: (a) z is close to w; that is, zw ≤ ε/µ, (b) z is nearly stationary on F θ ; that is dist 0, ∂F θ (z) ≤ ε, where ∂F θ refers to the regular subdifferential, and, (c) F θ is uniformly close to F θ as per [START_REF] Bonawitz | Towards Federated Learning at Scale: System Design[END_REF]. Thus, we state the convergence guarantee of our algorithm in the nonsmooth nonconvex case in terms of the Moreau envelope Φ µ θ (although it never appeared in the algorithm). Theorem 3. Let the number of rounds T be fixed and set µ = 2L. Denote ∆F 0 = F θ (w (0) )inf F θ . Let ŵ be sampled uniformly at random from the sequence w (0) , • • • , w (T -1) produced by Algorithm 3 with an appropriately tuned learning rate. Then, we have,

E ∇Φ µ θ ( ŵ) 2 ≤ ∆ 0 LG 2 T + (1 -τ -1 ) 1/3 ∆ 0 LG T 2/3 + ∆ 0 L T .
Proof. Let z (t) = prox F θ /µ (w (t) ) be the proximal point of w (t) . We expand out the recursion w (t+1) = w (t) -

γ k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) to get Φ µ θ (w (t+1) ) ≤ F θ (z (t) ) + µ 2 z (t) -w (t+1) 2 = F θ (z (t) ) + µ 2 z (t) -w (t) 2 + µγ z (t) -w (t) , k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) + µγ 2 2 k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) 2 = Φ µ θ (w (t) ) + T 1 + T 2 .
The term T 1 which carries a O(γ)-coefficient controls the rate of convergence while T 2 carries a O(γ 2 )-coefficient and is a noise term. The latter can be controlled by making the learning rate small. We can handle the first term T 1 by leveraging a property of F θ known as weak convexity, meaning that adding a quadratic makes it convex. In particular,

F θ + (L/2) • 2 is convex, so that z (t) -w (t) , k∈S π (t) k ∇F k (w (t) ) ≤ F θ,S (z (t) ) -F θ,S (w (t) ) + L 2 z (t) -w (t) 2 .
Next, we take an expectation with respect to the sampling S of clients (i.e., conditioned on F (t) = σ(w (t) ), the σ-algebra generated by w (t) ). Since z (t) is independent of S (i.e., z (t) is F (t) -measurable), we get F θ on the right hand side. Next, we use that z (t) minimizes the strongly convex right hand side of [START_REF] Bottou | Optimization Methods for Large-Scale Machine Learning[END_REF] to get

E t z (t) -w (t) , k∈S π (t) k ∇F k (w (t) ) ≤ -L z (t) -w (t) 2 = - 1 4L ∇Φ µ θ (w (t) ) 2 .
This gives us a bound on A in terms of ∇Φ Convergence: Convex Case. We consider the convergence of function values in the case where each F k is convex. Owing to the non-smoothness of F θ and F θ , we consider the following smoothed version of the objective in (2) and the corresponding modification to Algorithm 3. First, define the Kullback-Leibler (KL) divergence between π ∈ ∆ |S|-1 and the uniform distribution

(1/|S|, • • • , 1/|S|) over S ⊂ [N ] as D S (π) = k∈S π k log(π k |S|) .
We simply write D(π) when S = [N ]. Inspired by [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF][START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF][START_REF] Devolder | First-order methods of smooth convex optimization with inexact oracle[END_REF], we define the smooth counterpart to (2) as

F ν θ (w) = max π∈P θ N k=1 π k F k (w) -νD(π) + λ 2 w 2 , (8)
where ν > 0 is a fixed smoothing parameter. We have that |F ν θ (w) -F θ (w)| ≤ 2ν log N . Finally, we modify line 3 of Algorithm 3 to handle F ν θ rather than F θ as

π (t) = arg max π∈P θ,S k∈S π k F k (w (t) ) -νD S (π) . (9)
Theorem 4. Suppose each function F k is convex and 0 < λ < L. Define a condition number κ = (L + λ)/λ and fix a time horizon T ≥ √ 2κ 3 . Consider the sequence (w (t) ) T t=0 of iterates produced by the Algorithm 3 with line 3 replaced by [START_REF] Bun | Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds[END_REF]. Define the averaged iterate

w (t) = t i=0 β i w (i) t i=0 β i
, where

β i = 1 - γλτ 2 -(1+i)
, and w = arg min w∈R d F θ (w). Then, with appropriate tuning of the learning rate γ and smoothing parameter ν, we have the bound

EF θ (w (T ) ) -F θ (w ) ≤ λ w (0) -w 2 exp - T √ 2κ 3 + G 2 λT + G 2 κ 2 λT 2 + B √ θm ,
where we hide absolute constants and factors polylogarithmic in the problem parameters T, G, λ, κ.

Remark 2 (About the Rate). As soon as T κ 3/2 (ignoring constants and polylog factors), we achieve the optimal rate of 1/(λT ) rate of strongly convex stochastic optimization up to the bias B/ √ θm. Further, the bias B/ √ θm due to partial participation can be controlled by choosing the cohort size m large enough. In the experiments of Section 7, we obtain meaningful numerical results when m is around 50 or 100 and θ around 1/2, indicating that the worst-case bound (6) can be pessimistic.

Proof Sketch of Theorem 4. We start with some additional notation. We absorb the regularization into the client losses to define Fk (w) = F k (w) + (λ/2) w 2 . Now, consider the smoothed counterpart of (2) on a subset S ⊂ [N ] with a smoothing parameter ν > 0 as

F ν θ,S (w) = max π∈P θ,S k∈S π k Fk (w) -νD S (π) .
It follows from the properties of smoothing [START_REF] Nesterov | Smooth minimization of non-smooth functions[END_REF][START_REF] Beck | Smoothing and First Order Methods: A Unified Framework[END_REF] and composition rules that F ν θ,S is L -Lipschitz, where L is as defined the statement of the theorem. Finally, let F t denote the sigma algebra generated by w (t) and let

E t [•] := E[•|F t ].
We start the proof with the decomposition

w (t+1) -w 2 = w (t) -w 2 -2γ k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j , w (t) -w + γ 2 k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ) 2 ,
where w is arbitrary. We bound the inner product term using the λ-strong convexity and L-smoothness of Fk . We bound the third term by using the variance bound of [START_REF] Levy | Large-Scale Methods for Distributionally Robust Optimization[END_REF]Prop. 2] as

E S∼Um k∈S π (t) k ∇F k (w (t) ) -∇F ν θ (w (t) ) 2 ≤ 8G 2 θm ,
where U m is the uniform distribution over subsets S ⊂ [N ] of size m, and

F ν θ (w) := E S∼Um F ν θ,S (
F ν θ (w (t) ) -F ν θ (w ) ≤ 16G 2 γτ θn + 9(L + λ) 2 λτ d (t) (10)
+ 1 γτ 1 - λγτ 2 w (t) -w 2 - 1 γτ E t w (t+1) -w 2 ,
where d (t) is the client drift term, defined as

d (t) := E S∼Um   k∈S π (t) k τ -1 j=0 w (t) k,j -w (t) 2 F t   . Note that d (t) = 0 if τ = 1, so d (t)
is the bias from making multiple local gradient steps on each client. This term can be bounded in terms of the left-hand side again using smoothness and the variance bound as

d (t) ≤ c γ 2 τ 2 (τ -1) G 2 + L F ν θ (w (t) ) -F ν θ (w ) .
The final missing piece is a bound which allows us to translate statements about convergence of F ν θ in terms of convergence of F θ . We achieve this using the bias bound of (6) together with approximation error of smoothing. Summing [START_REF] Caldas | LEAF: A benchmark for federated settings[END_REF] with weights as required by w (T ) with Jensen's inequality, and using (i) the bound on the client drift d (t) , (ii) the bound on the bias, (iii) optimizing the choice of the learning rate and smoothing coefficient give the final statement of the theorem. The details are provided in Appendix A.2.

Privacy Analysis

We now analyze the privacy and utility of Algorithm 2.

First, recall the definition of zero-concentrated differential privacy [START_REF] Bun | Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds[END_REF]: a randomized algorithm A satisfies (1/2)ε 2concentrated differential privacy if the Rényi α-divergence D α (A(X) A(X )) ≤ αε 2 /2 for all α ∈ (0, ∞) and all sequences X, X of inputs which differ by the addition or removal of the data of one client.

Intuitively, the addition or removal of the data contributed by one client should not change the output distribution of the randomized algorithm by much, as measured by the Rényi divergence. A smaller value of ε implies a stronger privacy guarantee. This notion of differential privacy can be translated back-and-forth with the usual one, cf. [START_REF] Canonne | The Discrete Gaussian for Differential Privacy[END_REF].

Error Criterion. We approximate the

(1-θ)-quantile of { 1 , • • • , N } by the quantile of a histogram h = (h 1 , • • • , h n ) of client losses with individual entries h j = N k=1 I(l j-1 ≤ k < l j ), where the bin edges 0 = l 0 < l 1 < • • • < l n = B are given. The bin edge l j corresponding to index j ∈ [n] approximates the (1 -θ)-quantile well if h 1 + • • • + h j ≈ (1 -θ)(h 1 + • • • + h n ).
We measure this error of approximation by the difference between the two sides. Formally, we define the error R θ (h, j) of approximating the

(1 -θ)-quantile of histogram h ∈ R n with index j ∈ [n] by R θ (h, j) = j i=1 h i n i=1 h i -(1 -θ) . (11)
We define the best achievable error R * θ (h) for estimating the (1θ)-quantile of histogram h and the best approximating index j * (h) as

R * θ (h) = min j∈[n]
R θ (h, j) , and j * θ (h) = arg min

j∈[n] R θ (h, j) , (12)
where we assume ties are broken in an arbitrary but deterministic manner. Lastly, we define the quantile error ∆ θ (h, ĥ) of estimating the quantile of h from that of ĥ as ∆ θ ( ĥ, h) = R θ h, j * θ ( ĥ) .

Essentially, if the index j * θ ( ĥ) computed from the estimate ĥ corresponds to the (1θ )-quantile of h, the quantile error satisfies ∆ θ (h, ĥ) = |θθ |.

Privacy and Utility Analysis. We now analysis the differential privacy bound of Algorithm 2 as well as the error in the quantile computation.

Theorem 5. Fix a δ > 0. Suppose that σ ≥ 1/2 and c > 0 are given, and and the modular arithmetic is performed on base M ≥ 2 + 2cN + 2N 2σ 2 log(4N n/δ). Then we have the following with probability at least 1δ:

(a) Algorithm 2 satisfies (1/2)ε 2 -concentrated DP with ε = min c 2 N σ 2 + ψn 2 , c √ N σ + ψ √ n ,
where ψ = 10

N -1 i=1 exp -2π 2 σ 2 i/(i + 1) ≤ 10(N -1) exp(-2π 2 σ 2 ).
(b) The quantile error of histogram ĥ returned by Algorithm 2 is at most

∆ θ ( ĥ, h) ≤ R * θ ( ĥ) 1 + 2σ 2 n c 2 N log 4 δ + (2 -θ) 2σ 2 n c 2 N log 4 δ ,
where R * θ ( ĥ) is the error in the estimation of (1θ)-quantile of histogram ĥ. Let us interpret the result. The effective noise scale is σ/c. Since the dominant term of the privacy error is

ε ≈ c/(σ √ N ), we choose σ/c ≈ (ε √ N ) -1
, so that the algorithm satisfies (1/2)ε 2 -concentrated DP. The role of c is to avoid degeneracy of the discrete Gaussian as σ → 0. In particular, the theorem requires σ ≥ 1/2. The error ∆ θ ( ĥ, h) is (ignoring constants and log factors)

∆ θ ( ĥ, h) R * θ ( ĥ) 1 + √ n εN + (1 + ρ) √ n εN .
If we take σ = O(1) and c = O(ε √ N ), we require M N 3/2 , ignoring constants and log factors.

Proof. Define the event

E mod = N k=1 n j=1 - M -2 2N ≤ cx k,j + ξ k,j ≤ M -2 2N . ( 13
)
Note that under E mod , no modular wraparound occurs in the algorithm, i.e., xk = cx k + ξ k and ĥ =

N k=1 xk c = n k=1 x k + ξ k c .
We assume that E mod holds throughout. The analysis of the privacy follows from the sensitivity of the sum query. Namely, let X = (x 1 , • • • , x N ) be a sequence and define A(X) = N k=1 cx k as the (rescaled) sum query. In our case, each x i is a canonical basis vector since it is a local histogram constructed from a single scalar. Algorithm 2 adds discrete Gaussian noise to the sum query to make it differentially private. That is, we get the randomized algorithm A(X) = A(X) + N k=1 ξ k . It was shown in [START_REF] Kairouz | The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation[END_REF]Corollary 12] that A(X) is approximately distributed as N Z (A(X), N σ 2 ), so a desired privacy guarantee follows from that of the discrete Gaussian mechanism [START_REF] Canonne | The Discrete Gaussian for Differential Privacy[END_REF]. In particular, for two sequences X and X differing by the addition or removal of a single basis vector x , we have that

D α (A(X) A(X )) ≈ D α (N Z (A(X), N σ 2 ) N Z (A(X ), N σ 2 )) = αc 2 2N σ 2 .
A rigorous analysis of the error, following the recipe of [START_REF] Kairouz | The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation[END_REF] leads to the first part of the theorem; the details can be found in Appendix B.

For the second part, we analyze the quantile error. Define N = n j=1 ĥj , as the analogue to N = n j=1 h j and shorthand ρ = 1θ. We bound the quantile error as

∆ θ ĥ, h = 1 N j * θ ( ĥ) j=1 h j -ρ ≤ 1 N j * θ ( ĥ) j=1 h j -ĥj + 1 N j * θ ( ĥ) j=1 ĥj -N ρ + ρ n N -N ≤ max i∈[n] 1 cN i j=1 N k=1 ξ k,j + 1 + | N -N | N R * θ ( ĥ) + ρ N N -N .
Let us define an event E sum under which we can bound each of the terms to get the desired bound:

E sum = max j∈[n] j i=1 N k=1 ξ k,i ≤ 2σ 2 N n log(4/δ) . (14)
Finally, it remains to bound the probability of E mod and E sum . This can be achieved using standard concentration arguments, which we defer to Appendix B.

Discussion

We discuss connections of ∆-FL to risk measures and fair resource allocation.

Connection to Risk Measures. The framework of risk measures in economics and finance formalizes the notion of minimizing the worst-case cost over a set of distributions [START_REF] Föllmer | Convex measures of risk and trading constraints[END_REF][START_REF] Rockafellar | The Fundamental Risk Quadrangle in Risk Management, Optimization and Statistical Estimation[END_REF][START_REF] Föllmer | Stochastic Finance: An Introduction in Discrete Time[END_REF]. The superquantile S θ (•) is a special case of a risk measure. The ∆-FL framework, which minimizes the superquantile of the per-client losses (Property 1), can be extended to other risk measures M by minimizing the objective

F M (w) := M(Z(w)) + λ 2 w 2 ,
where Z(w) is a discrete random variable which takes value F k (w) with probability α k for k ∈ [N ]. Another example of a risk measure is the entropic risk measure, which is defined as M ν ent (Z) = E[exp(νZ)]/ν where ν ∈ R + is a parameter. The analogue of ∆-FL with the entropic risk minimizes

F ν ent (w) = 1 ν log N k=1 α k exp νF k (w) + λ 2 w 2 .
This objective F ν ent (w) coincides with the one studied recently in [START_REF] Li | Tilted Empirical Risk Minimization[END_REF] under the name Tilted-ERM subsequent to the first presentation of this work [START_REF] Laguel | Device Heterogeneity in Federated Learning: A Superquantile Approach[END_REF]. Finally, we note that F ν ent is also related to the smoothed objective F ν θ from (8) as the limit

F ν ent (w) = lim θ→0 F ν θ (w) ,
where we extend the definition D(π) = N k=1 π k log(π k /α k ) as the KL divergence between π and α for unequal α k 's. Maximin Strategy for Resource Allocation. We would like to point out an interesting analogy between distributional robustness and proportional fairness. The superquantile-based objective in Eq. ( 2) is a maximin-type objective that is reminiscent of maximin objectives used in load balancing and network scheduling [START_REF] Kubiak | Proportional Optimization and Fairness[END_REF][START_REF] Stanczak | Fundamentals of Resource Allocation in Wireless Networks: Theory and Algorithms[END_REF][START_REF] Pantelidou | Scheduling in Wireless Networks[END_REF].

We can draw an analogy between the two worlds, federated learning and resource allocation resp., by identifying errors to rates and clients to users. The maximin fair strategy to resource allocation seeks to treat all users as fairly as possible by making their rates as large and as equal as possible, so that no rate can be increased without sacrificing other rates that are smaller or equal [START_REF] Pantelidou | Scheduling in Wireless Networks[END_REF].

Our superquantile-based ∆-FL framework builds off the maximin decision theoretic foundation to frame an objective that we optimize with respect to parameters of models, and this, iteratively, over multiple rounds of clientserver communication, while preserving privacy of each client.

This compositional nature of our problem, where we optimize a composition (in the mathematical sense) of a maximin-type objective and a loss function and model predictions is a difference with resource allocation in communication networks. Further explorations of the analogy are left for future work.

Model Family and Conformity Levels θ. Using a single global value of the conformity level θ for all clients could fail to balance supporting clients with low conformity with fitting the population. On the other hand, measuring the conformity of clients requires transfer of user data, a violation of privacy. To circumvent this issue, we use a similar idea to the one of [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF] where a family of models is trained simultaneously for various levels, and each test client can then tune its conformity.

Experiments

In this section, we demonstrate the effectiveness of ∆-FL in handling heterogeneity in federated learning. Our experiments were implemented in Python using automatic differentiation provided by PyTorch while the data was preprocessed using LEAF [START_REF] Caldas | LEAF: A benchmark for federated settings[END_REF]. The code to reproduce our experiments can be found online. 4 We start by describing the datasets, tasks and models in Section 7.1. We present numerical comparisons to several recent works -we list them in Section 7.2 and present the experimental results in Section 7.3. Finally, we demonstrate that ∆-FL provides the most favorable tradeoff between average error and the error on nonconforming clients in Section 7. [START_REF] Ben-Tal | Robust Solutions of Optimization Problems Affected by Uncertain Probabilities[END_REF]. Full details regarding the experiments as well as additional results are provided in the supplementary material.

Datasets, Tasks and Models

We consider two learning tasks. The dataset and task statistics are summarized in Table 1.

(a) Character Recognition: We use the EMNIST dataset [START_REF] Cohen | EMNIST: an extension of MNIST to handwritten letters[END_REF], where the input x is a 28 × 28 grayscale image of a handwritten character and the output y is its label (0-9, a-z, A-Z). Each client is a writer of the character x. The weight α k assigned to author k is the number of characters written by this author. We train both a linear model and a convolutional neural network architecture (ConvNet). The ConvNet consists in two 5×5 convolutional layers with max-pooling followed by one fully connected layer. Outputs are vectors of scores with respect to each of the 62 classes. The multinomial logistic loss is used to train both models. (b) Sentiment Analysis: We use the Sent140 dataset [START_REF] Go | Twitter Sentiment Classification using Distant Supervision[END_REF] where the input x is a tweet and the output y = ±1 is its sentiment. Each client is a distinct Twitter user. The weight α k assigned to user k is the number of tweets publised by this user. We train both a logistic regression and a Long-Short Term Memory neural network architecture (LSTM). The LSTM is built on the GloVe embeddings of the words of the tweet [START_REF] Hochreiter | Long Short-Term Memory[END_REF]. The hidden dimension of the LSTM is same as the embedding dimension, i.e., 50. We refer to the latter as "RNN". The loss used to train both models is the binary logistic loss.

Algorithms and Hyperparameters

We list here the recent works we perform numerical comparisons with and discuss their hyperparameters.

Algorithms. As discussed in Section 3, a federated learning method is characterized by the objective function as well as the federated optimization algorithm. We consider two methods optimizing the vanilla FL objective: FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF] and FedProx [START_REF] Li | Federated Optimization in Heterogeneous Networks[END_REF]. The latter augments FedAvg with a proximal term for more stable optimization. We compare to one more variant of FedAvg. Note that ∆-FL the weight π (t) (see line 3 of Algorithm 3) is sparse, i.e., it is non-zero for only some of the m selected clients, cf. Proposition 2. This is equivalent to a fewer number of effective clients per round, which is θm on average. We use as baseline FedAvg with θm clients per round, where m is the number of clients per round in ∆-FL; we call it FedAvg-Sub. We also consider two heterogeneity-aware objectives: Tilted-ERM [START_REF] Li | Tilted Empirical Risk Minimization[END_REF], which is the analogue of ∆-FL with the entropic risk measure (cf. Section 6) and AFL [START_REF] Mohri | Agnostic Federated Learning[END_REF], whose objective is obtained as the limit lim θ→0 F θ (w) of the ∆-FL objective. We also consider q-FFL [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF], which raises the per-client loss F k to the (q + 1) th power, for some q > 0. We optimize q-FFL and Tilted-ERM with the federated optimization algorithms proposed in their respective papers. We use q-FFL with q = 10 in place of AFL, as it found to have more stable convergence with similar performance.

Hyperparameters. We fix the number of clients per round to be m = 100 for each dataset-model pair with the exception of Sent140-RNN, for which we use m = 50. We fixed an iteration budget for each dataset during which FedAvg converged. We tuned a learning rate schedule using grid search to find the smallest terminal loss averaged over training clients for FedAvg. The same iteration budget and learning rate schedule were used for all other methods including ∆-FL. Each method, except FedAvg-Sub, selected m clients per round for training, as specified earlier. The regularization parameter λ, and the proximal weight of FedProx were tuned to minimize the 90 th percentile of the misclassification error on a held-out subset of training clients. We run q-FFL for q ∈ {10 -3 , 10 -2 , . . . , 10} and report q with the smallest 90 th percentile of misclassification error on test clients. We run Tilted-ERM with a temperature parameter ν ∈ {0.1, 0.5, 1, 5, 10, 50, 100, 200} and also report ν with the smallest 90 th percentile of misclassification error on test clients. We optimize ∆-FL with Algorithm 3 for conformity θ ∈ {0.8, 0.5, 0.1}.

Experimental Results

We measure in Table 2 the 90 th percentile of the misclassification error across the test clients, as a measure of the right tail of the per-client performance. We also measure in Table 3 the mean error, which measures the average test performance. Our main findings are summarized below.

∆-FL consistently achieves the smallest 90 th percentile error. ∆-FL achieves a 3.3% absolute (12% relative) improvement over any vanilla FL objective on EMNIST-ConvNet. Among the heterogeneity aware objectives, ∆-FL achieves 1.8% improvement over the next best objective, which is Tilted-ERM. We note that q-FFL marginally outperforms ∆-FL on Sent140-Linear, but the difference 0.05% is much smaller than the standard deviation across runs.

∆-FL is competitive at multiple values of θ. For EMNIST-ConvNet, ∆-FL with θ ∈ {0.5, 0.8} is better in 90 th percentile error than all other methods we compare to, and ∆-FL with θ = 0.1 is tied with T ilted -ERM , the next best method. We also empirically confirm that ∆-FL interpolates between FedAvg (θ → 1) and AFL (θ → 0).

∆-FL works best for larger values of conformity levels. We observe that ∆-FL with θ = 0.1 is unstable for Sent140-RNN. This is consistent with Theorem 4, which requires m to be much larger than 1/θ (cf. Remark 2). Indeed, this can be explained by ∆-FL's sparse re-weighting, which only gives non-zero weights to θm = 5 clients on average in each round (cf. Remark 1).

∆-FL is yet competitive in terms of average error. Perhaps surprisingly, ∆-FL actually gets the best test error performance on EMNIST-ConvNet and Sent140-Linear. This suggests that the average test distribution is shifted relative to the average training distribution p α . In the other cases, we find that the reduction in mean error is small relative to the gains in the 90 th percentile error compared to Vanilla FL methods.

Minimizing superquantile loss over all clients performs better than minimizing worst error over all clients. Specifically, AFL which aims to minimize the worst error among all clients, as well as other objectives which approximate it (∆-FL with θ → 0, q-FFL with q → ∞, Tilted-ERM with ν → 0) tend to achieve poor performance. We find that AFL achieves the highest error both in terms of 90 th percentile and the mean. ∆-FL offers a more nuanced and more effective approach via the constraint set conf(p π ) ≥ θ than the straight pessimistic approach minimizing the worst error among all clients.

Exploring the Trade-off Between Average and Tail Error

We visualize in Figures 3 and4 the distribution of test errors to explore the trade-off various methods provide between the average error and the error on nonconforming clients.

∆-FL yields improved prediction on non-conforming clients. This can be observed from the histogram of ∆-FL in Figure 3, which exhibits thinner tails than FedAvg or Tilted-ERM. We see that the vanilla FL objective of FedAvg sacrifices performance on the nonconforming clients. Tilted-ERM does improve over FedAvg in this regard, but ∆-FL has a thinner right tail than Tilted-ERM, showing a better handling of heterogeneity.

∆-FL yields improved prediction on data-poor clients. We observe in Figure 4 that Tilted-ERM and q-FFL mainly improve the performance on data-rich clients, that is clients with lots of data. On the other hand, ∆-FL gives a greater reduction in misclassification error on data-poor clients, that is clients with little data (< 200 examples per client).

Conclusion

We present the ∆-FL framework that operates with heterogeneous clients while still guaranteeing a minimal level of predictive performance to each individual client. We model the similarity between client data distributions using the conformity, which is a scalar summary of how closely a client conforms to the population. ∆-FL relies on a superquantile-based objective, parameterized by the conformity, to minimize the tail statistics of the prediction errors on the client data distributions. We present a federated optimization algorithm compatible with secure aggregation, which interleaves client reweighting steps with federated averaging steps. We derive finite time convergence guarantees that cover both convex and non-convex settings. Experimental results on federated learning benchmarks demonstrate superior performance of ∆-FL over state-of-the-art baselines on the upper quantiles of the error on test clients, with particular improvements on data-poor clients, while being competitive on the mean error.

Federated Learning with Heterogeneous Devices:

A Superquantile Optimization Approach • We have for all µ > 0 that Φ µ θ (w) ≤ F θ (w). Notation. Let S = S (t) denote the random set of clients selected in round t of Algorithm 3. We define

Supplementary Material

Table of Contents

∇F θ,S (w (t) ) = k∈S π (t) k ∇F k (w (t) ) , (16)
where π

(t) k ∈ arg max π∈P θ,S k∈S π k F k (w (t)
) is selected as in line 3 of Algorithm 3. A key consequence of the chain rule [START_REF] Rockafellar | Variational analysis[END_REF]Thm. 10.6] is

∇F θ,S (w (t) ) ∈ ∂F θ,S (w (t) ) . ( 17
)
Convergence Analysis. We now state and prove the convergence result in the nonconvex case.

Theorem 6. Fix and the number of rounds T , fix µ = 2L and set the learning rate

γ = 1 4τ L , 1 τ √ T ∆F 0 LG 2 , 1 τ T 1/3 ∆F 0 32LG 2 (1 -τ -1 ) 1/3
, where we denote

∆F 0 = Φ µ θ (w (0) ) -inf Φ µ θ ≤ F θ (w (0) ) -inf F θ . Let ŵ be sampled uniformly at random from {w (0) , • • • , w (T -1) }.
Ignoring absolute constants, we have the bound,

E ∇Φ µ θ ( ŵ) 2 ≤ ∆F 0 LG 2 T + ∆F 0 LG(1 -τ -1 ) 1/2 T 2/3 + ∆F 0 L T .
Proof. We start with some notation. Throughout, we denote z (t) as the proximal point of w (t) :

z (t) = prox F θ /µ (w (t) ) = arg min z F θ (z) + µ 2 z -w (t) 2 .
Let F (t) denote the sigma algebra generated by w (t) and define

E t [•] = E[• | F (t) ].
By definition, we have that z (t) is also F (t) -measurable. We use the update w (t+1) = w (t)γ k∈S π

(t) k τ -1 j=0 ∇F k (w (t) k,j ) to get Φ µ θ (w (t+1) ) = min z F θ (z) + µ 2 z -w (t+1) 2 ≤ F θ (z (t) ) + µ 2 z (t) -w (t+1) 2 = F θ (z (t) ) + µ 2 z (t) -w (t) 2 + µγ z (t) -w (t) , k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) + µγ 2 2 k∈S π (t) k τ -1 j=0 ∇F k (w k,j ) (t) ) 2 = Φ µ θ (w (t) ) + µγ z (t) -w (t) , k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) =:T1 + µγ 2 2 k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) 2 =:T2 . ( 18
)
We handle both T 1 and T 2 separately. We start with T 1 by defining

C j := z (t) -w (t) , k∈S π (t) k ∇F k (w (t) k,j ) -∇F k (w (t)
) .

We use the weak convexity of F θ,S , in particular [START_REF] Cohen | EMNIST: an extension of MNIST to handwritten letters[END_REF], to bound

z (t) -w (t) , k∈S π (t) k ∇F k (w (t) k,j ) = z (t) -w (t) , k∈S π (t) k ∇F k (w (t) ) + C j (16)
= z (t)w (t) , ∇F θ,S (w (t) ) + C j (15),( 17)

≤ F θ,S (z (t) ) -F θ,S (w (t) ) + L 2 z (t) -w (t) 2 + C j .
Taking an expectation conditioned on F (t) and noting that z (t) is F (t) -measurable (so the expectation is only over the randomness in S), we get

E t z (t) -w (t) , k∈S π (t) k ∇F k (w (t) k,j ) ≤ F θ (z (t) ) + µ 2 z (t) -w (t) 2 + F θ (w (t) ) - µ -L 2 z (t) -w (t) 2 + E t [C j ] .
Note that the function

h(z) := F θ (z) + µ 2 z -w (t) 2
is (µ -L)-strongly convex and z (t) is its minimizer. This gives,

h(w (t) ) -h(z (t) ) ≥ µ -L 2 z (t) -w (t) 2 .
This implies,

E t z (t) -w (t) , k∈S π (t) k ∇F k (w (t) k,j ) ≤ -(µ -L) z (t) -w (t) 2 + E t [C j ] .
Next, we bound the term C j as follows:

|C j | = z (t) -w (t) , k∈S π (t) k ∇F k (w (t) k,j ) -∇F k (w (t) ) ≤ µ -L 2 z (t) -w (t) 2 + 1 2(µ -L) k∈S π (t) k ∇F k (w (t) k,j ) -∇F k (w (t) ) 2 ≤ µ -L 2 z (t) -w (t) 2 + 1 2(µ -L) k∈S π (t) k ∇F k (w (t) k,j ) -∇F k (w (t) ) 2 ≤ µ -L 2 z (t) -w (t) 2 + L 2 2(µ -L) k∈S π (t) k w (t) k,j -w (t) 2 .
Together with the previous inequality and the equality ∇Φ µ θ (w (t) ) = µ(w (t)z (t) ), we get a bound on T 1 as

E t [T 1 ] ≤ - γτ (µ -L) 2µ ∇Φ µ θ (w (t) ) 2 + µγL 2 2(µ -L) d (t) , (19)
where

d (t) = k∈S τ -1 j=0 π (t) k w (t) k,j -w (t) 2
is the client drift. Next, we bound T 2 as

T 2 = µγ 2 2 k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) 2 ≤ µγ 2 τ 2 k∈S π (t) k τ -1 j=0 ∇F k (w (t) k,j ) 2 ≤ µγ 2 τ 2 G 2 2 , ( 20
)
where we used Jensen's inequality and ∇F k (w

(t) k,j ) 2 ≤ G 2 since F k is G-Lipschitz.
Next, we plug in [START_REF] Deng | Distributionally Robust Federated Averaging[END_REF] and ( 20) into ( 18) and invoke Proposition 12 to bound the client drift d (t) to get

E t Φ µ θ (w (t+1) ) ≤ Φ µ θ (w (t) ) - γτ (µ -L) 2 ∇Φ µ θ (w (t) ) 2 + µγ 2 τ 2 G 2 2 1 + 8L 2 γ µ -L (τ -1) .
Finally, taking an unconditional expectation, summing this up over t = 0 to T -1 and rearranging gives us the bound

E ∇Φ µ θ ( ŵ) 2 ≤ 2∆F 0 γτ T + 2γτ LG 2 (1 + 8Lγ(τ -1)) ,
where we plugged in µ = 2L. Plugging in the choice of γ (cf. Lemma 15) completes the proof.

A.2 Convergence Analysis: Strongly Convex Case

The main result is the following.

Theorem 7 (Convergence rate, Strongly Convex Case). Suppose that each F k is convex and the regularization parameter satisfies 0 < λ < L. Define notation κ = (L + λ)/λ, w = arg min w F θ (w) and ∆ 0 = w (0)w 2 . Assume also that the number of rounds is T ≥ √ 2κ 3 . Fix a smoothing parameter

ν =        G 2 λκ , if T ≤ √ 2κ 3 log 1 ∨ CT 2 κ 2 , 2G 2 κ 2 λT 2 log 1 ∨ CT 2 κ 2 , if √ 2κ 3 log 1 ∨ CT 2 κ 2 ≤ T ≤ κ 2 log 1 ∨ CT 2 κ 2 , 2G 2 λT log (1 ∨ CT ) , else,
where C = λ 2 ∆ 0 /(2G 2 log m), and a learning rate

γ = min √ λ 18τ (L + λ) √ L , 1 4τ L , 1 λτ T log 1 ∨ λ 2 ∆ 0 θm G 2 T , 1 λτ T log 2 1 ∨ λ 2 ∆ 0 T 2 G 2 κ 2 (1 -τ -1 )
T ,

where L = L + λ + G 2 /ν. Consider the sequence (w (t) ) T t=0 produced by Algorithm 3 run with smoothing parameter ν and learning rate γ, and the corresponding averaged iterate

w (T ) := T t=0 w (t) 1 -λγτ 2 -(1+t) T r=0 1 -λγτ 2 -(1+r)
.

Then, ignoring absolute constants, we have the bound,

E F θ (w (T ) ) -F θ (w ) ≤ λ w (0) -w 2 exp -T / √ 2κ 3 + B √ θm + G 2 λT 1 θm + log m log 1 ∨ λ 2 ∆ 0 T G 2 + G 2 κ 2 λT 2 1 -τ -1 + log m log 2 1 ∨ λ 2 ∆ 0 T 2 G 2 κ 2 .
We give the proof in a sequence of results. We start with some notation.

Notation. We define the client drift as

d (t) := E S∼Um   k∈S π (t) k τ -1 j=0 w (t) k,j -w (t) 2 F t   . (21)
We define the averaged superquantile as

F ν θ (w) = E S∼Um [F ν θ,S (w)] , (22)
where U m is the uniform distribution over subsets of [N ] of size m. Finally, let w = arg min w F ν θ (w). Effect of One Round. The crux of the proof of Theorem 7 is the following statement. Proposition 8. Consider the setting of Theorem 7. Let (w (t) ) t≥0 the sequence of global models generated by Algorithm 3. For any t ≥ 0, we have:

F ν θ (w (t) ) -F ν θ (w ) ≤ 1 γτ 1 - λγτ 2 w (t) -w 2 - 1 γτ w (t+1) -w 2 + 16τ G 2 γ θm + 9 (L + λ) 2 τ λ d (t) ,
where d (t) denotes the client drift, defined in [START_REF] Dieuleveut | Communication Trade-offs for Local-SGD with Large Step Size[END_REF].

Proof. We denote

E t [•] := E[• | F t ]. We expand the update w (t+1) = w (t) -γ k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ) to get E t w (t+1) -w 2 = w (t) -w 2 -2γE t   k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ), w (t) -w   =:A + γ 2 E t k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ) 2 =:B
.

Let us first bound A. We use λ-strong convexity (cf. ( 28)) of the functions Fk to get

k∈S π (t) k ∇ Fk (w (t) k,j ), w (t) -w = k∈S π (t) k ∇ Fk (w (t) ), w (t) -w + k∈S π (t) k ∇ Fk (w (t) k,j ) -∇ Fk (w (t) ) , w (t) -w ≥ F ν θ,S (w (t) ) -F ν θ,S (w ) + λ 2 w (t) -w 2 - k∈S π (t) k ∇ Fk (w (t)
k,j ) -∇ Fk (w (t) ) , w (t)w .

Next, using successively the triangle inequality, the Cauchy-Schwartz inequality and (L + λ)-smoothness of the Fk yields:

k∈S π (t) k ∇ Fk (w (t) k,j ) -∇ Fk (w (t) ) , w (t) -w ≤ k∈S π (t) k ∇ Fk (w (t) k,j ) -∇ Fk (w (t) ), w (t) -w ≤ k∈S π (t) k ∇ Fk (w (t) k,j ) -∇ Fk (w (t) ) w (t) -w ≤ k∈S π (t) k (L + λ) w (t) k,j -w (t) w (t) -w .
Finally, using 2|ab| ≤ a 2 /c 2 + c 2 b 2 and the convexity of

t → t 2 , k∈S π (t) k ∇ Fk (w (t) k,j ) -∇ Fk (w (t) ) , w (t) -w ≤ 4 λ k∈S π (t) k (L + λ) w (t) k,j -w (t) 2 + λ 4 w (t) -w 2 ≤ λ 4 w (t) -w 2 + 4 (L + λ) 2 λ k∈S π (t) k w (t) k,j -w (t) 2 .
Overall, we bound A as

A ≥ 2γ E t τ -1 j=0 F ν θ,S (w (t) ) -F ν θ,S (w ) + λ 4 w (t) -w 2 - 4 (L + λ) 2 λ k∈S π (t) k w (t) k,j -w (t) 2 ≥ 2γτ F ν θ (w (t) ) -F ν θ (w ) + λγτ 2 w (t) -w 2 - 8γ (L + λ) 2 λ d (t) ,
where we use the definition of d (t) from ( 21). We bound B using Proposition 13. Putting these together, we get,

E t w (t+1) -w 2 ≤ 1 - λγτ 2 w (t) -w 2 -(2γτ -4γ 2 τ 2 L )(F ν θ (w (t) ) -F ν θ (w )) + 16τ 2 G 2 γ 2 θm + 2 γ 2 τ (L + λ) 2 + 4γ (L + λ) 2 λ d (t) .
With γ ≤ (4τ L ) -1 we have 2γτ -4γ 2 τ 2 L ≥ γτ . Likewise, the same condition on γ also implies 2(γ (L + λ)

2 + 4(L + λ) 2 /(τ λ)) ≤ 9 (L + λ) 2 /(τ λ).
Rearranging completes the proof.

Proof of Theorem 7. We are now ready to prove the theorem.

Proof of Theorem 7. Plugging in the client drift bound of Proposition 12 into the bound of Proposition 8 and rearranging, we get

1 - 18L (L + λ) 2 τ 2 γ 2 e 2 λ F ν θ (w (t) ) -F ν θ (w ) ≤ 1 γτ 1 - λγτ 2 w (t) -w 2 - 1 γτ E t w (t+1) -w 2 + 16τ G 2 γ θm + 9G 2 (L + λ) 2 τ 2 γ 2 e 2 λ 4 + 8 θm . Since 36e 2 ≤ 18 2 for γ ≤ √ λ(18τ (L + λ) √ L ) -1 , we have 18L (L + λ) 2 τ 2 γ 2 e 2 /λ ≤ 1 2 which implies: F ν θ (w (t) ) -F ν θ (w ) ≤ 2 γτ 1 - λγτ 2 w (t) -w 2 - 2 γτ E t w (t+1) -w 2 + 32τ G 2 γ θm + 18G 2 (L + λ) 2 τ 2 γ 2 e 2 λ 4 + 8 θm =:T1
.

Next, we use convexity to get

E F ν θ (w (T ) ) -F ν θ (w ) ≤ 1 T t=0 1 -λγτ 2 -(1+t) T t=0 1 - λγτ 2 -(1+t) E F ν θ (w (t) ) -F ν θ (w )
so that telescoping the sum yields

E F ν θ (w (T ) ) -F ν θ (w ) ≤ 2 w (0) -w 2 γτ T t=0 1 -λγτ 2 -(1+t) + T 1 .
Now, we can lower bound the denominator with

T t=0 1 - λγτ 2 -(1+t) ≥ 1 γτ λ e T γτ λ ,
to get the bound

E F ν θ (w (T ) ) -F ν θ (w ) ≤ 2λe -T γτ λ w (0) -w 2 + T 1 . (23)
It remains to translate the results on F ν θ into F θ . For the left hand side, we use the bias bound of Property 9. For the right hand side, we use the λ-strong convexity of F θ and Property 9 we have:

w (0) -w 2 ≤ 2 w (0) -w 2 + 2 w -w 2 ≤ 2 w (0) -w 2 + 4 λ (F θ (w ) -F θ (w )) ≤ 2 w (0) -w 2 + 4 λ F θ (w ) -F ν θ (w ) + F ν θ (w ) -F ν θ (w ) + F ν θ (w ) -F θ (w ) ≤ 2 w (0) -w 2 + 4 λ 2B √ θm + 4 ν log m , since F ν θ (w ) -F ν θ (w ) ≤ 0.
Plugging this into [START_REF] Duchi | Variance-based Regularization with Convex Objectives[END_REF] gives us the bound

E F θ (w (T ) ) -F θ (w ) ≤ 4λ w (0) -w 2 e -T γτ λ + 32τ G 2 γ θm + 18G 2 (L + λ) 2 τ 2 γ 2 e 2 λ 4 + 8 θm + 2B √ θm + 2 ν log m 1 + 8e -T γτ λ .
Hyperparameter Optimization. To complete the proof from here, it remains to optimize the learning rate γ and the smoothing parameter ν. We invoke Lemma 14 to optimize for γ. Ignoring absolute constants, this gives us the bound

E F θ (w (T ) ) -F θ (w ) ≤ λ∆ 0 exp(-λτ ΓT ) + G 2 θmλT log 1 ∨ λ 2 ∆ 0 T θm G 2 + G 2 κ 2 λT 2 (1 -τ -1 ) log 2 1 ∨ λ 2 ∆ 0 T 2 G 2 κ 2 + B √ θm + ν log m ,
where we take

Γ = min √ λ 18τ (L + λ) √ L , 1 4τ L ,
Next, we set ν. The two terms that depend on ν are

λ∆ 0 exp(-λτ ΓT ) + ν log m = λ∆ 0 exp   - T κ + G 2 λν ∨ κ κ + G 2 λν   + ν log m ≤ λ∆ 0 max exp - λνT G 2 , exp - T κ λν 2G 2 + ν log m .
Assume now that ν ≤ 2G 2 /(λκ 2 ), so the first term in the max is active. The conditions of Lemma 14 are met since T ≥ 2κ is assumed; that gives us the choice

ν = G 2 λκ ∧ 2G 2 λT log 1 ∨ λ 2 ∆ 0 T 2G 2 log m ,
so that the error is bounded by

λ∆ 0 exp - T 2κ + 2G 2 λT log(m) log 1 ∨ λ 2 ∆ 0 T 2G 2 log m .
Likewise, if ν > 2G 2 /(λκ 2 ), the second term inside the max is active. The conditions of Lemma 14 are met since T ≥ √ 2κ 3 is assumed. That gives us the choice

ν ≤ G 2 λκ ∧ 2G 2 κ 2 λT 2 log 2 1 ∨ λ 2 ∆ 0 T 2 2G 2 κ 2 log m ,
so that the error is bounded by

λ∆ 0 exp - T √ 2κ 3 + 2G 2 κ 2 λT 2 log(m) log 2 1 ∨ λ 2 ∆ 0 T 2 2G 2 κ 2 log m .
Plugging in these choices completes the proof.

A.3 Intermediate Results

We present some prerequisites and some intermediate results which are required in the convergence proofs of both the convex and nonconvex cases. Note that for any S ⊂ [N ] of size m, the partial superquantile is differentiable at w with :

∇F ν θ,S (w) = k∈S π k ∇ Fk (w) (24)
where π denotes solution to the maximization

F ν θ,S (w) = max π∈P θ,S k∈S π k Fk (w) -ν D S (π)
Bias and variance of the partial superquantile. We use the partial superquantile defined on a subset S ⊂ [N ] to approximate the full superquantile. We start with the quality of this approximation.

Property 9. Let U m denote the uniform distribution over all subsets of [N ] of size m. For any w ∈ R d , we have

F ν θ (w) -F θ (w) ≤ B √ θm + 2 ν log m , E S∼Um ∇F ν θ,S (w) -∇F ν θ (w) 2 ≤ 8G 2 θm .
Smoothing and smoothness constants. Bounding Gradient Dissimilarity. Bounding of the variance of gradient estimators is a key assumption in the analysis of stochastic gradients methods (see e.g. the textbook [START_REF] Bottou | Optimization Methods for Large-Scale Machine Learning[END_REF]). In the centralized setting, when a stochastic objective

E ξ [f (w, ξ)],
it is standard to assume for a given estimator g w of ∇ w E [f (w, ξ] that there exists some constants M 1 , M 2 > 0 such that for all w ∈ R d ,

E [g w ] 2 ≤ M 1 or E [g w ] 2 ≤ M 1 + M 2 ∇ w E [f (w, ξ] 2 .
In the federated setting, the use of a subset S ⊂ [N ] of clients in each round induces noise on the estimation of the average gradient over the whole network. Thus, such assumption translates into a bound on the gradient dissimilarity among the clients [START_REF] Karimireddy | SCAFFOLD: stochastic controlled averaging for federated learning[END_REF][START_REF] Wang | Adaptive federated learning in resource constrained edge computing systems[END_REF]:

1 N k∈[N ] ∇ Fk (w) 2 ≤ M 1 + M 2 1 N k∈[N ] ∇ Fk (w) 2 .
In this work, we also consider the minimization of the global loss F ν θ by a stochastic algorithm based on a partial participation of the clients in the network, with the additional difficulties that we only have access to a biased estimator F ν θ of the loss F ν θ and its gradient. In particular, the adaptive reweighting of the clients selected at each round does not permit the direct use of such assumption. We show instead in the next lemma that the variance of stochastic gradient estimator can also be bounded, thanks to the Lipschitz assumption.

Proposition 11 (Gradient Dissimilarity). Consider the quantities π (t) , w (t) from Algorithm 3. We have,

E k∈S π (t) k ∇ Fk (w (t) ) 2 F t ≤ 4 + 8 θm G 2 + ∇F ν θ (w (t) ) 2 .
Proof. We drop the superscript t throughout this proof. By centering the second moment (cf. ( 27)), we have:

k∈S π k ∇ Fj (w) 2 = k∈S π k ∇ Fk (w) -∇F ν θ,S (w) 2 + ∇F ν θ,S (w) 2
= k∈S π k (∇F k (w) - i∈S π i ∇F i (w)) 2 + ∇F ν θ,S (w) 2 .
Now since the weights π k sum to one, we may use the convexity of • 2 to get:

k∈S π k ∇ Fj (w) 2 ≤ k,i∈S π k π i ∇F i (w) -∇F k (w) 2 + ∇F ν θ,S (w) 2 .
The squared triangle inequality (cf. ( 26)) together with the Lipschitz assumption on the functions F k yields:

k∈S π k ∇ Fk (w) 2 ≤ 2 k,i∈S π k π i ∇F k (w) 2 + ∇F i (w) 2 ∇F ν θ,S (w) 2 ≤ 4 G 2 + ∇F ν θ,S (w) 2 .
Thus, taking an expectation over S ∼ U m gives

E k∈S π k ∇ Fj (w) 2 F t ≤ 4 G 2 + E S∼Um ∇F ν θ,S (w) 2 .
By centering (cf. ( 27)), we get,

E k∈S π k ∇ Fk (w) 2 F t ≤ 4 G 2 + ∇F ν θ (w) 2 + E ∇F ν θ,S (w) -∇F ν θ (w) 2 F t . (25)
Finally, substituting the variance bound from Lemma 9 into (25) yields the stated result.

Bounding the Client Drift. During federated learning, each client takes multiple local steps. This causes the resulting update to be a biased estimator of a descent direction for the global objective. This phenomenon has been referred to as "client drift" [START_REF] Li | On the Convergence of FedAvg on Non-IID Data[END_REF][START_REF] Karimireddy | SCAFFOLD: stochastic controlled averaging for federated learning[END_REF]. Current proof techniques rely on treating this as a "noise" term which is to be controlled. In the context of this work, the reweighting by π (t) requires us to adapt this typical definition of client drift to our setting. In particular, recall that we define the client drift d (t) in outer iteration t of the algorithm as

d (t) := E S∼Um   k∈S π (t) k τ -1 j=0 w (t) k,j -w (t) 2 F t   .
Proposition 12 (Client Drift). If γ ≤ 1 4τ (L+λ) , we have the following bounds for any t ≥ 0:

d (t) ≤ τ 2 (τ -1)γ 2 e 2 4 + 8 θm G 2 + ∇F ν θ (w (t)
) 2 and,

d (t) ≤ τ 2 (τ -1)γ 2 e 2 4 + 8 θm G 2 + 2L F ν θ (w (t) ) -F ν θ (w ) .
Furthermore, if λ = 0, we have the bound

d (t) ≤ 8τ 2 (τ -1)γ 2 G 2 .
The last bound also works without smoothing, i.e., ν = 0.

Proof. If τ = 1, there is nothing to prove as both sides of the inequality are 0. We assume now that τ > 1. Let us first fix S ⊂ [N ] of size |S| = m. For any k ∈ S and j ∈ {1, . . . , τ -1}, by the squared triangle inequality (cf. ( 26)), we have:

w (t) k,j -w (t) 2 = w (r) k,j-1 -γ∇ Fk (w (t) k,j-1 ) -w (t) 2 ≤ 1 + 1 τ -1 w (t) k,j-1 -w (t) 2 + τ γ 2 ∇ Fk (w (t) k,j-1 ) 2 .
The squared triangle inequality (cf. ( 26)) together with the smoothness of the local losses gives:

w (t) k,j -w (t) 2 ≤ 1 + 1 τ -1 w (t) k,j-1 -w (t) 2 + 2τ γ 2 ∇ Fk (w (t) k,j-1 ) -∇ Fk (w (t) ) 2 + ∇ Fk (w (t) ) 2 ≤ 1 + 1 τ -1 w (t) k,j-1 -w (t) 2 + 2τ γ 2 (L + λ) 2 w (t) k,j-1 -w (t) 2 + 2τ γ 2 ∇ Fk (w (t) ) 2 .
Hence, for γ ≤ 1 4τ (L+λ) , we get:

w (t) k,j -w (t) 2 ≤ 1 + 2 τ -1 w (t) k,j-1 -w (t) 2 + 2τ γ 2 ∇ Fk (w (t) ) 2 .
Unrolling this recursion yields for any j ≤ τ -1

w (t) k,j -w (t) 2 ≤ j-1 i=0 1 + 2 τ -1 i 2τ γ 2 ∇ Fk (w (t) ) 2 ≤ τ -1 2 1 + 2 τ -1 j 2τ γ 2 ∇ Fk (w (t) ) 2 ≤ τ -1 2 1 + 2 τ -1 τ -1 2τ γ 2 ∇ Fk (w (t) ) 2 ≤ τ (τ -1)γ 2 e 2 ∇ Fk (w (t) ) 2 ,
where we use (1 + 1/x) x ≤ e for any x > 0. If λ = 0 we have that ∇ Fk (w (t) )

2 = ∇F k (w (t) ) 2 ≤ G 2 since F k is G-Lipschitz;
this gives us the final bound in the statement. When λ = 0, this does not hold. In this case, we apply Lemma 11 to get

d (t) ≤ τ 2 (τ -1)γ 2 e 2 E S∼Um k∈S π (t) k ∇ Fk (w (t) ) 2 F (t) ≤ τ 2 (τ -1)γ 2 e 2 4 + 8 θm G 2 + ∇F ν θ (w (t) ) 2 .
This gives the first bound. The second bound follows from the first by smoothness (cf. ( 29)).

Bound on the Norm of Each Update. We bound the expected squared norm of each update w (t+1)w (t) , which has the closed form expression:

w (t+1) -w (t) = -γ k∈S π (t) k τ -1 j=0 ∇ Fk (w (t)
k,j ) .

Proposition 13. We have the bounds,

γ 2 E    k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ) 2 F t    ≤ 2γ 2 τ (L + λ) 2 d (t) + 16τ 2 γ 2 G 2 θm + 2τ 2 γ 2 ∇F ν θ (w (t) ) 2 ≤ 2γ 2 τ (L + λ) 2 d (t) + 16τ 2 γ 2 G 2 θm + 4τ 2 γ 2 L F ν θ (w (t) ) -F ν θ (w ) ,
where d (t) is the client drift term defined in [START_REF] Dieuleveut | Communication Trade-offs for Local-SGD with Large Step Size[END_REF].

Proof. Using the the squared triangle inequality (cf. Eq. ( 26)) together with the gradient formula [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], we get:

k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ) 2 ≤ 2 k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ) -∇ Fk (w (t) ) 2 + 2 k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) ) 2 ≤ 2τ k∈S π (t) k τ -1 j=0 ∇ Fk (w (t) k,j ) -∇ Fk (w (t) ) 2 + 2τ 2 ∇F ν θ,S (w (t) ) 2 .
For the first term, we invoke (L + λ)-smoothness of Fk and take an expectation to get 2τ (L + λ) 2 d (t) . For the second term, we use centering (cf. Eq. ( 27)) followed by the variance bound of Lemma 9 to get:

E t ∇F ν θ,S (w (t) ) 2 = E t   k∈S π (t) k ∇ Fk (w (t) ) -∇F ν θ (w (t) ) 2   + ∇F ν θ (w (t) ) 2 ≤ 8G 2 θm + ∇F ν θ (w (t) ) 2 .
This gives the first bound. The second bound follows from the first by smoothness (cf. Eq. ( 29)).

A.4 Useful Inequalities and Technical Results

We recall a few standard inequalities:

• Squared Triangle inequality: For any x, y ∈ R d and α > 0 we have:

x + y 2 ≤ (1 + α) x 2 + 1 + 1 α y 2 . (26)
• Centering the second moment: For any R d -valued random vector X such that E X 2 < ∞,

E X 2 = E X -E [X] 2 + E [X] 2 (27)
• Strong convexity: Let F : R d → R be µ-strongly convex. Then for any x, y ∈ R d , we have:

∇F (x), x -y ≥ F (x) -F (y) + µ 2 x -y 2 (28)
• Smoothness: Let F : R d → R be L-smooth and let F be the minimum value of F (assuming it exists). Then for any x ∈ R d , we have:

∇F (x) 2 ≤ 2L (F (x) -F ) (29)
Lemma 14. Consider the map ϕ : (0, Γ] → R + given by

ϕ(γ) = A exp(-γT ) + Bγ + Cγ 2 ,
where Γ, A, B, C > 0 are given. If T > 1/Γ, then, we have,

ϕ(γ ) ≤ A exp(-ΓT ) + B T + B T log 1 ∨ AT B + C T 2 + C T 2 log 2 1 ∨ AT 2 C ,
where γ is given by

γ = min Γ, 1 T log 1 ∨ AT B , 1 T log 1 ∨ AT 2 C . Proof. Define γ 1 = T -1 log(1 ∨ AT /B) and γ 2 = T -1 log(1 ∨ AT 2 /C). If γ = Γ, we have that Γ ≤ γ 1 and Γ ≤ γ 2 so that ϕ(γ ) = A exp(-ΓT ) + BΓ + CΓ 2 ≤ A exp(-ΓT ) + Bγ 1 + Cγ 2 2 . Now suppose that γ = γ 1 so that γ 1 ≤ γ 2 . Then, we have, ϕ(γ ) = A exp(-γ 1 T ) + Bγ 1 + Cγ 2 1 ≤ B T + B T log(1 ∨ AT /B) + Cγ 2 2 .
The third case is identical to the second.

The proof of the next lemma is elementary and is omitted.

Lemma 15. Consider the map ϕ : (0, Γ] → R + given by

ϕ(γ) = A γT + Bγ + Cγ 2 ,
where Γ, A, B, C > 0 are given. Then, we have,

ϕ(γ ) ≤ A ΓT + 2 AB T 1/2 + 2 AC T 2/3
, where γ is given by

γ = min Γ, A BT , C 1/3 A T 1/3
.

B Privacy Analysis B.1 Preliminaries

The discrete Gaussian mechanism was introduced in [START_REF] Canonne | The Discrete Gaussian for Differential Privacy[END_REF] as an extension of the Gaussian mechanism to integer data. A random variable ξ is said to satisfy the discrete Gaussian distribution with mean µ and variance proxy σ 2 if

P(ξ = i) = C exp - (i -µ) 2 2σ 2 for all i ∈ Z ,
where C is an appropriate normalizing constant. We denote it by N Z (µ, σ 2 ). We need the following property of the discrete Gaussian.

Property 16. Let ξ be distributed according to N Z (µ, σ 2 ). Then, E[ξ] = µ. Furthermore, if µ = 0, then ξ is sub-Gaussian with variance proxy σ 2 , i.e., E[exp(λξ)] ≤ exp(λ 2 σ 2 /2) for all λ > 0.

B.2 Proof of Privacy and Utility of Quantile Computation

Proof of Theorem 5. We start by defining and controlling the probabilities of some events. Throughout, let δ > 0 be fixed. Define the event

E mod = N k=1 n j=1 - M -2 2N ≤ γx k,j + ξ k,j ≤ M -2 2N . (30)
Note that under E mod , no modular wraparound occurs in the algorithm, i.e., xk = γx k + ξ k and ĥ

= N k=1 xk γ = N k=1 x k + ξ k γ .
We assume that E mod holds throughout.

Privacy Analysis. We start by establishing the sensitivity of the sum query over x k 's as 1. Define the input space X to be the canonical basis vectors in R n , i.e., the set of all vectors in {0, 1} n with only one 1, and let X * = ∪ ∞ N =1 denote the set of all sequences of elements of X . We consider the rescaled sum query A((x 1 , • • • , x N )) = N k=1 γx N . The L 2 sensitivity S(A) of this query A is supremum over all X ∈ X * and X which is obtained by concatenating x to X:

S(A) = sup X,X A(X) -A(X ) 2 = sup x ∈X γ x 2 = γ .
We invoke the privacy bound of sums of discrete Gaussians (Lemma 19) to claim that an algorithm A returning A(x) + N k=1 ξ k satisfies (1/2)ε 2 -concentrated DP where ε is as in the theorem statement. The fact that the quantile and all further functions of it remains private follows from the post-processing property of DP (also known as the data-processing inequality).

Utility Analysis. Define N = n j=1 ĥj , as the analogue to N = n j=1 h j . Below, we use shorthand ρ = 1θ. We bound the quantile error as

∆ θ ĥ, h = R θ h, j * θ ( ĥ) = 1 N j * θ ( ĥ) j=1 h j -ρ ≤ 1 N j * θ ( ĥ) j=1 h j -ĥj + 1 N j * θ ( ĥ) j=1 ĥj -N ρ + ρ n N -N ≤ max j ∈[n] 1 γN j j=1 N k=1 ξ k,j + 1 + | N -N | N R * θ ( ĥ) + ρ N N -N .
Let us define an event E sum under which the first term and last terms are bounded:

E sum =    max j∈[n] j j =1 N k=1 ξ k,j ≤ 2σ 2 N n log(4/δ)    . (31)
Under E sum , we also have

|N -N | = 1 γ n j=1 N k=1 ξ k,j ≤ 2σ 2 N n γ log 4 δ .
Plugging this back into ∆ ρ ( ĥ, h) gives us the desired bound, provided E sum holds.

Bounding the Failure Probability. The algorithm fails when at least one of E mod or E sum fail to hold. We have from Claim 17 that P(E mod ) ≥ 1δ/2 and from Claim 18 that P(E sum ) ≥ 1δ/2. With a union bound, we get that P(E sum ∩ E prod ) ≥ 1δ, i.e., the algorithm succeeds with probability at least 1δ.

We state and prove bounds on probabilities of the events E mod , E sum defined above.

Claim 17. If M ≥ 2 + 2γN + 2N 2σ 2 log(4N n/δ), then P(E mod ) ≥ 1 -δ/2.
Proof. Each discrete Gaussian random variable ξ k,j is centered and sub-Gaussian with variance proxy σ 2 (cf. Property 16). A Cramér-Chernoff bound (cf. Lemma 20) gives us the exponential tail bound

P |ξ k,j | > 2σ 2 log(4N n/δ) ≤ δ 2N n .
Using a union bound for k ∈ [N ], j ∈ [n] and x k,j ∈ {0, 1} completes the proof.

Claim 18. We have that P(E sum ) ≥ 1δ/2.

Proof. Each discrete Gaussian random variable ξ k,j is centered and sub-Gaussian with variance proxy σ 2 , i.e., E[ξ k,j ] = 0 and E[exp(λξ k,j )] ≤ exp(λ 2 σ 2 /2) for all λ ∈ R (cf. Property 16). Therefore, ζ j := N k=1 ξ k,j is centered and sub-Gaussian with variance proxy nσ 2 , since E[ζ j ] = 0, and

E[exp(λζ j )] = N k=1 E[exp(λξ k,j )] ≤ exp(λ 2 σ 2 N/2)
by independence. We get a bound on the partial sums from Lemma 21; this involves constructing a martingale ( j j =1 ζ j ) n j=1 and applying the maximal inequality. The bound we get is

P   max j∈[n] j j =1 ζ j > t   ≤ exp - t 2 2σ 2 N n .
Plugging in t = 2σ 2 N n log(2/δ) completes the proof.

B.3 Useful Results

The distributed discrete Gaussian mechanism gets privacy guarantees by adding a sum of discrete Gaussian random variables. We give a bound in its privacy. The following lemma is due to [START_REF] Kairouz | The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation[END_REF].

Lemma 19 (Privacy of Sum of Discrete Gaussians). Fix σ ≥ 1/2. Let M be a deterministic algorithm with 2sensitivity S. Define a randomized algorithm A, which when given an input x, samples ξ

1 , • • • , ξ n ∼ N Z (0, σ 2 I d ) and returns A(x) + n i=1 ξ i . Then, A satisfies ε 2 /2-concentrated DP with ε = min S nσ 2 + ψd 2 , S √ nσ + ψ √ d ,
where ψ = 10

n-1 k=1 exp -2π 2 σ 2 k/(k + 1) ≤ 10(n -1) exp(-2π 2 σ 2 ).

• ConvNet: We also consider a convolutional neural network with two convolutional layers with max-pooling and one fully connected layer (F.C) of which outputs a vector in R 62 . The outputs of the ConvNet are scores with respect to each class. They are also used with a softmax operation to compute probabilities.

The loss used to train both models is the multinomial logistic loss L(p, y) =log p y where p denotes the vector of probabilities computed by the model and p y denotes its y th component. In the convex case we add a quadratic regularization term of the form (λ/2) w 2 2 .

Sent140 for Sentiment Analysis.

Dataset. Sent140 [START_REF] Go | Twitter Sentiment Classification using Distant Supervision[END_REF] is a text dataset of 1,600,498 tweets produced by 660,120 Twitter accounts. Each tweet is represented by a character string with emojis redacted. Each tweet is labeled with a binary sentiment reaction (i.e., positive or negative), which is inferred based on the emojis in the original tweet.

Train and Test Devices. Each client represents a twitter account and contains only tweets published by this account.

From this set of clients we discarded all clients containing less that 50 tweets, and split the 877 remaining clients rest of clients into a train set and a test set of sizes 438 and 439 respectively. This split was held fixed for all experiments. Each word in the tweet is encoded by its 50-dimensional GloVe embedding [START_REF] Pennington | GloVe: Global Vectors for Word Representation[END_REF].

Model. We consider the following models.

• Linear Model: We consider a l 2 -regularized linear logistic regression model where the parameter vector w is of dimension 50. In this case, each F k is convex. We summarize each tweet by the average of the GloVe embeddings of the words of the tweet.

• RNN: The nonconvex model is a Long Short Term Memory (LSTM) model [START_REF] Hochreiter | Long Short-Term Memory[END_REF] built on the GloVe embeddings of the words of the tweet. The hidden dimension of the LSTM is same as the embedding dimension, i.e., 50. We refer to it as "RNN".

The loss function is the binary logistic loss.

C.2 Algorithms and Hyperparameters

Algorithm and Baselines.

The proposed ∆-FL is run for three values of θ ∈ {0.8, 0.5, 0.1}. We compare it to the following baselines:

• FedAvg [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]: It is the de facto standard for the vanilla federated learning objective.

• FedAvg, θ: We also consider FedAvg with a random client subselection step: local updates are run on a fraction of the initial number of clients randomly selected per round. For each dataset, we try three values of, corresponding to the average number of clients selected by ∆-FL for the three values of θ used. In the main paper, we report as FedAvg-Sub the performance of FedAvg, θ with θ ∈ {0.8, 0.5, 0.1} which gives the best performance on ∆-FL (i.e., lowest 90 th percentile of test misclassification error). Here we report numbers for all values of θ considered.

• FedProx [START_REF] Li | Federated Optimization in Heterogeneous Networks[END_REF]: It augments FedAvg with a proximal term but still minimizes the vanilla federated learning objective.

• q-FFL [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF]: It raises the per-client losses to the power (1 + q), where q ≥ 0 is a parameter, in order to focus on clients with higher loss. We run q-FFL for values of q in {10 j , j ∈ {-3, • • • , 1}}.

• AFL [START_REF] Mohri | Agnostic Federated Learning[END_REF]: It aims to minimize the worst per-client loss. We implement it as an asymptotic version of q-FFL, using a large value of q, as this was found to yield better convergence with comparable performance [START_REF] Li | Fair Resource Allocation in Federated Learning[END_REF]. In the experiments we take q = 10.0.

The experiments are conducted on the datasets described in Appendix C.1.

Hyperparameters. Hardware. We run each experiment as a simulation as a single process. The linear models were trained on m5.8xlarge AWS instances, each with an Intel Xeon Platinum 8000 series processor with 128 GB of memory running at most 3.1 GHz. The neural network experiments were trained on workstation with an Intel i9 processor with 128 GB of memory at 1.2 GHz, and two Nvidia Titan Xp GPUs. The Sent140 RNN experiments were run on a CPU while the other neural network experiments were run using GPUs.

Software Packages. Our implementation is based on NumPy using the Python language. In the neural network experiments, we use PyTorch to implement the LocalUpdate procedure, i.e., the model itself and the automatic differentiation routines provided by PyTorch to make SGD updates.

Randomness. Since several sampling routines appear in the procedures such as the selection of clients or the local stochastic gradient, we carry our experiments with five different seeds and plot the average metric value over these seeds. Each simulation is run on a single process. Where appropriate, we report one standard deviation from the mean.

Figure 1 :

 1 Figure 1: Schematic summary of the ∆-FL framework. Left: The server maintains multiple models w θ j , one for each level of conformity θj. Middle: During training, selected clients participate in training each model w θ j . Individual updates are securely aggregated to update the server model. Right: Each test user is allowed to select their level of conformity θ, and are served the corresponding model w θ .

Figure 2 :

 2 Figure 2: Left: The set of mixture weights π = (π1, π2, π3) of conformity conf(pπ) ≥ θ is given by the intersection of the box constraints 0 ≤ π k ≤ (3θ) -1 for k = 1, 2, 3, with the simplex constraint π1 + π2 + π3 = 1. Right: (1-θ)-quantile Q θ (Z) and superquantile S θ (Z) of a continuous r.v. Z.

Figure 2 . 2 :

 22 (c) Local Updates (loop of line 7): Staring from w (t) k,0 = w (t) , each client k ∈ S makes τ local gradient or stochastic gradient descent steps with a learning rate γ. Algorithm 1 The ∆-FL Algorithm Input: Input: Initial iterate w (0) , number of communication rounds T , number of clients per round m, number of local updates τ , local step size γ 1: for t = 0, 1, • • • , T -1 do Sample m clients from [N ] without replacement in S 3:

k 12 :

 12 end for 13: return w T (d) Update Aggregation (line 11):

  ) defined on a sample S ⊂ [N ] of clients, and U m is the uniform distribution over subsets of [N ] of size m. Fortunately, the bias introduced by Algorithm 3 can be bounded as[START_REF] Levy | Large-Scale Methods for Distributionally Robust Optimization[END_REF] Prop. 1]

2 .

 2 A standard argument to handle the noise term B and telescoping the resulting inequality over t = 0, • • • , T -1 completes the proof. The full details are given in Appendix A.1.

  w) as the expectation of F ν θ,S over random subsets S ∼ U m . Putting these together and taking w = w := arg min F ν θ gives the inequality,

Figure 3 : 5 Figure 4 :

 354 Figure 3: Histogram of misclassification error on test clients for the EMNIST-ConvNet and Sent140-RNN.

Convergence Analysis 1 A. 1 14 C

 1114 Convergence Analysis: Non-convex Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 A.2 Convergence Analysis: Strongly Convex Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 A.3 Intermediate Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 A.4 Useful Inequalities and Technical Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 B Privacy Analysis 13 B.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 B.2 Proof of Privacy and Utility of Quantile Computation . . . . . . . . . . . . . . . . . . . . . . . . . . 13 B.3 Useful Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Numerical Experiments: Complete Results 15 C.1 Datasets and Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 C.2 Algorithms and Hyperparameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 C.3 Evaluation Strategy and Other Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 C.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

Property 10 .

 10 The following result is standard [2, Theorem 4.1, Lemma 4.2]. For every ν > 0, we have that F ν θ,S and F ν θ,S are L -smooth with L = L + λ + G 2 ν .

  Evaluation times. We evaluate the model during training process for once every l communication rounds. The value of l used was l = 50 for EMNIST linear model, l = 10 for EMNIST ConvNet, l = 20 for Sent140 linear model and l = 25 for Sent140 RNN.

  losses and accuracies across devices sizes for EMNIST (Linear Model) losses and accuracies across devices sizes for EMNIST(ConvNet Model)

Figure 7 :

 7 Figure 7: Scatter plot of (a) loss on training client vs. amount of local data, and (b) misclassification error on testing client vs. amount of local data for EMNIST.

  : (1) Communication Bottleneck: The repeated exchange of massive models between the server and clients over resourcelimited wireless networks makes communication an important bottleneck. Therefore, training algorithms should be able to trade-off more local computation for lower communication cost. (2) Statistical Heterogeneity: The training distribution q k and a specific test distribution p are likely to be different from each other. Therefore, a model which works well on average over all test clients might not work well on each individual test client.(3) Privacy: The data on each client is extremely privacy-sensitive. Federated learning is designed to protect data privacy since no user data is transferred to a data center. This privacy is enhanced by secure aggregation of model parameters, which refers to aggregating client updates such that no client update is directly revealed to any other client or the server. This is achieved by cryptographic protocols based on secure multiparty communication[START_REF] Bonawitz | Practical Secure Aggregation for Privacy-Preserving Machine Learning[END_REF].

Table 1 :

 1 Dataset description and statistics.

	Task	Dataset	#Classes Devices #Data per client
					Median Max
	Image Recognition EMNIST	62	1730	179	447
	Sentiment Analysis Sent140	2	877	69	549

Table 2 :

 2 90 th percentile of the distribution of misclassification error (in %) on the test devices. Each entry is the mean over five random seeds while the standard deviation is reported in the subscript. The boldfaced/highlighted entries denote the smallest value for each dataset-model pair.

		EMNIST	Sent140
		Linear	ConvNet	Linear	RNN
	FedAvg	49.660.67	28.461.07	46.830.54	49.673.95
	FedAvg-Sub	50.280.77	27.570.81	46.600.38	46.943.84
	FedProx	49.150.74	27.011.86	46.830.54	49.864.07
	q-FFL	49.900.58	28.020.80	46.390.40	48.664.68
	Tilted-ERM	48.590.62	25.461.49	46.690.49	46.543.27
	AFL	51.620.28	45.081.00	47.520.32	57.781.19
	∆-FL, θ = 0.8	49.100.24	26.231.15	46.440.38	46.464.39
	∆-FL, θ = 0.5	48.440.38	23.690.94	46.640.41	50.488.24
	∆-FL, θ = 0.1	50.340.95	25.462.77	51.391.07	86.4510.95

Table 3 :

 3 Mean of the distribution of misclassification error (in %) on the test devices. Each entry is the mean over five random seeds while the standard deviation is reported in the subscript. The boldfaced/highlighted entries denote the smallest value for each dataset-model pair.

		EMNIST	Sent140
		Linear	ConvNet	Linear	RNN
	FedAvg	34.380.38	16.640.50	34.750.31	30.160.44
	FedAvg-Sub	34.510.47	16.230.23	34.470.03	29.860.46
	FedProx	33.820.30	16.020.54	34.740.31	30.200.48
	q-FFL	34.340.33	16.590.30	34.480.06	29.960.56
	Tilted-ERM	34.020.30	15.680.38	34.700.31	30.040.25
	AFL	39.330.27	33.010.37	35.980.08	37.740.65
	∆-FL, θ = 0.8	34.490.26	16.090.40	34.410.22	30.310.33
	∆-FL, θ = 0.5	35.020.20	15.490.30	35.290.25	33.592.44
	∆-FL, θ = 0.1	38.330.48	16.371.03	37.790.89	51.9811.81

Table 4 :

 4 Metrics for the test misclassification error for EMNIST (Linear Model).

	Method	Mean	Standard Deviation 10 th Percentile	Median	90 th Percentile
	FedAvg FedAvg θ = 0.8 FedAvg θ = 0.5 FedAvg θ = 0.1 FedProx q-FFL (Best q = 1.0) Tilted-ERM (Best t = 1.0) 34.15 ± 0.25 34.38 ± 0.38 34.20 ± 0.45 34.51 ± 0.47 34.60 ± 0.46 33.82 ± 0.30 34.71 ± 0.27 AFL 39.32 ± 0.27 ∆-FL θ = 0.8 34.48 ± 0.26 ∆-FL θ = 0.5 35.01 ± 0.20 ∆-FL θ = 0.1 38.32 ± 0.48	18.39 ± 0.33 18.25 ± 0.22 18.21 ± 0.30 18.58 ± 0.31 18.25 ± 0.23 19.34 ± 0.30 10.78 ± 0.30 25.42 ± 0.27 19.16 ± 0.32 20.46 ± 0.34 23.86 ± 0.59	21.54 ± 0.35 21.37 ± 0.26 21.40 ± 0.36 21.71 ± 0.37 21.37 ± 0.35 22.33 ± 0.41 22.43 ± 0.29 28.64 ± 0.43 22.24 ± 0.32 23.64 ± 0.22 27.27 ± 0.64	32.61 ± 0.39 32.10 ± 0.34 32.36 ± 0.59 32.54 ± 0.37 31.75 ± 0.20 32.80 ± 0.23 32.36 ± 0.23 38.16 ± 0.34 32.85 ± 0.31 33.83 ± 0.34 37.52 ± 0.67	49.65 ± 0.67 49.92 ± 1.16 50.28 ± 0.77 50.33 ± 1.28 49.15 ± 0.74 49.90 ± 0.58 48.59 ± 0.62 51.62 ± 0.28 49.10 ± 0.24 48.44 ± 0.38 50.34 ± 0.95

Table 5 :

 5 Metrics for the test misclassification error for EMNIST (ConvNet Model).

	Method	Mean	Standard Deviation 10 th Percentile	Median	90 th Percentile
	FedAvg FedAvg θ = 0.8 FedAvg θ = 0.5 FedAvg θ = 0.1 FedProx q-FFL (Best q = 0.001) Tilted-ERM (Best t = 1.0) 15.69 ± 0.38 16.63 ± 0.50 15.95 ± 0.42 16.22 ± 0.23 15.97 ± 0.43 16.01 ± 0.54 16.58 ± 0.30 AFL 33.00 ± 0.37 ∆-FL θ = 0.8 16.08 ± 0.40 ∆-FL θ = 0.5 15.48 ± 0.30 ∆-FL θ = 0.1 16.37 ± 1.03	4.94 ± 0.14 5.25 ± 0.19 5.06 ± 0.17 5.40 ± 0.42 5.16 ± 0.32 5.05 ± 0.21 7.31 ± 0.68 20.38 ± 0.23 5.60 ± 0.14 6.13 ± 0.15 6.61 ± 0.42	6.43 ± 0.24 6.86 ± 0.38 6.47 ± 0.28 7.10 ± 0.64 6.68 ± 0.44 6.53 ± 0.20 7.26 ± 0.51 22.92 ± 0.23 7.31 ± 0.29 8.08 ± 0.16 8.28 ± 0.65	15.34 ± 0.37 14.84 ± 0.24 15.05 ± 0.25 14.76 ± 0.20 14.88 ± 0.29 15.40 ± 0.43 14.66 ± 0.16 31.58 ± 0.27 14.85 ± 0.48 14.73 ± 0.22 23.69 ± 0.94 28.46 ± 1.07 26.82 ± 1.28 27.56 ± 0.81 26.35 ± 2.08 27.01 ± 1.86 28.02 ± 0.80 25.46 ± 1.49 45.07 ± 1.00 26.23 ± 1.15 15.49 ± 1.03 25.45 ± 2.77
	number of datapoints on the client.

Table 6 :

 6 Metrics for the test misclassification error for Sent140 (Linear Model).

	Method	Mean	Standard Deviation 10 th Percentile	Median	90 th Percentile
	FedAvg FedAvg θ = 0.8 FedAvg θ = 0.5 FedAvg θ = 0.1 FedProx q-FFL (Best q = 1.0) Tilted-ERM (Best t = 1.0) 34.71 ± 0.31 34.74 ± 0.31 34.47 ± 0.03 34.46 ± 0.07 34.79 ± 0.32 34.74 ± 0.31 34.48 ± 0.06 AFL 35.97 ± 0.08 ∆-FL θ = 0.8 34.41 ± 0.22 ∆-FL θ = 0.5 35.28 ± 0.25 ∆-FL θ = 0.1 37.78 ± 0.89	12.16 ± 0.15 12.08 ± 0.16 12.11 ± 0.24 11.97 ± 0.37 12.16 ± 0.15 11.96 ± 0.14 12.00 ± 0.14 11.83 ± 0.09 12.17 ± 0.11 11.68 ± 0.40 12.86 ± 0.52	21.89 ± 0.24 21.69 ± 0.26 21.55 ± 0.51 34.48 ± 0.20 34.81 ± 0.38 34.62 ± 0.17 22.08 ± 0.75 34.93 ± 0.35 21.89 ± 0.24 34.82 ± 0.39 21.61 ± 0.24 34.57 ± 0.16 21.83 ± 0.34 34.91 ± 0.39 23.58 ± 0.28 36.09 ± 0.17 21.77 ± 0.34 34.64 ± 0.25 23.03 ± 0.38 35.55 ± 0.53 23.93 ± 0.99 37.80 ± 1.30	46.83 ± 0.54 46.59 ± 0.38 47.00 ± 0.40 46.69 ± 0.84 46.83 ± 0.54 46.38 ± 0.40 46.70 ± 0.50 47.51 ± 0.32 46.44 ± 0.38 46.64 ± 0.41 51.38 ± 1.07

Table 7 :

 7 Metrics for the test misclassification error for Sent140 (RNN Model).

	Method	Mean	Standard Deviation 10 th Percentile	Median	90 th Percentile

For simplicity, we consider full gradient steps on each client.

https://github.com/krishnap25/simplicial-fl

Acknowledgements

The authors would like to thank Zachary Garrett, Peter Kairouz, Jakub Konečný, Brendan McMahan, Sewoong Oh, Krzysztof Ostrowski, Keith Rush, and Lun Wang for fruitful discussions. We acknowledge support from NSF DMS 2023166, DMS 1839371, CCF 2019844, the CIFAR program "Learning in Machines and Brains", faculty research awards, and a JP Morgan PhD fellowship. This work has been partially supported by MIAI -Grenoble Alpes, (ANR-19-P3IA-0003).

A Convergence Analysis

Below, we restate and prove Theorem 3 as Theorem 6 in Appendix A.1 and Theorem 4 as Theorem 7 in Appendix A.2,

A.1 Convergence Analysis: Non-convex Case

We review some definitions of subdifferentials and weak convexity before we get to the main theorem.

Nonconvex Subdifferentials. We start by recalling the definition of subgradients for nonsmooth functions (in finite dimension), following the terminology of [START_REF] Rockafellar | Variational analysis[END_REF]. Consider a function ψ : R d → R ∪ {+∞} and a point w such that ψ( w) < +∞. The regular (or Fréchet) subdifferential of ψ at w is defined by ∂ψ( w) = s ∈ R d : ψ(w) ≥ ψ( w) + s, ww) + o( ww ) .

The regular subdifferential thus corresponds to the set of gradients of smooth functions that are below ψ and coincide with it at w. These notions generalize (sub)gradients of both smooth functions and convex functions: it reduces to the singleton {∇ψ( w)} when ψ is smooth and to the standard subdifferential from convex analysis when ψ is convex.

Weak Convexity. We recall the notion of weak convexity, which is one way of characterizing functions which are "close" to convex. A function ψ : R d → R is said to be η-weakly convex if the function w → ψ(w) + (η/2) w 2 is convex [START_REF] Nurminskii | The quasigradient method for the solving of the nonlinear programming problems[END_REF]. The class of weakly convex functions includes all convex functions (with η = 0) and all L-smooth functions (with η = L).

Weak convexity also admits an equivalent first-order condition: for any w, z ∈ R d and s ∈ ∂ψ(w), we have,

Weak convexity will feature in our developments in two ways: • In our case, both F θ as well as F θ,S are L-weakly convex, since each can be written as the maximum of a family of L-smooth functions [START_REF] Drusvyatskiy | Efficiency of minimizing compositions of convex functions and smooth maps[END_REF]Lemma 4.2]. • The prox operator for weakly convex function is well-defined. Let ψ be a η-weakly convex function. Its proximal or prox operator, with parameter µ > 0 is defined as

It is well-defined (i.e., the argmin exists and is unique) for µ > η, since the function inside the argmin is (µη)strongly convex. In nonsmooth and nonconvex optimization of weakly convex functions, we are interested in finding stationary points w.r.t. the regular subdifferential, i.e., points w satisfying 0 ∈ ∂ψ(w). A natural measure of near-stationarity is, therefore,

Moreau Envelope. Given a parameter µ > 0, we define the Moreau envelope of F θ as

The Moreau envelope is well-defined since F θ is bounded from below by our assumptions. We will use two standard properties of the Moreau envelope:

• Since F θ,S is L-weakly convex, we have that its Moreau envelope

• The stationary points of Φ µ θ and F θ coincide and inf Φ

Next, we record two standard concentration results.

Lemma 20 (Cramér-Chernoff). Let ξ be a real-valued and centered sub-Gaussian random variable with variance proxy σ 2 , i.e., E[ξ] = 0 and E[exp(λξ)] ≤ exp(λ 2 σ 2 /2) for all λ > 0. Then, we have for any t > 0,

Lemma 21 (Maximal Inequality). Let ξ 1 , ξ 2 , • • • be i.i.d. centered sub-Gaussian random variables with variance proxy σ 2 , i.e., E[ξ j ] = 0 and E[exp(λξ j )] ≤ exp(λ 2 σ 2 /2) for all λ ∈ R and j = 1, 2, • • • . Then, it holds for any t > 0 and integer n ≥ 1 that

C Numerical Experiments: Complete Results

We conduct our experiments on two datasets from computer vision and natural language processing. These datasets contain a natural, non-iid split of data which is reflective of data heterogeneity encountered in federated learning. In this section, we describe in details the experimental setup and the results. Here is its outline:

• Appendix C.1 describes the datasets and tasks.

• Appendix C.2 presents the algorithm and the hyperparameters used.

• Appendix C.3 details the evaluation methodology.

• Appendix C.4 gives the experimental comparison of ∆-FL to baselines.

Since each client has a finite number of datapoints in the examples below, we let its probability distribution π k to be the empirical distribution over the available examples, and the weight α k to be proportional to the number of datapoints available on the client.

C.1 Datasets and Tasks

We use the two following datasets, described in detail below. The data was preprocessed using LEAF [START_REF] Caldas | LEAF: A benchmark for federated settings[END_REF].

EMNIST for handwritten-letter recognition.

Dataset. EMNIST [START_REF] Cohen | EMNIST: an extension of MNIST to handwritten letters[END_REF] is a character recognition dataset. This dataset contains images of handwritten digits or letters, labeled with their identification (a-z,A-Z, 0-9). The images are grey-scaled pictures of 28 × 28 = 784 pixels.

Train and Test Devices. Each image is also annotated with the "writer" of the image, i.e., the human subject who hand-wrote the digit/letter during the data collection process. Each client corresponds to one writer. From this set of clients, we discard all clients containing less than 100 images. The remaining clients were partitioned into two groups -1730 training and 1730 testing clients. For each experiment we subsampled 865 training and 865 testing clients for computational tractability, where the sampled clients vary based on the random seed of each experiment.

Model. We consider the following models for this task.

• Linear Model: We use a linear softmax regression model. In this case each F k is convex. We train parameters w ∈ R 62×784 . Given an input image x ∈ R 784 , the score of each class c ∈ [START_REF] Pennington | GloVe: Global Vectors for Word Representation[END_REF] is the dot product w c , x . The probability p c assigned to each class is then computed as a softmax: p c = exp w c , x / c exp w c , x . The prediction for a given image is then the class with the highest probability.

Rounds. We measure the progress of each algorithm by the number of calls to secure aggregation routine for weight vectors, i.e., the number of communication rounds.

For the experiments, we choose the number of communication rounds depending on the convergence of the optimization for FedAvg. For the EMNIST dataset, we run the algorithm for 3000 communication rounds with the linear model and 1000 for the ConvNet. For the Sent140 dataset, we run the 1000 communication rounds for the linear model and 600 for the RNN.

Devices per Round. We choose the same number of clients per round for each method, with the exception of F edAvg, θ. All clients are assumed to be available and selections are made uniformly at random. In particular, we select 100 clients per round for all experiments with the exception of Sent140 RNN for which we used 50 clients per round.

Local Updates and Minibatch Size. Each selected client locally runs 1 epoch of mini-batch stochastic gradient descent locally. We used the default mini-batch of 10 for all experiments [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF], except for 16 for EMNIST ConvNet. This is because the latter experiments were run using on a GPU, as we describe in the section on the hardware.

Learning rate scheme. We now describe the learning rate γ t used during LocalUpdate. For the linear model we used a constant fixed learning rate γ t ≡ γ 0 , while for the neural network models, we using a step decay scheme of the learning rate γ t = γ 0 c -t/t0 for some where γ 0 and 0 < c ≤ 1 are tuned. We tuned the learning rates only for the baseline FedAvg and used the same learning rate for the other baselines and ∆-FL at all values of θ.

For the neural network models, we fixed t 0 so that the learning rate was decayed once or twice during the fixed time horizon T . In particular, we used t 0 = 400 for EMNIST ConvNet (where T = 1000) and t 0 = 200 for Sent140 RNN (where T = 600). We tuned c from the set {2 -3 , 2 -2 , 2 -1 , 1}, while the choice of the range of γ 0 depended on the dataset-model pair. The tuning criterion we used was the mean of the loss distribution over the training clients (with client k weighted by α k ) at the end of the time horizon. That is, we chose the γ 0 , c which gave the best terminal training loss.

Tuning of the regularization parameter. The regularization parameter λ for linear models was tuned with cross validation from the set {10 -k : k ∈ {3, • • • , 8}}. This was performed as described below.

For each dataset, we held out half the training clients as validation clients. Then, for different values of the regularization parameter, we trained a model with the (smaller subset of) training clients and evaluate its performance on the validation clients. We selected the value of the regularization parameter as the one which gave the smallest 90 th percentile of the misclassification error on the validation clients.

Baselines Parameters. We tune the proximal parameter of FedProx with cross validation. The procedure we followed is identical to the procedure we described above for the regularization parameter λ. The set of parameters tested is {10 -j , j ∈ {0, . . . , 3}}. We did not attempt to tune the parameter q of q-FFL and report the performance of all values of q which we tried.

Hyperparameters of ∆-FL. We optimize ∆-FL via Algorithm 3 with a fixed number of local steps, corresponding to one epoch. For simplicity, we calculate the quantile exactly, assuming client losses are available to the server.

C.3 Evaluation Strategy and Other Details

Evaluation metrics. We record the loss of each training client and the misclassification error of each testing client, as measured on its local data.

The evaluation metrics noted in Section C.4 are the following : the weighted mean of the loss distribution over the training clients, the (unweighted) mean misclassification error over the testing clients, the weighted τ -percentile of the loss over the training client and the (unweighted) τ -percentile of the misclassification error over the testing clients for values of τ among {20, 50, 60, 80, 90, 95}. We also present the 90 th and 95 th superquantile of the test misclassification error (i.e., average misclassification error of the worst 10% and 5% of the clients respectively), as well as the average test misclassification error of the best 10% clients. The weight α k used for training client k was set proportional to the

C.4 Experimental Results

We now present the experimental results of the paper.

• We present different metrics on the distribution of test misclassification error over the clients, comparing ∆-FL to baselines.

• We study the convergence of Algorithm 3 for ∆-FL over the course of the optimization, and compare it with FedAvg.

• We plot the histograms of the distribution of losses over train clients as well as the test misclassification errors over test clients at the end of the training process.

• We present in the form of scatter plots the training loss and test misclassification error across clients achieved at the end of training, versus the number of local data points on the client.

• We present the number of clients having a loss greater than the quantile at each communication round for ∆-FL. This gives the effective number of clients selected in each round, cf. Proposition 2 and Remark 1.

Comparison to Baselines. We now present a detailed comparison of various statistics of the test misclassification error distribution for different methods in Table 4-For each column the smallest mean over five random runs is highlighted in Histogram of test misclassification error over devices for EMNIST bold. Further, if no other method is within one standard deviation of this method, the entire entry (i.e., mean ± std) is highlighted in bold.

Histograms of Loss and Test Misc. Error over Devices. Here, we plot the histograms of the loss distribution over training clients and the misclassification error distribution over testing clients. We report the losses and errors obtained at the end of the training process. Each metric is averaged per client over 5 runs of the random seed. Figure 5 shows the histograms for EMNIST, while Figure 6 shows the histograms for Sent140 dataset. for Sent140. We note that ∆-FL tends to exhibit thinner upper tails at at multiple values of θ and a lower variance of the distribution in most of the cases. This is also confirmed by the figures in table 4 to 7. This shows the benefit of using ∆-FL over vanilla FedAvg.

Performance compared to local data size. Next, we plot the loss on training clients versus the amount of local data on the client and the misclassification error on the test clients versus the amount of local data on the client. See Figure 7 for EMNIST and Figure 8 for Sent140.

Observe firstly that improvement over the worst cases is achieved regardless of the local data size of the clients. Indeed, the client re-weighting step operates a sorting of the loss of the clients which does not prevent small clients from being selected. In contrary, FedAvg, by averaging with respect to the weights of the clients is likely to put more the accent on the clients with larger local data size. Secondly, ∆-FL appears to reduce the variance of of the loss on the train clients. Lastly, note that amongst test clients with a small number of data points (e.g., < 200 for EMNIST or < 100 for Sent140), ∆-FL reduces the variance of the misclassification error. Both effects are more pronounced on the neural network models.