# Fast networked data selection via distributed smoothed quantile estimation

arXiv: https://arxiv.org/abs/2406.01929 · HTML: https://mlsanity.com/paper/2406.01929/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 65 references that are in the map.
- First posted on arXiv 4 Jun 2024.

## Builds on (most cited first, 18 of 18)

- [Client Selection for Federated Learning with Heterogeneous Resources in Mobile Edge](https://mlsanity.com/paper/1804.08333/) (2018)
- [Client Selection in Federated Learning: Convergence Analysis and Power-of-Choice Selection Strategies](https://mlsanity.com/paper/2010.01243/) (2020)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Smoothed Quantile Regression with Large-Scale Inference](https://mlsanity.com/paper/2012.05187/) (2020)
- [Convergence Rate of Distributed ADMM over Networks](https://mlsanity.com/paper/1601.00194/) (2016)
- [Smoothing quantile regressions](https://mlsanity.com/paper/1905.08535/) (2019)
- [Revisiting EXTRA for Smooth Distributed Optimization](https://mlsanity.com/paper/2002.10110/) (2020)
- [Submodular Observation Selection and Information Gathering for Quadratic Models](https://mlsanity.com/paper/1905.09919/) (2019)
- [Distributed support-vector-machine over dynamic balanced directed networks](https://mlsanity.com/paper/2104.00399/) (2021)
- [Client Selection in Federated Learning based on Gradients Importance](https://mlsanity.com/paper/2111.11204/) (2021)
- [Improved Convergence Rate for a Distributed Two-Time-Scale Gradient Method under Random Quantization](https://mlsanity.com/paper/2105.14089/) (2021)
- [Discretized Distributed Optimization over Dynamic Digraphs](https://mlsanity.com/paper/2311.07939/) (2023)
- [Optimal Gossip Algorithms for Exact and Approximate Quantile Computations](https://mlsanity.com/paper/1711.09258/) (2017)
- [Distributed remote estimation over the collision channel with and without local communication](https://mlsanity.com/paper/2005.11438/) (2020)
- [Top-k data selection via distributed sample quantile inference](https://mlsanity.com/paper/2212.00230/) (2022)
- [Communication Efficient Algorithms for Top-k Selection Problems](https://mlsanity.com/paper/1502.03942/) (2015)
- [Critical Connectivity and Fastest Convergence Rates of Distributed Consensus with Switching Topologies and Additive Noises](https://mlsanity.com/paper/1510.07021/) (2015)

## Abstract (arXiv)

Collecting the most informative data from a large dataset distributed over a network is a fundamental problem in many fields, including control, signal processing and machine learning. In this paper, we establish a connection between selecting the most informative data and finding the top-k elements of a multiset. The top-k selection in a network can be formulated as a distributed nonsmooth convex optimization problem known as quantile estimation. Unfortunately, the lack of smoothness in the local objective functions leads to extremely slow convergence and poor scalability with respect to the network size. To overcome the deficiency, we propose an accelerated method that employs smoothing techniques. Leveraging the piecewise linearity of the local objective functions in quantile estimation, we characterize the iteration complexity required to achieve top-k selection, a challenging task due to the lack of strong convexity. Several numerical results are provided to validate the effectiveness of the algorithm and the correctness of the theory.