28 citations · 174 across the 52 of their papers we have counts for
32 papers · 1 filter
Vanilla Policy Optimization Is Both Optimal and Differentially Private for Stochastic Contextual Bandits
Idan Attias, Orin Levy, Alexander Ryabchenko +2
Can vanilla policy optimization explore enough to achieve near-optimal regret in stochastic contextual bandits? We show that standard exponential policy updates driven by offline r…
Protecting the Undeleted in Machine Unlearning
Aloni Cohen, Refael Kohen, Kobbi Nissim +1
Machine unlearning aims to remove specific data points from a trained model, often striving to emulate "perfect retraining", i.e., producing the model that would have been obtained…
The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for Norm Estimation
Sara Ahmadian, Edith Cohen, Uri Stemmer
Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the black-box adversarial se…
Nearly Optimal Sample Complexity for Learning with Label Proportions
Robert Busa-Fekete, Travis Dick, Claudio Gentile +3
We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each…
Private Truly-Everlasting Robust-Prediction
Uri Stemmer
Private Everlasting Prediction (PEP), recently introduced by Naor et al. [2023], is a model for differentially private learning in which the learner never publicly releases a hypot…
Hot PATE: Private Aggregation of Distributions for Diverse Task
Edith Cohen, Benjamin Cohen-Wang, Xin Lyu +3
The Private Aggregation of Teacher Ensembles (PATE) framework enables privacy-preserving machine learning by aggregating responses from disjoint subsets of sensitive data. Adaptati…
Private Everlasting Prediction
Moni Naor, Kobbi Nissim, Uri Stemmer +1
A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privac…
Adaptive Data Analysis in a Balanced Adversarial Model
Kobbi Nissim, Uri Stemmer, Eliad Tsfadia
In adaptive data analysis, a mechanism gets i.i.d. samples from an unknown distribution , and is required to provide accurate estimations to a sequence of adaptively chosen…
On Differentially Private Online Predictions
Haim Kaplan, Yishay Mansour, Shay Moran +2
In this work we introduce an interactive variant of joint differential privacy towards handling online processes in which existing privacy definitions seem too restrictive. We stud…
Concurrent Shuffle Differential Privacy Under Continual Observation
Jay Tenenbaum, Haim Kaplan, Yishay Mansour +1
We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batc…
Differentially-Private Bayes Consistency
Olivier Bousquet, Haim Kaplan, Aryeh Kontorovich +4
We construct a universally Bayes consistent learning rule that satisfies differential privacy (DP). We first handle the setting of binary classification and then extend our rule to…
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
Edith Cohen, Xin Lyu, Jelani Nelson +2
The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of (for generalizati…
Monotone Learning
Olivier Bousquet, Amit Daniely, Haim Kaplan +3
The amount of training-data is one of the key factors which determines the generalization capacity of learning algorithms. Intuitively, one expects the error rate to decrease as th…
Adaptive Data Analysis with Correlated Observations
Aryeh Kontorovich, Menachem Sadigurschi, Uri Stemmer
The vast majority of the work on adaptive data analysis focuses on the case where the samples in the dataset are independent. Several approaches and tools have been successfully ap…
Differentially-Private Clustering of Easy Instances
Edith Cohen, Haim Kaplan, Yishay Mansour +2
Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify cluster centers without disclosing information on individual…
Differentially Private Approximate Quantiles
Haim Kaplan, Shachar Schnapp, Uri Stemmer
In this work we study the problem of differentially private (DP) quantiles, in which given dataset and quantiles , we want to output quantile estim…
FriendlyCore: Practical Differentially Private Aggregation
Eliad Tsfadia, Edith Cohen, Haim Kaplan +2
Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or to the large numb…
On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
Menachem Sadigurschi, Uri Stemmer
We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid with differential privacy. Existing results show that the sam…
Differentially Private Multi-Armed Bandits in the Shuffle Model
Jay Tenenbaum, Haim Kaplan, Yishay Mansour +1
We give an -differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model with a distribution-dependent regret of $O\left(\left(\s…
The Sparse Vector Technique, Revisited
Haim Kaplan, Yishay Mansour, Uri Stemmer
We revisit one of the most basic and widely applicable techniques in the literature of differential privacy - the sparse vector technique [Dwork et al., STOC 2009]. This simple alg…
Differentially Private Weighted Sampling
Edith Cohen, Ofir Geri, Tamas Sarlos +1
Common datasets have the form of elements with keys (e.g., transactions and products) and the goal is to perform analytics on the aggregated form of key and frequency pairs. A weig…
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
Haim Kaplan, Yishay Mansour, Uri Stemmer +1
We present a differentially private learner for halfspaces over a finite grid in with sample complexity , which improves the…
Closure Properties for Private Classification and Online Prediction
Noga Alon, Amos Beimel, Shay Moran +1
Let~$\cH$ be a class of boolean functions and consider a {\it composed class} $\cH'$ that is derived from~$\cH$ using some arbitrary aggregation rule (for example, $\cH'$ may be th…
Locally Private k-Means Clustering
Uri Stemmer
We design a new algorithm for the Euclidean -means problem that operates in the local model of differential privacy. Unlike in the non-private literature, differentially private…