In Byzantine collaborative learning, n clients in a peer-to-peer network collectively learn a model without sharing their data by exchanging and aggregating stochastic gradient estimates. Byzantine clients can prevent others from collecting identical sets of gradient estimates. The aggregation step thus needs to be combined with an efficient (approximate) agreement subroutine to ensure convergence of the training process. In this work, we study the geometric median aggregation rule for Byzantine collaborative learning. We show that known approaches do not provide theoretical guarantees on convergence or gradient quality in the agreement subroutine. To satisfy these theoretical guarantees, we present a hyperbox algorithm for geometric median aggregation. We practically evaluate our algorithm in both centralized and decentralized settings under Byzantine attacks on non-i.i.d. data. We show that our geometric median-based approaches can tolerate sign-flip attacks better than known mean-based approaches from the literature.

In this paper, we present distributed fault-tolerant algorithms that approximate the centroid (i.e., the average) of a set of n data points in $$\mathbb {R}^d$$ . Our work falls into the broader area of multidimensional Byzantine approximate agreement. We show that state-of-the-art algorithms, such as agreeing inside the convex hull of all non-faulty vectors, or minimum-diameter averaging (MDA), in the worst case either prevent us from agreeing on a vector close to the centroid (in terms of approximation quality), or allow Byzantine parties to influence the output considerably (in terms of validity). To design better approximation algorithms, we propose a novel concept of defining an approximation ratio of the centroid by including the vectors of the Byzantine adversaries in the definition. We analyze synchronous algorithms in the public channel communication model. We show that the standard agreement algorithms based on agreeing inside the convex hull of all non-faulty vectors do not allow us to compute a better approximation than 2d of the centroid. On the other hand, MDA can be used to achieve constant approximation at the cost of only satisfying strong validity. As a trade-off, we develop an approach that reaches a $$2\sqrt{d}$$ -approximation of the centroid, while satisfying box validity. Our approach provides optimal resilience, allowing up to $$t

Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming and parallel algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimilar. The task is to partition the elements and the objective is to minimize disagreements, that is, the number of dissimilar elements grouped together and similar elements that get separated.

In this work, we present a constant-round algorithm for the $2$-ruling set problem in the Congested Clique model. As a direct consequence, we obtain a constant round algorithm in the MPC model with linear space-per-machine and optimal total space. Our results improve on the $O(\log \log \log n)$-round algorithm by [HPS, DISC'14] and the $O(\log \log Δ)$-round algorithm by [GGKMR, PODC'18]. Our techniques can also be applied to the semi-streaming model to obtain an $O(1)$-pass algorithm. Our main technical contribution is a novel sampling procedure that returns a small subgraph such that almost all nodes in the input graph are adjacent to the sampled subgraph. An MIS on the sampled subgraph provides a $2$-ruling set for a large fraction of the input graph. As a technical challenge, we must handle the remaining part of the graph, which might still be relatively large. We overcome this challenge by showing useful structural properties of the remaining graph and show that running our process twice yields a $2$-ruling set of the original input graph with high probability.

Identifying clusters of similar elements in a set is a common task in data analysis. With the immense growth of data and physical limitations on single processor speed, it is necessary to find efficient parallel algorithms for clustering tasks. In this paper, we study the problem of correlation clustering in bounded arboricity graphs with respect to the Massively Parallel Computation (MPC) model. More specifically, we are given a complete graph where the edges are either positive or negative, indicating whether pairs of vertices are similar or dissimilar. The task is to partition the vertices into clusters with as few disagreements as possible. That is, we want to minimize the number of positive inter-cluster edges and negative intra-cluster edges. Consider an input graph G on n vertices such that the positive edges induce a λ-arboric graph. Our main result is a 3-approximation (in expectation) algorithm to correlation clustering that runs in (log λ ⋅ poly(log log n)) MPC rounds in the strongly sublinear memory regime. This is obtained by combining structural properties of correlation clustering on bounded arboricity graphs with the insights of Fischer and Noever (SODA '18) on randomized greedy MIS and the PIVOT algorithm of Ailon, Charikar, and Newman (STOC '05). Combined with known graph matching algorithms, our structural property also implies an exact algorithm and algorithms with worst case (1+ε)-approximation guarantees in the special case of forests, where λ = 1.