research
∙
07/28/2023
Mean Estimation with User-level Privacy under Data Heterogeneity
A key challenge in many modern data analysis tasks is that user data are...
share
research
∙
07/27/2023
Samplable Anonymous Aggregation for Private Federated Data Analysis
We revisit the problem of designing scalable protocols for private stati...
research
∙
07/21/2023
Differentially Private Heavy Hitter Detection using Federated Analytics
In this work, we study practical heuristics to improve the performance o...
research
∙
06/07/2023
Fast Optimal Locally Private Mean Estimation via Random Projections
We study the problem of locally private mean estimation of high-dimensio...
research
∙
02/27/2023
Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime
We consider online learning problems in the realizable setting, where th...
research
∙
11/18/2022
Private Federated Statistics in an Interactive Setting
Privately learning statistics of events on devices can enable improved u...
research
∙
10/24/2022
Private Online Prediction from Experts: Separations and Faster Rates
Online prediction from experts is a fundamental problem in machine learn...
research
∙
10/24/2022
Subspace Recovery from Heterogeneous Data with Non-isotropic Noise
Recovering linear subspaces from data is a fundamental and important tas...
research
∙
09/29/2022
No Free Lunch in "Privacy for Free: How does Dataset Condensation Help Privacy"
New methods designed to preserve data privacy require careful scrutiny. ...
research
∙
08/09/2022
Stronger Privacy Amplification by Shuffling for Rényi and Approximate Differential Privacy
The shuffle model of differential privacy has gained significant interes...
research
∙
05/05/2022
Optimal Algorithms for Mean Estimation under Local Differential Privacy
We study the problem of mean estimation of ℓ_2-bounded vectors under the...
research
∙
03/01/2022
Private Frequency Estimation via Projective Geometry
In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR...
research
∙
03/02/2021
Private Stochastic Convex Optimization: Optimal Rates in ℓ_1 Geometry
Stochastic convex optimization over an ℓ_1-bounded domain is ubiquitous ...
research
∙
02/24/2021
Lossless Compression of Efficient Private Local Randomizers
Locally Differentially Private (LDP) Reports are commonly used for colle...
research
∙
12/23/2020
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Th...
research
∙
12/11/2020
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
Modern machine learning models are complex and frequently encode surpris...
research
∙
08/25/2020
Individual Privacy Accounting via a Renyi Filter
We consider a sequential setting in which a single dataset of individual...
research
∙
08/09/2020
What Neural Networks Memorize and Why: Discovering the Long Tail via Influence Estimation
Deep learning algorithms are well-known to have a propensity for fitting...
research
∙
06/12/2020
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
Uniform stability is a notion of algorithmic stability that bounds the w...
research
∙
05/10/2020
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
We study differentially private (DP) algorithms for stochastic convex op...
research
∙
11/24/2019
PAC learning with stable and private predictions
We study binary classification algorithms for which the prediction on an...
research
∙
11/11/2019
Interaction is necessary for distributed learning with privacy or communication constraints
Local differential privacy (LDP) is a model where users send privatized ...
research
∙
08/27/2019
Private Stochastic Convex Optimization with Optimal Rates
We study differentially private (DP) algorithms for stochastic convex op...
research
∙
06/12/2019
Does Learning Require Memorization? A Short Tale about a Long Tail
State-of-the-art results on image recognition tasks are achieved using o...
research
∙
05/24/2019
The advantages of multiple classes for reducing overfitting from test set reuse
Excessive reuse of holdout data can lead to overfitting. However, there ...
research
∙
02/27/2019
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
Algorithmic stability is a classical approach to understanding and analy...
research
∙
12/24/2018
Generalization Bounds for Uniformly Stable Algorithms
Uniform stability of a learning algorithm is a classical notion of algor...
research
∙
11/29/2018
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
Sensitive statistics are often collected across sets of users, with repe...
research
∙
09/24/2018
Learning without Interaction Requires Separation
One of the key resources in large-scale learning systems is the number o...
research
∙
08/20/2018
Privacy Amplification by Iteration
Many commonly used learning algorithms work by iteratively updating an i...
research
∙
03/27/2018
Privacy-preserving Prediction
Ensuring differential privacy of models learned from sensitive user data...
research
∙
03/12/2018
The Everlasting Database: Statistical Validity at a Fair Price
The problem of handling adaptivity in data analysis, intentional or not,...
research
∙
12/19/2017
Calibrating Noise to Variance in Adaptive Data Analysis
Datasets are often used multiple times and each successive analysis may ...
research
∙
06/15/2017
Generalization for Adaptively-chosen Estimators via Stable Median
Datasets are often reused to perform multiple statistical analyses in an...
research
∙
11/20/2016
Dealing with Range Anxiety in Mean Estimation via Statistical Queries
We give algorithms for estimating the expectation of a given real-valued...
research
∙
08/15/2016
Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
In stochastic convex optimization the goal is to minimize a convex funct...
research
∙
08/07/2016
A General Characterization of the Statistical Query Complexity
Statistical query (SQ) algorithms are algorithms that have access to an ...
research
∙
07/11/2013
Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy
We describe a framework for designing efficient active learning algorith...
research
∙
11/05/2012
Learning using Local Membership Queries
We introduce a new model of membership query (MQ) learning, where the le...
research
∙
03/25/2011
Distribution-Independent Evolvability of Linear Threshold Functions
Valiant's (2007) model of evolvability models the evolutionary process o...
research
∙
12/03/2010