Kunal Talwar

ICLR Conference 2025 Conference Paper

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 whether privately finding an SOSP is more challenging than finding an FOSP. Specifically, Ganesh et al. (2023) claimed that an $\alpha$-SOSP can be found with $\alpha=\Tilde{O}(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{3/7})$, where $n$ is the dataset size, $d$ is the dimension, and $\epsilon$ is the differential privacy parameter. However, a recent analysis revealed an issue in their saddle point escape procedure, leading to weaker guarantees. Building on the SpiderBoost algorithm framework, we propose a new approach that uses adaptive batch sizes and incorporates the binary tree mechanism. Our method not only corrects this issue but also improves the results for privately finding an SOSP, achieving $\alpha=\Tilde{O}(\frac{1}{n^{1/3}}+(\frac{\sqrt{d}}{n\epsilon})^{1/2})$. This improved bound matches the state-of-the-art for finding a FOSP, suggesting that privately finding an SOSP may be achievable at no additional cost.

NeurIPS Conference 2025 Conference Paper

Enabling Differentially Private Federated Learning for Speech Recognition: Benchmarks, Adaptive Optimizers, and Gradient Clipping

• Martin Pelikan
• Shams Azam
• Vitaly Feldman
• Jan Silovsky
• Kunal Talwar
• Christopher Brinton
• Tatiana Likhomanenko

While federated learning (FL) and differential privacy (DP) have been extensively studied, their application to automatic speech recognition (ASR) remains largely unexplored due to the challenges in training large transformer models. Specifically, large models further exacerbate issues in FL as they are particularly susceptible to gradient heterogeneity across layers, unlike the relatively uniform gradient behavior observed in shallow models. As a result, prior works struggle to converge with standard optimization techniques, even in the absence of DP mechanisms. To the best of our knowledge, no existing work establishes a competitive, practical recipe for FL with DP in the context of ASR. To address this gap, we establish **the first benchmark for FL with DP** in end-to-end ASR. Our approach centers on per-layer clipping and layer-wise gradient normalization: theoretical analysis reveals that these techniques together mitigate clipping bias and gradient heterogeneity across layers in deeper models. Consistent with these theoretical insights, our empirical results show that FL with DP is viable under strong privacy guarantees, provided a population of at least several million users. Specifically, we achieve user-level ($7. 2$, $10^{-9}$)-DP (resp. ($4. 5$, $10^{-9}$)-DP) with only a 1. 3\% (resp. 4. 6\%) absolute drop in word error rate when extrapolating to high (resp. low) population scales for FL with DP in ASR. Although our experiments focus on ASR, the underlying principles we uncover — particularly those concerning gradient heterogeneity and layer-wise gradient normalization — offer broader guidance for designing scalable, privacy-preserving FL algorithms for large models across domains. Code of all experiments and benchmarks is available at https: //github. com/apple/ml-pfl4asr.

ICML Conference 2025 Conference Paper

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 conversion of any non-private bandit algorithm to a private bandit algorithm. Instantiating our conversion with existing non-private bandit algorithms gives a regret upper bound of $O\left(\frac{\sqrt{KT}}{\sqrt{\epsilon}}\right)$, improving upon the existing upper bound $O\left(\frac{\sqrt{KT \log(KT)}}{\epsilon}\right)$ for all $\epsilon \leq 1$. In particular, our algorithms allow for sublinear expected regret even when $\epsilon \leq \frac{1}{\sqrt{T}}$, establishing the first known separation between central and local differential privacy for this problem. For bandits with expert advice, we give the first differentially private algorithms, with expected regret $O\left(\frac{\sqrt{NT}}{\sqrt{\epsilon}}\right), O\left(\frac{\sqrt{KT\log(N)}\log(KT)}{\epsilon}\right)$, and $\tilde{O}\left(\frac{N^{1/6}K^{1/2}T^{2/3}\log(NT)}{\epsilon ^{1/3}} + \frac{N^{1/2}\log(NT)}{\epsilon}\right)$, where $K$ and $N$ are the number of actions and experts respectively. These rates allow us to get sublinear regret for different combinations of small and large $K, N$ and $\epsilon. $

STOC Conference 2025 Conference Paper

Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis

• Xin Lyu 0003
• 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, especially in the “low accuracy” regime. Unlike reconstruction/discrepancy approaches however, they are more suited for query sets that arise naturally from the fingerprinting codes construction. In this work, we propose a general framework for proving fingerprinting type lower bounds, that allows us to tailor the technique to the geometry of the query set. Our approach allows us to prove several new results, including the following. We show that any (sample- and population-)accurate algorithm for answering Q arbitrary adaptive counting queries over a universe X to accuracy α needs Ω(√log| X |· log Q /α 3 ) samples, matching known upper bounds. This shows that the approaches based on differential privacy are optimal for this question, and improves significantly on the previously known lower bounds of log Q /α 2 and min(√ Q , √log| X |)/α 2 . We show that any (,δ)-DP algorithm for answering Q counting queries to accuracy α needs Ω(√ log| X | log(1/δ) log Q / α 2 ) samples, matching known upper bounds up to constants. Our framework allows for proving this bound via a direct correlation analysis and improves the prior bound of [] by √log(1/δ). For privately releasing a set of random 0-1 queries, we show tight sample complexity lower bounds in the high accuracy regime. In the low accuracy regime, the picture is more complex. For random queries, we show that there is a discontinuity in the sample complexity. For Q random queries over a universe, the sample complexity grows as Θ , δ (1/α 2 ), with no dependence on Q or | X |. This new sample complexity bound, based on sparse histograms, is asymptotically better than known lower bounds for CDP. However, at α ≈ √log| X |/√ Q , the sample complexity jumps to Θ ,δ (√ Q /α).

ICML Conference 2025 Conference Paper

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 Goldstein-stationary point with sample complexity bounds that improve on existing works. We start by providing a single-pass $(\epsilon, \delta)$-DP algorithm that returns an $(\alpha, \beta)$-stationary point as long as the dataset is of size $\widetilde{\Omega}(\sqrt{d}/\alpha\beta^{3}+d/\epsilon\alpha\beta^{2})$, which is $\Omega(\sqrt{d})$ times smaller than the algorithm of Zhang et al. (2024) for this task, where $d$ is the dimension. We then provide a multi-pass polynomial time algorithm which further improves the sample complexity to $\widetilde{\Omega}\left(d/\beta^2+d^{3/4}/\epsilon\alpha^{1/2}\beta^{3/2}\right)$, by designing a sample efficient ERM algorithm, and proving that Goldstein-stationary points generalize from the empirical loss to the population loss.

NeurIPS Conference 2025 Conference Paper

Instance-Optimality for Private KL Distribution Estimation

• Jiayuan Ye
• Vitaly Feldman
• Kunal Talwar

We study the fundamental problem of estimating an unknown discrete distribution $p$ over $d$ symbols, given $n$ i. i. d. samples from the distribution. We are interested in minimizing the KL divergence between the true distribution and the algorithm's estimate. We first construct minimax optimal private estimators. Minimax optimality however fails to shed light on an algorithm's performance on individual (non-worst-case) instances $p$ and simple minimax-optimal DP estimators can have poor empirical performance on real distributions. We then study this problem from an instance-optimality viewpoint, where the algorithm's error on $p$ is compared to the minimum achievable estimation error over a small local neighborhood of $p$. Under natural notions of local neighborhood, we propose algorithms that achieve instance-optimality up to constant factors, with and without a differential privacy constraint. Our upper bounds rely on (private) variants of the Good-Turing estimator. Our lower bounds use additive local neighborhoods that more precisely captures the hardness of distribution estimation in KL divergence, compared to ones considered in prior works.

ICML Conference 2025 Conference Paper

Local Pan-privacy for Federated Analytics

• Vitaly Feldman
• Audra McMillan
• Guy N. Rothblum
• Kunal Talwar

Pan-privacy was proposed by Dwork et al. (2010) as an approach to designing a private analytics system that retains its privacy properties in the face of intrusions that expose the system’s internal state. Motivated by Federated telemetry applications, we study local pan-privacy, where privacy should be retained under repeated unannounced intrusions on the local state. We consider the problem of monitoring the count of an event in a federated system, where event occurrences on a local device should be hidden even from an intruder on that device. We show that under reasonable constraints, the goal of providing information-theoretic differential privacy under intrusion is incompatible with collecting telemetry information. We then show that this problem can be solved in a scalable way using standard cryptographic primitives.

NeurIPS Conference 2025 Conference Paper

PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors

• Hilal Asi
• Vitaly Feldman
• Hannah Keller
• Guy Rothblum
• Kunal Talwar

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 gradients in private federated learning, where the aggregate itself is protected via noise addition to ensure differential privacy. Existing approaches require communication scaling with the dimensionality, and thus limit the dimensionality of vectors one can efficiently process in this setup. We propose PREAMBLE: {\bf Pr}ivate {\bf E}fficient {\bf A}ggregation {\bf M}echanism via {\bf BL}ock-sparse {\bf E}uclidean Vectors. PREAMBLE builds on an extension of distributed point functions that enables communication- and computation-efficient aggregation of {\em block-sparse vectors}, which are sparse vectors where the non-zero entries occur in a small number of clusters of consecutive coordinates. We show that these block-sparse DPFs can be combined with random sampling and privacy amplification by sampling results, to allow asymptotically optimal privacy-utility trade-offs for vector aggregation, at a fraction of the communication cost. When coupled with recent advances in numerical privacy accounting, our approach incurs a negligible overhead in noise variance, compared to the Gaussian mechanism used with Prio.

NeurIPS Conference 2024 Conference Paper

Instance-Optimal Private Density Estimation in the Wasserstein Distance

• Vitaly Feldman
• Audra McMillan
• Satchit Sivakumar
• Kunal Talwar

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 for density estimation. For example, when estimating population densities in a geographic region, a small Wasserstein distance means that the estimate is able to capture roughly where the population mass is. In this work we study differentially private density estimation in the Wasserstein distance. We design and analyze instance-optimal algorithms for this problem that can adapt to easy instances. For distributions $P$ over $\mathbb{R}$, we consider a strong notion of instance-optimality: an algorithm that uniformly achieves the instance-optimal estimation rate is competitive with an algorithm that is told that the distribution is either $P$ or $Q_P$ for some distribution $Q_P$ whose probability density function (pdf) is within a factor of 2 of the pdf of $P$. For distributions over $\mathbb{R}^2$, we use a slightly different notion of instance optimality. We say that an algorithm is instance-optimal if it is competitive with an algorithm that is given a constant multiplicative approximation of the density of the distribution. We characterize the instance-optimal estimation rates in both these settings and show that they are uniformly achievable (up to polylogarithmic factors). Our approach for $\mathbb{R}^2$ extends to arbitrary metric spaces as it goes via hierarchically separated trees. As a special case our results lead to instance-optimal learning in TV distance for discrete distributions.

NeurIPS Conference 2024 Conference Paper

Private and Personalized Frequency Estimation in a Federated Setting

• Amrith Setlur
• Vitaly Feldman
• Kunal Talwar

Motivated by the problem of next word prediction on user devices we introduce and study the problem of personalized frequency histogram estimation in a federated setting. In this problem, over some domain, each user observes a number of samples from a distribution which is specific to that user. The goal is to compute for all users a personalized estimate of the user's distribution with error measured in KL divergence. We focus on addressing two central challenges: statistical heterogeneity and protection of user privacy. Our approach to the problem relies on discovering and exploiting similar subpopulations of users which are often present and latent in real-world data, while minimizing user privacy leakage at the same time. We first present a non-private clustering-based algorithm for the problem, and give a provably joint differentially private version of it with a private data-dependent initialization scheme. Next, we propose a simple data model which is based on a mixture of Dirichlet distributions, to formally motivate our non-private algorithm and demonstrate some properties of its components. Finally, we provide an extensive empirical evaluation of our private and non-private algorithms under varying levels of statistical and size heterogeneity on the Reddit, StackOverflow, and Amazon Reviews datasets. Our results demonstrate significant improvements over standard and clustering-based baselines, and in particular, they show that it is possible to improve over direct personalization of a single global model.

NeurIPS Conference 2024 Conference Paper

Private Online Learning via Lazy Algorithms

• Hilal Asi
• Tomer Koren
• Daogao Liu
• Kunal Talwar

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 transforms lazy online learning algorithms into private algorithms. We apply our transformation for differentially private OPE and OCO using existing lazy algorithms for these problems. Our final algorithms obtain regret which significantly improves the regret in the high privacy regime $\varepsilon \ll 1$, obtaining $\sqrt{T \log d} + T^{1/3} \log(d)/\varepsilon^{2/3}$ for DP-OPE and $\sqrt{T} + T^{1/3} \sqrt{d}/\varepsilon^{2/3}$ for DP-OCO. We also complement our results with a lower bound for DP-OPE, showing that these rates are optimal for a natural family of low-switching private algorithms.

ICML Conference 2024 Conference Paper

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages

• Hilal Asi
• Vitaly Feldman
• Jelani Nelson
• Huy L. Nguyen 0001
• Kunal Talwar
• Samson Zhou

We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v^{(i)} \in \mathbb{R}^d$. We propose a new multi-message protocol that achieves the optimal error using $O(\min(n\varepsilon^2, d))$ messages per user. Moreover, we show that any (unbiased) protocol that achieves optimal error must require each user to send $\Omega(\min(n\varepsilon^2, d)/\log(n))$ messages, demonstrating the optimality of our message complexity up to logarithmic factors. Additionally, we study the single-message setting and design a protocol that achieves mean squared error $O(dn^{d/(d+2)}\varepsilon^{-4/(d+2)})$. Moreover, we show that any single-message protocol must incur mean squared error $\Omega(dn^{d/(d+2)})$, showing that our protocol is optimal in the standard setting where $\varepsilon = \Theta(1)$. Finally, we study robustness to malicious users and show that malicious users can incur large additive error with a single shuffler.

NeurIPS Conference 2023 Conference Paper

Fast Optimal Locally Private Mean Estimation via Random Projections

• Hilal Asi
• Vitaly Feldman
• Jelani Nelson
• Huy Nguyen
• Kunal Talwar

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 have high communication and/or run-time complexity. We propose a new algorithmic framework, namely ProjUnit, for private mean estimation that yields algorithms that are computationally efficient, have low communication complexity, and incur optimal error up to a $1+o(1)$-factor. Our framework is deceptively simple: each randomizer projects its input to a random low-dimensional subspace and then runs an optimal algorithm such a PrivUnitG in the lower dimensional space. We analyze the error of the algorithm in terms of properties of the random projection ensemble, and study two instantiations. We conduct several experiments for private mean estimation and private federated learning which demonstrate that our algorithms obtain nearly the same utility as optimal algorithms while having significantly lower communication and computational cost.

ICML Conference 2023 Conference Paper

Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime

• Hilal Asi
• Vitaly Feldman
• Tomer Koren
• Kunal Talwar

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 regret bounds. For the problem of online prediction from experts, we design new algorithms that obtain near-optimal regret $O \big( \varepsilon^{-1} \mathsf{poly}(\log{d}) \big)$ where $d$ is the number of experts. This significantly improves over the best existing regret bounds for the DP non-realizable setting which are $O \big( \varepsilon^{-1} \min\big\{d, \sqrt{T\log d}\big\} \big)$. We also develop an adaptive algorithm for the small-loss setting with regret $(L^\star+ \varepsilon^{-1}) \cdot O(\mathsf{poly}(\log{d}))$ where $L^\star$ is the total loss of the best expert. Additionally, we consider DP online convex optimization in the realizable setting and propose an algorithm with near-optimal regret $O \big(\varepsilon^{-1} \mathsf{poly}(d) \big)$, as well as an algorithm for the smooth case with regret $O \big( (\sqrt{Td}/\varepsilon)^{2/3} \big)$, both significantly improving over existing bounds in the non-realizable regime.

SODA Conference 2023 Conference Paper

Stronger Privacy Amplification by Shuffling for Renyi 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 [18, 12]. A key result in this model is that randomly shuffling locally randomized data amplifies differential privacy guarantees. Such amplification implies substantially stronger privacy guarantees for systems in which data is contributed anonymously [8]. In this work, we improve the state of the art privacy amplification by shuffling results both theoretically and numerically. Our first contribution is the first asymptotically optimal analysis of the Renyi differential privacy parameters for the shuffled outputs of LDP randomizers. Our second contribution is a new analysis of privacy amplification by shuffling. This analysis improves on the techniques of Feldman et al. [20] and leads to tighter numerical bounds in all parameter settings. * The full version of the paper can be accessed at https: //arxiv. org/abs/2208. 04591

NeurIPS Conference 2022 Conference Paper

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 devices. This research field has a unique set of practical challenges, and to systematically make advances, new datasets curated to be compatible with this paradigm are needed. Existing federated learning benchmarks in the image domain do not accurately capture the scale and heterogeneity of many real-world use cases. We introduce FLAIR, a challenging large-scale annotated image dataset for multi-label classification suitable for federated learning. FLAIR has 429, 078 images from 51, 414 Flickr users and captures many of the intricacies typically encountered in federated learning, such as heterogeneous user data and a long-tailed label distribution. We implement multiple baselines in different learning setups for different tasks on this dataset. We believe FLAIR can serve as a challenging benchmark for advancing the state-of-the art in federated learning. Dataset access and the code for the benchmark are available at https: //github. com/apple/ml-flair.

NeurIPS Conference 2022 Conference Paper

Mean Estimation with User-level Privacy under Data Heterogeneity

• Rachel Cummings
• Vitaly Feldman
• Audra McMillan
• Kunal Talwar

A key challenge in many modern data analysis tasks is that user data is heterogeneous. Different users may possess vastly different numbers of data points. More importantly, it cannot be assumed that all users sample from the same underlying distribution. This is true, for example in language data, where different speech styles result in data heterogeneity. In this work we propose a simple model of heterogeneous user data that differs in both distribution and quantity of data, and we provide a method for estimating the population-level mean while preserving user-level differential privacy. We demonstrate asymptotic optimality of our estimator and also prove general lower bounds on the error achievable in our problem.

ICML Conference 2022 Conference Paper

Optimal Algorithms for Mean Estimation under Local Differential Privacy

• Hilal Asi
• Vitaly Feldman
• Kunal Talwar

We study the problem of mean estimation of $\ell_2$-bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achieve the (asymptotic) optimal rates for this problem, the performance of these algorithms in practice can vary significantly due to varying (and often large) hidden constants. In this work, we investigate the question of designing the randomizer with the smallest variance. We show that PrivUnit (Bhowmick et al. 2018) with optimized parameters achieves the optimal variance among a large family of natural randomizers. To prove this result, we establish some properties of local randomizers, and use symmetrization arguments that allow us to write the optimal randomizer as the optimizer of a certain linear program. These structural results, which should extend to other problems, then allow us to show that the optimal randomizer belongs to the PrivUnit family. We also develop a new variant of PrivUnit based on the Gaussian distribution which is more amenable to mathematical analysis and enjoys the same optimality guarantees. This allows us to establish several useful properties on the exact constants of the optimal error as well as to numerically estimate these constants.

ICML Conference 2022 Conference Paper

Practical Almost-Linear-Time Approximation Algorithms for Hybrid and Overlapping Graph Clustering

• Lorenzo Orecchia
• Konstantinos Ameranis
• Charalampos E. Tsourakakis
• Kunal Talwar

Detecting communities in real-world networks and clustering similarity graphs are major data mining tasks with a wide range of applications in graph mining, collaborative filtering, and bioinformatics. In many such applications, overwhelming empirical evidence suggests that communities and clusters are naturally overlapping, i. e. , the boundary of a cluster may contain both edges across clusters and nodes that are shared with other clusters, calling for novel hybrid graph partitioning algorithms (HGP). While almost-linear-time approximation algorithms are known for edge-boundary-based graph partitioning, little progress has been made on fast algorithms for HGP, even in the special case of vertex-boundary-based graph partitioning. In this work, we introduce a frame-work based on two novel clustering objectives, which naturally extend the well-studied notion of conductance to clusters with hybrid vertex-and edge-boundary structure. Our main algorithmic contributions are almost-linear-time algorithms O(log n)-approximation algorithms for both these objectives. To this end, we show that the cut-matching framework of (Khandekar et al. , 2014) can be significantly extended to incorporate hybrid partitions. Crucially, we implement our approximation algorithm to produce both hybrid partitions and optimality certificates for large graphs, easily scaling to tens of millions of edges, and test our implementation on real-world datasets against other competitive baselines.

NeurIPS Conference 2022 Conference Paper

Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss

• Jason 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. Stochastic Gradient Langevin Dynamics). However, foundational theoretical questions about this algorithm's privacy loss remain open---even in the seemingly simple setting of smooth convex losses over a bounded domain. Our main result resolves these questions: for a large range of parameters, we characterize the differential privacy up to a constant. This result reveals that all previous analyses for this setting have the wrong qualitative behavior. Specifically, while previous privacy analyses increase ad infinitum in the number of iterations, we show that after a small burn-in period, running SGD longer leaks no further privacy. Our analysis departs from previous approaches based on fast mixing, instead using techniques based on optimal transport (namely, Privacy Amplification by Iteration) and the Sampled Gaussian Mechanism (namely, Privacy Amplification by Sampling). Our techniques readily extend to other settings.

ICML Conference 2022 Conference Paper

Private frequency estimation via projective geometry

• Vitaly Feldman
• Jelani Nelson
• Huy L. Nguyen 0001
• Kunal Talwar

In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For universe size of k and with n users, our eps-LDP algorithm has communication cost ceil(log_2 k) and computation cost O(n + k\exp(eps) log k) for the server to approximately reconstruct the frequency histogram, while achieve optimal privacy-utility tradeoff. In many practical settings this is a significant improvement over the O (n+k^2) computation cost that is achieved by the recent PI-RAPPOR algorithm (Feldman and Talwar; 2021). Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR while using approximately 75x less memory. In addition, the running time of our algorithm is comparable to that of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. The error of our algorithm essentially matches that of the communication- and time-inefficient but utility-optimal SubsetSelection (SS) algorithm (Ye and Barg; 2017). Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction for the server.

NeurIPS Conference 2022 Conference Paper

Subspace Recovery from Heterogeneous Data with Non-isotropic Noise

• John C. Duchi
• Vitaly Feldman
• Lunjia Hu
• Kunal Talwar

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 basic formulation of this problem: the principal component analysis (PCA), with a focus on dealing with irregular noise. Our data come from $n$ users with user $i$ contributing data samples from a $d$-dimensional distribution with mean $\mu_i$. Our goal is to recover the linear subspace shared by $\mu_1, \ldots, \mu_n$ using the data points from all users, where every data point from user $i$ is formed by adding an independent mean-zero noise vector to $\mu_i$. If we only have one data point from every user, subspace recovery is information-theoretically impossible when the covariance matrices of the noise vectors can be non-spherical, necessitating additional restrictive assumptions in previous work. We avoid these assumptions by leveraging at least two data points from each user, which allows us to design an efficiently-computable estimator under non-spherical and user-dependent noise. We prove an upper bound for the estimation error of our estimator in general scenarios where the number of data points and amount of noise can vary across users, and prove an information-theoretic error lower bound that not only matches the upper bound up to a constant factor, but also holds even for spherical Gaussian noise. This implies that our estimator does not introduce additional estimation error (up to a constant factor) due to irregularity in the noise. We show additional results for a linear regression problem in a similar setup.

ICML Conference 2021 Conference Paper

Characterizing Structural Regularities of Labeled Data in Overparameterized Models

• Ziheng Jiang
• Chiyuan Zhang
• Kunal Talwar
• Michael Mozer

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 does not accept payment in advance. Likewise, deep neural networks can generalize across instances that share common patterns or structures, yet have the capacity to memorize rare or irregular forms. We analyze how individual instances are treated by a model via a consistency score. The score characterizes the expected accuracy for a held-out instance given training sets of varying size sampled from the data distribution. We obtain empirical estimates of this score for individual instances in multiple data sets, and we show that the score identifies out-of-distribution and mislabeled examples at one end of the continuum and strongly regular examples at the other end. We identify computationally inexpensive proxies to the consistency score using statistics collected during training. We apply the score toward understanding the dynamics of representation learning and to filter outliers during training.

FOCS Conference 2021 Conference Paper

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 [1] demonstrates that random shuffling amplifies differential privacy guarantees of locally randomized data. Such amplification implies substan-tially stronger privacy guarantees for systems in which data is contributed anonymously [2] and has lead to significant interest in the shuffle model of privacy [3], [1]. We give a characterization of the privacy guarantee of the random shuffling of $\mathbf{n}$ data records input to epsilon-differentially private local randomizers that significantly im-proves over previous work and achieves the asymptotically optimal dependence in epsilon. Our result is based on a new approach that is simpler than previous work and extends to approximate differential privacy with nearly the same guarantees. Importantly, our work also yields an algorithm for deriving tighter bounds on the resulting epsilon and delta as well as Rényi differential privacy guarantees. We show numerically that our algorithm gets to within a small constant factor of the optimal bound. As a direct corollary of our analysis we derive a simple and nearly optimal algorithm for frequency estimation in the shuffle model of privacy. We also observe that our result implies the first asymptotically optimal privacy analysis of noisy stochastic gradient descent that applies to sampling without replacement.

ICML Conference 2021 Conference Paper

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 algorithms require sending prohibitively large messages from the client device to the server (such as when constructing histograms over a large domain or learning a high-dimensional model). Here we demonstrate a general approach that, under standard cryptographic assumptions, compresses every efficient LDP algorithm with negligible loss in privacy and utility guarantees. The practical implication of our result is that in typical applications every message can be compressed to the size of the server’s pseudo-random generator seed. From this general approach we derive low-communication algorithms for the problems of frequency estimation and high-dimensional mean estimation. Our algorithms are simpler and more accurate than existing low-communication LDP algorithms for these well-studied problems.

ICML Conference 2021 Conference Paper

Private Adaptive Gradient Methods for Convex Optimization

• Hilal Asi
• John C. Duchi
• Alireza Fallah 0001
• Omid Javidbakht
• Kunal Talwar

We study adaptive methods for differentially private convex optimization, proposing and analyzing differentially private variants of a Stochastic Gradient Descent (SGD) algorithm with adaptive stepsizes, as well as the AdaGrad algorithm. We provide upper bounds on the regret of both algorithms and show that the bounds are (worst-case) optimal. As a consequence of our development, we show that our private versions of AdaGrad outperform adaptive SGD, which in turn outperforms traditional SGD in scenarios with non-isotropic gradients where (non-private) Adagrad provably outperforms SGD. The major challenge is that the isotropic noise typically added for privacy dominates the signal in gradient geometry for high-dimensional problems; approaches to this that effectively optimize over lower-dimensional subspaces simply ignore the actual problems that varying gradient geometries introduce. In contrast, we study non-isotropic clipping and noise addition, developing a principled theoretical approach; the consequent procedures also enjoy significantly stronger empirical performance than prior approaches.

ICML Conference 2021 Conference Paper

Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry

• Hilal Asi
• Vitaly Feldman
• Tomer Koren
• Kunal Talwar

Stochastic convex optimization over an $\ell_1$-bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differential privacy. We show that, up to logarithmic factors the optimal excess population loss of any $(\epsilon, \delta)$-differentially private optimizer is $\sqrt{\log(d)/n} + \sqrt{d}/\epsilon n. $ The upper bound is based on a new algorithm that combines the iterative localization approach of Feldman et al. (2020) with a new analysis of private regularized mirror descent. It applies to $\ell_p$ bounded domains for $p\in [1, 2]$ and queries at most $n^{3/2}$ gradients improving over the best previously known algorithm for the $\ell_2$ case which needs $n^2$ gradients. Further, we show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $\sqrt{\log(d)/n} + (\log(d)/\epsilon n)^{2/3}. $ This bound is achieved by a new variance-reduced version of the Frank-Wolfe algorithm that requires just a single pass over the data. We also show that the lower bound in this case is the minimum of the two rates mentioned above.

STOC Conference 2021 Conference Paper

When is memorization of irrelevant training data necessary for high-accuracy learning?

• Gavin Brown 0003
• Mark Bun
• Vitaly Feldman
• Adam Smith 0006
• Kunal Talwar

Modern machine learning models are complex and frequently encode surprising amounts of information about individual inputs. In extreme cases, complex models appear to memorize entire input examples, including seemingly irrelevant information (social security numbers from text, for example). In this paper, we aim to understand whether this sort of memorization is necessary for accurate learning. We describe natural prediction problems in which every sufficiently accurate training algorithm must encode, in the prediction model, essentially all the information about a large subset of its training examples. This remains true even when the examples are high-dimensional and have entropy much higher than the sample size, and even when most of that information is ultimately irrelevant to the task at hand. Further, our results do not depend on the training algorithm or the class of models used for learning. Our problems are simple and fairly natural variants of the next-symbol prediction and the cluster labeling tasks. These tasks can be seen as abstractions of text- and image-related prediction problems. To establish our results, we reduce from a family of one-way communication problems for which we prove new information complexity lower bounds.

NeurIPS Conference 2020 Conference Paper

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 $\exp(-f)$ for a suitable function $f$. When the domain of the distribution is high-dimensional, this sampling can be challenging. Using heuristic sampling schemes such as Gibbs sampling does not necessarily lead to provable privacy. When $f$ is convex, techniques from log-concave sampling lead to polynomial-time algorithms, albeit with large polynomials. Langevin dynamics-based algorithms offer much faster alternatives under some distance measures such as statistical distance. In this work, we establish rapid convergence for these algorithms under distance measures more suitable for differential privacy. For smooth, strongly-convex $f$, we give the first results proving convergence in R\'enyi divergence. This gives us fast differentially private algorithms for such $f$. Our techniques and simple and generic and apply also to underdamped Langevin dynamics.

NeurIPS Conference 2020 Conference Paper

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 are surprisingly robust to errors in the training data. In this work, we identify a set of conditions on the data under which such surrogate loss minimization algorithms provably learn the correct classifier. This allows us to establish, in a unified framework, the robustness of these algorithms under various models on data as well as error. In particular, we show that if the data is linearly classifiable with a slightly non-trivial margin (i. e. a margin at least $C\div\sqrt{d}$ for $d$-dimensional unit vectors), and the class-conditional distributions are near isotropic and logconcave, then surrogate loss minimization has negligible error on the uncorrupted data even when a constant fraction of examples are adversarially mislabeled.

STOC Conference 2020 Conference Paper

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 convex loss functions. A recent work of Bassily et al. (2019) has established the optimal bound on the excess population loss achievable given n samples. Unfortunately, their algorithm achieving this bound is relatively inefficient: it requires O (min{ n 3/2 , n 5/2 / d }) gradient computations, where d is the dimension of the optimization problem.

NeurIPS Conference 2020 Conference Paper

Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses

• Raef Bassily
• Vitaly Feldman
• Cristóbal Guzmán
• Kunal Talwar

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. An influential work of Hardt et al. [2016] provides strong upper bounds on the uniform stability of the stochastic gradient descent (SGD) algorithm on sufficiently smooth convex losses. These results led to important progress in understanding of the generalization properties of SGD and several applications to differentially private convex optimization for smooth losses. Our work is the first to address uniform stability of SGD on nonsmooth convex losses. Specifically, we provide sharp upper and lower bounds for several forms of SGD and full-batch GD on arbitrary Lipschitz nonsmooth convex losses. Our lower bounds show that, in the nonsmooth case, (S)GD can be inherently less stable than in the smooth case. On the other hand, our upper bounds show that (S)GD is sufficiently stable for deriving new and useful bounds on generalization error. Most notably, we obtain the first dimension-independent generalization bounds for multi-pass SGD in the nonsmooth case. In addition, our bound allow us to derive a new algorithm for differentially private nonsmooth stochastic convex optimization with optimal excess population risk. Our algorithm is simpler and more efficient than the best known algorithm for the nonsmooth case, due to Feldman et al. [2020].

NeurIPS Conference 2020 Conference Paper

Stochastic Optimization with Laggard Data Pipelines

• Naman Agarwal
• Rohan Anil
• Tomer Koren
• Kunal Talwar
• Cyril Zhang

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/network operations have emerged as new performance bottlenecks, as opposed to hardware-accelerated gradient computations. In this regime, a recently proposed approach is data echoing (Choi et al. , 2019), which takes repeated gradient steps on the same batch while waiting for fresh data to arrive from upstream. We provide the first convergence analyses of "data-echoed" extensions of common optimization methods, showing that they exhibit provable improvements over their synchronous counterparts. Specifically, we show that in convex optimization with stochastic minibatches, data echoing affords speedups on the curvature-dominated part of the convergence rate, while maintaining the optimal statistical rate.

SODA Conference 2019 Conference Paper

Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity

• Úlfar Erlingsson
• Vitaly Feldman
• Ilya Mironov
• Ananth Raghunathan
• Kunal Talwar
• Abhradeep Thakurta

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 usage may be monitored via such reports. We study the collection of such statistics in the local differential privacy (LDP) model, and describe an algorithm whose privacy cost is polylogarithmic in the number of changes to a user's value. More fundamentally—by building on anonymity of the users’ reports—we also demonstrate how the privacy cost of our LDP algorithm can actually be much lower when viewed in the central model of differential privacy. We show, via a new and general privacy amplification technique, that any permutation-invariant algorithm satisfying ε-local differential privacy will satisfy -central differential privacy. By this, we explain how the high noise and overhead of LDP protocols is a consequence of them being significantly more private in the central model. As a practical corollary, our results imply that several LDP-based industrial deployments may have much lower privacy cost than their advertised ε would indicate—at least if reports are anonymized.

NeurIPS Conference 2019 Conference Paper

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 these two problems are efficiently reducible to each other. Recent work (Ma et al. 2019) shows that in the non-convex case, sampling can sometimes be provably faster. We present a simpler and stronger separation. We then compare sampling and optimization in more detail and show that they are provably incomparable: there are families of continuous functions for which optimization is easy but sampling is NP-hard, and vice versa. Further, we show function families that exhibit a sharp phase transition in the computational complexity of sampling, as one varies the natural temperature parameter. Our results draw on a connection to analogous separations in the discrete setting which are well-studied.

STOC Conference 2019 Conference Paper

Private selection from private candidates

• Jingcheng Liu 0001
• 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, measured as a real-valued score function, does not change by much when one person’s data changes. In many applications such as hyperparameter optimization, this stability assumption is much too strong. In this work, we consider the selection problem under a much weaker stability assumption on the candidates, namely that the score functions are differentially private. Under this assumption, we present algorithms that are near-optimal along the three relevant dimensions: privacy, utility and computational efficiency. Our result can be seen as a generalization of the exponential mechanism and its existing generalizations. We also develop an online version of our algorithm, that can be seen as a generalization of the sparse vector technique to this weaker stability assumption. We show how our results imply better algorithms for hyperparameter selection in differentially private machine learning, as well as for adaptive data analysis.

NeurIPS Conference 2019 Conference Paper

Private Stochastic Convex Optimization with Optimal Rates

• Raef Bassily
• Vitaly Feldman
• Kunal Talwar
• Abhradeep Guha Thakurta

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. ~samples from a distribution over convex and Lipschitz loss functions. A long line of existing work on private convex optimization focuses on the empirical loss and derives asymptotically tight bounds on the excess empirical loss. However a significant gap exists in the known bounds for the population loss. We show that, up to logarithmic factors, the optimal excess population loss for DP algorithms is equal to the larger of the optimal non-private excess population loss, and the optimal excess empirical loss of DP algorithms. This implies that, contrary to intuition based on private ERM, private SCO has asymptotically the same rate of $1/\sqrt{n}$ as non-private SCO in the parameter regime most common in practice. The best previous result in this setting gives rate of $1/n^{1/4}$. Our approach builds on existing differentially private algorithms and relies on the analysis of algorithmic stability to ensure generalization.

ICML Conference 2019 Conference Paper

Semi-Cyclic Stochastic Gradient Descent

• Hubert Eichner
• Tomer Koren
• H. Brendan McMahan
• Nathan Srebro
• Kunal Talwar

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-specific, distribution. This situation arises, e. g. , in Federated Learning where the mobile devices available for updates at different times during the day have different characteristics. We show that such block-cyclic structure can significantly deteriorate the performance of SGD, but propose a simple approach that allows prediction with the same guarantees as for i. i. d. , non-cyclic, sampling.

NeurIPS Conference 2018 Conference Paper

Adversarially Robust Generalization Requires More Data

• Ludwig Schmidt
• Shibani Santurkar
• Dimitris Tsipras
• Kunal Talwar
• Aleksander Madry

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" accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of "standard" learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

FOCS Conference 2018 Conference Paper

Balancing Vectors in Any Norm

• Daniel Dadush
• Aleksandar Nikolov
• Kunal Talwar
• Nicole Tomczak-Jaegermann

In the vector balancing problem, we are given symmetric convex bodies C and K in R^n, and our goal is to determine the minimum number β ≥ 0, known as the vector balancing constant from C to K, such that for any sequence of vectors in C there always exists a signed combination of them lying inside β K. Many fundamental results in discrepancy theory, such as the Beck-Fiala theorem (Discrete Appl. ~Math '81), Spencer's "six standard deviations suffice" theorem (Trans. ~Amer. ~Math. ~Soc '85) and Banaszczyk's vector balancing theorem (Random Structures & Algorithms '98) correspond to bounds on vector balancing constants. The above theorems have inspired much research in recent years within theoretical computer science. In this work, we show that all vector balancing constants admit "good" approximate characterizations, with approximation factors depending only polylogarithmically on the dimension n. First, we show that a volumetric lower bound due to Banaszczyk is tight within a O(log n) factor. Our proof is algorithmic, and we show that Rothvoss's (FOCS '14) partial coloring algorithm can be analyzed to obtain these guarantees. Second, we present a novel convex program which encodes the "best possible way" to apply Banaszczyk's vector balancing theorem for bounding vector balancing constants from above, and show that it is tight within an O(log^2. 5 n) factor. This also directly yields a corresponding polynomial time approximation algorithm both for vector balancing constants, and for the hereditary discrepancy of any sequence of vectors with respect to an arbitrary norm.

ICML Conference 2018 Conference Paper

Online Linear Quadratic Control

• Alon Cohen
• Avinatan Hassidim
• Tomer Koren
• Nevena Lazic
• Yishay Mansour
• Kunal Talwar

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 learning algorithms in this setting that guarantee $O(\sqrt{T})$ regret under mild assumptions, where $T$ is the time horizon. Our algorithms rely on a novel SDP relaxation for the steady-state distribution of the system. Crucially, and in contrast to previously proposed relaxations, the feasible solutions of our SDP all correspond to “strongly stable” policies that mix exponentially fast to a steady state.

FOCS Conference 2018 Conference Paper

Privacy Amplification by Iteration

• Vitaly Feldman
• Ilya Mironov
• Kunal Talwar
• Abhradeep Thakurta

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 such algorithms often involves ensuring privacy of each step and then reasoning about the cumulative privacy cost of the algorithm. This is enabled by composition theorems for differential privacy that allow releasing of all the intermediate results. In this work, we demonstrate that for contractive iterations, not releasing the intermediate results strongly amplifies the privacy guarantees. We describe several applications of this new analysis technique to solving convex optimization problems via noisy stochastic gradient descent. For example, we demonstrate that a relatively small number of non-private data points from the same distribution can be used to close the gap between private and non-private convex optimization. In addition, we demonstrate that we can achieve guarantees similar to those obtainable using the privacy-amplification-by-sampling technique in several natural settings where that technique cannot be applied.

ICLR Conference 2018 Conference Paper

Scalable Private Learning with PATE

• Nicolas Papernot
• Shuang Song 0001
• Ilya Mironov
• Ananth Raghunathan
• Kunal Talwar
• Úlfar Erlingsson

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 personal information. To address those concerns, one promising approach is Private Aggregation of Teacher Ensembles, or PATE, which transfers to a "student" model the knowledge of an ensemble of "teacher" models, with intuitive privacy provided by training teachers on disjoint data and strong privacy guaranteed by noisy aggregation of teachers’ answers. However, PATE has so far been evaluated only on simple classification tasks like MNIST, leaving unclear its utility when applied to larger-scale learning tasks and real-world datasets. In this work, we show how PATE can scale to learning tasks with large numbers of output classes and uncurated, imbalanced training data with errors. For this, we introduce new noisy aggregation mechanisms for teacher ensembles that are more selective and add less noise, and prove their tighter differential-privacy guarantees. Our new mechanisms build on two insights: the chance of teacher consensus is increased by using more concentrated noise and, lacking consensus, no answer need be given to a student. The consensus answers used are more likely to be correct, offer better intuitive privacy, and incur lower-differential privacy cost. Our evaluation shows our mechanisms improve on the original PATE on all measures, and scale to larger tasks with both high utility and very strong privacy (ε < 1.0).

SODA Conference 2017 Conference Paper

LAST but not Least: Online Spanners for Buy-at-Bulk

• Anupam Gupta 0001
• R. Ravi 0001
• Kunal Talwar
• Seeun William Umboh

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-embeddings, giving us randomized algorithms. Moreover, the optimal results with a logarithmic competitive ratio requires the metric on which the network is being built to be known up-front; the competitive ratios then depend on the size of this metric (which could be much larger than the number of terminals that arrive). We consider the buy-at-bulk problem in the least restrictive model where the metric is not known in advance, but revealed in parts along with the demand points seeking connectivity arriving online. For the single sink buy-at-bulk problem, we give a deterministic online algorithm with competitive ratio that is logarithmic in k, the number of terminals that have arrived, matching the lower bound known even for the online Steiner tree problem. In the oblivious case when the buy-at-bulk function used to compute the edge-costs of the network is not known in advance (but is the same across all edges), we give a deterministic algorithm with competitive ratio polylogarithmic in k, the number of terminals. At the heart of our algorithms are optimal constructions for online Light Approximate Shortest-path Trees (LASTs) and spanners, and their variants. We give constructions that have optimal trade-offs in terms of cost and stretch. We also define and give constructions for a new notion of LASTs where the set of roots (in addition to the points) expands over time. We expect these techniques will find applications in other online network-design problems.

ICLR Conference 2017 Conference Paper

Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data

• Nicolas Papernot
• Martín Abadi
• Úlfar Erlingsson
• Ian J. Goodfellow
• Kunal Talwar

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 store some of its training data; careful analysis of the model may therefore reveal sensitive information. To address this problem, we demonstrate a generally applicable approach to providing strong privacy guarantees for training data: Private Aggregation of Teacher Ensembles (PATE). The approach combines, in a black-box fashion, multiple models trained with disjoint datasets, such as records from different subsets of users. Because they rely directly on sensitive data, these models are not published, but instead used as ''teachers'' for a ''student'' model. The student learns to predict an output chosen by noisy voting among all of the teachers, and cannot directly access an individual teacher or the underlying data or parameters. The student's privacy properties can be understood both intuitively (since no single teacher and thus no single dataset dictates the student's training) and formally, in terms of differential privacy. These properties hold even if an adversary can not only query the student but also inspect its internal workings. Compared with previous work, the approach imposes only weak assumptions on how teachers are trained: it applies to any model, including non-convex models like DNNs. We achieve state-of-the-art privacy/utility trade-offs on MNIST and SVHN thanks to an improved privacy analysis and semi-supervised learning.

SODA Conference 2015 Conference Paper

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 of a hypergraph, defined as the maximum discrepancy of a restriction of the hypergraph to a subset of its vertices, is a measure of its complexity. Lovász, Spencer and Vesztergombi (1986) related the natural extension of this quantity to matrices to rounding algorithms for linear programs, and gave a determinant based lower bound on the hereditary discrepancy. Matoušek (2011) showed that this bound is tight up to a polylogarithmic factor, leaving open the question of actually computing this bound. Recent work by Nikolov, Talwar and Zhang (2013) showed a polynomial time Õ (log 3 n )-approximation to hereditary discrepancy, as a by-product of their work in differential privacy. In this paper, we give a direct simple O (log 3/2 n )-approximation algorithm for this problem. We show that up to this approximation factor, the hereditary discrepancy of a matrix A is characterized by the optimal value of simple geometric convex program that seeks to minimize the largest ℓ ∞ norm of any point in a ellipsoid containing the columns of A. This characterization promises to be a useful tool in discrepancy theory.

NeurIPS Conference 2015 Conference Paper

Nearly Optimal Private LASSO

• Kunal Talwar
• Abhradeep Guha Thakurta
• Li Zhang

We present a nearly optimal differentially private version of the well known LASSO estimator. Our algorithm provides privacy protection with respect to each training data item. The excess risk of our algorithm, compared to the non-private version, is $\widetilde{O}(1/n^{2/3})$, assuming all the input data has bounded $\ell_\infty$ norm. This is the first differentially private algorithm that achieves such a bound without the polynomial dependence on $p$ under no addition assumption on the design matrix. In addition, we show that this error bound is nearly optimal amongst all differentially private algorithms.

STOC Conference 2014 Conference Paper

Analyze gauss: optimal bounds for privacy-preserving principal component analysis

• Cynthia Dwork
• Kunal Talwar
• Abhradeep Thakurta
• Li Zhang 0001

We consider the problem of privately releasing a low dimensional approximation to a set of data records, represented as a matrix A in which each row corresponds to an individual and each column to an attribute. Our goal is to compute a subspace that captures the covariance of A as much as possible, classically known as principal component analysis (PCA). We assume that each row of A has ℓ 2 norm bounded by one, and the privacy guarantee is defined with respect to addition or removal of any single row. We show that the well-known, but misnamed, randomized response algorithm, with properly tuned parameters, provides nearly optimal additive quality gap compared to the best possible singular subspace of A . We further show that when A T A has a large eigenvalue gap -- a reason often cited for PCA -- the quality improves significantly. Optimality (up to logarithmic factors) is proved using techniques inspired by the recent work of Bun, Ullman, and Vadhan on applying Tardos's fingerprinting codes to the construction of hard instances for private mechanisms for 1-way marginal queries. Along the way we define a list culling game which may be of independent interest. By combining the randomized response mechanism with the well-known following the perturbed leader algorithm of Kalai and Vempala we obtain a private online algorithm with nearly optimal regret. The regret of our algorithm even outperforms all the previously known online non-private algorithms of this type. We achieve this better bound by, satisfyingly, borrowing insights and tools from differential privacy!

STOC Conference 2014 Conference Paper

Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs

• Ittai Abraham
• Cyril Gavoille
• Anupam Gupta 0001
• Ofer Neiman
• Kunal Talwar

We prove that any graph excluding K r as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O ( r/ Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove O ( r 2 /Δ) fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter O ( r ) and strong-diameter partitions with padding parameter O ( r 2 ) for K r -free graphs, O ( k ) for treewidth- k graphs, and O (log g ) for graphs with genus g .

SODA Conference 2014 Conference Paper

Non-Uniform Graph Partitioning

• Robert Krauthgamer
• Joseph Naor
• Roy Schwartz 0002
• Kunal Talwar

SODA Conference 2013 Conference Paper

Minimum Makespan Scheduling with Low Rank Processing Times

• Aditya Bhaskara
• Ravishankar Krishnaswamy
• Kunal Talwar
• Udi Wieder

We investigate approximation algorithms for the classical minimum makespan scheduling problem, focusing on instances where the rank of the matrix describing the processing times of the jobs is bounded. A bounded rank matrix arises naturally when the processing time of a job on machine depends upon a bounded set of resources. A bounded rank matrix also shows up when jobs have varying degrees of parallelizability and the machines have multiple cores. We are interested in studying the tractability of the problem as a function of the (positive) rank of the processing-time matrix. At one extreme is the case of unit rank, also known as related machines, which admits a PTAS [7], and at the other extreme is the full rank case ( unrelated machines ), which is NP-hard to approximate within a factor better than 3/2 [8]. Our main technical contribution is in showing that the approximability of the problem is not smooth with the rank of the matrix. From the inapproximability side, we show that the problem becomes APX-hard, even for rank four matrices. For rank seven matrices, we prove that it is hard to approximate to a factor 3/2, matching the inapproximability result for general unrelated machines. From the algorithmic side, we obtain a quasi-polynomial approximation scheme (i. e. , a (1 + ε) approximation in time n poly (1/ε, log n ) ) for the rank two case. This implies that the problem is not APX-hard in this case, unless NP has quasi-polynomial algorithms. Our algorithm is a subtle dynamic program which runs in polynomial time in some interesting special cases. The classification of the three dimensional problem remains open.

SODA Conference 2013 Conference Paper

On differentially private low rank approximation

• Michael Kapralov
• Kunal Talwar

STOC Conference 2013 Conference Paper

Sparsest cut on bounded treewidth graphs: algorithms and hardness results

• Anupam Gupta 0001
• Kunal Talwar
• David Witmer

We give a 2-approximation algorithm for the non-uniform Sparsest Cut problem that runs in time n O(k) , where k is the treewidth of the graph. This improves on the previous 2 2 k -approximation in time poly(n) 2 O(k) due to Chlamtac et al. [18].

STOC Conference 2013 Conference Paper

The geometry of differential privacy: the sparse and approximate cases

• Aleksandar Nikolov
• Kunal Talwar
• Li Zhang 0001

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 and range queries and has been the focus of a long line of work. For a given set of d linear queries over a database x ∈ R N , we seek to find the differentially private mechanism that has the minimum mean squared error. For pure differential privacy, [5, 32] give an O(log 2 d) approximation to the optimal mechanism. Our first contribution is to give an efficient O(log 2 d) approximation guarantee for the case of (ε,δ)-differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of [44], using tools from convex geometry. We next consider the sparse case when the number of queries exceeds the number of individuals in the database, i.e. when d > n Δ |x| 1 . The lower bounds used in the previous approximation algorithm no longer apply --- in fact better mechanisms are known in this setting [7, 27, 28, 31, 49]. Our second main contribution is to give an efficient (ε,δ)-differentially private mechanism that, for any given query set A and an upper bound n on |x| 1 , has mean squared error within polylog(d,N) of the optimal for A and n. This approximation is achieved by coupling the Gaussian noise addition approach with linear regression over the l 1 ball. Additionally, we show a similar polylogarithmic approximation guarantee for the optimal ε-differentially private mechanism in this sparse setting. Our work also shows that for arbitrary counting queries, i.e. A with entries in {0,1}, there is an ε-differentially private mechanism with expected error ~O(√n) per query, improving on the ~O(n 2/3 ) bound of [7] and matching the lower bound implied by [15] up to logarithmic factors. The connection between the hereditary discrepancy and the privacy mechanism enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix A.

STOC Conference 2012 Conference Paper

Unconditional differentially private mechanisms for linear queries

• Aditya Bhaskara
• Daniel Dadush
• Ravishankar Krishnaswamy
• Kunal Talwar

We investigate the problem of designing differentially private mechanisms for a set of d linear queries over a database, while adding as little error as possible. Hardt and Talwar [HT10] related this problem to geometric properties of a convex body defined by the set of queries and gave a O(log 3 d)-approximation to the minimum l 2 2 error, assuming a conjecture from convex geometry called the Slicing or Hyperplane conjecture. In this work we give a mechanism that works unconditionally, and also gives an improved O(log 2 d) approximation to the expected l 2 2 error. We remove the dependence on the Slicing conjecture by using a result of Klartag [Kla06] that shows that any convex body is close to one for which the conjecture holds; our main contribution is in making this result constructive by using recent techniques of Dadush, Peikert and Vempala [DPV10]. The improvement in approximation ratio relies on a stronger lower bound we derive on the optimum. This new lower bound goes beyond the packing argument that has traditionally been used in Differential Privacy and allows us to add the packing lower bounds obtained from orthogonal subspaces. We are able to achieve this via a symmetrization argument which argues that there always exists a near optimal differentially private mechanism which adds noise that is independent of the input database! We believe this result should be of independent interest, and also discuss some interesting consequences.

SODA Conference 2010 Conference Paper

Differentially Private Combinatorial Optimization

• Anupam Gupta 0001
• Katrina Ligett
• Frank McSherry
• Aaron Roth 0001
• Kunal Talwar

Consider the following problem: given a metric space, some of whose points are “clients, ” select a set of at most k facility locations to minimize the average distance from the clients to their nearest facility. This is just the well-studied k -median problem, for which many approximation algorithms and hardness results are known. Note that the objective function encourages opening facilities in areas where there are many clients, and given a solution, it is often possible to get a good idea of where the clients are located. This raises the following quandary: what if the locations of the clients are sensitive information that we would like to keep private? Is it even possible to design good algorithms for this problem that preserve the privacy of the clients? In this paper, we initiate a systematic study of algorithms for discrete optimization problems in the framework of differential privacy (which formalizes the idea of protecting the privacy of individual input elements). We show that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the value of an optimal solution, let alone the entire solution. Apart from the k -median problem, we consider the problems of vertex and set cover, min-cut, k-median, facility location, and Steiner tree, and give approximation algorithms and lower bounds for these problems. We also consider the recently introduced submodular maximization problem, “Combinatorial Public Projects” (CPP), shown by Papadimitriou et al. [28] to be inapproximable to subpolynomial multiplicative factors by any efficient and truthful algorithm. We give a differentially private (and hence approximately truthful) algorithm that achieves a logarithmic additive approximation.

FOCS Conference 2010 Conference Paper

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 at the graph obtained by connecting every pair of points within a certain distance r. We then look at various notions of expansion in this graph relating them to the cell probe complexity of NNS for randomized and deterministic, exact and approximate algorithms. For example if the graph has node expansion Φ then we show that any deterministic i-probe data structure for n points must use space S where (St/n) t > Φ. We show similar results for randomized algorithms as well. These relationships can be used to derive most of the known lower bounds in the well known metric spaces such as l 1, l 2, l ∞, and some new ones, by simply computing their expansion. In the process, we strengthen and generalize our previous results. Additionally, we unify the approach in and the communication complexity based approach. Our work reduces the problem of proving cell probe lower bounds of near neighbor search to computing the appropriate expansion parameter. In our results, as in all previous results, the dependence on t is weak; that is, the bound drops exponentially in t. We show a much stronger (tight) time-space tradeoff for the class of dynamic low contention data structures. These are data structures that supports updates in the data set and that do not look up any single cell too often. A full version of the paper could be found in.

STOC Conference 2010 Conference Paper

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 d linear queries f:R n -> R non-adaptively. Here, the database is represented by a vector in R and proximity between databases is measured in the l 1 -metric. We show that the noise complexity is determined by two geometric parameters associated with the set of queries. We use this connection to give tight upper and lower bounds on the noise complexity for any d ≤ n. We show that for d random linear queries of sensitivity 1, it is necessary and sufficient to add l 2 -error Θ(min d√d/ε,d√(log (n/d))/ε) to achieve ε-differential privacy. Assuming the truth of a deep conjecture from convex geometry, known as the Hyperplane conjecture, we can extend our results to arbitrary linear queries giving nearly matching upper and lower bounds. Our bound translates to error $O(min d/ε,√(d log(n/d)/ε)) per answer. The best previous upper bound (Laplacian mechanism) gives a bound of O(min (d/ε,√n/ε)) per answer, while the best known lower bound was Ω(√d/ε). In contrast, our lower bound is strong enough to separate the concept of differential privacy from the notion of approximate differential privacy where an upper bound of O(√{d}/ε) can be achieved.

SODA Conference 2010 Conference Paper

The (1 + beta)-Choice Process and Weighted Balls-into-Bins

• Yuval Peres
• Kunal Talwar
• Udi Wieder

FOCS Conference 2010 Conference Paper

The Limits of Two-Party Differential Privacy

• Andrew McGregor 0001
• Ilya Mironov
• Toniann Pitassi
• Omer Reingold
• Kunal Talwar
• Salil P. Vadhan

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and in general. Our bounds expose a sharp contrast between the two-party setting and the simpler client-server setting (where privacy guarantees are one-sided). In addition, those bounds demonstrate a dramatic gap between the accuracy that can be obtained by differentially private data analysis versus the accuracy obtainable when privacy is relaxed to a computational variant of differential privacy. The first proof technique we develop demonstrates a connection between differential privacy and deterministic extraction from Santha-Vazirani sources. A second connection we expose indicates that the ability to approximate a function by a low-error differentially private protocol is strongly related to the ability to approximate it by a low communication protocol. (The connection goes in both directions).

TCS Journal 2009 Journal Article

A push–relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids

• Kamalika Chaudhuri
• Satish Rao
• Samantha Riesenfeld
• Kunal Talwar

In the minimum-degree minimum spanning tree (MDMST) problem, we are given a graph G, and the goal is to find a minimum spanning tree (MST) T, such that the maximum degree of T is as small as possible. This problem is NP-hard and generalizes the Hamiltonian path problem. We give an algorithm that outputs an MST of degree at most 2 Δ opt ( G ) + o ( Δ opt ( G ) ), where Δ opt ( G ) denotes the degree of the optimal tree. This result improves on a previous result of Fischer [T. Fischer, Optimizing the degree of minimum weight spanning trees. Technical Report 14853, Dept. of Computer Science, Cornell University, Ithaca, NY, 1993] that finds an MST of degree at most b Δ opt ( G ) + log b n, for any b > 1. The MDMST problem is a special case of the following problem: given a k -ary hypergraph G = ( V, E ) and weighted matroid M with E as its ground set, find a minimum-cost basis (MCB) T of M such that the degree of T in G is as small as possible. Our algorithm immediately generalizes to this problem, finding an MCB of degree at most k 2 Δ opt ( G, M ) + O ( k k Δ opt ( G, M ) ). We use the push–relabel framework developed by Goldberg [A. V. Goldberg, A new max-flow algorithm, Technical Report MIT/LCS/TM-291, Massachusetts Institute of Technology, 1985 (Technical Report)] for the maximum-flow problem. To our knowledge, this is the first use of the push–relabel technique in an approximation algorithm for an NP-hard problem. The MDMST problem is closely connected to the bounded-degree minimum spanning tree (BDMST) problem. Given a graph G and degree bound B on its nodes, the BDMST problem is to find a minimum cost spanning tree among the spanning trees with maximum degree B. Previous algorithms for this problem by Könemann and Ravi [J. Könemann, R. Ravi, A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees, SIAM Journal on Computing 31(6) (2002) 1783–1793; J. Könemann, R. Ravi, Primal-dual meets local search: Approximating MST’s with nonuniform degree bounds, in: Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing, 2003, pp. 389–395] and by Chaudhuri et al. [K. Chaudhuri, S. Rao, S. Riesenfeld, K. Talwar, What would Edmonds do? Augmenting paths and witnesses for bounded degree MSTs, in: Proceedings of APPROX/RANDOM, 2005, pp. 26–39] incur a near-logarithmic additive error in the degree. We give the first BDMST algorithm that approximates both the degree and the cost to within a constant factor of the optimum. These results generalize to the case of nonuniform degree bounds.

SODA Conference 2009 Conference Paper

Secretary problems: weights and discounts

• Moshe Babaioff
• Michael Dinitz
• Anupam Gupta 0001
• Nicole Immorlica
• Kunal Talwar

The classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and this decision is irrevocable. Constant-competitive algorithms are known for the classical secretary problems (see, e. g. , the survey of Freeman [7]) and several variants. We study the following two extensions of the secretary problem: • In the discounted secretary problem, there is a time-dependent “discount” factor d ( t ), and the benefit derived from selecting an element/secretary e at time t is d ( t )· v ( e ). For this problem with arbitrary (not necessarily decreasing) functions d ( t ), we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of, and give a nearly-matching O (log n )-competitive algorithm. • In the weighted secretary problem, up to K secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of K positions, with position k having weight w ( k ), and assigning object/secretary e to position k has benefit w ( k ) · v ( e ). The goal is to select secretaries and assign them to positions to maximize Σ e, k w ( k ) · v ( e ) · x ek where x ek is an indicator variable that secretary e is assigned position k. We give constant-competitive algorithms for this problem. Most of these results can also be extended to the matroid secretary case (Babaioff et al. [2]) for a large family of matroids with a constant-factor loss, and an O (log rank) loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al. These problems have connections to online mechanism design (see, e. g. , Hajiaghayi et al. [9]). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problems.

FOCS Conference 2008 Conference Paper

A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match

• Rina Panigrahy
• Kunal Talwar
• Udi Wieder

This work investigates a geometric approach to proving cell probe lower bounds for data structure problems. We consider the {\em approximate nearest neighbor search problem} on the Boolean hypercube $(\bool^d, \onenorm{\cdot})$ with $d=\Theta(\log n)$. We show that any (randomized) data structure for the problem that answers $c$-approximate nearest neighbor search queries using $t$ probes must use space at least $n^{1+\Omega(1/ct)}$. In particular, our bound implies that any data structure that uses space $\tilde{O}(n)$ with polylogarithmic word size, and with constant probability gives a constant approximation to nearest neighbor search queries must be probed $\Omega(\log n/ \log\log n)$ times. This improves on the lower bound of $\Omega(\log\log d/\log\log\log d)$ probes shown by Chakrabarti and Regev~\cite{ChakrabartiR04} for any polynomial space data structure, and the $\Omega(\log\log d)$ lower bound in \Patrascu and Thorup~\cite{PatrascuT07} for linear space data structures. Our lower bound holds for the {\em near neighbor problem}, where the algorithm knows in advance a good approximation to the distance to the nearest neighbor. Additionally, it is an {\em average case} lower bound for the natural distribution for the problem. Our approach also gives the same bound for $(2-\frac{1}{c})$-approximation to the farthest neighbor problem. For the case of non-adaptive algorithms we can improve the bound slightly and show a $\Omega(\log n)$ lower bound on the time complexity of data structures with $O(n)$ space and logarithmic word size. We also show similar lower bounds for the partial match problem: any randomized $t$-probe data structure that solves the partial match problem on $\{0, 1, \star\}^d$ for $d=\Theta(\log n)$ must use space $n^{1+\Omega(1/t)}$. This implies an $\Omega(\log n/\log\log n)$ lower bound for time complexity of near linear space data structures, slightly improving the $\Omega(\log n /(\log \log n)^2)$ lower bound from~\cite{PatrascuT06a}, \cite{JayramKKR03} for this range of $d$. Recently and independently \Patrascu achieved similar bounds \cite{patrascu08}. Our results also generalize to approximate partial match, improving on the bounds of \cite{BarkolR02, PatrascuT06a}.

SODA Conference 2008 Conference Paper

Ultra-low-dimensional embeddings for doubling metrics

• T. -H. Hubert Chan
• Anupam Gupta 0001
• Kunal Talwar

TCS Journal 2007 Journal Article

A primal-dual algorithm for computing Fisher equilibrium in the absence of gross substitutability property

• Dinesh Garg
• Kamal Jain
• Kunal Talwar
• Vijay V. Vazirani

We provide the first strongly polynomial time exact combinatorial algorithm to compute Fisher equilibrium for the case when utility functions do not satisfy the Gross substitutability property. The motivation for this comes from the work of Kelly, Maulloo, and Tan [F. P. Kelly, A. K. Maulloo, D. K. H. Tan, Rate control for communication networks: Shadow prices, proportional fairness and stability, Journal of Operational Research (1998)] and Kelly and Vazirani [F. P. Kelly, Vijay V. Vazirani, Rate control as a market equilibrium (2003) (in preparation)] on rate control in communication networks. We consider a tree like network in which root is the source and all the leaf nodes are the sinks. Each sink has got a fixed amount of money which it can use to buy the capacities of the edges in the network. The edges of the network sell their capacities at certain prices. The objective of each edge is to fix a price that can fetch the maximum money for it, and the objective of each sink is to buy capacities on edges in such a way that it can facilitate the sink to pull maximum flow from the source. In this problem, the edges and the sinks play precisely the role of sellers and buyers, respectively, in Fisher’s market model. The utility of a buyer (or sink) takes the form of a Leontief function which is known for not satisfying Gross substitutability property. We develop an O ( m 3 ) exact combinatorial algorithm for computing equilibrium prices of the edges. The time taken by our algorithm is independent of the values of sink money and edge capacities. A corollary of our algorithm is that equilibrium prices and flows are rational numbers. Although there are algorithms to solve this problem they are all based on convex programming techniques. To the best of our knowledge, ours is the first strongly polynomial time exact combinatorial algorithm for computing equilibrium prices of Fisher’s model under the case when buyers’ utility functions do not satisfy gross substitutability property.

STOC Conference 2007 Conference Paper

Balanced allocations: the weighted case

• Kunal Talwar
• Udi Wieder

FOCS Conference 2007 Conference Paper

Balloon Popping With Applications to Ascending Auctions

• Nicole Immorlica
• Anna R. Karlin
• Mohammad Mahdian
• Kunal Talwar

We study the power of ascending auctions in a scenario in which a seller is selling a collection of identical items to anonymous unit'demand bidders. We show that even with full knowledge of the set of bidders' private valuations for the items, if the bidders are ex-ante identical, no ascending auction can extract more than a constant. times the revenue of the best fixed-price scheme. This problem is equivalent to the problem of coming up with an optimal strategy for blowing up indistinguishable balloons with known capacities in order to maximize the amount of contained, air. We show that the algorithm which simply inflates all balloons to a fixed volume is close to optimal in this setting.

STOC Conference 2007 Conference Paper

Hardness of routing with congestion in directed graphs

• Julia Chuzhoy
• Venkatesan Guruswami
• Sanjeev Khanna
• Kunal Talwar

Given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(N) paths go through any edge. We show that theproblem is hard to approximate within an N Ω(1/c(N)) factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming NP doesn't have N O(log logN) -time randomized algorithms. Here the congestion c(N) can beany function in the range 1 ≤ c(N) ≤ α log N/log log N for some absolute constant α > 0. The hardness result is in the right ballpark since a factor N O(1/c(N)) approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. We also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of N Ω(1/c) for c ranging from 1 to Θ((log n)/(log log n)).

FOCS Conference 2007 Conference Paper

Mechanism Design via Differential Privacy

• Frank McSherry
• Kunal Talwar

We study the role that privacy-preserving algorithms, which prevent the leakage of specific information about participants, can play in the design of mechanisms for strategic agents, which must encourage players to honestly report information. Specifically, we show that the recent notion of differential privacv, in addition to its own intrinsic virtue, can ensure that participants have limited effect on the outcome of the mechanism, and as a consequence have limited incentive to lie. More precisely, mechanisms with differential privacy are approximate dominant strategy under arbitrary player utility functions, are automatically resilient to coalitions, and easily allow repeatability. We study several special cases of the unlimited supply auction problem, providing new results for digital goods auctions, attribute auctions, and auctions with arbitrary structural constraints on the prices. As an important prelude to developing a privacy-preserving auction mechanism, we introduce and study a generalization of previous privacy work that accommodates the high sensitivity of the auction setting, where a single participant may dramatically alter the optimal fixed price, and a slight change in the offered price may take the revenue from optimal to zero.

STOC Conference 2007 Conference Paper

The price of privacy and the limits of LP decoding

• Cynthia Dwork
• Frank McSherry
• Kunal Talwar

This work is at theintersection of two lines of research. One line, initiated by Dinurand Nissim, investigates the price, in accuracy, of protecting privacy in a statistical database. The second, growing from an extensive literature on compressed sensing (see in particular the work of Donoho and collaborators [4,7,13,11])and explicitly connected to error-correcting codes by Candès and Tao ([4]; see also [5,3]), is in the use of linearprogramming for error correction. Our principal result is the discovery of a sharp threshhold ρ*∠ 0.239, so that if ρ < ρ* and A is a random m x n encoding matrix of independently chosen standardGaussians, where m = O(n), then with overwhelming probability overchoice of A , for all x ∈ R n , LP decoding corrects ⌊ ρ m⌋ arbitrary errors in the encoding Ax, while decoding can be made to fail if the error rate exceeds ρ*. Our boundresolves an open question of Candès, Rudelson, Tao, and Vershyin [3] and (oddly, but explicably) refutesempirical conclusions of Donoho [11] and Candès et al [3]. By scaling and rounding we can easilytransform these results to obtain polynomial-time decodable random linear codes with polynomial-sized alphabets tolerating any ρ < ρ* ∠ 0.239 fraction of arbitrary errors. In the context of privacy-preserving datamining our results say thatany privacy mechanism, interactive or non-interactive, providingreasonably accurate answers to a 0.761 fraction of randomly generated weighted subset sum queries, and arbitrary answers on the remaining 0.239 fraction, is blatantly non-private.

SODA Conference 2006 Conference Paper

Approximating unique games

• Anupam Gupta 0001
• Kunal Talwar

UAI Conference 2005 Conference Paper

On Privacy-Preserving Histograms

• Shuchi Chawla 0001
• Cynthia Dwork
• Frank McSherry
• Kunal Talwar

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 information. First, we extend the scope of their techniques to a broad and rich class of distributions, specifically, mixtures of highdimensional balls, spheres, Gaussians, and other "nice" distributions. Second, we randomize the histogram constructions to preserve spatial characteristics of the data, allowing us to approximate various quantities of interest, e.g., cost of the minimum spanning tree on the data, in a privacy-preserving fashion.

SODA Conference 2004 Conference Paper

Approximate classification via earthmover metrics

• Aaron Archer
• Jittat Fakcharoenphol
• Chris Harrelson
• Robert Krauthgamer
• Kunal Talwar
• Éva Tardos

STOC Conference 2004 Conference Paper

Bypassing the embedding: algorithms for low dimensional metrics

• Kunal Talwar

The doubling dimension of a metric is the smallest k such that any ball of radius 2r can be covered using 2 k balls of radius r. This concept for abstract metrics has been proposed as a natural analog to the dimension of a Euclidean space. If we could embed metrics with low doubling dimension into low dimensional Euclidean spaces, they would inherit several algorithmic and structural properties of the Euclidean spaces. Unfortunately however, such a restriction on dimension does not suffice to guarantee embeddibility in a normed space.In this paper we explore the option of bypassing the embedding. In particular we show the following for low dimensional metrics: Quasi-polynomial time (1+ε)-approximation algorithm for various optimization problems such as TSP, k-median and facility location. (1+ε)-approximate distance labeling scheme with optimal label length. (1+ε)-stretch polylogarithmic storage routing scheme.

STOC Conference 2004 Conference Paper

The complexity of pure Nash equilibria

• Alex Fabrikant
• Christos H. Papadimitriou
• Kunal Talwar

We investigate from the computational viewpoint multi-player games that are guaranteed to have pure Nash equilibria. We focus on congestion games, and show that a pure Nash equilibrium can be computed in polynomial time in the symmetric network case, while the problem is PLS-complete in general. We discuss implications to non-atomic congestion games, and we explore the scope of the potential function method for proving existence of pure Nash equilibria.

STOC Conference 2003 Conference Paper

A tight bound on approximating arbitrary metrics by tree metrics

• Jittat Fakcharoenphol
• Satish Rao
• Kunal Talwar

In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n) . This improves upon the result of Bartal who gave a bound of O(log n log log n) . Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(log n) -distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.

SODA Conference 2003 Conference Paper

An approximate truthful mechanism for combinatorial auctions with single parameter agents

• Aaron Archer
• Christos H. Papadimitriou
• Kunal Talwar
• Éva Tardos

SODA Conference 2003 Conference Paper

An improved approximation algorithm for the 0-extension problem

• Jittat Fakcharoenphol
• Chris Harrelson
• Satish Rao
• Kunal Talwar

FOCS Conference 2003 Conference Paper

Paths, Trees, and Minimum Latency Tours

• Kamalika Chaudhuri
• Philip Brighten Godfrey
• Satish Rao
• Kunal Talwar

We give improved approximation algorithms for a variety of latency minimization problems. In particular, we give a 3. 59-approximation to the minimum latency problem, improving on previous algorithms by a multiplicative factor of 2. Our techniques also give similar improvements for related problems like k-traveling repairmen and its multiple depot variant. We also observe that standard techniques can be used to speed up the previous and this algorithm by a factor of O/sup /spl tilde//(n).