Byzantine Machine Learning: MultiKrum and an optimal notion of robustness

• URL: http://arxiv.org/abs/2602.03899v1
• Date: Tue, 03 Feb 2026 09:07:03 GMT
• Title: Byzantine Machine Learning: MultiKrum and an optimal notion of robustness
• Abstract summary: We provide the first proof that MultiKrum is a robust aggregation rule, and bound its robustness coefficient.<n>We show that MultiKrum's bounds are never worse than Krum's, and better in realistic regimes.
• Score: 10.810599663861476
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Aggregation rules are the cornerstone of distributed (or federated) learning in the presence of adversaries, under the so-called Byzantine threat model. They are also interesting mathematical objects from the point of view of robust mean estimation. The Krum aggregation rule has been extensively studied, and endowed with formal robustness and convergence guarantees. Yet, MultiKrum, a natural extension of Krum, is often preferred in practice for its superior empirical performance, even though no theoretical guarantees were available until now. In this work, we provide the first proof that MultiKrum is a robust aggregation rule, and bound its robustness coefficient. To do so, we introduce $κ^\star$, the optimal *robustness coefficient* of an aggregation rule, which quantifies the accuracy of mean estimation in the presence of adversaries in a tighter manner compared with previously adopted notions of robustness. We then construct an upper and a lower bound on MultiKrum's robustness coefficient. As a by-product, we also improve on the best-known bounds on Krum's robustness coefficient. We show that MultiKrum's bounds are never worse than Krum's, and better in realistic regimes. We illustrate this analysis by an experimental investigation on the quality of the lower bound.

Related papers

• Near-Exponential Convergence Rates for kNN Classification based on Boltzmann Margin [6.244816393907942]
  Boltzmann margin is a new condition that bridges the gap between Tsybakov margin and Massart margin.<n>We establish the first near-exponential convergence rates for kNN classification.
  arXiv  Detail & Related papers  (2026-06-09T03:21:48Z)
• Improved Sample Complexity for Full Coverage in Compact and Continuous Spaces [0.0]
  We study uniform random sampling on the $d$-dimensional unit hypercube.<n>We derive a sample complexity bound with a logarithmic dependence on the failure probability.<n>Our findings offer a sharper theoretical tool for algorithms that rely on grid-based coverage guarantees.
  arXiv  Detail & Related papers  (2025-11-21T21:06:14Z)
• Understanding Robust Machine Learning for Nonparametric Regression with Heavy-Tailed Noise [10.844819221753042]
  We use Huber regression as a close-up example within Tikhonov-regularized risk minimization.<n>We address two central challenges: (i) the breakdown of standard concentration tools under weak moment assumptions, and (ii) the analytical difficulties introduced by unbounded hypothesis spaces.<n>Our study delivers principled rules, extends beyond Huber to other robust losses, and highlights prediction error, not excess risk, as the fundamental lens for analyzing robust learning.
  arXiv  Detail & Related papers  (2025-10-10T21:57:18Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  We propose a graph-based clustering algorithm that only relaxes the orthonormal constraint to derive clustering results.<n>To ensure a doubly constraint into a gradient, we transform the non-negative constraint into a class probability parameter.
  arXiv  Detail & Related papers  (2025-09-23T09:14:39Z)
• Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning [55.197497603087065]
  We analyze the performance of the Temporal Difference (TD) learning algorithm with linear function approximations.<n>We establish novel and general high-dimensional concentration inequalities and Berry-Esseen bounds for vector-valued martingales induced by Markov chains.
  arXiv  Detail & Related papers  (2025-02-19T15:33:55Z)
• Boosting Certificate Robustness for Time Series Classification with Efficient Self-Ensemble [10.63844868166531]
  Randomized Smoothing has emerged as a standout method due to its ability to certify a provable lower bound on robustness radius under $ell_p$-ball attacks. We propose a self-ensemble method to enhance the lower bound of the probability confidence of predicted labels by reducing the variance of classification margins. This approach also addresses the computational overhead issue of Deep Ensemble(DE) while remaining competitive and, in some cases, outperforming it in terms of robustness.
  arXiv  Detail & Related papers  (2024-09-04T15:22:08Z)
• Beyond Expectations: Learning with Stochastic Dominance Made Practical [88.06211893690964]
  dominance models risk-averse preferences for decision making with uncertain outcomes. Despite theoretically appealing, the application of dominance in machine learning has been scarce. We first generalize the dominance concept to enable feasible comparisons between any arbitrary pair of random variables. We then develop a simple and efficient approach for finding the optimal solution in terms of dominance.
  arXiv  Detail & Related papers  (2024-02-05T03:21:23Z)
• Certifying Ensembles: A General Certification Theory with S-Lipschitzness [128.2881318211724]
  Ensembling has shown to be beneficial for generalisation, uncertainty estimation, calibration, and mitigating the effects of concept drift. In this work, we generalise Lipschitz continuity by introducing S-Lipschitz classifiers, which we use to analyse the theoretical robustness of ensembles.
  arXiv  Detail & Related papers  (2023-04-25T17:50:45Z)
• Byzantine Machine Learning Made Easy by Resilient Averaging of Momentums [7.778461949427662]
  Byzantine resilience emerged as a prominent topic within the distributed machine learning community. We present emphRESAM (RESilient Averaging of Momentums), a unified framework that makes it simple to establish optimal Byzantine resilience.
  arXiv  Detail & Related papers  (2022-05-24T16:14:50Z)
• Robustness, Privacy, and Generalization of Adversarial Training [84.38148845727446]
  This paper establishes and quantifies the privacy-robustness trade-off and generalization-robustness trade-off in adversarial training. We show that adversarial training is $(varepsilon, delta)$-differentially private, where the magnitude of the differential privacy has a positive correlation with the robustified intensity. Our generalization bounds do not explicitly rely on the parameter size which would be large in deep learning.
  arXiv  Detail & Related papers  (2020-12-25T13:35:02Z)
• Provable tradeoffs in adversarially robust classification [96.48180210364893]
  We develop and leverage new tools, including recent breakthroughs from probability theory on robust isoperimetry. Our results reveal fundamental tradeoffs between standard and robust accuracy that grow when data is imbalanced.
  arXiv  Detail & Related papers  (2020-06-09T09:58:19Z)
• Distributional Robustness and Regularization in Reinforcement Learning [62.23012916708608]
  We introduce a new regularizer for empirical value functions and show that it lower bounds the Wasserstein distributionally robust value function. It suggests using regularization as a practical tool for dealing with $textitexternal uncertainty$ in reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-05T19:56:23Z)
• Robust $k$-means Clustering for Distributions with Two Moments [4.21934751979057]
  We consider the robust algorithms for the $k$-means clustering problem where a quantizer is constructed based on $N$ independent observations. Our main results are median of means based non-asymptotic excess distortion bounds that hold under the two bounded moments assumption in a general separable Hilbert space.
  arXiv  Detail & Related papers  (2020-02-06T16:36:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.