Author name cluster

Gil Einziger

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

UAI Conference 2022 Conference Paper

A geometric method for improved uncertainty estimation in real-time

Gabriella Chouraqui
Liron Cohen 0001
Gil Einziger
Liel Leman

Machine learning classifiers are probabilistic in nature, and thus inevitably involve uncertainty. Predicting the probability of a specific input to be correct is called uncertainty (or confidence) estimation and is crucial for risk management. Post-hoc model calibrations can improve models’ uncertainty estimations without the need for retraining, and without changing the model. Our work puts forward a geometric-based approach for uncertainty estimation. Roughly speaking, we use the geometric distance of the current input from the existing training inputs as a signal for estimating uncertainty and then calibrate that signal (instead of the model’s estimation) using standard post-hoc calibration techniques. We show that our method yields better uncertainty estimations than recently proposed approaches by extensively evaluating multiple datasets and models. In addition, we also demonstrate the possibility of performing our approach in near real-time applications. Our code is available at our Github: https: //github. com/NoSleepDeveloper/Geometric-Calibrator

Details

TCS Journal 2019 Journal Article

Give me some slack: Efficient network measurements

Ran Ben Basat
Gil Einziger
Roy Friedman

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 + τ ) where τ 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 Ω ( 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 Ω ( W log ⁡ R ) bits are needed in the exact window model, we show that approximate windows allow an exponential space reduction for constant τ. Specifically, for τ = Θ ( 1 ), we present a space lower bound of Ω ( log ⁡ ( R W ) ) bits. Additionally, we show an Ω ( log ⁡ ( W / ϵ ) ) lower bound for RWϵ additive approximations and a Ω ( log ⁡ ( W / ϵ ) + log ⁡ log ⁡ R ) bits lower bound for ( 1 + ϵ ) 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 [17] for ( 1 + ϵ ) -multiplicative approximation that requires O ( ϵ − 1 log ⁡ ( R W ) log ⁡ log ⁡ ( R W ) ) space and performs updates in O ( log ⁡ ( R W ) ) worst case time. Finally, we show asymptotic improvements for the Count-Distinct, General-Summing, and Maximum problems.

Details DOI

AAAI Conference 2019 Conference Paper

Verifying Robustness of Gradient Boosted Models

Gil Einziger
Maayan Goldstein
Yaniv Sa’ar
Itai Segall

Gradient boosted models are a fundamental machine learning technique. Robustness to small perturbations of the input is an important quality measure for machine learning models, but the literature lacks a method to prove the robustness of gradient boosted models. This work introduces VERIGB, a tool for quantifying the robustness of gradient boosted models. VERIGB encodes the model and the robustness property as an SMT formula, which enables state of the art verification tools to prove the model’s robustness. We extensively evaluate VERIGB on publicly available datasets and demonstrate a capability for verifying large models. Finally, we show that some model configurations tend to be inherently more robust than others.

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