2019/04/30 by Swanand Kadhe, Kadhe, Swanand, O. Ozan Koyluoglu +3 · 1 citation
Computer Science · #Adversarial Robustness in Machine Learning #Distributed #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Parallel #Stochastic Gradient Optimization Techniques #Topological and Geometric Data Analysis #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1904.13373
openalex publication_date 2019/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Distributed implementations of gradient-based methods, wherein a server\ndistributes gradient computations across worker machines, suffer from slow\nrunning machines, called 'stragglers'. Gradient coding is a coding-theoretic\nframework to mitigate stragglers by enabling the server to recover the gradient\nsum in the presence of stragglers. 'Approximate gradient codes' are variants of\ngradient codes that reduce computation and storage overhead per worker by\nallowing the server to approximately reconstruct the gradient sum.\n In this work, our goal is to construct approximate gradient codes that are\nresilient to stragglers selected by a computationally unbounded adversary. Our\nmotivation for constructing codes to mitigate adversarial stragglers stems from\nthe challenge of tackling stragglers in massive-scale elastic and serverless\nsystems, wherein it is difficult to statistically model stragglers. Towards\nthis end, we propose a class of approximate gradient codes based on balanced\nincomplete block designs (BIBDs). We show that the approximation error for\nthese codes depends only on the number of stragglers, and thus, adversarial\nstraggler selection has no advantage over random selection. In addition, the\nproposed codes admit computationally efficient decoding at the server. Next, to\ncharacterize fundamental limits of adversarial straggling, we consider the\nnotion of 'adversarial threshold' -- the smallest number of workers that an\nadversary must straggle to inflict certain approximation error. We compute a\nlower bound on the adversarial threshold, and show that codes based on\nsymmetric BIBDs maximize this lower bound among a wide class of codes, making\nthem excellent candidates for mitigating adversarial stragglers.\n