Publications (86)
On The Hereditary Discrepancy of Homogeneous Arithmetic Progressions
Aleksandar Nikolov, Kunal Talwar
We show that the hereditary discrepancy of homogeneous arithmetic progressions is lower bounded by . This bound is tight up to the constant in the exponent. O…
Privacy-Computation trade-offs in Private Repetition and Metaselection
Kunal Talwar
A Private Repetition algorithm takes as input a differentially private algorithm with constant success probability and boosts it to one that succeeds with high probability. These a…
Online learning over a finite action set with limited switching
Jason Altschuler, Kunal Talwar
This paper studies the value of switching actions in the Prediction From Experts (PFE) problem and Adversarial Multi-Armed Bandits (MAB) problem. First, we revisit the well-studied…
Differential Secrecy for Distributed Data and Applications to Robust Differentially Secure Vector Summation
Kunal Talwar
Computing the noisy sum of real-valued vectors is an important primitive in differentially private learning and statistics. In private federated learning applications, these vector…
Vertex Sparsifiers: New Results from Old Techniques
Matthias Englert, Anupam Gupta, Robert Krauthgamer +3
Given a capacitated graph and a set of terminals , how should we produce a graph only on the terminals so that every (multicommodity) flow betwee…
Sketching and Neural Networks
Amit Daniely, Nevena Lazic, Yoram Singer +1
High-dimensional sparse data present computational and statistical challenges for supervised learning. We propose compact linear sketches for reducing the dimensionality of the inp…
On the Protection of Private Information in Machine Learning Systems: Two Recent Approaches
MartÃn Abadi, Ãlfar Erlingsson, Ian Goodfellow +5
The recent, remarkable growth of machine learning has led to intense interest in the privacy of the data on which machine learning relies, and to new techniques for preserving priv…
Optimal Algorithms for Mean Estimation under Local Differential Privacy
Hilal Asi, Vitaly Feldman, Kunal Talwar
We study the problem of mean estimation of -bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achiev…
Subspace Recovery from Heterogeneous Data with Non-isotropic Noise
John Duchi, Vitaly Feldman, Lunjia Hu +1
Recovering linear subspaces from data is a fundamental and important task in statistics and machine learning. Motivated by heterogeneity in Federated Learning settings, we study a…
Instance-Optimality for Private KL Distribution Estimation
Jiayuan Ye, Vitaly Feldman, Kunal Talwar
We study the fundamental problem of estimating an unknown discrete distribution over symbols, given i.i.d. samples from the distribution. We are interested in minimizin…
Improved Sample Complexity for Private Nonsmooth Nonconvex Optimization
Guy Kornowski, Daogao Liu, Kunal Talwar
We study differentially private (DP) optimization algorithms for stochastic and empirical objectives which are neither smooth nor convex, and propose methods that return a Goldstei…
Concentration of the Langevin Algorithm's Stationary Distribution
Jason M. Altschuler, Kunal Talwar
A canonical algorithm for log-concave sampling is the Langevin Algorithm, aka the Langevin Diffusion run with some discretization stepsize . This discretization leads the La…
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
Gavin Brown, Mark Bun, Vitaly Feldman +2
Modern machine learning models are complex and frequently encode surprising amounts of information about individual inputs. In extreme cases, complex models appear to memorize enti…
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation
Ãlfar Erlingsson, Vitaly Feldman, Ilya Mironov +4
Recently, a number of approaches and techniques have been introduced for reporting software statistics with strong privacy guarantees. These range from abstract algorithms to compr…
Rényi Differential Privacy of the Sampled Gaussian Mechanism
Ilya Mironov, Kunal Talwar, Li Zhang
The Sampled Gaussian Mechanism (SGM)---a composition of subsampling and the additive Gaussian noise---has been successfully used in a number of machine learning applications. The m…
Characterizing Structural Regularities of Labeled Data in Overparameterized Models
Ziheng Jiang, Chiyuan Zhang, Kunal Talwar +1
Humans are accustomed to environments that contain both regularities and exceptions. For example, at most gas stations, one pays prior to pumping, but the occasional rural station…
Cram Less to Fit More: Training Data Pruning Improves Memorization of Facts
Jiayuan Ye, Vitaly Feldman, Kunal Talwar
Large language models (LLMs) can struggle to memorize factual knowledge in their parameters, often leading to hallucinations and poor performance on knowledge-intensive tasks. In t…
Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime
Hilal Asi, Vitaly Feldman, Tomer Koren +1
We consider online learning problems in the realizable setting, where there is a zero-loss solution, and propose new Differentially Private (DP) algorithms that obtain near-optimal…
Constrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithms
Anupam Gupta, Aaron Roth, Grant Schoenebeck +1
Constrained submodular maximization problems have long been studied, with near-optimal results known under a variety of constraints when the submodular function is monotone. The ca…
Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
Arun Ganesh, Kunal Talwar
Various differentially private algorithms instantiate the exponential mechanism, and require sampling from the distribution for a suitable function . When the domain…
On Privacy-Preserving Histograms
Shuchi Chawla, Cynthia Dwork, Frank McSherry +1
We advance the approach initiated by Chawla et al. for sanitizing (census) data so as to preserve the privacy of respondents while simultaneously extracting "useful" statistical in…
Stronger Privacy Amplification by Shuffling for Rényi and Approximate Differential Privacy
Vitaly Feldman, Audra McMillan, Kunal Talwar
The shuffle model of differential privacy has gained significant interest as an intermediate trust model between the standard local and central models [EFMRTT19; CSUZZ19]. A key re…
Adaptive Batch Size for Privately Finding Second-Order Stationary Points
Daogao Liu, Kunal Talwar
There is a gap between finding a first-order stationary point (FOSP) and a second-order stationary point (SOSP) under differential privacy constraints, and it remains unclear wheth…
Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Xin Lyu, Kunal Talwar
Fingerprinting codes are a crucial tool for proving lower bounds in differential privacy. They have been used to prove tight lower bounds for several fundamental questions, especia…
Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling
Jason M. Altschuler, Kunal Talwar
Sampling from a high-dimensional distribution is a fundamental task in statistics, engineering, and the sciences. A canonical approach is the Langevin Algorithm, i.e., the Markov c…
Private Stochastic Convex Optimization with Optimal Rates
Raef Bassily, Vitaly Feldman, Kunal Talwar +1
We study differentially private (DP) algorithms for stochastic convex optimization (SCO). In this problem the goal is to approximately minimize the population loss given i.i.d. sam…
Private Stochastic Convex Optimization: Optimal Rates in Linear Time
Vitaly Feldman, Tomer Koren, Kunal Talwar
We study differentially private (DP) algorithms for stochastic convex optimization: the problem of minimizing the population loss given i.i.d. samples from a distribution over conv…
Private Online Learning via Lazy Algorithms
Hilal Asi, Tomer Koren, Daogao Liu +1
We study the problem of private online learning, specifically, online prediction from experts (OPE) and online convex optimization (OCO). We propose a new transformation that trans…
Deep Learning with Differential Privacy
MartÃn Abadi, Andy Chu, Ian Goodfellow +4
Machine learning techniques based on neural networks are achieving remarkable results in a wide variety of domains. Often, the training of models requires large, representative dat…
PINE: Efficient Norm-Bound Verification for Secret-Shared Vectors
Guy N. Rothblum, Eran Omri, Junye Chen +1
Secure aggregation of high-dimensional vectors is a fundamental primitive in federated statistics and learning. A two-server system such as PRIO allows for scalable aggregation of…
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
Hilal Asi, Vitaly Feldman, Jelani Nelson +3
We study the problem of private vector mean estimation in the shuffle model of privacy where users each have a unit vector . We propose a new multi-mes…
Online Linear Quadratic Control
Alon Cohen, Avinatan Hassidim, Tomer Koren +3
We study the problem of controlling linear time-invariant systems with known noisy dynamics and adversarially chosen quadratic losses. We present the first efficient online learnin…
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
Vitaly Feldman, Audra McMillan, Kunal Talwar
Recent work of Erlingsson, Feldman, Mironov, Raghunathan, Talwar, and Thakurta [EFMRTT19] demonstrates that random shuffling amplifies differential privacy guarantees of locally ra…
LAST but not Least: Online Spanners for Buy-at-Bulk
Anupam Gupta, R. Ravi, Kunal Talwar +1
The online (uniform) buy-at-bulk network design problem asks us to design a network, where the edge-costs exhibit economy-of-scale. Previous approaches to this problem used tree- e…
The Importance of Being Smoothly Calibrated
Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar +1
Recent work has highlighted the centrality of smooth calibration [Kakade and Foster, 2008] as a robust measure of calibration error. We generalize, unify, and extend previous resul…
Instance-Optimal Private Density Estimation in the Wasserstein Distance
Vitaly Feldman, Audra McMillan, Satchit Sivakumar +1
Estimating the density of a distribution from samples is a fundamental problem in statistics. In many practical settings, the Wasserstein distance is an appropriate error metric fo…
Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data
Nicolas Papernot, MartÃn Abadi, Ãlfar Erlingsson +2
Some machine learning applications involve training data that is sensitive, such as the medical histories of patients in a clinical trial. A model may inadvertently and implicitly…
TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
MartÃn Abadi, Ashish Agarwal, Paul Barham +37
TensorFlow is an interface for expressing machine learning algorithms, and an implementation for executing such algorithms. A computation expressed using TensorFlow can be executed…
Changing Bases: Multistage Optimization for Matroids and Matchings
Anupam Gupta, Kunal Talwar, Udi Wieder
This paper is motivated by the fact that many systems need to be maintained continually while the underlying costs change over time. The challenge is to continually maintain near-o…
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán +1
Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. A…
Approximating Hereditary Discrepancy via Small Width Ellipsoids
Aleksandar Nikolov, Kunal Talwar
The Discrepancy of a hypergraph is the minimum attainable value, over two-colorings of its vertices, of the maximum absolute imbalance of any hyperedge. The Hereditary Discrepancy…
Differentially Private Heavy Hitter Detection using Federated Analytics
Karan Chadha, Junye Chen, John Duchi +5
In this work, we study practical heuristics to improve the performance of prefix-tree based algorithms for differentially private heavy hitter detection. Our model assumes each use…
Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry
Kunal Talwar, Abhradeep Thakurta, Li Zhang
Empirical Risk Minimization (ERM) is a standard technique in machine learning, where a model is selected by minimizing a loss function over constraint set. When the training datase…
Faster Rates for Private Adversarial Bandits
Hilal Asi, Vinod Raman, Kunal Talwar
We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conv…
Factorization Norms and Hereditary Discrepancy
Jiri Matousek, Aleksandar Nikolov, Kunal Talwar
The norm of a real matrix is the minimum number such that the column vectors of are contained in a -centered ellipsoid wh…
Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss
Jason M. Altschuler, Kunal Talwar
A central issue in machine learning is how to train models on sensitive user data. Industry has widely adopted a simple algorithm: Stochastic Gradient Descent with noise (a.k.a. St…
How to Complete a Doubling Metric
Anupam Gupta, Kunal Talwar
In recent years, considerable advances have been made in the study of properties of metric spaces in terms of their doubling dimension. This line of research has not only enhanced…
Stochastic Optimization with Laggard Data Pipelines
Naman Agarwal, Rohan Anil, Tomer Koren +2
State-of-the-art optimization is steadily shifting towards massively parallel pipelines with extremely large batch sizes. As a consequence, CPU-bound preprocessing and disk/memory/…
The Geometry of Differential Privacy: the Sparse and Approximate Cases
Aleksandar Nikolov, Kunal Talwar, Li Zhang
In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables an…
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Parikshit Gopalan, Noam Nisan, Rocco A. Servedio +2
A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure…
Private Online Prediction from Experts: Separations and Faster Rates
Hilal Asi, Vitaly Feldman, Tomer Koren +1
Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algori…
Private Frequency Estimation via Projective Geometry
Vitaly Feldman, Jelani Nelson, Huy Lê Nguyen +1
In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of and with use…
Learning Differentially Private Recurrent Language Models
H. Brendan McMahan, Daniel Ramage, Kunal Talwar +1
We demonstrate that it is possible to train large recurrent language models with user-level differential privacy guarantees with only a negligible cost in predictive accuracy. Our…
Fast Optimal Locally Private Mean Estimation via Random Projections
Hilal Asi, Vitaly Feldman, Jelani Nelson +2
We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball. Existing algorithms for this problem either incur sub-optimal error or ha…
On Privately Estimating a Single Parameter
Hilal Asi, John C. Duchi, Kunal Talwar
We investigate differentially private estimators for individual parameters within larger parametric models. While generic private estimators exist, the estimators we provide repose…
Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs
Ittai Abraham, Cyril Gavoille, Anupam Gupta +2
We prove that any graph excluding as a minor has can be partitioned into clusters of diameter at most while removing at most fraction of the edges. This improv…
Semi-Cyclic Stochastic Gradient Descent
Hubert Eichner, Tomer Koren, H. Brendan McMahan +2
We consider convex SGD updates with a block-cyclic structure, i.e. where each cycle consists of a small number of blocks, each with many samples from a possibly different, block-sp…
Privacy Amplification by Iteration
Vitaly Feldman, Ilya Mironov, Kunal Talwar +1
Many commonly used learning algorithms work by iteratively updating an intermediate solution using one or a few data points in each iteration. Analysis of differential privacy for…
Differentially Private Combinatorial Optimization
Anupam Gupta, Katrina Ligett, Frank McSherry +2
Consider the following problem: given a metric space, some of whose points are "clients", open a set of at most facilities to minimize the average distance from the clients to…
Private Adaptive Gradient Methods for Convex Optimization
Hilal Asi, John Duchi, Alireza Fallah +2
We study adaptive methods for differentially private convex optimization, proposing and analyzing differentially private variants of a Stochastic Gradient Descent (SGD) algorithm w…
PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
Hilal Asi, Vitaly Feldman, Hannah Keller +2
We revisit the problem of secure aggregation of high-dimensional vectors in a two-server system such as Prio. These systems are typically used to aggregate vectors such as gradient…
Private Federated Statistics in an Interactive Setting
Audra McMillan, Omid Javidbakht, Kunal Talwar +21
Privately learning statistics of events on devices can enable improved user experience. Differentially private algorithms for such problems can benefit significantly from interacti…
FLAIR: Federated Learning Annotated Image Repository
Congzheng Song, Filip Granqvist, Kunal Talwar
Cross-device federated learning is an emerging machine learning (ML) paradigm where a large population of devices collectively train an ML model while the data remains on the devic…
Oblivious Stash Shuffle
Petros Maniatis, Ilya Mironov, Kunal Talwar
This is a companion report to Bittau et al. We restate and prove security of the Stash Shuffle.
On the Error Resistance of Hinge Loss Minimization
Kunal Talwar
Commonly used classification algorithms in machine learning, such as support vector machines, minimize a convex surrogate loss on training examples. In practice, these algorithms a…
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
Ãlfar Erlingsson, Vitaly Feldman, Ilya Mironov +3
Sensitive statistics are often collected across sets of users, with repeated collection of reports done over time. For example, trends in users' private preferences or software usa…
Sparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Results
Anupam Gupta, Kunal Talwar, David Witmer
We give a 2-approximation algorithm for Non-Uniform Sparsest Cut that runs in time , where is the treewidth of the graph. This improves on the previous -appr…
On the Geometry of Differential Privacy
Moritz Hardt, Kunal Talwar
We consider the noise complexity of differentially private mechanisms in the setting where the user asks linear queries $f\colon\Rn\to\Re$ non-adaptively. Here, the database is…
Efficient Calibration for Decision Making
Parikshit Gopalan, Konstantinos Stavropoulos, Kunal Talwar +1
A decision-theoretic characterization of perfect calibration is that an agent seeking to minimize a proper loss in expectation cannot improve their outcome by post-processing a per…
Lossless Compression of Efficient Private Local Randomizers
Vitaly Feldman, Kunal Talwar
Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting. In many cases the best known LDP algorith…
Random Rates for 0-Extension and Low-Diameter Decompositions
Anupam Gupta, Kunal Talwar
Consider the problem of partitioning an arbitrary metric space into pieces of diameter at most Î, such every pair of points is separated with relatively low probability. We propos…
Lower Bounds on Near Neighbor Search via Metric Expansion
Rina Panigrahy, Kunal Talwar, Udi Wieder
In this paper we show how the complexity of performing nearest neighbor (NNS) search on a metric space is related to the expansion of the metric space. Given a metric space we look…
Better Algorithms for Stochastic Bandits with Adversarial Corruptions
Anupam Gupta, Tomer Koren, Kunal Talwar
We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substanti…
Mean Estimation with User-level Privacy under Data Heterogeneity
Rachel Cummings, Vitaly Feldman, Audra McMillan +1
A key challenge in many modern data analysis tasks is that user data are heterogeneous. Different users may possess vastly different numbers of data points. More importantly, it ca…
Private Stochastic Convex Optimization: Optimal Rates in Geometry
Hilal Asi, Vitaly Feldman, Tomer Koren +1
Stochastic convex optimization over an -bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differe…
Private Selection from Private Candidates
Jingcheng Liu, Kunal Talwar
Differentially Private algorithms often need to select the best amongst many candidate options. Classical works on this selection problem require that the candidates' goodness, mea…
Scalable Private Learning with PATE
Nicolas Papernot, Shuang Song, Ilya Mironov +3
The rapid adoption of machine learning has increased concerns about the privacy implications of machine learning models trained on sensitive data, such as medical records or other…
Samplable Anonymous Aggregation for Private Federated Data Analysis
Kunal Talwar, Shan Wang, Audra McMillan +34
We revisit the problem of designing scalable protocols for private statistics and private federated learning when each device holds its private data. Locally differentially private…
Adversarially Robust Generalization Requires More Data
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras +2
Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high "standard" acc…
Enabling Differentially Private Federated Learning for Speech Recognition: Benchmarks, Adaptive Optimizers and Gradient Clipping
Martin Pelikan, Sheikh Shams Azam, Vitaly Feldman +4
While federated learning (FL) and differential privacy (DP) have been extensively studied, their application to automatic speech recognition (ASR) remains largely unexplored due to…
Computational Separations between Sampling and Optimization
Kunal Talwar
Two commonly arising computational tasks in Bayesian learning are Optimization (Maximum A Posteriori estimation) and Sampling (from the posterior distribution). In the convex case…
Local Pan-Privacy for Federated Analytics
Vitaly Feldman, Audra McMillan, Guy N. Rothblum +1
Pan-privacy was proposed by Dwork et al. as an approach to designing a private analytics system that retains its privacy properties in the face of intrusions that expose the system…
Consistent Weighted Sampling Made Fast, Small, and Easy
Bernhard Haeupler, Mark Manasse, Kunal Talwar
Document sketching using Jaccard similarity has been a workable effective technique in reducing near-duplicates in Web page and image search results, and has also proven useful in…
Balanced Allocations: A Simple Proof for the Heavily Loaded Case
Kunal Talwar, Udi Wieder
We provide a relatively simple proof that the expected gap between the maximum load and the average load in the two choice process is bounded by , irrespective…
Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations
Cynthia Dwork, Aleksandar Nikolov, Kunal Talwar
Consider a database of people, each represented by a bit-string of length corresponding to the setting of binary attributes. A -way marginal query is specified by a…
Wally: Batched Private Nearest Neighbor Search at Scale
Hilal Asi, Fabian Boemer, Nicholas Genise +8
We present Wally, a batched private nearest-neighbor search protocol that uses differential privacy to break the linear computation barrier of fully-oblivious schemes. In Tiptoe, t…