Asynchronous Gossip Algorithms for Rank-Based Statistical Methods

• URL: http://arxiv.org/abs/2509.07543v2
• Date: Thu, 11 Sep 2025 14:39:19 GMT
• Title: Asynchronous Gossip Algorithms for Rank-Based Statistical Methods
• Authors: Anna Van Elst, Igor Colin, Stephan Clémençon,
• Abstract summary: We introduce the first gossip algorithm for Wilcoxon rank-sum tests.<n>We provide rigorous convergence guarantees, including the first convergence rate bound for asynchronous gossip-based rank estimation.
• Score: 2.6636053598505307
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As decentralized AI and edge intelligence become increasingly prevalent, ensuring robustness and trustworthiness in such distributed settings has become a critical issue-especially in the presence of corrupted or adversarial data. Traditional decentralized algorithms are vulnerable to data contamination as they typically rely on simple statistics (e.g., means or sum), motivating the need for more robust statistics. In line with recent work on decentralized estimation of trimmed means and ranks, we develop gossip algorithms for computing a broad class of rank-based statistics, including L-statistics and rank statistics-both known for their robustness to outliers. We apply our method to perform robust distributed two-sample hypothesis testing, introducing the first gossip algorithm for Wilcoxon rank-sum tests. We provide rigorous convergence guarantees, including the first convergence rate bound for asynchronous gossip-based rank estimation. We empirically validate our theoretical results through experiments on diverse network topologies.

Related papers

• Robust Distributed Learning under Resource Constraints: Decentralized Quantile Estimation via (Asynchronous) ADMM [2.6636053598505307]
  We propose AsylADMM, a novel gossip algorithm for decentralized median and quantile estimation.<n>We show that our algorithm enables quantile-based trimming, geometric median estimation, and depth-based trimming.
  arXiv  Detail & Related papers  (2026-01-28T13:09:10Z)
• Conformal Prediction for Multi-Source Detection on a Network [59.17729745907474]
  We study the multi-source detection problem.<n>Given snapshot observations of node infection status on a graph, estimate the set of source nodes that initiated the propagation.<n>We propose a novel conformal prediction framework that provides statistically valid recall guarantees for source set detection.
  arXiv  Detail & Related papers  (2025-11-12T01:09:56Z)
• 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)
• Robust Barycenter Estimation using Semi-Unbalanced Neural Optimal Transport [84.51977664336056]
  We propose a novel scalable approach for estimating the robust continuous barycenter.<n>Our method is framed as a min-max optimization problem and is adaptable to general cost functions.
  arXiv  Detail & Related papers  (2024-10-04T23:27:33Z)
• The Benefit of Being Bayesian in Online Conformal Prediction [7.713245413733777]
  We study the online construction of confidence sets given a black-box machine learning model.<n>By converting the target confidence levels into quantile levels, the problem can be reduced to predicting the quantiles of a sequentially revealed data sequence.
  arXiv  Detail & Related papers  (2024-10-03T15:04:47Z)
• Sequential Manipulation Against Rank Aggregation: Theory and Algorithm [119.57122943187086]
  We leverage an online attack on the vulnerable data collection process. From the game-theoretic perspective, the confrontation scenario is formulated as a distributionally robust game. The proposed method manipulates the results of rank aggregation methods in a sequential manner.
  arXiv  Detail & Related papers  (2024-07-02T03:31:21Z)
• Marginal and training-conditional guarantees in one-shot federated conformal prediction [17.197488145781858]
  We study conformal prediction in the one-shot federated learning setting. The main goal is to compute marginally and training-conditionally valid prediction sets, at the server-level, in only one round of communication between the agents and the server.
  arXiv  Detail & Related papers  (2024-05-21T08:08:00Z)
• Differentially Private Federated Learning: Servers Trustworthiness, Estimation, and Statistical Inference [18.97060758177909]
  This paper investigates the challenges of high-dimensional estimation and inference under the constraints of differential privacy. We introduce a novel federated estimation algorithm tailored for linear regression models. We also propose methods for statistical inference, including coordinate-wise confidence intervals for individual parameters.
  arXiv  Detail & Related papers  (2024-04-25T02:14:07Z)
• Robust Consensus in Ranking Data Analysis: Definitions, Properties and Computational Issues [2.867517731896504]
  We introduce notions of robustness, together with dedicated statistical methods, for Consensus Ranking. We propose specific extensions of the popular concept of breakdown point, tailored to consensus ranking.
  arXiv  Detail & Related papers  (2023-03-22T19:36:56Z)
• Two-Stage Robust and Sparse Distributed Statistical Inference for Large-Scale Data [18.34490939288318]
  We address the problem of conducting statistical inference in settings involving large-scale data that may be high-dimensional and contaminated by outliers. We propose a two-stage distributed and robust statistical inference procedures coping with high-dimensional models by promoting sparsity.
  arXiv  Detail & Related papers  (2022-08-17T11:17:47Z)
• Valid Inference After Causal Discovery [73.87055989355737]
  We develop tools for valid post-causal-discovery inference. We show that a naive combination of causal discovery and subsequent inference algorithms leads to highly inflated miscoverage rates.
  arXiv  Detail & Related papers  (2022-08-11T17:40:45Z)
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination [82.52105963476703]
  A recurring theme in statistical learning, online learning, and beyond is that faster convergence rates are possible for problems with low noise. First-order guarantees are relatively well understood in statistical and online learning. We show that the logarithmic loss and an information-theoretic quantity called the triangular discrimination play a fundamental role in obtaining first-order guarantees.
  arXiv  Detail & Related papers  (2021-07-05T19:20:34Z)
• Risk Minimization from Adaptively Collected Data: Guarantees for Supervised and Policy Learning [57.88785630755165]
  Empirical risk minimization (ERM) is the workhorse of machine learning, but its model-agnostic guarantees can fail when we use adaptively collected data. We study a generic importance sampling weighted ERM algorithm for using adaptively collected data to minimize the average of a loss function over a hypothesis class. For policy learning, we provide rate-optimal regret guarantees that close an open gap in the existing literature whenever exploration decays to zero.
  arXiv  Detail & Related papers  (2021-06-03T09:50:13Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  The distributionally robust optimization framework is considered for training a parametric model. The objective is to endow the trained model with robustness against adversarially manipulated input data. Proposed algorithms offer robustness with little overhead.
  arXiv  Detail & Related papers  (2020-07-07T18:25:25Z)

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.