Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing
Authors: Sai Praneeth Karimireddy
Lie He
Martin Jaggi
Venue: ICLR 2022 Spotlight (2022)
Keywords: Federated learning
Distributed learning
Byzantine robust optimization
Heterogeneity (Non-IID)

Abstract: In Byzantine robust distributed or federated learning, a central server wants to train a machine learning model over data distributed across multiple workers. However, a fraction of these workers may deviate from the prescribed algorithm and send arbitrary messages. While this problem has received significant attention recently, most current defenses assume that the workers have identical data. For realistic cases when the data across workers are heterogeneous (non-iid), we design new attacks which circumvent current defenses, leading to significant loss of performance. We then propose a simple bucketing scheme that adapts existing robust algorithms to heterogeneous datasets at a negligible computational cost. We also theoretically and experimentally validate our approach, showing that combining bucketing with existing robust algorithms is effective against challenging attacks. Our work is the first to establish guaranteed convergence for the non-iid Byzantine robust problem under realistic assumptions.


Published as a conference paper at ICLR 2022
BYZANTINE-ROBUST LEARNING NEOUS DATASETS VIA BUCKETING
ON HETEROGE-
Sai Praneeth Karimireddy sai, karimiredddyeepf..ch
Lie He 1ie www.he@epp..hcc
Martin Jaggi martin. jaggiepff................. ch
ABSTRACT
In Byzantine robust distributed or federated learning, central server wants to train a machine learning model over data distributed across multiple workers. However, a fraction of these workers may deviate from the prescribed algorithm and send arbitrary messages. While this problem has received significant attention recently, most current defenses assume that the workers have identical data. For realistic cases when the data across workers are heterogeneous (non-iid), we design new attacks which circumvent current defenses, leading to significant loss of perfor- mance. We then propose simple bucketing scheme that adapts existing robust algorithms to heterogeneous datasets at negligible computational cost. We also theoretically and experimentally validate our approach, showing that combining bucketing with existing robust algorithms is effective against challenging attacks. Our work is the first to establish guaranteed convergence for the non-iid Byzantine robust problem under realistic assumptions.
INTRODUCTION
Distributed or federated machine learning, where the data is distributed across multiple workers, has become an increasingly important learning paradigm both due to growing sizes of datasets, as well data privacy concerns. In such setting, the workers collaborate train single model without directly transmitting their training data (McMahan et al., 2016; Bonawitz et al., 2019; Kairouz et al., 2019). However, by decentralizing the training across vast number of workers we potentially open ourselves to new security threats. Due to the presence of agents in the network which are actively malicious, or simply due to system and network failures, some workers may disobey the protocols and send arbitrary messages; such workers are also known Byzantine workers (Lamport et al., 2019). Byzantine robust optimization algorithms attempt to combine the updates received from the workers using robust aggregation rules and ensure that the training is not impacted by the presence of a small number malicious workers.
While this problem has received significant recent attention due to its importance, (Blanchard et al., 2017; Yin et al., 2018; Alistarh al., 2018; Karimireddy et al., 2021), I),, most of the current approaches assume that the data present each different worker has identical distribution. This assumption is very unrealistic in practice and heterogeneity is inherent distributed and federated learning (Kairouz et al., 2019). In this work, show that existing Byzantine aggregation rules catastrophically fail with very simple attacks (or sometimes even with no attacks) in realistic settings. We carefully examine the causes these failures, and propose a simple solution which provably solves the Byzantine resilient optimization problem under heterogeneous workers.
Concretely, our contributions in this work are summarized below
We show that when the data across workers is heterogeneous, existing aggregation rules fail to converge, even when no Byzantine adversaries are present. We also propose simple new attack. mimic, which explicitly takes advantage of data heterogeneity and circumvents median-based defenses. Together, these highlight the fragility of existing methods in real world settings.
We then propose a simple fix new bucketing step which can be used before any existing aggregation rule. We introduce a formal notion of robust aggregator (ARAgG) and prove that existing methods like KRUM, coordinate-wiss median (CM), and geometric median aka
"qqual contribution.

---

Published as a conference paper at ICLR 2022
robust federated averaging (RFA) though insufficient their own become provably robust aggregators when augmented with our bucketing.
We combine our notion of robust aggregator (ARAGG) with worker momentum to obtain optimal rates for Byzantine robust optimization with matching lower bounds. Unfortunately, our lower bounds imply that convergence an exact optimum may not be possible due to heterogeneity. We then circumvent this lower bound and show that when heterogeneity is mild (or when the model is overparameterized), we can in fact converge to exact optimum. This is the first result establishing convergence to the optimum for heterogeneous Byzantine robust optimization.
Finally, we evaluate the effect of the proposed techniques (bucketing and worker momentum) against known and new attacks showcasing drastic improvement on realistic heterogeneously distributed datasets.
Setup and notations. S nI.. Our objective is to minimize
Suppose that of the total n workers, the set of good workers is denoted by
f(x) = [e| Eieotf(aa) = Ex,
(1)
where ft is the loss function on worker i defined over its own (heterogeneous) data distribution E The (stochastic) gradient computed by a good worker E G over minibatch & is given as g E:) := V VFi(;; Et). The noise in every stochastic gradient is independent, unbiased with Le. (3, E:) f((x), and has bounded variance
Es) (=) S o². Further, we assume that the
data heterogeneity across the workers can be bounded as
E , < when there is no ambiguity.
/((=))] <
Vo.
We write of or simply 9: instead of g, (x",
Byzantine attack model. The set of Byzantine workers B C [r]] is fixed over time, with the remaining workers G being good, i.e. [n] = B w g. We write 5 for the fraction of Byzantine workers, [B] =: 9 5n. The Byzantine workers can deviate arbitrarily from our protocol, sending any update to the server. Further, they can collude and may even know the states of all other workers.
Our modeling assumes that the practitioner picks value of ā E 0.5). This 8 reflects the level of robustness required. A choice of a large 5 (say near 0.5) would mean that the system is very robust and can tolerate a large fraction of attackers, but the algorithm becomes much more conservative and slow, On the flip side, if the practitioner knows that the the number of Byzantine agents are going to be few, they can pick a small ó (say 0.05-0.1) ensuring some robustness with almost no impact on convergence. The choice of 5 can also be formulated as how expensive do we want to make an attack? To carry out a succesful attack the attacker would need control fraction of all workers. We recommend implementations claiming robustness be transparent about their choice of ö.
2 RELATED WORK
IID defenses. There has been a significant amount of recent work on the case when all workers have identical data distributions. Blanchard et al. (2017) initiated the study of Byzantine robust learning and proposed bistance-based aggregation approach KRUM and extended to (El Mhamdi et al., 2018; Damaskinos et al., 2019). Yin et al. (2018) propose to use and analyze the coordinate-wist median (CM), and Pillutla et al. (2019) use approximate geometric median. Bernstein et al. (2018) propose to use the signs of gradients and then aggregate them by majority vote, however, Karimireddy et al. (2019) show that it may fail to converge. Most recently, Alistarh et al. (2018); Allen-Zhu al. (202 EI Mhandi et al. (2021b); Karimireddy et al. (2021) showcase how to use past gradients to more accurately filter iid Byzantine workers and specifically time-coupled attacks. In particular, our work builds on top of (Karimireddy et al., 2021) and non-trivially extends to the non-iid setting.
IDD vs. NOn-IID attacks. For the iid setting, the vate-of-the-ar attacks are time-coupled at- tacks (Baruch et al., 2019; Xie et al., 2020). These attacks introduce small but consistent bias at every step which is hard to detect in any particular round, but accumulates over time and eventually leads to divergence, breaking most prior robust methods. Our work focuses developing attacks (and defenses) which specifically take advantages of the non-iid setting. The non-iid setting also enables targeted backdoor attacks which are designed to take advantage of -tiled data (Bagdasaryan et al., 2020; Bhagoji et al., 2018). However, this is a challenging and open problem (Sun et al., 2019; Wang al., 2020). Our focus is on the overall accuracy of the trained model, not any subproblem.
2

---

Published as a conference paper at ICLR 2022
Non-IID defenses. The non-iid defenses are relatively under-examined. Ghosh et al. (2019); Sattler et al. (2020) use an outlier-robust clustering method. When the server has the entire training dataset, the non-iid-ness is automatically addressed (Xic et al., 2019; Chen et al., 2018; Rajput et al., 2019). Typical examples are parallel training of neural networks on public cloud, or volunteer computing (Meeds et al., 2015; Miura & Harada, 2015). Note that Rajput et al. (2019) use hierarchical aggregation over "vote group" which is similar to the bucketing techniques but their results are limited to the iid setting. However, none of these methods are applicable to the standard federated learning. This is partially tackled in (Data & Diggavi, 2020; 2021) who analyze spectral methods for robust optimization. However, these methods require ((d²) time, making them infeasible for large scale optimization. Li et al. (2019) proposes an SGD variant (RSA) with additional Ep penalty which only works for strongly convex objectives. an independent recent work, Acharya et al. (2021) analyze geometric median (GM) on non-iid data using sparsified gradients. However, they do not defend against time coupled attacks, and their analysis neither proves convergence to the optimum nor recovers the standard rate of SGD when 8 0. In contrast, our analysis of GM addresses both issues and is more general. For decentralized training with non-iid data, a parallel work (E) Mhamdi et al., 2021a) considers asynchronous communication and unconstrained topologies and tolerates maximum number of Byzantine workers in their setting. However, no convergence rate is given. He al. (2022) consider decentralized training on constrained topologies and establish the consensus and convergence theory for a clipping based algorithm which tolerates a 5-fraction of Byzantine workers, limited by the spectral gap of the topology. Finally. Yang Li (2021) propose to use bucketing for asynchronous Byzantine learning which is very similar to the bucketing trick proposed in this paper for non-iid setup. Appendix F.1 we further compare these two methods in terms of purposes, techniques, and analysis.
Strong growth condition. The assumption that Eلح-v|/V - VV())) B [x=) I| for
some B 2 0 is also referred to as the strong growth condition (Schmidt & Roux, 2013). This has been extensively used to analyze and derive optimization algorithms for deep learning (Schmidt Roux, 3; Ma et al., 2018; Vaswani et al., 2019a;b; Meng et al., 2020). This line of work shows that the strong growth assumption both realistic and (perhaps more importantly) useful understanding optimization algorithms in deep learning. However, this is stronger than the weak growth condition which states that [] f (x) ff(=)]l < (f) - -f*) for some B 2 O. For a smooth function f. the strong growth condition always implies the weak growth condition. Further, for smooth convex functions this is equivalent to assuming that all the workers functions {ft} share a common optimum, commonly known interpolation. Our work uses the stronger version of the growth condition and it remains open to extend our results to the weaker version. This latter condition strictly necessary for heterogeneous Byzantine optimization (Gupta & Vaidya, 2020).
ATTACKS AGAINST EXISTING AGGREGATION SCHEMES
In this section we show that when the data across the workers is heterogeneous (non-iid), then we can design simple new attacks which take advantage of the heterogeneity, leading to the failure of existing aggregation schemes. We study three representative and widely used defenses:
Krum. For + j. let i + denote that æj belongs to the n q 2 closest vectors to æ;, Then,
KRUM(ZL...., D.. = argnin Σ ||= 22,1
Krum is computationally expensive, requiring (nn²) work by the server (Blanchard et al., 2017).
CM. Coordinate-winn wise median computes for the kthh coordinate:
[CM(z)....,, == median (aat)e, [=.]k) = argnin Ej= [[0:]] - [2,)]k]-
Coordinate-wise median is fast to implement requiring only (n) time (Chen et al., 2017).
RFA. Robust federated averaging (RFA) computes the geometric median
RFA(.))......................... mn) = argnin Σ |/0
22.122 |0
While the geometric median has no closed form solution, (Pillutla et al., 2019) approximate it using multiple iterations of smoothed Weiszfeld algorithm, each of which requires O(n) computation. 'The previous version of this work uses resampling which has identical performance as bucketing. The detailed comparison listed in Appendix A.2.4.
3

---

Published as a conference paper at ICLR 2022
Table 1: Test accuracy (%) with no Byzantine
Table 2: Test accuracy (%) under mimic attack
workers (Ō 0) on imbalanced data.
with = 0.2 fraction of Byzantine workers.
Ager
non-iid
Aggr
iid
Ava 08.19
98.75 1: 0.02
AVG 93.2010.22 0.21
92.73:10.32
KRUM
97.95:+0.25
89.90 4.75
KRUM
00.36:1.225
67.33:16678
CM
07.72:10.22
80.36 :: 0.05
CM
90.8010.112
64.27 3.370
98.62-4:0.8
82.60 0.84
RFA 92.92:10.25
78.93-1.9.27
CCLIP
98.78+0.10
98.78=0.06
CCLIP
93.16=0.22
91.53+00.00
3.1 FAILURE ON IMBALANCED DATA WITHOUT BYZANTINE WORKERS
We show that when the data amongst the workers is imbalanced, existing aggregation rules fail even in the absence of any Byzantine workers. Algorithms like KRUM select workers who are representative of a majority of the workers by relying on statistics such as pairwise differences between the various worker updates. Our key insight is that when the data across the workers heterogeneous, there is no single worker who is representative of the whole dataset. This is because each worker computes their local gradient over vastly different local data.
Example. Suppose that there are 2n + 1 workers with worker i holding (-1)* E {=1]. This means that the true mean O, but KRUM, CM, and RFA will output #1. This motivates our next attack.
Hence, for convergence it is important to not only select a good (non-Byzantine) worker, but also ensure that each of the good workers is selected with roughly equal frequency. In Table 1, we demonstrate failures of such aggregators by training on MNIST with n= 20 and no attackers (6=0). We construct an imbalanced dataset where each successive class has only fraction of samples of the previous class. We defer details of the experiments to Appendix A. As we can see, KRUM, CM and RFA match the ideal performance of SGD in the iid case, but only attain less than 90% accuracy in the non-iid case. This corresponds to learning only the top 2-3 classes and ignoring the rest.
similar phenomenon was observed when using batch-size 1 in the iid case by (Karimireddy et al., 2021). However, in the iid case this can be easily overcome by increasing the batch-size. In contrast, when the data across the works is non-iid (e.g. split by class), increasing the batch-size does not make the worker gradients any more similar and there remains big drop in performance. Finally, note that in Table a hitherto new algorithm (CCI.IP) maintains its performance both in the iid and the non-iid setting. We will explore this in more detail in Section 4.
3.2 MIMIC ATTACK ON BALANCED DATA
Motivated by how data imbalance could lead consistent errors in the aggregation rules and significant loss in accuracy, in this section, we will propose new attack mimic which specifically tries to maximize the perceived data imbalance even the original data is balanced.
Mimic attack. All Byzantine workers pick good worker (say i.) to mimic and copy its output (ac), ). This inserts a consistent bias towards evpr-emmaaii worker i, and thus repres-epr other workers. Since the attacker simply mimics good worker, it is impossible to distinguish it from a real worker and hence cannot be filtered out. Indeed, the target i, can be any fixed good worker. In Appendix B, we present an empirical rule to choose i, and include simple example demonstrating how median based aggregators suffer from the heterogeneity under mimic attack.
Table 2 shows the effectiveness of mimic attack even when the fraction of Byzantine nodes is small (i.e. π 25, [8] = 5). Note that this attack specifically targets the non-iid nature of the data- all robust aggregators maintain their performance in the iid setting and only suffer in the non-iid setting. Their performance is in fact worse than even simply averaging. As predicted by our example, KRUM and CM have the worst performance and RFA performs slightly better. We will discuss the remarkable performance of CCLIP in the next section.
4 CONSTRUCTING AN AGNOSTIC ROBUST AGGREGATOR USING BUCKETING
In Section 3 we demonstrated how existing aggregation rules fail in realistic non-iid scenarios, with and without attackers. In this section, we show how using bucketing can provably fix such aggregation rules. The underlying reason for this failure, as we saw previously, is that the existing methods fixate on the contribution of only the most likely worker, and ignore the contributions from the rest. To
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 Robust Aggregation (ARAGG) using bucketing
1: input { Fn , E N, aggregation rule AGGR
2: pick random permutation π of [x]
3: compute y: < E iis)
(- 11++1 (N) for {1...., [n/s]}
4: output @ t AGGR y.... Wa/4
I| aggregate after bucketing
overcome this issue, we propose to use bucketing which 'mixes' the data from all the workers thereby reducing the chance of any subset of the data being consistently ignored.
4.1 BUCKETING ALGORITHM
Given n inputs 21..... En- we perform s-bucketing which randomly partitions them into In/s] buckets with each bucket having no more than elements. Then, the contents of each bucket are averaged to construct { ..... [n/s]] } which are then input to an aggregator AGGR. The details are summarized in Algorithm I. The key property of our approach is that after bucketing, the resulting set of averaged (y),.... y / are much more homogeneous (lower variance) than the original inputs. Thus, when fed into existing aggregation schemes, the chance success increases. We formalize this in the following simple lemma.
Lemma (Bucketing reduces variance). Suppose we are given n independent (but not identical) random vectors (211.--., .n. such that good subset G C [m] of size at least [g] 2 n(1 5) satisfies:
E1lx;-0,) S p², for any fixed i, E.
Define T ==== To Ejeg Tz. Let the outputs after s-bucketing be {yr,..., Uin/s and denote & C (1...., [n/s]] as a good bucket set where a good bucket contains only elements belonging to G. Then [9] [n/s] (1 ōs) satisfies
Ely:] [[æ]] and
Ely: wsll 5//2///// 0²/s for any fixed i,j E G
The expectation in the above lemma is taken both over the random vectors as well as over the randomness of the bucketing procedure.
Remark Lemma I proves that after our bucketing procedure, we are left with outputs y, which have i) pairwise variance reduced by and ii) potentially times more fraction of Byzantine vectors. Hence, bucketing trades off increasing influence of Byzantine inputs against having more homogeneous vectors. Using = 1 simply shuffles the inputs and leaves them otherwise unchanged.
4.2 AGNOSTIC ROBUST AGGREGATION
We now define what it means for an agnostic robust aggregator to succeed.
Definition A (6maax -RAG)). Suppose we are given input {01...... [n) of which a subset G of size at least [G] > (1 - for S 6max < 0.5 and satisfies E|| xz < p² Then, the output i of a Byzantine robust aggregator satisfies:
E 2 < cōp² where à = ARAGG ...)
Further, ARAGG does not need know p² (only 8), and automatically adapts to any value p².
Our robust aggregator is parameterized by δmax < 0.5 which denotes the maximum amount of Byzantine inputs can handle, and a constant which determines its performance. If 8 0, i.e. when there are no Byzantine inputs, we are guaranteed to exactly recover the true average æ. Exact recovery also guaranteed when م = since in that case it easy to identify the good inputs since they are all equal and in majority. When both p > O and 8 > 0, we recover the average up to an additive error term. We also require that the robust aggregator agnostic to the value of p² and automatically adjusts its output to the current during training. The aggregator input though. This property is very useful the context of Byzantine robust optimization since the variance p² keeps changing over the training period, whereas the fraction of Byzantine workers 8 remains constant. This is a major difference from the definition used in (Karimireddy et al., 2021). Note that Definition A is defined for both homogeneous and heterogeneous data.
take 8 as
We next show that aggregators which we saw were not robust in Section 3, can be made to satisfy Definition A by combining with bucketing.
5

---

Published as a conference paper at ICLR 2022
Theorem I. Suppose are given inputs {æ1...., .n satisfying properties in Lemma 1 for some S mmax with δmax to be defined. Then, running Algorithm with s = [fmax/b yields the following:
Krum: KRUM BUCKETING(E), In,) = ())p2) with 8mag < 1/s.
Geometric median: E| o BUCKETING(
(6pp²) with mmax < 1/2
Coordinate median: E [[MMoBCCKTING
Fn 2 I Odd5p²) with Smax 1/2.
Note that all these methods satisfy our notion of an agnostic Byzantine robust aggregator (Defini- tion A). This because both our bucketing procedures as well as the underlying aggregators are independent of p². Further, error is (66p² and is information theoretically optimal, unlike previous analyses (e.g. Acharya et al. (2021) 1)) who had an error of O(p²).
The error of CM depends the dimension d which is problematic when d >> n. However, suspect this is because we measure stochasticity using Euclidean norms instead of coordinate-wise. In practice, we found that CM often outperforms KRUM, with RFA outperforming them both. Note that we select s = 6 to ensure that after bucketing, we have the maximum amount of Byzantine inputs tolerated by the method with (sō) = Ômax.
Remark (1-step Centered clipping). The 1-step centered clipping aggregator (CCLIP) given clipping radius T and an initial guess v of the average & performs
CCLIP(æ1.... Inn) U 1 Eie(m) (Zn v) min(1 5/||an - vl12)
Karimireddy et al. (2021) prove that CCLIP even without bucketing satisfies Definition with mmax 0.1, and (1)). This explains its good performance
non-idd data in Section 3. However, CCLIP is not agnostic since it requires clipping radius T as an input which in turn depends on p². Devising version of CCLIP which automatically adapts its clipping radius is an important open question. Empirically however, we observe that simple rules for setting work quite well-we always use T =
1-3 T-3
10
in our limited experiments where B is the coefficient of momentum.
While we have shown how to construct robust aggregator which satisfies some notion of robustness, haven't yet how this affects the Byzantine robust optimization problem. We investigate this question theoretically in the next section and empirically Section 6.
ROBUST NON-IID OPTIMIZATION USING A ROBUST AGGREGATOR
In this section, we study the problem of optimization in the presence of Byzantine workers and heterogeneity, given access to any robust aggregator satisfying Definition A. We then show that data heterogeneity makes Byzantine robust optimization especially challenging and prove lower bounds for the same. Finally, we see how mild heterogeneity, or sufficient overparamettrization can circumvent these lower bounds, obtaining convergence to the optimum.
Algorithm/ 2 Robust Optimization using any Agnostic Robust Aggregator
Input: ARAGG, 17, I: for i = 1,... ......d. do
2: for worker i [n] in parallel
9: t FF, {,) and m, + (1 1-3)g + +:33; 4: send m, if i E G, else send if Byzantine
3:
|/ worker momentum
5: in = ARAGG (m1,.... m,) and
mm. // update params using robust aggregate
5.1 ALGORITIIM DESCRIPTION
In Section we saw that bucketing could tackle heterogeneity across the workers by reducing ç². However, there still remains variance 6² in the gradients within each worker since each worker uses stochastic gradients. To reduce the effect of this variance, we rely on worker momentum. Each worker sends their local worker momentum vector m, be aggregated by ARAGG instead of g,: m 3m + (1 (x' for every i 9, x²
7) AGG m.).
This is equivalent to the usual momentum description up rescaling of step-size 77. Intuitively, using worker momentum m; averages over 1/(1-3) independent stochastic gradients g, and thus reduces the effect of the within-worker-variinne o² (Karimireddy et al., 2021). Note that the resulting {m.) are still heterogeneous across the workers. This heterogeneity is the key challenge we face.

---

Published as a conference paper at ICLR 2022
5.2 CONVERGENCE RATES
We now turn towards proving convergence rates for our bucketing aggregation method Algorithm 1 based on any existing aggregator AGGR. We will assume that for any fixed i g
Eg. (x) (=)( f d² and [)-e|lV{{(m) f=))| s <²,
Vo.
This first condition bounds the variance of the stochastic gradient within worker whereas the latter is a standard measure of inter-client heterogeneity in federated learning (Yu et al., 2019; Khaled et al., 2020; Karimireddy et al., 2020). Under these conditions, we can prove the following-
Theorem II. Suppose we are given (6max: (h-ax.c)-ARAGG. satisfying Definition A, and workers of which a subset 9 of size at least [9] 2 n 6) faithfully follow the algorithm for S 8max.. Further, for any good worker i G let Si be possibly non-convex function with L--lipschitz gradients, and the stochastic gradients on each worker be independent, unbiased and satisfy (2). Then, for Fo : f(x") - f*, the ouiput of Algorithm 2 satisfies
ET ElV((aaa =0(055 + +o LE (c8 +//) LFD )
Remark 4 (Unified proofs). Remark 3 shows that CCLIP is a robust aggregator, and Theorem I shows KRUM, RFA, and CM on combining with sufficient bucketing are all robust aggregators satisfying Definition A. Most of these methods had end-to-end convergence guarantees prior to our results. Thus, Theorem II gives the first unified analysis in both the iid and non-iid settings.
When + O i.c. as we reduce the number of Byzantine workers, the above rate recovers the optimal O( VTn
rate for non-convex SGD and even has linear speed-up with respect to the workers. In contrast, all previous algorithms for non-iid data (c.g. (Data & Diggavi, 2021; Acharya et al., 2021)) do not improve their rates for decreasing values of 6. This is also empirically reflected in Section 3.1, where these algorithms are shown to fail even in the absence of Byzantine workers (6 0).
Further, when robust rates of (Karimireddy et al., 2021). In both cases we converge to the optimum and can make the gradient arbitrarily small. However, when 0 > 0 and Ç > 0, Theorem II only shows convergence to radius of (VVCC) and not to the actual optimum. We will next explore this limitation.
the rate above simplifies O Ved + 1/n) which matches the iid Byzantine
5.3 LOWER BOUNDS AND THE CHALLENGE OF HETEROGENEITY
Suppose worker sends from the rest of the workers. This may be because worker j might be malicious and their update represents attempted attack. It may also be because worker has highly non-representative data. In the former case the update should be ignored, whereas in the latter the update represents a valuable source of specialized data. However, is impossible for the server distinguish between the two situations. The above argument can in fact be formalized to prove the following lower bound.
update which looks 'weird' and is very different from the updates
( Theorem III. Given any optimization algorithm ALG, we can find n. functions (f)(.).... ......neee (n())) of which at least (1 6)n are good (belong to G), I-smooth, j--strongly convex functions, and satisfy Eingll [+xx)) - V (z))2 < <² such that the output of ALG has an error at least E[f(ALG(f)..... fn)) f*] Ω2
and (A
fx)) 2(c()).
The expectation above is over the potential randomness of the algorithm. This theorem unfrotunately implies that is impossible to converge to the true optimum in the presence Byzantine workers. Note that the above lower bound is information theoretic in nature and is independent of how many gradients are computed or how long the algorithm run.
Remark (Matches lower bound). Suppose that we satisfy the heterogeneity condition (2) with <²> O and a = O. Then, the rate in Theorem Il can be simplified to O 1/T). While the second term this decays to O with T, the first term remains, implying that we only converge to a radius of VBC around the optimum. However, this matches our lower bound result from Theorem III and hence is in general unimprovable.
This a very strong negative result and seems to indicate that Byzantine robustness might be impossible to achieve in real world federated learning. This would be major stumbling block for deployment since the system would provably be vulnerable to attackers. We will next carefully examine the lower bound and will attempt to circumvent it.
7

---

Published as a conference paper at ICLR 2022
Table 3: Table + Bucketing (s=2).
Table 4: Table 2 + Bucketing (s=2)
Ager
non-lid
Aggr
non-lid
AvG 00.80
98.74=0.02
AvG 03.17:00.2 23
92.67:0.27
KRUM
96.35.10.20
93.27
KRUM
91.64110.30
53.15.13.96
CM
98.26:40.22
95.59=0.89
CM
91.91
73.60
RFA
98. 98.75+00.11
07.31=0.58
RFA
93.00=+0.23
91.17#0.51
CCLIP
98.79:20.10
98.75=0.02
CCLIP
93.17:0.23
92.56=0.21
5.4 CIRCUMVENTING LOWER BOUNDS USING OVERPARAMETERIZATIN
We previously saw some strong impossibility results posed by heterogeneity. In this section, we show that while indeed in the worst case being robust under heterogeneity is impossible, we may still converge to the true optimum under more realistic settings. We consider an alternative bound of (2):
Ey-s|[[[ (=)))]1 < ( Vxc.
(3)
Note that at the optimum xx we have f((") = O, and hence this assumption implies that (xx = 0 for all j E G. This is satisfied if the model is sufficiently perapaaramtterized and typically holds in most realistic settings (Vaswani et al., 2019a).
Theorem IV. Suppose we are given a (Smax, -ARARGG and n workers with loss functions {fi,..., }n} satisfying the conditions in Theorem II with 8 I ômax and (3) for some B < 6005
Then, for p [(x") - f", the output of Algorithm 2 satisfies
+ V ( 1-
(ov LE (F0+ 1/1)+ + -1)))))++)))))))))))))))))))))
Remark (Overparameterizztion fixes convergence). The rate in Theorem IV not only goes to 0 with T, but also matches that of the optimal iid rate of O f v + 1/1) (Karimireddy et al., 2021). Thus, using stronger heterogeneity assumption allows us circumvent lower bounds for the non-iid case and converge to a good solution even in the presence of Byzantine workers. This is the first result of its kind, and takes major step towards realistic and practical robust algorithms.
In the overparameterizee setting, we can be sure that we will able to simultaneously optimize all worker's losses. Hence, over time the agreement between all worker's gradients increases. This in turn makes any attempts by the attackers to derail training stand out easily, especially towards the end of the training. To take advantage of this increasing closeness, we need an aggregator which automatically adapts the quality of its output the good workers get closer. Thus, the agnostic robust aggregator is crucial to our overparameterized convergence result. We empirically demonstrate the effects of overparameteriiation in Appendix A.2.3.
6 EXPERIMENTS
In this section, demonstrate the effects of bucketing datasets distributed in non-iid fashion. Throughout the section, we illustrate the tasks, attacks, and defenses by an example of training an MLP on heterogeneous version of the MNIST dataset (LeCun et al., 1998). The dataset is sorted by labels and sequentially divided into equal parts among good workers; Byzantine workers have access to the entire dataset. Implementations are based on PyTorch (Paszke et al., 2019) and will be made publicly available. We defer details of setup, implementation, and runtime to Appendix A. Bucketing against the attacks on non-iid data. Section we have presented how heterogeneous data can lead to failure of existing robust aggregation rules. Here we apply our proposed bucketing with ==2 to the same aggregation rules, showing that bucketing overcomes the described failures. Results are presented in Table 3. Comparing Table 3 with Table 1, bucketing improves the aggregators' 1op-1 test accuracy on long-tail and non-iid dataset by 4% to 14% and allows them to learn classes at the tail distribution. For non-iid balanced dataset, bucketing also greatly improves the performance of KRUM and CM and makes RFA and CCLIP close to ideal performance. Similarly, combining aggregators with bucketing also performs much better on non-iid dataset under mimic attack. In Table 4, RFA and CCLIP recover iid accuracy, and KRUM, and CM are improved by around 15%. Bucketing against general Byzantine attacks. In Figure 1, we present thorough experiments on non-iid data over 25 workers with 5 Byzantine workers, under different attacks. In each subfigure, we compare an aggregation rule with its variant with bucketing. The aggregation rules compared are KRUM, CM, RFA, CCLIP. 5 different kinds of attacks applied (one per column in the figure): bit flipping (BF), label flipping (LF), mimic attack, as well as inner product manipulation (IPM) attack (Xie et al., 2020) and the "a little is enough" (ALIE) attack (Baruch al., 2019).
"The code is available at this url.
8

---

Published as a conference paper at ICLR 2022
Accuracy (S5)
1000
KRUM |BF
KRUM LF
KRUM mimic
KRUM IPM
KRUM ALIE
50-
Accuracy (N) Accuraty (%6 Accurscy (%)
100
IPM
50
CCli BF
CCIip LF
CCIip mimic
CCIip IPM
CCIi ALIE
0.0
55-
RF
RFA
IPM
1000
50-
200
400
6000
400
200
6000
200
400
6000
600
Ittrations
ltterations
Iterations
Rerations
Iterations
Figure 1: Ton-1 test accuracies of KRUM. CM. CCLIP. RFA. under 5 attacks on non-iid datasets.
100
90
90-
Accurany
60
80-
70-
8
60
50
0.9
50
0.9
100
300
200
300
Iterations
Iterations
(a) Fixed 9= IPM attackers, varying
(h) Fixed s= 2, varying number q
Figure 2: Top-1 accuracies of CCLIP with varying and when training on cluster of n n==33 nodes
Bit flipping: A Byzantine worker sends fz) instead of f due hardware failures etc.
Label flipping: Corrupt MNIST dataset by transforming labels by T(y) == 9
Mimic: Explained Section 3.2.
IPM: The attackers send T8T EEE (ax where c controls the strength of the attack.
ALIE: The attackers estimate the mean (ag and standard deviation ag of the good gradients, and
send μr - 20g to the server where z is small constant controlling the strength of the attack.
Both IPM and ALIE the state-of-the-art attacks in the iid distributed learning setups which takes advantage of the variances among workers. These attacks are much stronger in the non-iid setup. In the last two columns of Figure
show that worker momentum and bucketing reduce such variance while momentum alone is not enough. Overall, Figure I shows that bucketing improves the performances of almost all aggregators under all kinds of attacks. Note that r of CCLIP is not finetuned for each attack but rather fixed to 10 I-3 for all attacks. This scaling is required because CCLIP is not agnostic. We defer the discussion to Appendix 1.2.
Bucketing hyperparameter. Finally we study the influence of s and g on the heterogeneous MNIST dataset. We use CCLIP as the base aggregator and apply IPM attack. The Figure 2a confirms that larger gives faster convergence but s=2 is sufficient. Figure 2b shows that s 2 still behaves well when increasing g close to 25%. The complete evaluation of the results are deferred Appendix A. Discussion. In all our experiments, we consistently observe: i) mild bucketing (s = 2) improves performance, ii) worker momentum further stabilizes training, and finally iii) CCI.IP recovers the ideal performance. Given its ease of implementation, this leads us to strongly recommend using CCLIP in practical federated learning to safeguard against actively malicious agents or passive failures. RFA combined with bucketing and worker momentum also nearly recovers ideal performance and can instead be used when a proper radius 7 is hard to find, Designing an automatic and adaptively clipping radius well as its large scale empirical study is left for future work.
7 CONCLUSION
Heterogeneity poses unique challenges for Byzantine robust optimization. The first challenge is that existing defenses attempt to pick "representative" update, which may not exist in the non-iid setting. This, we showed, can be overcome by using bucketing. A second more fundamental challenge is that it is difficult to distinguish between "weird" but good worker from an actually Byzantine attacker. In fact, we proved strong impossibility results in such a setting. For this we showed how overparameterization (which is prevalent in real world deep learning) provides solution, ensuring convergence to the optimum even in the presence of attackers. Together, our results yield a practical provably Byzantine robust algorithms for the non-iid setting.

---

Published as a conference paper at ICLR 2022
Acknowledgement.
This project supported by SNSF grant 100020_200344
REFERENCES
Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topeu. Robust training in high dimensions via block coordinate geometric median descent. arXiv preprint Sttv:2206.088885 2021.
Dan Alistarh, Zeyuan Allen and Jemry Li. Byzantine stochastic gradient descent. In NeurIPS Advances in Neural Information Processing Systems, pp. 4613 4623, 2018.
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex
stochastic gradient descent. In ICLR 2021 International Conference of Learning Representations, 2021.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In AISTATS Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108, pp. 2938 2948, 2020.
Moran Baruch, Gilad Baruch, and Yoav Goldberg. A Little Is Enough: Cireumventing Defenses For Distributed Learning. NeurlPS, 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote communication efficient and fault tolerant. arXiv preprint 10X.vv8810005200 2018.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens, 2018.
Peva Blanchard, El Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent. In NeurlPS Advances Neural Information Processing Systems 30, pp. 119-129, 2017.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H Brendan McMahan, et al. Towards federated learning at scale: System design. In SysML Proceedings of the 2nd SysML Conference, Palo Alto, CA, USA, 2019.
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine- resilient distributed training via redundant gradients. arXiv preprint arXiv:1803.09877 2018.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings. Proceedings of the ACM Measurement and Analysis of Computing Systems, 1(2):1-25, Dec 2017. ISSN 2476-1249 doi: 10. 14533155503
Michael B Cohen, Yin Tat Lee, Gary Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 9-21, 2016.
Georgios Damaskinos, El Mahdi EI Mhamdi, Rachid Guerraoui, Arsany Hany Abdelmessih Guirguis, and Sébastien Louis Alexandre Rouault. Aggregathor: Byzantine machine learning via robust gradient aggregation. Conference on Systems and Machine Learning (SysML) 2019, Stanford, CA. USA, pp. 19, 2019.
Deepesh Data and Suhas Diggavi. Byzintine-resilient sgd in high dimensions on heterogeneous data. arXiv preprint arXiv:2005.0785 2020.
Deepesh Data and Suhas Diggavi. Byzintine-resilient high-dimensional sgd with local iterations on heterogeneous data. In ICML. 2021 37th International Conference on Machine Learning, 2021.
El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in byzantium. In International Conference on Machine Learning, pp. 3521- 3530. PMLR, 2018.
10

---

Published as a conference paper at ICLR 2022
EI Mahdi EI Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyén Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, hetero- geneous, asynchronous and nonconvex learning). Advances in Neural Information Processing Systems, 34, 2021a.
El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. Distributed momentum for byzantine- resilient stochastic gradient descent. In ICLR 2021 International Conference on Learning Representations, 2021b.
Avishek Ghosh, Justin Hong, Dong Yin, and Kannan Ramchandran. Robust federated learning in heterogeneous environment. arXiv preprint arXiv:1906.0666 2019.
Nirupam Gupta and Nitin H Vaidya. Resilience in collaborative optimization: redundant and independent cost functions. arXiv preprini arXiv:2003.09675, 2020.
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Byzantine- decentralized learning via self-centered clipping. arXiv preprint arXiv:2202.01555. 2022.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira. Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, 7aid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv preprint arXiv: 1912,04977, 2019.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi. Error Feedback Fixes SignSGD and other Gradient Compression Schemes. In ICML 2019 Proceedings of the 36th International Conference on Machine Learning, 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In ICML 2020 International Conference on Machine Learning, 2020.
Sai Praneeth Karimireddy, Li He, and Martin Jaggi. Learning from history for byzantine robust optimization. In ICML. 2021 37tth International Conference on Muchine Learning, 2021.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identical and heterogeneous data. AISTATS 2020 International Conference on Artificial Intelligence and Statistics, 2020.
Leslie Lamport, Robert Shostak. and Marshall Pease. The byzantine generals problem. In Concur- rency: the Works of Leslie Lamport, pp. 203-226. 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11 (1:1222778-2244 1998.
Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1544-1551, 2019.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. In International Conference on Machine Learning, pp. 3325-3334. PMLR, 2018.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera/ y Arcas. Communication efficieen learning of deep networks from decentralized data. arXiv preprint 16Xiv: 2016.
11

---

Published as a conference paper at ICLR 2022
Edward Meeds, Remeo Hendriks, Said Al Faraby, Magiel Bruntink, and Max Welling. Mlitb: machine learning in the browser. PeerJ Computer Science. I:el,, Jul 2015. ISSN 2376-5992. doi: 10.7717/pcerj-cs..1 URL http:// /xx. ottp:///dddddoo/////ooooooooooo. 10. w1w.111/peerr--c....
Si Yi Meng, Sharan Vaswani, Issam Hadj Laradji, Mark Schmidt, and Simon Lacoste-Julien. Fast and furious convergence: Stochastic second order methods under interpolation. In International Conference on Artificial Intelligence and Statistics, pp. 1375-1386. PMLR, 2020.
Stanislav Minsker et al. Geometric median and robust estimation in banach spaces. Bernoulli, 21(4): 2308-2335, 2015.
Ken Miura and Tatsuya Harada. Implementation of a practical distributed calculation system with browsers and javascript, and application to distributed deep learning. arXiv preprint arXiv:1503.05743. 2015.
Erkki Oja. Simplified neuron model as principal component analyzer. Journal of mathematical biology, 15(3):267-21) 1982.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pp. 8024-8035, 2019.
Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust Aggregation for Federated Learning. arXiv preprint 1912. 2019.
Shashank Rajput, Hongyi Wang. Zachary Charles, and Dimitris Papailiopoulos. Detox: redundancy- based framework for faster and more robust gradient aggregation. arXiv preprint arXiv:1907.12205: 2019.
Sattler, K. Müller, T. Wiegand, and W. Samek. On the byzantine robustness of clustered federated learning- In ICASSP 2020 2020 IEEE International Conference Acoustics, Speech and Signal 2020.
Processing (ICASSP), pp.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint / 30..006666.,, 2013.
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H Brendan McMahan. Can you really backdoor federated learning? arXiv preprint 19X1v:/911.079000 2019.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over- parameterized models and an accelerated perceptron. In AISTATS 2019 The 22nd International Conference on Artificial Intelligence and Statistics, 2019a
Sharan Vaswani, Aaron Mishkin, Issam Laradji, Mark Schmidt, Gauthier Gidel, and Simon Lacoste- Julien. Painless stochastic gradient: Interpolation, line-search, and convergence rates. Advances in neural information processing systems, 32, 2019b.
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. arXiv preprint ar arXiv:2007.0500 2020.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEF Transactions Signal Processing, 68:4583-4594 2020.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion based fault-tolerance. ICML 2019 35th International Conference on Machine Learning, 2019.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of Empires: Breaking srrantine-toleran SGD by Inner Product Manipulation. In UAI Proceeding of The 35th Uncertainty in Artificial Intelligence Conference, 2020.
12

---

Published as a conference paper at ICLR 2022
Yi-Rui Yang and Wu-Jun Li. Basgd: Buffered asynchronous sgd for byzantine learning. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 11751-11761. PMLR, 18-24 Jul 2021. URL htt.htttt///ttte. / ptwceeeceeeececpooooooooocooeecc i ngs ml p.rsss v 39/ y html.
Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter Bartlett. Byzantinerobbust distributed learning: Towards optimal statistical rates. arXiv preprint 17X3v0:803.01425 2018.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In AAAI 2019- Conference on Artificial Intelligence, 2019.
13


Reviews:
[{"review_id": "xSRHzQU3TYi", "reviewer": "Reviewer_ago1", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n1. **Lower bounds for Byzantine-robust optimization under bounded heterogeneity.** In Theorem III, the authors prove that even in the case of bounded heterogeneity (in the classical sense for papers on FL) one cannot achieve any predefined accuracy even for the strongly convex problems. In particular, they prove that functional suboptimality cannot be made smaller than $\\Omega(\\frac{\\delta \\zeta^2}{\\mu})$ ($\\mu$ - str. convexity parameter, $\\delta$ - fraction of Byzantines, $\\zeta^2$ - dissimilarity measure of the gradients of local loss functions). Typically, $\\mu$ is quite small and $\\zeta^2$ can be large for some FL problems when the clients naturally have highly heterogeneous data. In such situations, the lower bound is really pessimistic. Although this fact (Theorem III) is expected for the experts in optimization, it is very important for the field of Byzantine-robust optimization: it creates a clear picture of the limits of robustness.\n\n2. **New upper bounds for Byzantine-robust optimization under bounded heterogeneity.** The authors prove new complexity bounds for Byzantine-robust optimization under bounded heterogeneity in the non-convex case. The derived results match the established lower bound. Moreover, it is shown that one can achieve any predefined accuracy (Theorem IV) when the heterogeneity level at the point $x$ is proportional to $\\|\\nabla f(x)\\|^2$ (can be seen as a strong growth condition from (Vaswani et al., 2019)).\n\n3. **Bucketing as a tool to make Krum, Geometric Median, and Coordinate-wise Median robust.** (Karimireddy et al., 2021) show that even in the homogeneous case Krum, Geometric Median, and  Coordinate-wise Median are provably non-robust to Byzantine attacks. This work fixes this drawback of the mentioned aggregation rules (Theorem I) via a simple tool called bucketing. This result (together with Theorem II) is very important for Byzantine-tolerant optimization in the homogeneous case, since Krum, Geometric Median, and Coordinate-wise Median were not analyzed previously without restrictive assumptions. \n\n4. **Clarity.** The paper is well-motivated, clearly written, and has a good structure.\n\n## Weaknesses\n1. **Inaccuracies in the proofs.** I have checked all the proofs and noticed several inaccuracies and unexplained derivations. Although it is possible to fix all the issues, in the current shape, it is hard to follow some parts of the proofs. I list all my questions and comments in section **Questions and comments about the proofs** of my review.\n\n2. **Comparison with related work.** Unfortunately, it is not trivial to compare the results from this paper with other related works given the information provided in the related work section. The current version of the related work section summarizes the known works without going into the details. However, it is important for the paper to provide an explicit comparison with the related works (with the discussion of the derived rates and assumptions). I strongly encourage the authors to provide such a comparison at least in the appendix. Moreover, the authors should pay a lot of attention to the comparison with Yang & Li (2021) since they also use bucketing.\n\n## General questions and comments\n1. **Abstract, sentence \"Our work is the first...\":** This sentence is not correct since Li et al. (2019) also derive convergence results under realistic assumptions for strongly convex problems. Perhaps, the authors wanted to emphasize that their work provides the first guarantees under the not too strong assumption in the non-convex case.\n\n2. **Page 2, \"However, none of these methods are applicable to the standard federated learning.\"** This claim requires additional clarifications. For example, it is not clear why the method from Li et al. (2019) is not applicable.\n\n3. **Definition A:** I suggest the authors additionally emphasize that this definition is useful for both homogeneous and heterogeneous cases.\n\n4. **Remark 3:** This is 1 iteration of CClip, which is not necessarily the output of the aggregator.\n\n5. **Second paragraph after Remark 4, \"... which matches the optimal iid Byzantine robust rates of (Karimireddy et al., 2021)\".** It is not clear why the mentioned rate is optimal (and in what setting). Karimireddy et al. (2021) do not prove the lower bound. Moreover, there is a recent work, where the better rate is achieved (in terms of the number of iterations): Gorbunov et al. \"Secure Distributed Training at Scale.\" arXiv preprint arXiv:2106.11257 (2021).\n\n6. **Page 7, the sentence above Theorem 7, \"... typically holds in most realistic settings (Vaswani et al., 2019\".** Vaswani et al. (2019) do not provide evidence that this assumption holds in most realistic settings. In fact, they show it (Strong Growth Condition) for an example of squared hinge-loss in the case of linearly separable data. They also prove that Strong Growth Condition follows from the interpolation condition when the summands in the loss function are smooth and the loss satisfies PL-condition. However, in this case, the known bound upper bound for $B$ is proportional to $\\frac{L}{\\mu}$ where $L$ is the maximal smoothness constant of $f_i$ and $\\mu$ is the PL-parameter of $f$. Therefore, the current theoretical estimates for $B$ are quite large even for simple special cases.\n\n7. **Theorem IV, condition $B^2 < \\frac{1}{3c\\delta}$.** In view of my previous comment, this requirement may imply that $\\delta$ is tiny. I think the discussion of this requirement should be added to the paper.\n\n8. **Missing reference.** This work also addresses the heterogeneous case for Byzantine-robust optimization: *Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 68:4583–4596, 2020.* Moreover, Wu et al. (2020) also prove convergence guarantees under similar assumptions. Therefore, a detailed comparison of the derived results should be added.\n\n9. **Conclusion, the last sentence, \"... our results represent a major breakthrough...\"** Although the work makes a strong contribution to the field, in my opinion, it cannot be called a breakthrough taking into account that many of the building blocks were known and analyzed to some extent (bucketing, client momentum). I think only a couple of papers can be called a breakthrough objectively (e.g., Nesterov's acceleration and discoveries of the same caliber). So, I suggest the authors rewrite the sentence: let the readers decide for themselves whether this paper is a breakthrough or not.\n\n## Questions and comments about the proofs\n1. **Proof of Lemma 1, formula for $\\mathbb{E}_{\\pi}[y_i | i \\in \\widetilde{\\mathcal{G}}]$:** this is true, but the detailed derivation should be added.\n\n2. **Lemma 7.** First of all, the lower and upper bounds should be multiplied by $n$. Moreover, I have the following question about the proof of the lower bound: does the described distribution of $y_i$ correspond to any distribution of the initial vectors $x_i$ before the bucketing? This is crucial for the correctness of the lower bound.\n\n3. **Page 20, robustness of Krum.** The first formula is not proven. Moreover, it is not clear what is $S^{\\ast}$. Next, in the formula above \"Taking expectation now on both sides yields\" the minimization should be taken over the sets $S$ such that $|S| = \\frac{3m}{4}$. In the next formula, it seems that the numerator should contain $4n\\tilde{\\rho}^2$. After that, the sentence \"Then, the number of Byzantine workers can be bounded as $|\\tilde{\\mathcal{B}}| \\leq m(1/4 - \\delta)$\" should be rewritten as \"Then, the number of Byzantine buckets can be bounded as $|\\tilde{\\mathcal{B}}| \\leq m(1/4 - \\nu)$\". Finally, in the upper bound for $\\mathbb{E}\\|y_{k^\\ast} - \\bar{x}\\|^2$ the denominator of the first fraction should have $\\nu m$ instead of $\\nu n$.\n\n4. **Page 21, robustness of Geometric median.** In the third sentence, the word \"worker\" should be replaced by \"set\"/\"bucket\". There is also a typo in the formula after the words \"Squaring both sides, expanding, ...\": the sum in the first row should not have $\\mathbb{E}$ inside.\n\n5. **Appendix D, the proof of Theorem III.** The first formula should contain $\\delta$ instead of $\\hat\\delta$. Next, the formula after the words \"Note that the gradient heterogeneity ...\" should be supported by the full derivation (or explained). It is true but requires few extra steps.\n\n6. **Proof of Lemma 8** contains several inaccuracies and unexplained derivations. First of all, what is $\\mathbb{E}[\\cdot | i]$? If it is an expectation conditioned on $i$, then $\\mathbb{E}[g_i(x^{t-1}) | i] \\neq \\nabla f_i(x^{t-1})$ since $x^{t-1}$ depends on the stochasticity not related to the choice of $i$. But the proof uses $\\mathbb{E}[g_i(x^{t-1}) | i] = \\nabla f_i(x^{t-1})$. This should be fixed (here and below). Next, it is not clear what is $\\mathbb{E}_i[\\cdot]$. The first formula on page 24 is incorrect due to the same reason as the first formula in the proof. This issue should be fixed as well. The second formula on page 24 is also inaccurate: the RHS should have $\\zeta^2(1 - (1-\\alpha)^t)$. Next, there is a typo in the sentence \"This is because the randomness in the sampling...\". Finally, the last sentence in the proof the authors claim that it is enough to apply Definition A, but it is not correct: this definition requires $\\mathbb{E}\\|m_i^t - m_j^t\\|^2 \\leq \\rho_t^2$ while the authors prove a weaker result that $\\mathbb{E}_i\\|m_i^t - \\bar{m}^t\\|^2 \\leq \\rho_t^2$. Overall, the proof of Lemma 8 requires a major revision (and, probably, Definition A should also be changed to fit the proof).\n\n7. **Lemma 10.** Numerical constants are incorrect: instead of $\\frac{2\\alpha}{5}$ the formula should have $\\frac{5\\alpha}{16}$ and instead of $\\frac{\\alpha}{10}$ one should have $\\frac{3\\alpha}{32}$.\n\n8. **The proof of Theorem V** contains several places that should be better explained (and, most likely, corrected, because of the inaccuracies). First of all, it seems that the authors forgot to upper bound $\\mathbb{E}\\|m_t - \\bar{m}_t\\|^2$: it is contained in the RHS of the second formula in the proof, but it is omitted in the derivations on page 26. Next, the last formula on page 25 is inaccurate: one should have $\\nabla f(x^{t-1})$ in the RHS. Moreover, the next step in the proof is unclear: it seems that a lot of derivations are omitted. For me, it is not clear how the term $\\mathbb{E}\\|m_t - \\bar{m}_t\\|^2$ is handled. Therefore, this derivation should be significantly rewritten and checked.\n\n## Minor comments\n1. **$|\\mathcal{B}| = f$.** The symbol $f$ is already used to denote the objective function. I suggest using a different notation for the number of Byzantines.\n\n2. **Lemma 1.** $\\widetilde{\\mathcal{G}}$ is defined only in the proof. The authors should add the definition in the statement of the lemma.\n\n3. **Figure 9** contains low-resolution images. The authors should replace them with the ones with higher resolution.\n\n4. **Page 18, the last formula:** full stop is missing in the end of the of the formula (please, check other formulas that end sentences as well).\n\n5. **Page 19, the second sentence, \"... each can belong to only 1 bucket each\":** one \"each\" should be removed.\n\n6. **Lemma 9.** In this lemma, the authors use $m_t$ instead of $m^t$. The notation should be unified.\n\n7. **Lemma 10.** The authors use $x_{t-2}$ and $x^{t-1}$. The position of the indices should be unified.", "summary_of_the_paper": "The paper provides a systematic and deep theoretical study of the problem of Byzantine-robustness in the heterogeneous setup, i.e., when workers have non-identical datasets and, as s result, their local loss functions are non-identical. The authors prove that even under bounded heterogeneity it is impossible to provably achieve any predefined accuracy of the solution by any method. Next, the authors propose and analyze an algorithmic tool called *bucketing* and show that it makes some known aggregators such as Krum, coordinate-wise median, and geometric median to be *agnostic* robust aggregators. Under bounded heterogeneity assumption, the authors derive that Robust Client Momentum method from (Karimireddy et al., 2021) converges for non-convex problems to a neighborhood of a stationary point. Next, it is shown that the size of the neighborhood can be made arbitrarily small for over-parameterized problems. Numerical experiments corroborate theoretical findings and, in particular, show the benefits of the proposed bucketing procedure.\n\nOverall, the paper is well-motivated, clearly written, and contains solid contributions. There are also some minor inaccuracies in the proofs, small typos, and other minor weaknesses -- I list them below. I encourage the authors to address all of them.", "summary_of_the_review": "To sum up, I am sure that the paper should be accepted to the conference after minor improvements. If the authors apply all necessary corrections and address my comments properly, I will increase my score: the paper deserves acceptance as a spotlight or even oral talk.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "keaxtVCcGT", "reviewer": "Reviewer_WV2X", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n-I think that this is an elegant way of combining two key areas of work in the FL community: non-iid data sets + Byzantine nodes \n-Empirical results seem robust\n-The bucketing model is simple, believable, and it is nice that it composes well with existing methods. \n-The theoretical analysis of the model is extensive: it matches existing bounds when \\delta or \\rho=0, and the lower bound matches the non-trivial term that occurs when both \\delta,\\rho \\neq 0. \n\nWeaknesses:\n-Are there more complicated examples of non-iid models under non-adversarial attacks that perform poorly? The Rademacher distribution is a good starting point to justify the analysis, but seeing the performance of existing aggregators on more complicated data sets when \\delta=0 would be interesting. \n- Still not convinced about the upper bound on gradient norm in the over-parameterized setting (where the term is bounded by B \\times \\grad f(x)). Is this realistic? Perhaps I am not seeing how this falls out of over-parameterization. A note on this might be useful in the write-up of the paper.\n-The lower bound analysis (Theorem 3) could have some more intuition as well, in terms of what the argument is like, and what the functions that are used consist of. In particular, it would be interesting to note whether the author thinks the adversarial functions for the bound are efficiently computable, and if not, whether hard functions can occur in practice over the byzantine nodes (could this happen without some amount of coordination amongst the byzantine nodes for example?)\n-What about other types of attack objectives, i.e. backdoor attacks (this seems highly relevant in the non-iid setting, especially if the adversary has knowledge of which clients have which data)\n", "summary_of_the_paper": "This paper focuses on Byzantine-robust federated learning, a learning paradigm where a centralized server coordinates learning across a data set partitioned across multiple worker nodes, some of which are adversarial. Typically this is done via robust aggregation schemes which ensure that adversarial nodes do not hinder learning.  In this setting, the author's main focus is on studying the setting where honest worker nodes own heterogeneous data sets. As the authors mention, the existing literature on Byzantine-robust federated learning focuses on the setting in which honest worker nodes draw iid samples from an underlying data distribution, and although there is also existing literature on (non-Byzantine) federated learning over heterogenous data distributions amongst nodes, this work brings these two strands of research together. \n\nThe main results are the following: \n-Providing (simple) settings and empirical results wherein common aggregation methods fail in the presence of heterogeneous data, even when there are no adversarial nodes.\n-Providing a specific attack vector for the heterogeneous Byzantine setting, whereby adversarial nodes choose an honest node to replicate (\"Mimic\" attack). This exposition comes with an efficient algorithm for computing the most \"hurtful\" choice of node to mimic, and the authors empirically demonstrate the potential of this attack against common aggregation methods\n-Formally defining the design objective of \"Agnostic Robust Aggregators\", which quantifies degradation of aggregator performance as a function of byzantine tolerance and dataset heterogeneity.\n-Providing a simple randomized bucketing scheme. Messages from nodes are randomly averaged in buckets, where the number of buckets is a free parameter. Increasing the number of buckets reduces the variance of bucket representatives, but potentially increases the number of byzantine agents (post-bucketing). If there is sufficient margin in existing aggregation protocols, performing judicious bucketing before applying the aggregation rule permits making Agnostic Robust Aggregators out of existing aggregation schemes (with specifically quantifiable guarantees). \n-The authors also theoretically study optimization methods that make use of aggregation methods (via stochastic gradient descent). In this setting they provide upper bounds on convergence rates of optimization using robust aggregators (in terms of the parameters that govern the robustness of aggregation method as per Definition A), and show that these upper bounds match existing upper bounds in the case where there are no byzantine agents (\\delta = 0) or when data is homogeneous (\\rho = 0). In the regime where these terms are non-zero, convergence is not guaranteed, but via information theoretic methods, the authors also provide a matching lower bound\n-If heterogeneity bounds are more refined (whereby gradient variation is bounded by the order global gradient of the entire dataset), then the authors demonstrate convergence of robust aggregation methods on SGD. This setting applies when systems are over-parameterized. \n-Finally, the authors provide multiple experimental results that validate the theoretical findings of the work.", "summary_of_the_review": "I recommend this paper for acceptance. This seems like a fitting extension of existing work, and the authors have provided a corresponding framework for quantifying performance loss in the presence of byzantine agents and heterogeneous data for federated learning. Their results match existing work in regimes when there are no byzantine agents, and when there is a lack of heterogenous data. Furthermore, the non-trivial loss of performance in the regime where both byzantine agents and heterogenous data is present is accounted for in a matching lower bound. These results will be of interest to the growing body of work in federated learning at ICLR. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AhcQUecbpus", "reviewer": "Reviewer_oF9Y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "0. The investigated problem, Byzantine-robust distributed learning over non-iid data, is important. The algorithm development and the analysis both contain new results\n1. In the previous version of this paper, the authors propose resampling to reduce the heterogeneity across the workers. Why do the authors switch to bucketing in this version?\n2. In Page 2, the authors claim that “none of these (non-iid Byzantine-robust) methods are applicable to the standard federated learning.” Please justify this claim.\n3. Related to the above comment, the authors do not compare the proposed methods with any other non-iid Byzantine-robust methods.\n4. Also about the numerical experiments, the MNIST dataset is too simple. Testing on one or two additional large datasets could make the results more convincing (in particular, for the over-parametrized case).\n5. In Section 3.2, the mentioned mimic attack has appeared in other papers that investigate non-iid Byzantine-robustness. Please cite.\n6. In Section 4.2, why place centered clipping here? It should be located in Section 3.\n7. The role of momentum is not well investigated. The authors should indicate its contribution to the performance improvement. \n8. For the numerical experiments of the over-parametrized case, the authors use centered clipping as the basic aggregator. But centered clipping has certain robustness in the non-iid setting. Using other base aggregators, such as geometric median, could be better here.\n9. Theorem IV requires that B^2 is sufficiently small. Please check whether this condition can be satisfied in the numerical experiments.\n", "summary_of_the_paper": "In this paper, the authors consider Byzantine-robustness of a distributed learning system in the setting of non-iid data distribution. The bucketing technique is applied to reduce the heterogeneity across the workers. To further reduce the variance within each worker, the authors adopts the momentum technique. These two techniques can be combined with various robust aggregation rules. The authors prove the convergence of the combined methods, and show that they reach the lower bound. The authors also claim that for the over-parametrized case, the negative impact of data heterogeneity can be eliminated.", "summary_of_the_review": "Overall, this paper has publication merits, but some issues need to be addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8t9McEA18bb", "reviewer": "Reviewer_EczS", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\nThe bucketing scheme proposed in this paper is interesting. It is easy to adopt and does not bring much extra computational cost, but can improve the performance of existing Byzantine-resilient algorithms, as shown in the empirical results. Also, I appreciate that the authors provide convergence results for general aggregation rules, together with precise analysis for three common aggregation rules in Theorem I.\n\n## Weaknesses\nWhen decreasing the heterogeneity, the bucketing scheme also reduces the number of candidate vectors (gradients). However, in the worst case, the number of corrupted vectors will remain the same. Thus, the number of Byzantine workers that can be tolerated will decrease to $1/s$ when adopting bucketing. Although the empirical results show that $s=2$ is sufficient to overcome heterogeneity, the number of Byzantine workers that can be tolerated already drops by half in this case. I am not aiming to criticize the bucketing scheme but to point out the limitation. I think that this problem has truly restricted the application prospects of bucketing in general cases.\n", "summary_of_the_paper": "This paper proposes a bucketing scheme for robust distributed learning with heterogeneous data. Gradients are more homogeneous after bucketing, which will increase the robustness of existing algorithms. The author provides theoretical analysis as well as empirical results.", "summary_of_the_review": "Although there are weaknesses in this work, considering the challenges from heterogeneity, I think this work is slightly above the threshold.\n\n--------\n(Post-rebuttal)\nMy major concerns have been properly addressed by the authors and the quality of this paper has been improved after revision. Thus, I have raised my rating.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript proposes and analyses a bucketing method for Byzantine-robustness in non-iid federated learning. The manuscript shows how existing Byzantine-robust methods suffer vulnerabilities when the devices are non-iid, and describe a simple coordinated attack that defeats many existing defenses. In response, the primary algorithmic contribution is a bucketing approach that aggregates subgroups of devices before robust aggregation. This approach is also easily composed with existing Byzantine-robust methods. The manuscript includes an analysis of the performance of the proposed approach, including an information-theoretic lower bound for certain settings.

During the review, the main concerns are related to the clarity of the technical contributions, and unclear technical statements. The authors respond to these concerns and have satisfied the reviewers. After discussion, reviewers are generally strongly positive about the strength of the manuscript contributions. The authors are reminded to make the final changes agreed in the public discussion e.g., discussion of the reduction to SGD when  $\delta=0$
Decision: Accept (Spotlight)