Flag Aggregator: Scalable Distributed Training under Failures and Augmented Losses using Convex Optimization
Authors: Hamidreza Almasi
Harsh Mishra
Balajee Vamanan
Sathya N. Ravi
Venue: ICLR 2024 poster (2024)
Keywords: Robust
Aggregation
Distributed
Training
Failure
Augmented
Byzantine
Resilience
Primary area: optimization

Abstract: Modern ML applications increasingly rely on complex deep learning models and large datasets. There has been an exponential growth in the amount of computation needed to train the largest models. Therefore, to scale computation and data, these models are inevitably trained in a distributed manner in clusters of nodes, and their updates are aggregated before being applied to the model. However, a distributed setup is prone to Byzantine failures of individual nodes, components, and software. With data augmentation added to these settings, there is a critical need for robust and efficient aggregation systems. We define the quality of workers as reconstruction ratios $\in (0,1]$, and formulate aggregation as a Maximum Likelihood Estimation procedure using Beta densities. We show that the Regularized form of log-likelihood wrt subspace can be approximately solved using iterative least squares solver, and provide convergence guarantees using recent Convex Optimization landscape results. Our empirical findings demonstrate that our approach significantly enhances the robustness of state-of-the-art Byzantine resilient aggregators. We evaluate our method in a distributed setup with a parameter server, and show simultaneous improvements in communication efficiency and accuracy across various tasks.

Published as a conference paper at ICLR 2024
SCALABLE DISTRIBUTED TRAINING UNDER FAILURES AND AUGMENTED LOSSES USING CONVEX OPTIMIZATION
FLAG AGGREGATOR:
Hamidreza Almasi
Harsh Mishra Balajec Vamanan Sathya Ravi
Department of Computer Science University of Illinois Chicago
{ (halmas3, hmishr3, bvamanan, sathya) @uic. edu
ABSTRACT
Modern ML applications increasingly rely on complex deep learning models and large datasets. There has been an exponential growth in the amount of computation needed train the largest models. Therefore, to scale computation and data, these models are inevitably trained in a distributed manner in clusters nodes, and their updates are aggregated before being applied to the model. However, distributed setup is prone Byzantine failures of individual nodes, components, and software. With data augmentation added to these settings, there is critical need for robust and efficient aggregation systems. We define the quality of workers as reconstruction ratios E (0, 1]. and formulate aggregation as a Maximum Likelihood Estimation procedure using Beta densities. We show that the Regularized form of log-likelihood wrt subspace can be approximately solved using iterative least squares solver, and provide convergence guarantees using recent Convex Optimization landscape results. Our empirical findings demonstrate that our approach significantly enhances the robustness of state-of-the-a Byzantine resilient aggregators. We evaluate our method in distributed setup with a parameter server, and show simultaneous improvements in communication efficiency and accuracy across various tasks!
INTRODUCTION
How to Design Aggregators? We consider the problem of designing aggregation functions that can be written as optimization problems of the form,
A(g gp) E arg min ApI....,, YEC
(1)
where {g:}? C R are given estimates of an unknown summary statistic used compute the Aggregator Y". If we choose A to be a quadratic function that decomposes over g 's, and C R", then we can see is simply the standard mean operator. There is a mature literature of studying such functions for various scientific computing applications Grabisch et al. (2009). More recently, from the machine learning standpoint there has been a plethora of work Balakrishnan et (2017); Diakonikolas et al. (2019); Cheng et al. (2022); Diakonikolas et al. (2022) on designing provably robust aggregators for mean estimation tasks under various technical assumptions on the distribution moments of g:-
Distributed ML Use Cases. Consider training model with large dataset such as ImageNet-IK Russakovsky et al. (2015) or its augmented version which would require data to be distributed over p workers and uses back propagation. Indeed, in this case, g, 's are typically the gradients computed by individual workers at each iteration. In settings where the training objective is convex, the convergence and generalization properties of distributed optimization can be achieved by defining A weighted combination of gradients facilitated by simple consensus matrix, even if some 's are noisy Tsianos and Rabbat (2012); Yang et al. (2019a). In a distributed setup, as long as the
Our code is available at httpt::////gg thub. hami dra masi /P Algggggrgatoorr

---

Published as a conference paper at ICLR 2024
Estimate Subspace for Aggregation
Weight foe workers gredlient sullepaoss
Gradlients from werferss
Conratenated gredient matris
Left singilor vectors
Singular values
Right singilor
vettors
G
G. [Ggl -. 10p
E RP
Σ E Rewa
Flag Aggregator
vT Raxn
Ge:
.. M
Orz
-.
(ix
5
Yr
9
Ctf.
Wp.
Sp
..
U m]
dee1
9.59) JAR
DIG
YX
Augrented Tatt
Stable Diffodion
Iteration
1. (OL.9) WF)
Iteration
Figure Robust gradient aggregation our distributed training framework. our applications, each of the workers provides gradients computed using a random sample obtained from given training data, derived synthetic data from off-thh-shhelf Diffusion models, and random noise in each iteration. Our Flag Aggregator (FA) removes high frequency noise components by using few rounds of Singular Value Decomposition of the concatenated Gradient Matrix G, and provides new update Y*.
simultaneously minimize the total iteration communication complexity to a significant extent i.e., is possible to achieve convergence and robustness under technical assumptions on the moments of (unknown) distribution from which g 's drawn. However, it is still an open problem to determine the optimality of these procedures in terms of either convergence robustness Blanchard al. (2017); Farhadkhani al. (2022).
model is convex
Potential Causes of Noise. When data is distributed among workers, hardware and software failures in workers Bautista-Gomez et al. (2016); Schroeder and Gibson (2007); Gill al. (2011) can cause them to send incorrect gradients, which can significantly mislead the model Baruch et al. (2019). To see this, let's consider a simple experiment with 15 workers, that f them produce uniformly random gradients. Figure shows that the model accuracy is heavily impacted when > 0 when mean is used to aggregate the gradients.
The failures can occur due to component or software failures and their probability increases with the scale of the system Wang et al. (2017); Tiwari et al. (2015); Nie et al. (2016). Reliability theory used to analyze such failures, see Chapter in Ross (2014), but for large-scale training, the distribution of total system failures is not independent over workers, making the total noise gradients dependent and key challenge for large-scale training. Moreover, even if there are no issues with the infrastructure, our work is motivated by the prevalence of data augmentation, including hand-chosen augmentations. Since number of parameters is often greater than number of samples, data augmentation improves the generalization capabilities of large-scale models under technical conditions Yang al. (2019b): Heinze-Deml and Meinshausen (2017); Motiian et al. (2017). In particular, Adversarial training a common technique that finds samples that are close training samples but classified for parameter update purposes Addepalli et al. (2022). Unfortunately, computing adversarial samples is often difficult Wong et al. (2020), done using randomized algorithms Cohen al. (2019) and so may introduce dependent (across samples) noise themselves. other words, using adversarial training paradigm, or the so-called inner optimization lead to noise in gradients, which cause or simulate dependent "Byzantine" failures the distributed context since the final parameters are influenced by these samples.
60
50
Mcon. f=
Meon, fal
Mean,
Epoch 50
Figure 2: Tolerance to Byzantine workers for non-robust aggregator (mean).
different class at the current set of parameters, and then use such samples
2

---

Published as a conference paper at ICLR 2024
Available Computational Solutions. Most existing open source implementations of A rely just on (functions of) pairwise distances to filter gradients from workers using suitable neighborhood based thresholding schemes, based moment conditions Allouah et al. (2023a;b); Farhadkhani et al. (2022). While these may be a good strategy when the noise in samples/gradients is somewhat independent, these methods are suhoptimal when the noise is dependent or nonlinear, especially when n is large. Moreover, choosing discrete hyperparameters such as number of neighbors is impractical in our use cases since they hamper convergence of the overall training procedure. To mitigate the suboptimality of existing aggregation schemes, we explicitly estimate a subspace Y spanned by "most" of the gradient workers, and then use this subspace to estimate that a sparse linear combination of gi gradients, acheiving robustness.
We present new optimization based formulation for generalized gradient aggregation purposes in the context of distributed training of deep learning architectures, as shown in Figure 1.
Summary of our Contributions. From the theoretical perspective, we present a simple Maximum Likelihood Based estimation procedure for aggregation purposes, with novel regularization functions. Algorithmically, we argue that any procedure used to solve Flag Optimization can be directly used to obtain the optimal summary statistic Y* for our aggregation purposes. Experimentally, our results show resilience against Byzantine attacks, encompassing physical failures, while effectively managing the stochasticity arising from data augmentation schemes. In practice, we achieve significantly (<v 20%) better accuracy on standard datasets. Our implementation offers substantial advantages in reducing communication complexity across diverse noise settings through the utilization of our novel aggregation function, making it applicable in numerous scenarios.
2 ROBUST AGGREGATORS AS ORTHOGONALITY CONSTRAINED OPTIMIZATION
In this section, we first provide the basic intuition of our proposed approach to using subspaces for aggregation purposes using linear algebra, along with connections of our approach standard eigendecomposition based denoising approaches. We then present our overall optimization formulation in two steps, and argue that it can be optimized using existing methods.
2.1 OPTIMAL SUBSPACE HYPOTHESIS FOR DISTRIBUTED DESCENT
We will use lowercase letters g. to denote vectors, and uppercase letters Y,G to denote matrices. We will use boldfont 1 to denote the vector of all ones in appropriate dimensions. Let 9: E R. be the gradient vector from worker i, and Y E Raxm be an orthogonal matrix representation of a subspace that gradients could live in such that m S p. Now, we may interpret each column of Y as a basis function that act on I E IR", i.e., j-th coordinate of (Y'2 g) for S j S m is the application of j-th basis or column of Y on g. Recall that by definition of dot product, we have that if Y., 1 g, then (YT"g), g) will be close to zero. Equivalently, if E span(Y',, then (Y"g)² yTg will be bounded away from zero, see Chapter 2 in Absil (2008). Assuming that G E Raxp is the gradient matrix of workers. YYTG E R=XP is the reconstruction of G using Y as basis. That is, 7th column of T specifies the amount of gradient from worker i as a function of Y, and high 22 norm of YT g: implies that there basis Y such that Y L gi- So it is easy to see that the average over columns of yY G would give the final gradient for update. Please refer to Section in the supplement for more detail.
2000
Optimal
1750
Suboptimal
Subspace
1000
750
so0
250
0.5
Value Workers
Figure of Explained Minibatches
3:
Distributions Variances on
Explained Variance of worker i. we denote 2; = YF gj E Rm representing the transformation of gradient 9i to 2; using Y. then, 0 < || 2 x = (Y TYT 9, = Y g: is scalar,
and so is equal to its trace tr (gTYY'T 9z). Moreover, when Y is orthogonal, we have 0 S ||æs||a ||Y gill2 |||| lla S ||9:|e l since the operator norm (or largest singular value) ||Y]|2 of Y is most 1. Our main idea is to use | [2. 1 to define the quality of the subspace Y for aggregation, as is done in some previous works for Robust Principal Component Estimation Wright et al. (2009)-
3

---

Published as a conference paper at ICLR 2024
the quantity ||, /1///19 is called Explained/Expresssed variance of subspace Y wrt i-th worker Hein and Bühler (2010); Chakraborty et al. (2017) - we refer to /2/12/1l9sl as the "value" of i-th worker. In Figure 3, we (blue) as opposed to merely choosing the mean gradient (with unit norm) of all workers, then we can increase the value of workers.
from the spike near 1.0 that if we choose the subspace carefully
Advantages of Subspace based Aggregation. We can see that using subspace Y, we can easily: 1. handle different number of gradients from each worker, 2. compute gradient reconstruction YY efficiently whenever Y is constrained to be orthogonal Y = Σ yeys where yj is the i-th column of Y. otherwise have use eigendecomposition of Y to measure explained variance which can be time consuming. Please refer to the supplement for more details on reconstruction and why we require orthogonality constraint. In (practical) distributed settings, the quality (or noise level) of gradients in each worker may be different, and/or each worker may use different batch size. In such cases, handcrafted aggregation schemes may be difficult to maintain, and fine-tune. For these purposes with an Orthogonal Subspace Y, we can simply reweigh gradients of worker i according to its noise level, and/or use 9: E IRn where b; is the batch size i- worker with tr(2, 24) instead.
Why is optimizing over subspaces called "Flag" Optimization? Recent optimization results suggest that we can exploit the finer structure available in Flag Manifold to specify more precisely Monk (1959). For example, Y E R"xm can be parametrized directly subspace of dimension m or as a nested sequence of Yk E TRxm k = 1..... K where my < m S P S n such that sYkn(Y%) C span(Yk+1) with YK E Raxm When m my 1, we have the usual (real) Grassmanian Manifold (quotient of orthogonal group) whose coordinates can be used for optimization, please see Section in Ye al. (2022) for details. In fact, Mankovich al. (2022) used this idea to extend median in one-dimensional vector spaces to different finite dimensional subspaces using the so-called chordal distance between them. In our distributed training context, we use the explained variance of each worker instead. Here, workers may specify dimensions along which gradient information relevant for faster convergence an advantage currently not available in existing aggregation implementations - which may be used for smart initialization also. We use "Flag" to emphasize this additional nested structure available in our formulation for distributed training purposes.
2.2 APPROXIMATE MAXIMUM LIKELIHOOD ESTIMATION OF OPTIMAL SUBSPACE
Now that we can evaluate a subspace on individual gradients gi, we now show that finding subspace Y can be formulated using standard maximum likelihood estimation principles Murphy (2022). Our formulation reveals that regularization is critical for aggregation especially in distributed training. In order to write down the objective function for finding optimal Y, we proceed in the following two steps:
Step 1. Assume that each worker provides single gradient for simplicity. Now, denoting the value of ==[2: 2: we have E [0, 1]. Now by assuming that ey 's are observed information u of worker i by 5f gi
from Beta distribution with = 1 and f 2 (for simplicity), we can see that the likelihood P())) is,
P(u:): (1 - v1) v1) B(1, }
9. g.
(11 2)
where B(a, b) is the normalization constant. Then, the total log-like likelihood of observing gradients 9a as a function of (or vz's) is given by taking the log of product of TP(()))'s 'ss as (ignoring constants),
P
P
log II
P((.)))
Σ
log (P(c.)
log(1 (1- -x).
Step 2. Now we use Taylor's series with constant a > 0 to approximate individual worker log- likelihoodds log(1 u4) x a(l - vz)² a as follows: first, we know that exp Iog(e;) of On the other hand, using Taylor expansion of exp about the origin (so large > 1 is better), we have that exp log(us) ~ 1 log(es) Whence, we have that + log(us) Rs u.a which immediately implies
4

---

Published as a conference paper at ICLR 2024
that log(t;) s av a. So, by substituting the Taylor series approximation of log in Equation 3, we obtain the negative log-likelihood approximation to be minimized for robust aggregation purposes as,
I
P P((.)
(d(1--))-)))
Σ 2 ==1
- -log
where a > 1 is a sufficiently large constant. In the above mentioned steps, the first step is standard. Our key insight using Taylor expansion in (4) with a sufficiently large a eliminate log optimization which are known to be computationally expensive to solve, and instead solve smooth fa. a > 1 norm based optimization problems which can be done efficiently by modifying existing procedures Fornasier et al. (2011).
Extension to general beta distributions, and gradients a > 0, > 0, 9t E Raxk, Note that our derivation in the above two steps can be extended to any beta shape parameters >> 0,3 > 0 there will be two terms in the final negative log- likelihood expression in our formulation (4), one for each a, B. Similarly, by simply using & tr (g] "o""Y"'g 9:) to define value of worker i in equation (2), and then in our estimator in (4), we can easily handle multiple & gradients from a single worker i for Y.
2.3 FLAG AGGREGATOR FOR DISTRIBUTED OPTIMIZATION
It is now easy to see that by choosing 2, in equation (4), obtain the negative loglikelihood (ignoring constants) as (Σa= /1- 10l-g-y-- YY gg) showing that Flag Median can indeed be seen an Maximum Likelihood Estimator (MLE). In particular, Flag Median Mankovich et al. (2022) can be seen as MLE of Beta Distribution with parameters a 1 and 3 = 1.2. Recent results suggest that in many cases, MLE is ill-posed, and regularization is necessary, even when the likelihood distribution is Gaussian Karvonen and Oates (2023). So, based on the Flag Median estimator for subspaces, we propose an optimization based subspace estimator Y for aggregation purposes. We formulate our Flag Aggregator (FA) objective function with respect to Y as a regularized sum of likelihood based (or data) terms in (4) using trace operators tr(.) as the solution to the following constrained optimization problem:
tr (YT yo
A(Y) Y-TY=
min
+ AR(Y)
(5)
11
where À >>> is a regularization hyperparameter. In analysis, and implementation, we provide support for two possible choices for RY)):
(I) Mathematical norms: R(Y') can be a form of norm- norm-based regularization other than || since it is constant over the feasible set (5). For example, it could be convex norm with efficient convex approximation using trace functions such as, i.e. element-wiser E Σj=1 [Yayl tr(Ytt
where 5 > 0 is the tolerance parameter for regularization subsumed within X,
(2) Data-dependent norms: Following our subspace construction in Section 2.1, we may choose
R(Y) p- Ei / nnYT (0:)()9-))"" y))")) where D llg. 9 denotes the Di,
distance between gradient vectors g.. 9, from workers i, j. Intuitively, the pairwise terms in our loss function (5) favors subspace that also reconstructs the pairwise vectors g. 1 gy that are close to each other. So, by setting x = Opp), that is, the pairwise terms dominate the objective function in (5). Hence, À regularizes optimal solutions Y* of (5) to contain g with low pairwise distance in its span similar in spirit to AggregaThor in Damaskinos al. (2019).
Convergence of Flag Aggregator (FA) Algorithm 1. With these, we can state our main algorithmic result showing that our FA (5) can be solved efficiently using standard convex optimization proof techniques. In particular, in supplement, we present a smooth Semi-Definit Programming (SDP) relaxation of FA in equation (5) using the Flag structure. We use the SDP relaxation of the MLE in (4) to argue that solving FA problem may be tractable since SDPs can be solved efficiently from the theoretical standpoint. With this, we can view the IRLS procedure in I as solving the low rank parametrization of the smooth SDP relaxation, thus guaranteeing fast convergence to second order optimal (local) solutions. Importantly, our SDP based proof works for any degree of approximation of the constant a in equation (4) and only relies on smoothness of the loss function wrt Y. although speed of convergence is reduced for higher values of a 2, see Chen et al. (2020a).
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 Distributed SGD with proposed Flag Aggregator (FA) with elementwise & regularization
Input: Number of workers p. loss functions 42, fps per-worker minibatch size B, learning rate schedule 02e, initial parameters Wo, number of iterations T
Output: Updated parameters wy from any worker for ( 1 to T do
for p = 1 to p in parallel on machine p do
L Select a minibatch: 1p,1,t, fp.2,tt....p.....
Pp.t t E/
(w--1)
G, + {gr....... .9p.t) // Parameter Server zeceives gradients from p workers
Y + SVDm (G.) with Ge is the Cholesky factor of G,D,G" Al where I R=x= identity matrix // Do IRLS at the Pazameter Server for Obtain gradient direction de de = ,YYY, G,1 Compute, Send de to all machines for p 1 to p parallel on machine p do update model: W2 < W4-11 04
Return WT
IRLS procedure in Algorithm 1. IRLS is standard optimization technique in which we substitute general norm functions with weighted euclidean norm functions, The key advantage of this substitution is that may obtain closed form solution to the substituted euclidean norm version. Starting from (random) feasible point Youd. the weights are calculated with the general norm functions. Then, the solution Ynew the weighted euclidean norm optimization is obtained. This corresponds to one iteration in IRLS and repeating the above step with this new Yne corresponds to the IRIS procedure. For aggregation purposes in FA, in each iteration the square root function or more generally, the a-th root function in equation (4) is replaced by reweighted quadratic function which has a closed-form solution given by SVD.
How is FA aggregator different from (Bulyan and Multi-Krum)? Bulyan is strong Byzantine resilient gradient aggregation rule for p 2 4f + where p is the total number workers and f is the number of Byzantine workers. Bulyan is two-stage algorithm. In the first stage, a gradient aggregation rule R like coordinate-wise median Yin et al. (2018) or Krum Blanchard et al. (2017) recursively used to select 0 p 2f gradients. The process which is closest to R's output (e.g. for Krum, this would be the gradient with the top score, and hence the exact output of R). The chosen gradient is removed from the received set and added to the selection set S repeatedly until |S| 0. The second stage produces the resulting gradient. If 3= 2f, each coordinate would be the average of 3-nearest to the median coordinate of the gradients in S. In matrix terms, if we consider S E R as matrix with each column having one non-zero entry summing 1, Bulyan would return RGLU( where 1, RTm the vector of all ones, while FA would return !Yy"G1, Importantly, the gradient matrix is being in Bulyan, but left-multiplies like discrepancy, in supplement we show that by observing the optimality conditions of (5) wrt Y, we show that yY G can be seen as a right multiplication by a matrix parametrized by lagrangian multipliers associated with the orthogonality constraints in (5). This means should be possible to combine both approaches for faster aggregation.
R to select gradient vector gi
FA, before getting averaged. While this may seem
3 EXPERIMENTS
In this section, we conduct experiments to test our proposed FA in the context of distributed training in two testbeds. First, to test the performance of our FA scheme solved using IRLS (Flag Mean) on standard Byzantine benchmarks. Then, to evaluate the ability of existing state-of-the-an gradient aggregators we augment data via two techniques that can be implemented with Sci-kit package.
Implementation Details. We implement FA in Pytorch Paszke et al. (2019), which is popular but does not support Byzantine resilience natively. We adopt the parameter server architecture and employ Pytorch's 's distributed RPC framework with TensorPipe backend for machine- machine-to-maching to-machine communication. We extend Garfield's Pytorch library Guerraoui al. (2021) with FA and limit our

---

Published as a conference paper at ICLR 2024
IRLS convergence criteria small error, 10-10 10, iterations of flag mean for SVD calculation.
We set m p+1
3.1 SETUP
Baselines: We compare FA to several existing aggregation rules: (1) coordinate-wise Trimmed
Mean Yin et al. (2018) (2) coordinate-wise Median Yin et al. (2018) (3) mean-around-mediig (MeaMed) Xie et al. (2018a) 8a) (4) Phocas Xie et al. (2) (5) Multi-Krum Blanchard et al. (2017) (6) Bulyan El Mhammi et al. (2018). In the supplement, also compare FA to using the (7) top-m principal components of the gradient matrix, (8) RESAM Farhadkhani et al. (2022), and (9) CGE Gupta al. (2021) as baselines.
Accuracy: The fraction of correct predictions among all predictions, using the test dataset (top-1 cross-aceuracy).
Testbed: We used servers as our experimental platform. Each server has Intel(R) (eon(R) Gold 6240 18-core CPU @ 2.60GHz with Hyper-Threading and 384GB of RAM. Servers have Tesla V100 PCIe 32GB GPU and employ a Mellanox ConnectX-5 100Gbps NIC to connect to a switch. We use one the servers the parameter server and instantiate 15 workers on other servers, each hosting 5 worker nodes, unless specified differently in specific experiments. For the experiments designed to show scalability, we instantiate 60 workers.
We focus on the image classification task since it is a widely used task for benchmarking in distributed training Chilimbi al. (2014). We train ResNet-18 He et al. (2016) on CIFAR-10 Krizhevsky (2009) which has 60,000 32 x 32 color images in 10 classes. For the scalability experiment, we train a CNN with two convolutional layers followed by two fully connected layers on MNIST LeCun and Cortes (2010) which has 70,000 28 28 grayscale images in 10 classes. We also run another set of experiments on Tiny ImageNet Le and Yang (2015) in the supplement. We use SGD as the optimizer, and cross-entropy to measure loss. The batch size for each worker is 128 unless otherwise stated. Also, we use a learning decay strategy where we decrease the learning rate by factor of 0.2 every 10 epochs.
Dataset and model:
Threat models: We assess the performance of FA in the presence of various categories of Byzantine workers. These categories encompass scenarios where workers either transmit gradients chosen uniformly at random in [0, 1) with μ 0.5 and scenarios serve as representations of errors in the physical settings. Additionally, workers may also evaluate FA when
/ provide incomplete tensors. These
employ nin-linear augmented data, as described below. In the supplement, Byzantine workers send I (Ox amplified sign-flipped gradients Allen-Zhu et al. (2021) or send the gradients based on the Fall of Empires attack with 0.1 Xie et al. (2020).
Evaluating resilience against nonlinear data augmentation: In order to induce Byzantine behavior in our workers utilize ODE solvers approximately solve 2 non-linear processes, Lotka Volterra Kelly (2016) and Arnold's Cat Map Bao and Yang (2012), as augmentation methods. Since the augmented samples are deterministic, albeit nonlinear functions of training samples, the "noise" is dependent across samples.
In Lotka Volterra, we use the following linear gradient transformation of 2D pixels:
(x, v) - (oez Bay, day 79),
where a, y y and 6 are hyperparameters. We choose them to be 3. 3. - and -1 respectively.
Second, we nonsmooth transformation called Arnold's Cat Map data augmentation scheme. Once again, the map can be specified using a two-dimensional matrix as,
2x + y x
(x.
mod 1,
N
where mod represents the modulus operation, x and y are the coordinates or pixels of images and N is the height/width of images (assumed to be square). We also used smooth approximation of the Cat Map obtained by approximating the mod function as,
1 (x, v) + n ((1 cxp(-mmmma log(a)))) (1 exp(-m log(oz)
2x +
+ y
7

---

Published as a conference paper at ICLR 2024
Flag Aggregator
Multi-Krum
Median
Phocas
Bulyan
MeaMed
Trimmed Mean
50
Accuracy (N)
Accuracy
40
40-
300
30
10
10
10
20
20
30
10
30
40
Epech
(a) ==
(b) ʃ
(c) ʃ
Figure 4: Tolerance to the number of Byzantine workers for robust aggregators for batch size 128.
60
50
Accuracy (96)
Accuracy (N)
-00
40
40
30-
30
30
20
10
10-
30
30
10
20
20
Epoch
Epoch
(a) bs 64
bs 128
(c) bs 192
Figure 5: Marginal utility of larger batch sizes under a fixed noise level f 3.
where 0i
2mtz 02 -ب, and m is the degree of approximation, which we choose to be 0.95 in our data augmentation experiments. Please refer the appendix F.3 where we explain our implementation for nonlinear data augmentation routines.
3.2 RESULTS
Tolerance to the number of Byzantine workers: In this experiment, we show the effect of Byzantine behavior on the convergence of different gradient aggregation rules in comparison to FA. Byzantine workers send uniformly random gradients in [o, 1] with coordinatewise mean 0.5 and standard
deviation I2 and we vary the number of these workers from to 3. Figure 4 shows that for some rules, i.e. Trimmed Mean, the presence of even single Byzantine worker has catastrophic impact. For other rules, the number of Byzantine workers increases, filtering out the outliers becomes more challenging because the amount of noise increases. Regardless, FA remains more robust
We empirically verified the batch size required to identify our optimal Y* the FA matrix at each iteration. In particular, we fixed the noise level to 3 Byzantine workers and varied batch sizes. Similar to the previous experiment, Byzantine workers send uniformly random gradients. We show the results in Figure 5. Our results indicate that, in cases where larger batch size is training requirement, FA achieves a significantly better accuracy compared to the existing state of the art aggregators. This may useful some large scale vision applications, for more details. Empirically, we can already see that our spectral relaxation to identify gradient subspace is effective in practice in all our experiments.
Marginal utility of larger batch sizes under fixed noise level:
Keskar al. (2017); You al. (2019)
Tolerance to communication loss: To analyze the effect of unreliable communication channels between the workers and the parameter server on convergence, physical link between some of the workers and the parameter server randomly drops percentage of packets. Here, we set the loss rate three links to 10% i.e., there are Byzantine workers in our setting. The loss is introduced using the netem queuing discipline in Linux designed to emulate the properties wide area networks Hsieh et al. (2017). The two main takeaways in Figure 6a are:
design an experiment where the
8

---

Published as a conference paper at ICLR 2024
Flng Aggregator
Bulyan
Multi-kruu
MenMed
Median
Iimmed Mean
Phocas
70
Spoch
Epoch
Eooch
Eooch
(a) 15, =
(b) 11,f=
(c) 13, =
(d)
15,
Figure 6: We present results under two different gradient attacks. The attack (a) corresponds to dropping 10% of gradients from / workers. The attacks in (b)-(d) correspond to generic f workers sending random gradient vectors, i.e. we fix the noise level while adding more workers.
1. FA converges to a significantly higher accuracy than other aggregators, and thus is more robust to unreliable underlying network transports.
2. Considering -accurrycc for comparison, FA reaches a similar accuracy in less total number of training iterations, and thus is more robust to slow underlying network transports.
Analyzing the marginal utility of additional workers. To see the effect of adding more workers to fixed number of Byzantine workers, we ran experiments where we fixed f. and increased p. Our experimental results shown in Figures 6b-6d indicate that our FA algorithm possesses strong resilience property for reasonable choices of p.
The effect of having augmented data during training in Byzantine workers: Figure 7 shows FA can handle nonlinear data augmentation much more stable fashion. Please see supplement for details on the level of noise, and exact solver settings that were used to obtain augmented images.
50
2
Top-1 Accuracy (SG)
60-
Accuracy
50
80
1Ap-15//e3
Kuhi-Krum
Bulyan
IA 1kp=01//12
MasMed
Median
10
Nue Krum
20
30
20
30 Epoch
15
20
Figure 7: Accuracy Figure 8: CIFAR-10 with Figure 9: Scaling FA to using augmented data in ResNet-18, = 7, and f larger setups workers
The effect of the regularization parameter in FA: The data-dependent regularization parameter in FA provides flexibility in the loss function to cover aggregators that benefit from pairwise distances such as Bulyan and Multi-Krum. To verify whether varying À can interpolate Bulyan and Kulti-Krum, we change À in Figure 8. We can when FA improves or performs similarly for range of X. Here, we set p and f to satisfy the strong Byzantine resilience condition of Bulyan, i.e, p 2 4 + 3.
Scaling out to real-world situations with more workers: In distributed MI, p and are usually large. To test high-dimensional settings commonly dealt in Semantic Vision with our FA, we used ResNet-18. Now, specifically test the scalability FA, we fully utilized our available GPU servers and set up to 60 workers (up to f = 14 Byzantine) with the MNIST dataset and simple CNN with two convolutional layers followed by two fully connected layers (useful for simple detection). Figure 9 shows evidence that FA is feasible for larger setups.
4 CONCLUSION
In this paper we proposed Flag Aggregator (FA) that can be used for robust aggregation of gradients in distributed training. FA is optimization-base subspace estimator that formulates aggregation as a Maximum Likelihood Estimation procedure using Beta densities. We perform extensive evaluations of FA and show it can be effectively used in providing Byzantine resilience for gradient aggregation. Using techniques from convex optimization, we theoretically analyze FA and with tractable relaxations show its amenability to be solved by off-the-shelf solvers first-order reweighing methods.

---

Published as a conference paper at ICLR 2024
5 ACKNOWLEDGEMENTS
We are grateful to UIC-ICR start-up funds and Discovery Partners Institute for supporting our work. We thank anonymous ICLR 2024 reviewers for their time, suggestions, and constructive criticism throughout the review process which ultimately led to an improved version of our submission.
REFERENCES
Michel Grabisch, Jean-Luc Marichal, Radko Mesiar, and Endre Pap. Aggregation functions, volume 127. Cambridge University Press, 2009.
Sivaraman Balakrishnan, Simon S. Du, Jerry Li, and Aarti Singh. Computationally efficient robust sparse estimation in high dimensions. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 169-212. PMLR, 07-10 Jul 2017. URL https: https:://ptceeeeeeeehe /prcceedcccceeesssseeoe.es. balakria ahranishnan11 17 html.
Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart. Outlier-robust nigh-dimensional sparse estimation via iterative filtering. Advances in Neural Information Processing Systems, 32, 2019.
Yu Cheng, Ilias Diakonikolas, Rong Ge, Shivam Gupta, Daniel M. Kane, and Mahdi Soltanolkotabi. Outlier-robust sparse estimation via non-convex optimization. Advances Neural Information Processing Systems, 2022.
Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Ankit Pensia, and Thanasis Pittas. Robust sparse mean estimation via sum of squares. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 4703-4763, PMLR, 02-05 Jul 2022. URL https: http:///pooeeeeeeeeeee html.
mlr. mirr.pres// v17 wtt.ppees//iB///aaaioooii.. wtw./////aaaoooooss2222222
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 (3):211-252, 2015,
doi: 1007/s| 1263-015-0816-y.
Konstantinos I Tsianos and Michael G Rabbat. Distributed strongly convex optimization. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 593-600. IEEE, 2012.
Tao Yang, Xinlei Yi, Junfeng Wu, Ye Yuan, Di Wu, Ziyang Meng, Yiguang Hong, Hong Wang, Zongli Lin, and Karl H Johansson. A survey of distributed optimization. Annual Reviews in Control, 47:278-305 2019a.
Peva Blanchard, EI Mahdi EI Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Proceedings of the 31st International Conference on Neural Information Processing Systems. NIPS' 17, page 118-128. Curran Associates Inc., 2017. ISBN 97815 10866666.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentums. International Conference on Machine Learning, pages 6246-6283. PMLR, 2022.
Leonardo Bautista- Bautista-Gomez, Ferad Zyulkyarov, Osman Unsal, and Simon Mclntosh-Smithh Unprotected computing: A large-scale study of dram raw error rate on a supercomputer. In SC '16: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 645-655, 2016. doi: 10. 19.1009//..211.54..
Bianca Schroeder and Garth A. Gibson. Disk failures in the real world: What does mttf of 1,000,000 hours mean to you? In Proceedings of the 5th USENIX Conference on File and Storage Technologies, FAST '07 page 1 1-es, USA, 2007. USENIX Association.
10

---

Published as a conference paper at ICLR 2024
Phillipa Gill, Navendu Jain, and Nachiappan Nagappan. Understanding network failures in data centers: Measurement, analysis, and implications. SIGCOMM Comput. Commun. Rev, 41(4): 350-361, aug 2011. ISSN 0146-4833. doi: 10.1 10.14552043366420188777 https:/// 1111111111/224111111
201 8477.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: /prpcee/ ings neeereiiiiinnnnnnnnisseee nwwrips.uee.o httpps.cpppppeeeeeeeeeeeppppeeee 2019 (o11//Lleeecccs911n1.
8 6bbbcaffbaeeeld Paper.pdf.
Guosai Wang, Lifei Zhang, and Wei Xu. What can we learn from four years of data center hardware failures? In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 25-36, 2017. doi: 10.1119/DNN.207..00
Devesh Tiwari, Saurabh Gupta, James Rogers, Don Maxwell, Paolo Rech, Sudharshan Vazhkudai, Daniel Oliveira, Dave Londo, Nathan DeBardeleben, Philippe Navaux, Luigi Carro, and Arthur Bland. Understanding gpu errors on large-scale hpc systems and the implications for system design and operation. In 20/5 IEEE 2/st International Symposium on High Performance Computer Architecture (HPCA), pages 331 -322, 2015. doi: 10.1109/HPCA.2015. 70766044
Bin Nie, Devesh Tiwari, Saurabh Gupta, Evgenia Smirni, and James H. Rogers. A large-scale study of soft-errors on gpus the field. 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA), pages 519-530, 2016. doi: 10. 10.1109/HCC.22116..
Sheldon M Ross. Introduction probability models. Academic press, 2014.
Fanny Yang, Zuowen Wang, and Christina Heinze-Deml. Invariance-inducing regularization using worst-case transformations suffices to boost accuracy and spatial robustness. In H. Wallach, H. Larochelle. A. Beygelzimer, F. d'Alché-Buc. E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates. neurips cc pdf.
Inc.. 2019b. URL
1d01bd2el
Christina Heinze-Denn and Nicolai Meinshausen. Conditional variance penalties and domain shift robustness, 2017. URL https:tppp........... http://wwwwwv.....aaa/ abs// /tt.///1....1.1.11
Saeid Motiaa, Marco Piccirilli, Donald A. Adjeroh, and Gianfranco Doretto. Unified deep supervised domain adaptation and generalization. In IEEE International Conference on Computer Vision (ICCV), 2017.
Sravanti Addepalli. Samyak Jain, et al. Efficient and effective augmentation strategy for adversarial training. Advances in Neural Information Processing Systems, 35:1488-1501, 1501, 2022.
Eric Wong, Leslie Rice, and J Zico Kolter. Fast is better than free: Revisiting adversarial training. arXiv preprint arXiv:2001.00 200499000003994,, 2020.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310-1320, PMLR, 2019.
Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Distributed learning with curious and adversarial machines. arXiv preprint arXiv:2302.0477 2023a.
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In International Conference on Artificial Intelligence and Statistics, pages 1232-13000 1300. PMLR, 2023b.
P-A Absil. Optimization algorithms on matrix manifolds. Princeton University Press, 2008
John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Advances in neural information processing systems, 22, 2009.

---

Published as a conference paper at ICLR 2024
Matthias
Hein and Thomas Bühler. An inverse power method for nonlinear cigenproblems with applications 1-spectral clustering and sparse pea. Advances in neural information processing systems, 23, 2010.
Rudrasis Chakraborty, Soren Hauberg, and Baba C Vemuri. Intrinsic grassmann averages for online linear and robust subspace learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 6196-6204, 2017.
D. Monk. The geometry of flag manifolds. 253-286, 1959. doi: https://doi.org/10.. 1ttp://11111///m//222922222222 URL httppt:://oddtaathsttteee mnlinelibrary wiley. com/ doi http://///....////////a////e//// 9..iss--92..... 253.
Procoodddd......iiiii Proceedings of the London Mathematical Society, s3-9(2):
Ke Ye, Ken Sze-Wai Wong, and Lek-Heng Lim. Optimization on flag manifolds. Mathematical Programming, 194(1-2):621-666)) 2022.
Nathan Mankovich, Emily J King, Chris Peterson, and Michael Kirby. The flag median and flagirls. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 10339-10347, 2022.
Kevin P Murphy. Probabilistic machine learning: introduction. MIT press, 2022.
Massimo Fornasier, Holger Rauhut, and Rachel Ward. Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM Journal on Optimization, 2144) 2011.
Toni Karvonen and Chris J Oates. Maximum likelihood estimation in gaussian process regression is ill-posed. Journal of Machine Learning Research, 24(120): 2023.
Georgios Damaskinos, El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, and Sébastien Rouault. Aggregathor: Byzantine machine learning via robust gradient aggregation. Proceedings of Machine Learning and Systems, 1:81-106, 2019.
Yuxin Chen, Yuejie Chi, Jianqing Fan, Cong Ma, and Yuling Yan. Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization. SIAM journal on optimization, 30(4):3098-31) 3121, 2020a.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Syzantine-robust distributed learning: Towards optimal statistical rates. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseurch, pages 5650-5659, PMLR, 10-15 Jul 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32, 2019.
Rachid Guerraoui, Arsany Guirguis, Jérémy Plassmann, Anton Ragot, and Sébastien Rouault. Garfield: System support for byzantine machine learning (regular paper). In 2021 51st Annual IEEE/FFI International Conference on Dependable Systems and Networks (DSN), pages 39-51, 2021. doi: 10. 111900NN49987..00
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd, 2018a.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Phocas: dimensional byzantine-resilient stochastic gradient descent, 2018b.
El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in Byzantium. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3521-3530. PMLR, 10-15 Jul 2018.
Nirupam Gupta, Shuo Liu, and Nitin H. Vaidya. Byzantine fault-tolerant distributed machine learning using stochastic gradient descent (sgd) and norm basdd comparative gradient elimination (cge), 2021.
12

---

Published as a conference paper at ICLR 2024
Trishul Chilimbi, Yutaka Suzue, Johnson Apacible, and Karthik Kalyanaraman. Project adam: Building am efficient and scalable deep learning training system. In Proceedings of the 11th USENIX Conference Operating Systems Design and Implementation, OSDI' 14, page 571-582, USA, 2014.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), doi: 10.1109/CVPR.2016.99.
pages 770-778, 2016.
Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009. URL https: //www. cs toronto, http//kkii/eeeennnnin features 2009- TR. pdf.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010. URL httpp:/yaann lecun. com/ exdb hondst/nns//......m
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge, 2015.
Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex stochastic gradient descent. 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
net forum? i id=PbEHqvEtes..
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Ryan P. Adams and Vibhav Gogate, editors, Proceedings of The 35th Uncertainty Artificcal Intelligence Conference, volume 115 of Proceedings of Machine Learning Research, pages 261-270. PMLR, 22-25 Jul 2020. URL https: pptppeeieeee..... m1 mlr.press/ http//111///ieeee xi000a........mm httll.
David Kelly. Rough path recursions and diffusion approximations. The Annals Applied Probability, 26( (6(1)) 461, 2016.
Jianghong Bao and Qigui Yang. Period of the discrete arnold cat map and general cat map. Nonlinear Dynamics, 132)::365-1375. 2012.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017. URL https: //opnrevie//er.eiee.... net/ forum?id wwerumidd=HooyRRll
Yang You, Jonathan Hseu, Chris Ying, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large-bater batch training for Istm and beyond. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC '1, 2019.
Kevin Hsieh, Aaron Harlap, Nandita Vijaykumar, Dimitris Konomis, Gregory R. Ganger, Phillip B. Gibbons, and Onur Mutlu. Gaia: Geo-distributed machine learning approaching lan speeds. In Proceedings of the 14th USENIX Conference on Networked Systems Design and Implementation, page 629 029-647,40 2017.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Detox: A bedundancy-bbsed framework for faster and more robust gradient aggregation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bor Buce E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems, volume 32, 2019.
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. DRACO: Byzantine resiliet distributed training via redundant gradients. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 903-912. PMLR, 10-15 Jul 2018
13

---

Published as a conference paper at ICLR 2024
Christian Kümmerle, Claudio Mayrink Verdun, and Dominik Stöger. Iteratively reweighted least squares for basis pursuit with global linear convergence rate. Advances Neural Information Processing Systems, 34:2873-288 2886, 2021.
Deeksha Adil, Richard Peng, and Sushant Sachdeva. Fast, provably convergent irls algorithm for p-norm linear regression. Advances in Neural Information Processing Systems, 32, 2019.
Chris M. Bishop. Training with noise is equivalent to tikhonov regularization. Neural Computation, 7(1):088-116, 1995. doi: (11166//eco.1995 1995.7.11100.
Zhun Zhong, Liang Zheng, Guoliang Kang. Shaozi Li, and Yi Yang. Random erasing data augmentation. Proceedings of the AAAI Conference on Artificial Intelligence, 34:13001-13008, Apr. 2020, doi: 10. 10.1609/aaai.v34kt AAAI/ MAAI/article/vieer /700.
URL https:/ /ojs. aaai org/ index.niix. php/
Terrance Vries and Graham W Tayllor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv:
2017.
Yash Goyal, Tejas Khot, Douglas Summers- Dhruv Batra, and Devi Parikh. Making the in vqa matter: Elevating the role of image understanding in visual question answering. International Journal of Computer Vision 127:398-45 414, 2017.
Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu. Uniter: Universal image-text representation learning. In ECCV, 2020b.
Yu Huang, Chenzhuang Du, Zihui Xue, Xuanyao Chen, Hang Zhao, and Longbo Huang. What makes multimodal learning better than single (provably). NeurIPS, 2021.
Miguel Sousa Lobo, Lieven Vandenberghe, Stephen Boyd, and Hervé Lebret. Applications of second-order cone programming. Linear algebra and its applications, 284(1-3):193-228, 1998.
Srinadh Bhojanapalli, Nicolas Boumal, Prateek Jain, and Praneeth Netrapalli. Smoothed analysis for low-rank solutions to semidefinite programs in quadratic penalty form. In Conference On Learning Theory, pages 9243-3270 PMLR, 2018.
Chungen Shen, Yunlong Wang, Wenjuan Xue, and Lei-Hong Zhang. An accelerated active-set algorithm for quadratic semidefinite program with general constraints. Computational Optimization and Applications, 78(1):1 4-,2, 2021.
Ariel Kleiner, Ali Rahimi, and Michael Jordan. Random conic pursuit for semidefinite programming. Advances in Neural Information Processing Systems, 23, 2010.
Hans Mittelmann. An independent benchmarking of sdp and soep solvers. Programming, 95(2):407-430, 2003.
Mathernatiaal
Robert J Vanderbei and Hande Yurttan. Using loqo to solve second-order cone programming problems. Constraints, 1(2), 1998.
Hezhi Luo, Xiaodi Bai, Gino Lim, and Jiming Peng. New global algorithms for quadratic programming with few negative eigenvalues based on alternative direction method and convex relaxation. Mathematical Programming Computation, 11(1):119-17,, 2019.
A Shapiro and JD Botha. Dual algorithm for orthogonal procrustes rotations. SIAM journal on matrix analysis and applications, 933):388-33 33333,3,, 1988.
Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60, 2018.
14

---

Published as a conference paper at ICLR 2024
Prateck Jain, Purushottam Kar, et al. Non-convex optimization for machine learning. Foundations and Trends in Machine Learning, 10(3-4):142300 2017.
Liqun Qi. Some simple estimates for singular values of a matrix. Linear algebra and its applications, 56:105-119, 1984.
Olga Klopp, Karim Lounici, and Alexandre B. Tsybakov. Robust matrix completion, 2016.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kem, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272. 2020. doi: 10.1038//41522-09---11
Amedeo Sapio, Marco Canini, Chen- Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan Ports, and Peter Richtárik. Scaling distributed machine learning with [In-Network] aggregation. In 18th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pages 785-808, 2021.
ChonLam Lao, Yanfang Le, Kshiteej Mahajan, Yixi Chen, Wenfei Wu, Aditya Akella, and Michael Swift. {ATP): In-network aggregation for multi-tenant learning. In /8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 21), pages 741-761, 2021.
Pat Bosshart, Glen Gibb, Hun-Seok Kim, George Varghese, Nick McKeown, Martin Izzard, Fernando Mujica, and Mark Horowitz. Forwarding metamorphosis: Fast programmable match-action processing in hardware for sdn. In Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, SIGCOMM '13, page 99-1 10, New York, NY, USA, 2013. Association for Computing Machinery, ISBN 9781 450320566. doi: 10.1145/2486001. 2486011 URL https: /ooi. org/ 10.1145/2 0200/11866601100 (w1.8860012288880 2486011.
N McKeown. Pisa: Protocol independent switch architecture. In P4 Workshop, 2015.
Yifan Yuan, Omar Alama, Jiawei Fei, Jacob Nelson, Dan RK Ports, Amedeo Sapio, Marco Canini, and Nam Sung Kim. Unlocking the power of inline (Floating-Poing operations on programmable switches. In 19th USENIX Symposium Networked Systems Design and Implementation (NSDI 22), pages 683-700, 2022.
Zhourui Song, Zhenyu Liu, and Dongsheng Wang. Computation error analysis of block floating point arithmetic oriented convolution neural network accelerator design. Proceedings of the Thirty-Secone AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI 18/IAAI 18/EAAI 18. AAAI Press, 2018. ISBN 978- 978-1-57735-8800
15

---

Published as a conference paper at ICLR 2024
A BACKGROUND AND RELATED WORK
Researchers have approached the Byzantine resilience problem from two main directions. In the first class of works, techniques such as geometric median and majority voting try to perform robust aggregation Damaskinos et al. (2019), Bernstein et al. (2019), Blanchard et al. (2017). The other class of works uses redundancy and assigns each worker redundant gradient computation tasks Rajput et al. (2019), Chen et al. (2018).
From another aspect, robustness can be provided on two levels. In weak Byzantine resilience methods such as Coordinate- wise median Yin et al. (2018) and Krum Blanchard et al. (2017), the learning is guaranteed to converge. In strong Byzantine resilience, the learning converges to a state as the system would converge in case no Byzantine worker existed. Draco Chen et al. (2018) and Bulyan El Mhamdi et al. (2018) are examples of this class, Convergence analysis of iterated reweighing type algorithms has been done for specific problem classes. For example, Kümmerle et al. (2021); Adil et al. (2019) show that when IRLS is applied for sparse regression tasks, the iterates can converge linearly. Convergence analysis of matrix factorization problems using IRLS Stype schemes has been proposed before, see Fornasier et al. 1); Chen et al. (2020a).
is well known that data augmentation techniques help in improving the generalization capabilities of models by adding more identically distributed samples to the data pool. Yang et al. (2019b); Heinze-Dere Deme and Meinshausen (2017); Motiian et al. (2017). The techniques have evolved along with the development of the models, progressing from the basic ones like rotation, translation, cropping, flipping, injecting Gaussian noise Bishop (1995) etc., to now the sophisticated ones (random erasing/masking Zhong et al. (2020), cutout De and Taylor (2017) etc.). Multi-moda learning setups Goyal et al. (2017); Chen et al. (2020b); Huang et al. (2021), use different ways to combine data of different modalities (text, images, audio etc.) to train deep learning networks.
B TRACTABILITY OF COMPUTING FLAG AGGREGATORS
In this section, we characterize the computational complexity of solving the Flag Aggregation problem via IRLS type schemes using results from convex optimization. First, we present tight convex relaxation of the Flag Median problem by considering it as an instantiation of rank constrained optimization problem. We then show that we can represent our convex relaxation as a Second Order Cone Program which can be solved using off-the-shelf solvers Lobo et al. (1998). Second, we argue that approximately solving such rank constrained problems in the factored space is an effective strategy using new results from Bhojanapalli et al. (2018 8) which builds on asymptotic convergence in Fornasier et al. (2011). Our results highlight that the Flag Median problem can be approximately solved using smooth optimization techniques, thus explaining the practical success of an IRLS type iterative solver.
Interpreting Flag Aggregator (equation 5 in the main paper) in the Case 1. We first present a convex reformulation of the Flag Aggregator problem (5) in the case when the number of subspaces (or columns) is equal to 1. To make the exposition easier, we will also assume that À O. With these assumptions, and using the fact that l/lll2 = 1, each term in the objective function of our FA aggregator in (5) can be rewritten as,
V (1-()))))))- V (1 "...") B.vll2
(6)
where we use the notation 9r = -gt// [| to denote the normalized worker gradients, Ruxn is the n n identity matrix, and B, is the square root of the matrix -- g.g. Observe that we can rewrite all the terms in equation (5) in the main paper in a similar fashion as in (6). Furthermore, by relaxing the feasible set to the n- -all given by {y E R ||y/|2 S 1). we obtain Second Order Cone Programming (SOCP) relaxation of our FA problem in (5). SOCP problems can be solved using off-the-shelf packages with open source optimization solvers for gradient aggregation purposes in small scale settings, that is, when the number of parameters n ss 10a Shen et al. (2021); Kleiner et al. (2010); Mittelmann (2003). Our convex reformulation immediately yields insights on why reweighing type algorithm that was proposed in Mankovich et al. (2022) works well in practice- for example see Section 3 in Vanderbei and Yurttan (1998) in which various smoothing functions similar to the Flag Median (square) based smoothing are listed options. More generally, our SOCP
16

---

Published as a conference paper at ICLR 2024
relaxation shows that if the smoothed version can be solved in closed form (or efficiently), then reweighing based algorithm can be safely considered a viable candidate for aggregation purposes.
Tractable Reformulations when > 1 for Aggregation Purposes. Note that for any feasible Y such that Y"y = I, we have that the tr(Y) = m.
Remark B.1 (Parametrizing Subspaces using Y.). This assumption is without loss of generality, To see this, first note that in general, a (nondegenerate) subspace S of a vector space V/ is defined as subset of V that is closed under linear combinations. Fortunately, in finite dimensions, we can represent S as a rectangular matrix M by Fundamental theorem of linear algebra. So, we simply use Y to represent the basis of this matrix M that represents the subspace S in our FA formulation.
Using this, we can rewrite each term in the objective function of our FA aggregator in equation (5) in the main paper as,
1 m 19:
V tr
YT
where M, M,, 1,...,P is symmetric matrix with at most one negative eigenvalue. Optimization problems involving quadratic functions with negative eigenvalues can be solved globally, in some cases Luo et al. (2019); Shapiro and Botha (1988). We consider methods that can efficiently (say in polynomial running time in r)) provide solutions that are locally optimal. order to do so, we consider the Semi Definite programming relaxation obtained by introducing matrix Z 2 0 E Ram nm to represent the term YY", constrained to be rank one, and such that tr(Z) = m.
By using vec(Y) RT to denote the vector obtained by stacking columns of Z, when 1, obtain a trace norm constrained SOCP, Importantly, objective function can be written as a sum of terms of the form,
vec(YYy @ M.) vec(Y)= (ZT (I ()),
(8)
where & denotes the usual tensor (or Kronecker) product between matrices.
Properties of lifted formulation in (8). There are some advantages to the loss function as specified in our reformulation (8). First, note that then our relaxation coincides with the usual trace norm based -iilaan- relaxation used for solving Max-Cut problem with approximation guarantees Goemans and Williamson (1995). A Albeit, our objective function not linear, and to our knowledge, it is not trivial extend the results to nonlinear cases such as ours in (8). Moreover, even when M, 2 O, the v makes the relaxation nonconvex, so it is not possible to use off-the-shelf disciplined convex programming software packages such CVXPy Diamond and Boyd (2016); Agrawal et al. (2018). Our key observation is that away from 0, v- a differentiable function. Hence, the objective function in (8) is differentiable with respect Z.
Remark B.2 (Using SDP relaxation for Aggregation.). In essence, if the optimal solution Z* to the SDP relaxation is a rank one matrix, then by rank factorization theorem, Z be written as Z" = vec(Y") (Y*)" where vec(Y*) E Rmmx1 So, after reshaping, we can obtain our optimal subspace estimate Y E Rm for aggregation purposes. In the case the optimal Z* is not low rank, we simply use the largest rank one component of 2", and reshape it to get Y*.
C THE NECESSITY OF ORTHOGONALITY CONSTRAINT FOR EFFICIENCY
This necessity is folklore result that can be found in various places, but provide formal proof here for completeness. Given the gradient matrix G and subspace Y. projection of onto Y is given by P= G. The entry ,; has the amount (measured using dot product) of g, along yj- So, YP gives us the reconstruction of G using each column of Y. By reconstruction we mean that the matrix "Y"G G is the best (or optimal) m- m-rann reconstruction of G - here optimality is with respect to Squared & norm which is also known as Mean Reconstruction Error (MSE). In detail, we are given with gradient matrix G, and j = 1, ..... m such that yj 's are orthonormal, that is, v By 1 if = j'. and otherwise. Since each column of G' is multiplied by the Projection matrix Y separately, we consider each 9i individually.
17

---

Published as a conference paper at ICLR 2024
given with just one y such that |/y/2 1. Then projecting 9I onto y in MSE is the solution to a 1-d optimization problem:
(i) Case 1: m = 1,
gf llvll
arg min PER
MSE(P) = 119: - pyll2 = 119.11 22p9 + p" llvll
- 9 y.
(9)
where we used the fact that llyll2 = 1 in the last line. So the reconstruction is given by scaling by the optimal p = o. y. It turns out that this calculation can be performed with each basis as we show in the next case.
(ii) Case 2: m > 1, so we are given m pairwise orthonormal vectors and similar to previous case have to determine the m projection coefficients for each Jr- Given Jt, determine p E R as follows:
arg min Pl
MSE .M Pm)) = 9i
PjUs ==1
11g:
12
P
+
10y 11
)=1
j=1
(10)
where we used orthogonality relationship in the last equality. By setting V, (MSE) we see that the reconstruction problem decomposes to m 1-d optimization problems each with closed
9.¹ J = I,..., m as in the previous case. So in this case, the reconstruction is given by Σ, PソU, = Σ, 9.
form solutions рj
af= y4 Ill 2
= YY
This illustrates why we require orthogonality constraints since otherwise, reconstruction might be does not imply YY = I since m. n. In literature,
computationally expensive. Note that Y the matrix YY'r is often called as the family of Projection matrices (not the YTG as we do here) since (2Y YY"YYT -YYTT = YYT for any orthonormal Y.
D SOLVING FLAG AGGREGATION EFFICIENTLY
Convergence Analysis when m 1. Note that for the case 1, that is, FA provides unit vector y E T.a to get aggregated gradient as yy² G. we can use smoothness based convergence results in nonconvex optimization, for example, please see Jain et al. (2017). We believe this addresses most of the standard training pipelines used in practice. Now, we focus on the case with m 1.
Now that we have smooth reformulation of the aggregation problem that we would like to solve, it is tempting to solve it using first order methods. However, naively applying first order methods can lead slow convergence, especially since the number of decision variables is now increased to m Standard projection oracles for trace norm require us to compute the full Singular Value Decomposition (SVD) of Z which becomes computationally expensive even for small values of m, 7 R 10.
Fortunately, recent results show that the factored form smooth SDPs be solved in polynomial time using gradient based methods. That is, by setting Z = vec(Y )eee(Y)" and minimizing the loss functions [Y) / vec(YY)T (T & M,) vec(Y) with respect to Y, we have that the set of locally optimal points coincide, see Bhojanapalli al. (2018). Moreover, we have the following convergence result for first order methods like Gradient Descent that require SVD of n x p matrices:
Lemma D.I. If 14 are K4 smmoth,,, with a 7) -ipschitt Hessian, then projected gradient descent with constant step size converges to a locally optimal solution to (8) in ( iterations where 0 < x²2 /n a error tolerance parameler,
max; Ke, and max; T/-
Above lemma D.I says that gradient descent will output an aggregation Y that satisfies second order sufficiency conditions with respect to smooth reformulated loss function (8). All the terms inside Ô in lemma D.1 are logarithmic dimensions m. n, lipschitz constant I., and accuracy parameter c. Remark D.2 (Numerical Considerations.). Note that the lipschitz constant i of the overall objective function depends on M. That is, when M, has negative eigenvalues, then K can be high due the square root function. We can consider three related ways to avoid this issue. First, we can choose a value m' > in our trace constraint such that M, 2 0. Similarly, we expand (8) (in v-) as outer
18

---

Published as a conference paper at ICLR 2024
product of columns of Y suggesting that 99" term need to be normalized by m. thus making M, > O. Secondly, we can consider adding quadratic term such as || to make the function quadratic. This has the effect of decreasing K and 17 of the objective function for optimization. Finally, use m, = max(ki, m) instead of min in defining the loss function as in Mankovich et al. (2022) which would also make M, Z O.
E PROOF OF LEMMA D.1 WHEN m > 1.
We provide the missing details in Section when m 1. To that end, we will assume that each worker i provides the server with list of k; gradients, that is, 9j [Rn strict generalization of the case considered in the main paper (with k = 1), that may be useful independently. Note that in Mankovich et al. (2022), these gi are assumed be subspaces whereas we do not make that assumption in our FA algorithm.
Now, we will show that the RHS in equation (7) and LHS in equation (8) are equivalent. For that, need to recall an elementary linear algebra fact relating tensor/Kroneee product, and tr operator. Recall the definition of Kronecker product:
Definition E.1. Let A RRd Xd2 B E gei Xe>, then A@ B E idher xd2ea is given by,
@1,1 B
01,dg B
A B =
(11)
ad.
ad, dg
where di,j denotes the entry at the i-th row, j th column of A. Lemma E.2 (Equivalence of Objective Functions.). Let Y E Raxm 9 Bank (so, M E RRXx). Then, we have that,
Ir (Y Y) == ir (r vec(Y)) (T& vee(Y)
(12)
where I E R is the identity matrix.
Proof. Using the definition of tensor product in equation (11), we can simplify the right hand side of equation (12) as,
8/11
:
M
0
Un
:
M
vec(Y)) (I M) vec(Y) 1y1,," ". "r1, .. Mim:
:
3/mm
M_
:
y mmn
2 My
m
((_urst) Uun M
Σ
tr (リnyg M) = tr Σ Minl MD
tr
1=1
(13)
tr (YY M) = tt -Y
(14)
where used the cyclic property of trace operator tr(-) in equations (13), and (14) that is, tr(AAC) tr(CA)) = tr(CAA for any dimension compatible matrices A, B, C.
E.1
PROOF LEMMA D.
Recall that, given M, = 7 @ Mr the lifted cone programming relaxation of FA can be written as,
min Σ Vi(zzrM. s.t. Z z 0. tr(Z) m, Z = zT
(15)
19

---

Published as a conference paper at ICLR 2024
where is the rank of Z number of columns of Y. We now the above Lemma E.2 to show that the objective function with respect to Z in the lifted formulation is smooth which gives us the desired convergence result in Lemma D.I.
Proof. let R; > 0,
V (T) + R
Mis
(16)
dz
2 R4 + tr( (T M:)
where M, = / 00 M, as equation (8). Now, since M, is constant with respect to Z, the gradient term affected only through scalar / Ir((ZT M.) + Rs. So the largest magnitude or entrywise &o -nom of the Hessian is given by.
a
||
11ZTT M.)
M oo
(17)
0z
2/ (112z (i) +
Now, we will argue that the gradient and hessian are lipschitz continuous the lifted space. Since any feasible Z 2 0 is positive semidefinite, if M, ž O, then the scalar tr( (2 M,) is at least m A,M, where XMh is the smallest (or mn-th) eigenvalue of M,. So, we can choose R₂ Ovi. If not, then there is negative eigenvalue, possibly repeated. So, the gradient might not exist. In cases where M, has Ar,
0 With these choices, we have that the gradient of the objective function in (8) is lipschitz continuous. By a similar analysis using can show that Hessian is also lipschitz continuous with respect to Z. In other
negative eigenvalues, we can choose A; = R min; min
mnn
the third derivative, words, all the lipschitz constant of both the gradient and hessian of our overall objective function is controlled by A 0. Hence, we have all conditions satisfied required for Lemma 1 in Bhojanapalli et al. (2018) 8), and we have our convergence result for FA in the factored space of vec(Y).
Few remarks are in order with respect to our convergence result. First, is the choice important for convergence? Our convergence result shows that a perturbed objective function r( M,) + has the same second order stationary points as that of the objective function in the factored form formulated using (or vec(Y)). We can avoid this perturbation argument if we explicitly add constraints tr( tr(Z" l (.) 2 O, since projections on linear constraints can be performed efficiently exactly (sometimes) approximately. Note that these constraints natural since it is not possible to evaluate the square root of a negative number. Alternatively, we can use a smooth approximate
approximation of the absolute values
Ir(Z" M.). In this case, it is easy to see from (16), and
(17) that the constants governing the lipschitz continuity as dependent on the absolute values of the minimum eigenvalues, as expected. essence, no, the choice of 7 does not affect the nature of landscape approximate locally optimal points remain approximately locally optimal. In practice, we expect the choice of to affect the performance of first order methods.
Second, can we assume M, > O for gradient aggregation purposes? Yes, this because, when using first order methods to obtain locally optimal solution, the scale or norm of the gradient becomes a secondary factor in terms of convergence. So, we can safely normalize each M, by the nuclear norm || I- == Σ j=1 Jj where oy is the j-th singular value of M.. This ensures that / - M, ż 0, assistant convergence. While ||M,]]_ itself might be computationally expensive to compute, we may be able to use estimates of ||M]]|+ via simple procedures as Qi (1984). In most practical implementations including ours, simply compute the average of the gradients computed by each worker before sending it to the parameter server, that is, k = k = in which case simply normalizing by the euclidean norm is sufficient for convergence result hold. Our FA based distributed training Algorithm solves the factored form for gradient aggregation purposes (in Step 6) at the parameter server.
Finally, please note that our technical assumptions are standard in optimization literature, that exploits smoothness of the objective function since the feasible set of Y in (1) is bounded, assumptions
20

---

Published as a conference paper at ICLR 2024
satisfied. Our proof techniques are standard, and we simply use them reformulation to obtain convergence guarantee second order stationary points for IRLS iterations since there exists a tractable SDP relaxation.
E.2 FA OPTIMALITY CONDITIONS AND SIMILARITIES WITH BULYAN EL MHAMDI ET AL. (2018) BASELINE.
We first restate our Flag Aggregator with gi E Boxk x in optimization terms as follows,
(YT y tr (of 9.)
min YYTY=
A(Y
=
AR(Y),
(18)
and write its associated Lagrangian L defined by,
P
tr (Y M tr (gf 9s
C(YT))
XR(Y) (T" (yTY-1))
(19)
where I' E Rm denotes the Lagrange multipliers associated with the orthogonality constraints in equation (18). In particular, since the constraints have equality, there are sign restrictions on r2 so they are often referred to as "free". Moreover, since is a real matrix, the constraints are symmetric (i.e., vf yj f yi). may assume that r r", without loss of generality.
We will introduce some notations to make calculations easier. We will use 9i Runk to denote normalized gradients matrix of the data terms in equation (18). That is, we define
9:g. d.g.0;"
(20)
(1--
u(YT u(YTass y in(o? 9.)
tr (9T
With this notation, we are ready to use the first optimality conditions associated with the constrained optimization problem in (18) with its Lagrangian in (19) By first order optimality KKT conditions, we have that,
0 = Vy) =
Σ
-T Jrlh 1=1
Y. + AVR(Y.) + 2Y.T.
GD.GD + AVR(YY) 2Y.T. (Objective)
(21)
0 = V.) Y.Y. (Feasibility)
where Y, E Raxm_ r. R mm are the optimal primal parameters, lagrangian multipliers, and D. IRP the diagonal matrix with entries equal to -d; < 0 as in equation (20). We may ignore the Feasibility conditions since our algorithm returns an orthogonal matrix by design, and focus on the Objective conditions. Aside, IRLS corresponds to solving this lagrangian equations in (21) directly. When À = 0, the solution to the lagrangian corresponds to computing the SVD of GD. While using functions that can be approximated as quadratic functions regularization, VR(Y)= = PI where P is a positive semidefinite matrix, and so we have to compute the cholesky decomposition of GDG XPI first, and then a SVD as stated in Algorithm in the main paper.
Now, by bringing the term associated with Lagrangian to the other side, and then right multiplying by r-1 inverse of T we have that Y, satisfies the following identity.
1 Y, -
+ (VR((Y)) 1.
(22)
21

---

Published as a conference paper at ICLR 2024
By using the identity (22), write equivalent representation of our aggregation rule Y.Y. given by,
Y.Y 1 (GD.G"Y + -VR((Y)) r.
(Y. (. + )V
<GD,G" AVR(Y.)) M
= =G -.D.G" M. + AVR(Y.) ERPXm
GS, AVR(Y.).1.
= GSRA + AVR(Y, )
(23)
that is, the update rule FA can be seen as left multiplication with the square "flag selection" matrix SSA S. E RP'P, and then perturbing with the gradient (Y.... of the regularization function R with a different matrix M as in equation (23). Importantly, we can see equation (23) that the (reduced) selection matrix S E Rxx in Bulyan El Mhamdi et al. (2018) is equivalent to the total 20
selection matrix SSA E REXP in our FA setup. Moreover, we can also see that domain knowledge in terms of regularization function may also determine the optimal subspace, albeit additively only. We leave the algorithmic implications of our result as future work.
Remark E.3 (Invertibility of T. in Equation (22).). Theoretically, note that I is symmetric, so by Spectral Theorem, we know that its eigen decomposition exists. So, we may use pseudo-inverse instead of its inverse. Computationally, given any primal solution Y. we can obtain r, by left multiplying equation (21) by Y. and use feasibility i.e., Y = 7. Now, we obtain r- columnwise by using some numerical solver such conjugate gradient (with fixed iterations) on I' with standard basis vectors. In either case, our proof can be used with the preferred approximation choice of r, to get the equivalence as in equation (23).
Remark E.4 (Provable Robustness Guarantees for FA.). Since our FA scheme based on convexity, is possible to show worst-case robustness guarantees for FA iterations under mild technical conditions on Y - even under correlated noise, see for e.g. Assumption in Klopp et al. (2016)). fact, by using the selection matrix SFX in equation (23) in Lemma 1 in Damaskinos et al. (2019) and following the proof, we can get similar provable robustness guarantees for FA. We leave the theoretical analysis as future work.
F ADDITIONAL EXPERIMENTS
F.1 THE EFFECT OF REGULARIZATIO PARAMETER
Our algorithm depends on the regularization parameter X. Figure 10 below illustrates the effect of this parameter on similarity of aggregated gradient vectors for FA and Multi-Krum, For this experiment, we sample the gradients output by the parameter server across multiple epochs for both FA and Kuuti-Krum and compute the cosine similarity of corresponding vectors. We repeat the experiment with different À values. As we can see, for smaller iterations there is some similarity between the gradients computed by FA and Multi- Krumm This similarity is more visible for smaller values.
0.6
Contae Stathett
64
Costee
2.0
302
100
-0.
150
Jandkao
Figure 10: The effect of the regularization parameter À on similarity FA performance to Multi-Krum
22

---

Published as a conference paper at ICLR 2024
F.2 EXPERIMENTS WITH OTHER BYZANTINE ATTACKS BASELINES
In Figure 11, we present convergence plot to study FA when there are no Byzantine workers. Essentially, when f = 0, a robust aggregator should perform just well as the standard distributed SGD with Mean as the aggregator. However, for f 0, the Mean aggregator is not robust, demonstrated in Figure 2. Figure 11 illustrates that FA outperforms the mean, which aligns with the findings of Mankovich et al. (2022).
60
T0p-1 Accuracy (9)accy)9))
60-
30
20
Flgg Aggregator
So far we have presented results where Byzantine workers send uniformly random gradient vectors, synthetic data (nonlinear data augmentation routines), or where percentage of gradients are dropped and zeroed communication loss. Here we provide more results when Byzantine workers send a gradient based on the Fall of Empires attack with 0.1 Xie al. (2020) in Figure 12a and when they send 10x amplified sign-flipped gradients Allen-Zhu et al. (2021) in Figure 12b. Because mathematically, one iteration of FA with uniform weights assigned across all workers is equivalent to PCA, we also add a baseline for top-m principal components of the gradient matrix in Figure 12c. The novelty in our FA approach the extension of PCA to an iteratively reweighted form that is guaranteed to converge. Specifically, we show that we obtain convergent procedure in which we repeatedly solve weighted PCA problems. Moreover, the convergence guarantee immediately follows when the procedure is viewed as IRLS procedure solving the MLE problem induced by the value of workers modeled with a beta distribution as in Section 2.2.
10
20
Epoch
Figure
11: Convergence with
the parameter server show tolerance
f=
Flag Aggregator Bulyan
Multi-Krum
Median
Phocas
MeaMed
Trimmed Mean
PCA
60
60-
50
Accuracy (%)
accuratt
Accuracy
4.
40
20
20
20
30
15
15
20
Epoch
Epoch
Epoch
(a) Fall of Empires
(b) Sign-fipppigg
(c) PCA baseline
Figure 12: Robustness towards other attacks and comparison PCA baseline, p 15,
Flag Aggregator Bulyan
RESAM Multi-Krum
RESAM Median
RESAM Phocas RESAM
RESAM
MeaMad
Mean
Accuracy (%)
Accurdyy
3.0
10t-1 Accuracy
30
40-
40
10-
10
Epoch
Epoch
Epoch
(a) Fall of Empires,
(b) Augmented CIFAR- 2
(c) Sign-flipping f
Figure 13: Robustness comparison with RESAM and CGE, p = 15.
We compared FA to RESAM Farhadkhani et al. (2022) that adapts the concept of gradient momentum to distributed architectures. RESAM involves each honest worker sending the momentums of their
23

---

Published as a conference paper at ICLR 2024
stochastic gradients the server, instead of just the gradients. Similar Allouah et al. (2023a:b), RESAM still relies on resilient aggregation at the server, so we complement it with the existing baselines including Comparative Gradient Elimination (CGE) Gupta et al. (2021). CGE sorts the gradients based on their Fuclidean norms and averages the gradients corresponding to the smallest p f norms. Figure 13 shows that FA outperforms all baselines under three different scenarios. In addition, FA is designed as robust standalone aggregator that needs no extra computation or space for calculating gradient momentums and storing them on the worker side.
F.3 EXPERIMENTS WITH THE TINY IMAGENET DATASET
We repeated our experiments with Tiny ImageNet Le and Yang (2015) which contains 100000 images of 200 classes (500 for each class) downsized 64x64 colored images. We our batch size 192 and use ResNet-50 He et al. (2016) throughout the experiments.
Tolerance the number of Byzantine workers: In this experiment, we have p = 15 workers of which f 1, ... 3 are Byzantine and send random gradients. The accuracy of test data for FA in comparison to other aggregators is shown Figure 14. As we can see, for f = and f = 2, FA converges a higher accuracy than all other schemes. For all cases, FA also converges in ~2 less number iterations.
Flng Agpregater
Bulyan
Multi Krum
MeaMed
Modian
Tiimmdd Mean
Phocas
25
1og-1 Accuraca 15
2.0
30
Accuracy
25
20
1.0
10-
Epoch
Epoch
Epoch
(a) f ==
(b) ʃ =
(c)
ʃ 3
Figure 14: Tolerance to the number of Byzantine workers for robust aggregators.
Tolerance to communication loss: We set 10% rate for the links connecting / = 1, ., 3 of the workers to the parameter server. Figure 15 shows that our takeaways in the main paper also confirmed this setting with the new datasct.
Agpregator
Rccuracy acy
Accuracy
Accuracy
30
30.
30
5
10
15
20
25
10
15
20
25
10
15
20
25
Epach
Epach
Epoth
(a) f =
(b) f
(c) f 3
Figure 15: Tolerance to communication loss
The effect of having augmented data during training in Byzantine workers: As mentioned the main paper, we choose two non linear augmentation schemes, Lotka Volterra (shown in rows 1 and of Figure 16) and Arnol''s Cat Map (shown in rows 2 and 4 Figure 16). We used SciPy's 's Virtanen al. (2020) solve ivp method solve the differential equations, by using the LSODA solver. In addition to the setup described the main paper, we also added a varying level of Gaussian noise to each of the training images. All the images in the training set randomly chosen be augmented
24

---

Published as a conference paper at ICLR 2024
with varying noise levels of the above mentioned augmentation schemes. We have provided the code that implements all our data augmentation schemes in the supplement zipped folder.
As seen from the figure, Amold's Cat Map augmentations stretch the images and rearrange them within a unit square, thus resulting in streaky patterns. Whereas the Lotka Volterra augmentations distort the images while keeping the images similar to the original ones. We perform experiments with data augmented with varying shares using the two methods and show the results in Figure 17. For CIFAR-IO, we showed the results when all of the samples in Byzantine workers augmented in Figure in the main paper. For Tiny ImageNet, this case is shown Figure 17a. Figures 1 and 17c show the results under different ratios on CIFAR- 10. By changing the ratios were interested to see if streaky patterns augmented by Arnold's s Cat Map would introduce more adverse effect from Byzantine workers compared Lotka Volterra. Although the results do not show a significant signal, we can see that the augmentations did impact the overall gradients and that FA performs significantly better.
Figure 16: Tinylmagenet data with Augmentation: Row 1: Lotka Volterra augmentation on Class Horse. Row 2: Amool'' Cat Map augmentation on Class Horse. Row 3:tot Volterra augmentation on Class Ship. Row 4: Arnold's Cat Map augmentation on Class Ship.
Finp Agpregator
Bulyan
Multi-Krum
MeaMed
Madian
Thimedd Hean
Photas
50-
60
60
Aocuracy (96)
40
50
5.5
Accuracy
Accuracy
30
40
20
30
30
10
20
20
10
Epoch
Epoch
Epoch
(a) 100% Lotka-Voltent on Tiny
(b) 50% Lotka- Volterr, 50%
(c) 33% Lotka-Volterra 66%
ImageNet
Amold's Cat Map CIFAR-10
Arood's Cat Map CIFAR-10
Figure 17: Accuracy of using augmented data in 3 workers
G DISCUSSION AND LIMITATION
Is it possible to fully "offload" FA computation to switches? Recent work propose that aggregation be performed entirely on network infrastructure to alleviate any communication bottleneck that may arise Sapio et al. (2021); Lao et al. (2021). However, to the best of our knowledge, switches that are in use today only allow limited computation to be performed on gradient gi as packets whenever they are transmitted Bosshart et al. (2013); McKeown (2015). That is, programmability is restrictive at the moment- switches used in practice have no floating point, or loop support, and near. For instance, Yuan et al.
severely memory/state constrained. Fortunately, solutions (2022) have already introduced support for floating point arithmetic in programmable switches. We may use quantization approaches for SVD calculation with some accuracy loss Song et al. (2018) to
25

---

Published as a conference paper at ICLR 2024
3000
Fie Aogingiie
Bapen
2500
PisPic
Time 13
2000
Miciut
Accuraty
-40
1500
Bag ARTRI Iuzen
30
1000
Mealled
20
Medten
500
10
40
1000
15:00
2000
2500
Epoch
Time (5)
(a) Iteration time
(b) time-to-accuracy
Figure 18: Wall clock time comparison
approximate floating point arithmetic. Offloading FA to switches has great potential in improving its computational complexity because the switch would perform as a high-throughput streaming parameter server synchronize gradients over the network. Considering that FA's accuracy currently outperforms its competition in several experiments, an offloaded FA can reach their accuracy even faster it could reach a higher accuracy in the same amount of time.
Potential Limitation: Since we perform SVD in every iteration of FA, the complexity of the algorithm would be OnnNss(E )2 with No being the number of iterations for the algorithm. Figure 18 shows the wall clock time it takes for FA to reach a certain epoch (18a) or accuracy (18b) compared other methods under fixed amount of random noise f = with p 15 workers on CIFAR-10. Although the iteration complexity of FA is higher, each iteration has higher utility as reflected in the timeuto-accuracy measures. This makes FA comparable to others in a shorter time span, however, eventually FA converges to a better state as shown in Figure 18b. Regardless, it is possible to take advantage of fast, randomized SVD solvers to lower the wall clock time. In detail, to calculate the left singular values GD E R=xP, we use the fact that number of workers p < n and solve the p x p eigenvalue problem which can be fast in practice. Upon receiving the right singular vectors, first order methods can be used obtain the left singular vectors. this sense, we can use any fast, randomized SVD algorithm to solve for the right and/or left singular vectors.
Towards Federated Learning Environments: As we extend our gaze beyond current implementation, the potential of FA within federated learning environments emerges as intriguing frontier. Our scalability investigations, as illustrated in Figure 9, serve as preliminary foundation for this exploration. We show FA's adaptability to more complex distributed settings, hinting its viability across expanded cluster configurations.
Envisioning the implementation of FA in federated context, we propose hierarchical architectural model. This model involves gradient-computiin aggregating workers within clusters, akin to a parameter server but on localized scale. These aggregating nodes then engage in further synthesis of results across multiple clusters, fostering scalable, federated framework. This architecture not only maintains FA's core aggregation capabilities but also adapts them to the nuanced demands of federated learning, marking significant stride toward broader applicability.
workers transmitting their results to designated
Charting the Path Forward: Our goal is to enhance the robustness and scalability of distributed training systems. By exploring the expansion of FA to more clusters and investigating computational offloading, we highlight our commitment to leading progress in the field. As we advance, our efforts are aimed at not just refining FA but also devising innovative solutions to meet the broad spectrum of challenges in distributed training.
26


Reviews:
[{"review_id": "YADMInOQuX", "reviewer": "Reviewer_YEpb", "summary": "This paper proposes Flag Aggregator, a simple Maximum Likelihood Based estimation procedure for aggregation purposes. They show that any procedure used to solve Flag Optimization can be directly used to obtain the optimal summary statistic $Y^*$.The authors also show the approach is resilient against Byzantine attacks for gradient aggregation.", "questions": "I'll increase my rating if comparison to more recent algorithms is provided.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Gradient aggregation is a critical design choice in many of the distributed training applications, and is ubiquitous. The proposed method seems promising and useful for this space.", "weaknesses": "- I am not sure how much overhead the SVD might bring in practice, could you provide some real-world measurement? So far all the empirical results are epoch-wise measuring.\n- Most of the baseline compared in the experiments seem to be from at least five years ago (2018); I wonder if the authors can compare their approach with latest algorithms? For instance  Allouah et al. (2023a;b); Farhadkhani et al. (2022) as mentioned in the related work.", "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": "", "extra_scores": {}}, {"review_id": "jrGqwvxsPw", "reviewer": "Reviewer_PqPx", "summary": "This work proposes an aggregation function based on low-rank projection. In particular, for a given matrix $G$, this work proposes to perform the aggregation by projecting it to a low-dimensional space, $YY^TG1$, where $Y$ is the subspace chosen based on low-rank factorization of $G$. The connection between the algorithm and the Maximum Likelihood Estimation procedure using Beta densities is presented. Experimental results show improvements in communication efficiency and accuracy compared to previous works.", "questions": "n/a", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method is simple yet effective. Theoretical analysis is also provided to backup the algorithm.\n\n2. Detailed experimental results are provided, and better accuracy has been shown compared to the previous works.", "weaknesses": "Here are a few comments regarding the experimental section:\n\n1. The choice of setting the subspace rank $m$ to $(p+1)/2$ in all experiments raises a question. Is this decision rooted in theoretical analysis or other considerations?\n\n2. The paper introduces a general framework in Section 2, considering a general norm and suggesting SDP for solving the system. However, the focus shifts to $\\ell_1$ regularization later due to its ease of optimization. An experimental comparison of different regularization terms could bridge the apparent gap between Sections 2 and 3.\n\n3. It would be useful to explore whether the proposed algorithm offers advantages even when $f=0$.", "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": "", "extra_scores": {}}, {"review_id": "ubcIodcuS7", "reviewer": "Reviewer_Es7u", "summary": "This work proposes a novel robust aggregator, i.e., Flag Aggregator (FA), to deal with Byzantine faults in distributed computation. FA is an optimization-based subspace estimator that formulates aggregation as a maximum likelihood estimation procedure using Beta densities. In distributed training setups where vanilla mean aggregators are replaced by robust aggregators without additional tricks, FA consistently outperforms many other existing robust aggregators in extensive experiments with various batch sizes, fractions of Byzantine nodes, and number of nodes.", "questions": "1. In line 22, the description of quadratic function is not clear to me, can the authors put it simpler? \n2. How will the augmented data and stable diffusion influence the mutual dependence of distributed data, can the authors comment on that?\n3. In line 72, what does it mean for noise to be nonlinear? \n4. In line 73 & 74, how does the discrete hyper parameters hamper convergence of the overall training procedure, can you elaborate on that?\n5. In line 76, the authors mention 'sparse', does that correspond to the choice of the second dimension of $Y$, i.e., $m$, how is $m$ chosen? \n6. In line 115, it seems that $g$ should $g_i$, and there is no need to use trace on a scalar right? \n7. In figure 3, I don't understand what is optimal subspace, do you mean optimality in the sense of formulation (5)?\n8. Why is beta distribution used in the formulation of FA? \n9. In the experiment starting from line 300, what attacks are being used?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The proposed FA is novel in the distributed optimization literature. FA makes use of dependence among distributed gradients, while most existing aggregators only exploit the pairwise distance or moment conditions. This is beneficial in that if one can design aggregator that utilizes the data dependence, this aggregator is actually adaptive to this specific problem automatically, and thus one can improve performance. The authors provide insights on the intuitions, formulations, and approximate solutions to FA.\n3. Consistent empirical performance improvement against many existing aggregators is achieved, among extensive experiments that investigate many facets of the Byzantine distribution optimization problem.", "weaknesses": "1. There are no specific examples that can show FA is theoretically better than existing methods, and thus makes the claim not persuasive to some audience. It can be, possibly, FA only performs well in the specific datasets, models, the way of distributing datasets among compute nodes in the experiments presented in this work. Even a naive toy example would help people understand why FA is theoretically better. \n2. There are no comparisons between FA and existing aggregators in terms of computation complexity. It can be that, FA is too expensive to use in every iteration. \n3. The intuition behind the development of FA is not clear enough to me, this goes to the first bullet, can the authors provide an example or a simple problem model to illustrate this? And why is FA optimal as claimed in line 83? Can the authors elaborate on this point?", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)