Author name cluster

Ran Ben-Basat

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

2 author rows

ICML Conference 2024 Conference Paper

Accelerating Federated Learning with Quick Distributed Mean Estimation

Ran Ben-Basat
Shay Vargaftik
Amit Portnoy
Gil Einziger
Yaniv Ben-Itzhak
Michael Mitzenmacher

Distributed Mean Estimation (DME), in which $n$ clients communicate vectors to a parameter server that estimates their average, is a fundamental building block in communication-efficient federated learning. In this paper, we improve on previous DME techniques that achieve the optimal $O(1/n)$ Normalized Mean Squared Error (NMSE) guarantee by asymptotically improving the complexity for either encoding or decoding (or both). To achieve this, we formalize the problem in a novel way that allows us to use off-the-shelf mathematical solvers to design the quantization. Using various datasets and training tasks, we demonstrate how QUIC-FL achieves state of the art accuracy with faster encoding and decoding times compared to other DME methods.

Details

ICML Conference 2022 Conference Paper

EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning

Shay Vargaftik
Ran Ben-Basat
Amit Portnoy
Gal Mendelson
Yaniv Ben-Itzhak
Michael Mitzenmacher

Distributed Mean Estimation (DME) is a central building block in federated learning, where clients send local gradients to a parameter server for averaging and updating the model. Due to communication constraints, clients often use lossy compression techniques to compress the gradients, resulting in estimation inaccuracies. DME is more challenging when clients have diverse network conditions, such as constrained communication budgets and packet losses. In such settings, DME techniques often incur a significant increase in the estimation error leading to degraded learning performance. In this work, we propose a robust DME technique named EDEN that naturally handles heterogeneous communication budgets and packet losses. We derive appealing theoretical guarantees for EDEN and evaluate it empirically. Our results demonstrate that EDEN consistently improves over state-of-the-art DME techniques.

Details

NeurIPS Conference 2021 Conference Paper

DRIVE: One-bit Distributed Mean Estimation

Shay Vargaftik
Ran Ben-Basat
Amit Portnoy
Gal Mendelson
Yaniv Ben-Itzhak
Michael Mitzenmacher

We consider the problem where $n$ clients transmit $d$-dimensional real-valued vectors using $d(1+o(1))$ bits each, in a manner that allows the receiver to approximately reconstruct their mean. Such compression problems naturally arise in distributed and federated learning. We provide novel mathematical results and derive computationally efficient algorithms that are more accurate than previous compression techniques. We evaluate our methods on a collection of distributed and federated learning tasks, using a variety of datasets, and show a consistent improvement over the state of the art.

PDF Details

MFCS Conference 2018 Conference Paper

Give Me Some Slack: Efficient Network Measurements

Ran Ben-Basat
Gil Einziger
Roy Friedman 0001

Many networking applications require timely access to recent network measurements, which can be captured using a sliding window model. Maintaining such measurements is a challenging task due to the fast line speed and scarcity of fast memory in routers. In this work, we study the impact of allowing slack in the window size on the asymptotic requirements of sliding window problems. That is, the algorithm can dynamically adjust the window size between W and W(1+tau) where tau is a small positive parameter. We demonstrate this model's attractiveness by showing that it enables efficient algorithms to problems such as Maximum and General-Summing that require Omega(W) bits even for constant factor approximations in the exact sliding window model. Additionally, for problems that admit sub-linear approximation algorithms such as Basic-Summing and Count-Distinct, the slack model enables a further asymptotic improvement. The main focus of the paper is on the widely studied Basic-Summing problem of computing the sum of the last W integers from {0, 1. .. ,R} in a stream. While it is known that Omega(W log R) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant tau. Specifically, for tau=Theta(1), we present a space lower bound of Omega(log(RW)) bits. Additionally, we show an Omega(log (W/epsilon)) lower bound for RW epsilon additive approximations and a Omega(log (W/epsilon)+log log R) bits lower bound for (1+epsilon) multiplicative approximations. Our work is the first to study this problem in the exact and additive approximation settings. For all settings, we provide memory optimal algorithms that operate in worst case constant time. This strictly improves on the work of [Mayur Datar et al. , 2002] for (1+epsilon)-multiplicative approximation that requires O(epsilon^(-1) log(RW)log log (RW)) space and performs updates in O(log (RW)) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing and Maximum problems.

Details

TCS Journal 2016 Journal Article

The k-distinct language: Parameterized automata constructions

Ran Ben-Basat
Ariel Gabizon
Meirav Zehavi

In this paper, we pioneer a study of parameterized automata constructions for languages related to the design of parameterized algorithms. We focus on the k-Distinct language L k ( Σ ) ⊆ Σ k, defined as the set of words of length k over an alphabet Σ whose symbols are all distinct. This language is implicitly related to several breakthrough techniques developed during the last two decades, to design parameterized algorithms for fundamental problems such as k-Path and r-Dimensional k-Matching. Building upon the color coding, divide-and-color and narrow sieves techniques, we obtain the following automata constructions for L k ( Σ ). We develop non-deterministic automata (NFAs) of sizes 4 k + o ( k ) ⋅ n O ( 1 ) and ( 2 e ) k + o ( k ) ⋅ n O ( 1 ), where the latter satisfies a ‘bounded ambiguity’ property relevant to approximate counting, as well as a non-deterministic xor automaton (NXA) of size 2 k ⋅ n O ( 1 ), where n = | Σ |. We show that our constructions can be used to develop both deterministic and randomized algorithms for k-Path, r-Dimensional k -Matching and Module Motif in a natural manner, considering also their approximate counting variants. Our framework is modular and consists of two parts: designing an automaton for k-Distinct, and designing a problem specific automaton, as well as an algorithm for deciding whether the intersection automaton's language is empty, or for counting the number of accepting paths in it.

Details DOI