Robust Distributed Learning under Resource Constraints: Decentralized Quantile Estimation via (Asynchronous) ADMM

• URL: http://arxiv.org/abs/2601.20571v1
• Date: Wed, 28 Jan 2026 13:09:10 GMT
• Title: Robust Distributed Learning under Resource Constraints: Decentralized Quantile Estimation via (Asynchronous) ADMM
• Authors: Anna van Elst, Igor Colin, Stephan Clémençon,
• Abstract summary: 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.
• Score: 2.6636053598505307
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Specifications for decentralized learning on resource-constrained edge devices require algorithms that are communication-efficient, robust to data corruption, and lightweight in memory usage. While state-of-the-art gossip-based methods satisfy the first requirement, achieving robustness remains challenging. Asynchronous decentralized ADMM-based methods have been explored for estimating the median, a statistical centrality measure that is notoriously more robust than the mean. However, existing approaches require memory that scales with node degree, making them impractical when memory is limited. In this paper, we propose AsylADMM, a novel gossip algorithm for decentralized median and quantile estimation, primarily designed for asynchronous updates and requiring only two variables per node. We analyze a synchronous variant of AsylADMM to establish theoretical guarantees and empirically demonstrate fast convergence for the asynchronous algorithm. We then show that our algorithm enables quantile-based trimming, geometric median estimation, and depth-based trimming, with quantile-based trimming empirically outperforming existing rank-based methods. Finally, we provide a novel theoretical analysis of rank-based trimming via Markov chain theory.

Related papers

• Asynchronous Gossip Algorithms for Rank-Based Statistical Methods [2.6636053598505307]
  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.
  arXiv  Detail & Related papers  (2025-09-09T09:23:36Z)
• Theory of Decentralized Robust Kernel-Based Learning [8.407288892993703]
  We propose a new robust kernel-based learning algorithm within the framework of reproducing kernel Hilbert spaces.<n>We show each local robust estimator generated from the decentralized algorithm can be utilized to approximate the regression function.<n>We provide rigorous selection rules for local sample size and show that, under properly selected step size and scaling parameter $sigma$, the decentralized robust algorithm can achieve optimal learning rates.
  arXiv  Detail & Related papers  (2025-06-05T16:30:05Z)
• 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)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Exploiting Structure for Optimal Multi-Agent Bayesian Decentralized Estimation [4.320393382724066]
  Key challenge in Bayesian decentralized data fusion is the rumor propagation' or double counting' phenomenon. We show that by exploiting the probabilistic independence structure in multi-agent decentralized fusion problems a tighter bound can be found. We then test our new non-monolithic CI algorithm on a large-scale target tracking simulation and show that it achieves a tighter bound and a more accurate estimate.
  arXiv  Detail & Related papers  (2023-07-20T05:16:33Z)
• Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning [55.198301429316125]
  Machine learning (ML) is a key technique for big-data-driven modelling and analysis of massive Internet of Things (IoT) based intelligent and ubiquitous computing. For fast-increasing applications and data amounts, distributed learning is a promising emerging paradigm since it is often impractical or inefficient to share/aggregate data. This paper studies the problem of training an ML model over decentralized systems, where data are distributed over many user devices.
  arXiv  Detail & Related papers  (2022-02-07T15:04:15Z)
• Adaptive Stochastic ADMM for Decentralized Reinforcement Learning in Edge Industrial IoT [106.83952081124195]
  Reinforcement learning (RL) has been widely investigated and shown to be a promising solution for decision-making and optimal control processes. We propose an adaptive ADMM (asI-ADMM) algorithm and apply it to decentralized RL with edge-computing-empowered IIoT networks. Experiment results show that our proposed algorithms outperform the state of the art in terms of communication costs and scalability, and can well adapt to complex IoT environments.
  arXiv  Detail & Related papers  (2021-06-30T16:49:07Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  Big data, including applications with high security requirements, are often collected and stored on multiple heterogeneous devices, such as mobile devices, drones and vehicles. Due to the limitations of communication costs and security requirements, it is of paramount importance to extract information in a decentralized manner instead of aggregating data to a fusion center. We consider the problem of learning model parameters in a multi-agent system with data locally processed via distributed edge nodes. A class of mini-batch alternating direction method of multipliers (ADMM) algorithms is explored to develop the distributed learning model.
  arXiv  Detail & Related papers  (2020-10-02T10:41:59Z)
• Optimal Complexity in Decentralized Training [45.468216452357375]
  We present a gossip-style decentralized algorithm that achieves the lower bound with only a gap. We show DeTAG enjoys faster convergence compared to baselines, especially on unshuffled data and in sparse networks.
  arXiv  Detail & Related papers  (2020-06-15T02:03:04Z)
• Q-GADMM: Quantized Group ADMM for Communication Efficient Decentralized Machine Learning [66.18202188565922]
  We propose a communication-efficient decentralized machine learning (ML) algorithm, coined QGADMM (QGADMM)<n>We develop a novel quantization method to adaptively adjust modelization levels and their probabilities, while proving the convergence of QGADMM for convex functions.
  arXiv  Detail & Related papers  (2019-10-23T10:47:06Z)

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.