Pasin Manurangsi
Authored Publications
Google Publications
Other Publications
Sort By
Preview abstract
Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources using the well-established framework of differential privacy. We present algorithms for approximate envy-freeness and proportionality when two instances are considered to be adjacent if they differ only on the utility of a single agent for a single item. On the other hand, we provide strong negative results for both fairness criteria when the adjacency notion allows the entire utility function of a single agent to change.
View details
Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique
ITCS 2023 (to appear)
Preview abstract
We study the complexity of computing (and approximating) VC Dimension and Littlestone's Dimension when we are given the concept class explicitly. We give a simple reduction from Maximum (Unbalanced) Biclique problem to approximating VC Dimension and Littlestone's Dimension. With this connection, we derive a range of hardness of approximation results and running time lower bounds. For example, under the (randomized) Gap-Exponential Time Hypothesis or the Strongish Planted Clique Hypothesis, we show a tight inapproximability result: both dimensions are hard to approximate to within a factor of o(log n) in polynomial-time. These improve upon constant-factor inapproximability results from [Manurangsi and Rubinstein, COLT 2017].
View details
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Jelani Osei Nelson
Justin Y. Chen
Shyam Narayanan
Yinzhan Xu
SODA 2023 (to appear)
Preview abstract
We study the problem of releasing the weights of all-pairs shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most 1 in the ℓ1-distance. We give an algorithm with additive error ̃O(n^2/3/ε) in the ε-DP case and an algorithm with additive error ̃O(√n/ε) in the (ε, δ)-DP case, where n denotes the number of vertices. This positively answers a question of Sealfon [Sea16, Sea20], who asked whether a o(n) error algorithm exists. We also show that an additive error of Ω(n1/6) is necessary for any sufficiently small ε, δ > 0.
Furthermore, we show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly n^{(√17−3)/2+o(1)}/ε in the ε-DP case and roughly n^{√2−1+o(1)}/ε in the (ε, δ)-DP case. Previously, it was only known how to obtain ̃O(n2/3/ε1/3) additive error in the ε-DP case and ̃O(√n/ε) additive error in the (ε, δ)-DP case for bounded-weight graphs [Sea16].
Finally, we consider a relaxation where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, the additive error can be reduced to ̃O(n^{1/2+O(1/k)}/ε) in the ε-DP case and ̃O(n^{1/3+O(1/k)}/ε) in the (ε, δ)-DP case.
View details
Leveraging Bias-Variance Trade-offs for Regression with Label Differential Privacy
Avinash Varadarajan
Chiyuan Zhang
Ethan Leeman
Pritish Kamath
NeurIPS 2023 (2023)
Preview abstract
We propose a new family of label randomization mechanisms for the task of training regression models under the constraint of label differential privacy (DP). In particular, we leverage the trade-offs between bias and variance to construct better noising mechanisms depending on a privately estimated prior distribution over the labels. We demonstrate that these mechanisms achieve state-of-the-art privacy-accuracy trade-offs on several datasets, highlighting the importance of bias-reducing constraints when training neural networks with label DP. We also provide theoretical results shedding light on the structural properties of the optimal bias-reduced mechanisms.
View details
Preview abstract
In this work, we study the task of estimating the numbers of distinct and k-occurring items in a time window under the constraint of differential privacy (DP). We consider several variants depending on whether the queries are on general time windows (between times t1 and t2), or are restricted to being cumulative (between times 1 and t2), and depending on whether the DP neighboring relation is event-level or the more stringent item-level. We obtain nearly tight upper and lower bounds on the errors of DP algorithms for these problems. En route, we obtain an event-level DP algorithm for estimating, at each time step, the number of distinct items seen over the last W updates with error polylogarithmic in W; this answers an open question of Bolot et al. (ICDT 2013).
View details
Preview abstract
We study the fine-grained complexity of the famous $k$-center problem in the metric induced by a graph with $n$ vertices and $m$ edges. The problem is NP-hard to approximate within a factor strictly better than $2$, and several $2$-approximation algorithms are known.
Two of the most well-known approaches for the $2$-approximation are (1) finding a maximal distance $r$-independent set (where the minimum pairwise distance is greater than $r$) and (2) Gonzalez's algorithm that iteratively adds the center farthest from the currently chosen centers.
For the approach based on distance-$r$ independent sets, Thorup [SIAM J. Comput. '05] already gave a nearly linear time algorithm. While Thorup's algorithm is not complicated, it still requires tools such as an approximate oracle for neighborhood size by Cohen [J. Comput. Syst. Sci. '97]. Our main result is a nearly straightforward algorithm that improves the running time by an $O(\log n$) factor. It results in an $(2+\eps)$-approximation for $k$-center in $O((m + n \log n)\log n \log(n/\eps))$ time.
For Gonzalez's algorithm [Theor. Comput. Sci. 85], we show that the simple $\widetilde{O}(mk)$-time implementation is nearly optimal if we insist the {\em exact} implementation. On the other hand, we show that an $(1+\eps)$-approximate version of the algorithm is efficiently implementable, leading to an $(2+\eps)$-approximation algorithm in running time $O((m + n \log n)\log^2 n / \eps)$. We also show that, unlike in the distance $r$-independent set-based algorithm, the dependency of $1/\eps$ in the running time is essentially optimal for $(1 + \eps)$-approximate Gonzalez's.
View details
Preview abstract
Differential privacy is often applied with a privacy parameter that is larger than the theory suggests is ideal; various informal justifications for tolerating large privacy parameters have been proposed.
In this work, we consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis.
In this framework, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person (i.e., all the attributes).
View details
The Price of Justified Representation
Ayumi Igarashi
Edith Elkind
Piotr Faliszewski
Ulrike Schmidt-Kraepelin
Warut Suksompong
AAAI 2022
Preview abstract
In multiwinner approval voting, the goal is to select k-member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the algorithmic complexity of finding 'good' committees that provide JR (obtaining a hardness result, an approximation algorithm, and a positive result for the one-dimensional setting), and study this problem empirically on several synthetic datasets.
View details
Preview abstract
Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by fixing the bracket, these results ignore the prevalent aspect of player seeds, which can significantly constrain the chosen bracket. We show that certain structural conditions that guarantee that a player can win a knockout tournament without seeds are no longer sufficient in light of seed constraints. On the other hand, we prove that when the pairwise match outcomes are generated randomly, all players are still likely to be knockout winners under the same probability threshold with seeds as without seeds. In addition, we investigate the complexity of deciding whether a manipulation is possible when seeds are present.
View details
Preview abstract
In this work, we study the large-scale pretraining of BERT-Large~\citep{devlin2018bert} with differentially private SGD (DP-SGD). We show that combined with a careful implementation, scaling up the batch size to millions (i.e., mega-batches) improves the utility of the DP-SGD step for BERT; we also enhance the training efficiency by using an increasing batch size schedule. Our implementation builds on the recent work of \citet{subramani20}, who demonstrated that the overhead of a DP-SGD step is minimized with effective use of JAX \cite{jax2018github, frostig2018compiling} primitives in conjunction with the XLA compiler \cite{xladocs}. Our implementation achieves a masked language model accuracy of 60.5\% at a batch size of 2M, for $\eps = 5$, which is a reasonable privacy setting. To put this number in perspective, non-private BERT models achieve an accuracy of $\sim$70\%.
View details
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
Amir Abboud
Euiwoong Lee
49th International Colloquium on Automata, Languages and Programming (ICALP) (2022)
Preview abstract
The privacy loss distribution (PLD) provides a tight characterization of the privacy loss of a mechanism in the context of differential privacy (DP). Recent work has shown that PLD-based accounting allows for tighter (ε,δ)-DP guarantees for many popular mechanisms compared to other known methods. A key question in PLD-based accounting is how to approximate any (potentially continuous) PLD with a PLD over any specified discrete support.
We present a novel approach to this problem. Our approach supports both pessimistic estimation, which overestimates the hockey-stick divergence (i.e., δ) for any value of ε, and optimistic estimation, which underestimates the hockey-stick divergence. Moreover, we show that our pessimistic estimate is the best possible among all pessimistic estimates. Experimental evaluation shows that our approach can work with much larger discretization intervals while keeping a similar error bound compared to previous approaches and yet give a better approximation than existing methods.
View details
Preview abstract
In this paper, we consider the problem of differentially private (DP) algorithms for isotonic regression. For the most general problem of isotonic regression over a partially ordered set (poset) X and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given n input points, has an expected excess empirical risk of roughly width(X)⋅log|X|/n, where width(X) is the width of the poset. In contrast, we also obtain a near-matching lower bound of roughly (width(X)+log|X|)/n, that holds even for approximate-DP algorithms. Moreover, we show that the above bounds are essentially the best that can be obtained without utilizing any further structure of the poset.
In the special case of a totally ordered set and for ℓ1 and ℓ2^2 losses, our algorithm can be implemented in near-linear running time; we also provide extensions of this algorithm to the problem of private isotonic regression with additional structural constraints on the output function.
View details
Preview abstract
In this paper we consider the problem of aggregating multiple user-generated tracks in a differentially private manner. For this problem we propose a new aggregation algorithm that adds noise sufficient enough to guarantee privacy while preserving the utility of the aggregate. Under natural and simple assumptions, we also show that this algorithm has provably good guarantees.
View details
Preview abstract
We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate privacy parameters for compositions of mechanisms.
For the task of self-composing a broad class of mechanisms $K$ times, this algorithm achieves a running time \& memory usage of $\polylog(K)$ (e.g., this class includes the sub-sampled Gaussian mechanism, that appears in the analysis of DP-SGD).
By comparison, recent work by Gopi et al. (NeurIPS 2021) has a running time of $\wtilde{O}(\sqrt{K})$ for the same task.
Our approach extends to the case of composing $K$ different mechanisms in the same class, improving upon the running time / memory usage in the work of Gopi et al. from $\wtilde{O}(K^{1.5})$ to $\wtilde{O}(K)$.
View details
Distributed, Private, Sparse Histograms in the Two-Server Model
Adria Gascon
James Bell
Phillipp Schoppmann
CCS 2022
Preview abstract
We consider the computation of sparse, (ε, ϑ)-differentially private~(DP) histograms in the two-server model of secure multi-party computation~(MPC), which has recently gained traction in the context of privacy-preserving measurements of aggregate user data. We introduce protocols that enable two semi-honest non-colluding servers to compute histograms over the data held by multiple users, while only learning a private view of the data. Our solution achieves the same asymptotic l∞-error of O(log(1/ϑ)/ε) as in the central model of DP, but without relying on a trusted curator. The server communication and computation costs of our protocol are independent of the number of histogram buckets, and are linear in the number of users, while the client cost is independent of the number of users, ε, and ϑ. Its linear dependence on the number of users lets our protocol scale well, which we confirm using microbenchmarks: for a billion users, ε = 0.5, and ϑ = 10-11, the per-user cost of our protocol is only 1.08 ms of server computation and 339 bytes of communication. In contrast, a baseline protocol using garbled circuits only allows up to 106 users, where it requires 600 KB communication per user.
View details
Justifying Committees in Multiwinner Approval Voting
Ayumi Igarashi
Edith Elkind
Piotr Faliszewski
Ulrike Schmidt-Kraepelin
Warut Suksompong
SAGT 2022
Preview abstract
Justified representation (JR) is a well-known notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups that are smaller than the target size k. In this paper, we study such groups—known as n/k-justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n/k-justifying groups of size less than k/2 are likely to exist, which implies that the number of JR committees is usually large. We then present approximation algorithms that compute a small n/k-justifying group for any given instance, and an exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n/k-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.
View details
Preview abstract
In this note, we consider the problem of differentially privately (DP) computing an anonymoized histogram, which is defined as the multiset of counts of the input dataset (without bucket labels). In the low-privacy regime ε ≥ 1, we give an ε-DP algorithm with an l1-error bound of O(√n/e^ε). In the high-privacy regime ε < 1, we give an Ω(sqrt(n log(1/ε)/ε)) lower bound on the l1 error. In both cases, our bounds asymptotically match the previously known lower/upper bounds due to [Suresh, NeurIPS 2019].
View details
Preview abstract
We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i.i.d. labeled examples (x,y)∈ℝN×{±1}, where the distribution of x is arbitrary and the label y is a Massart corruption of f(x), for an unknown halfspace f:ℝN→{±1}, with flipping probability η(x)≤η<1/2. The goal of the learner is to compute a hypothesis with small 0-1 error. Our main result is the first computational hardness result for this learning problem. Specifically, assuming the (widely believed) subexponential-time hardness of the Learning with Errors (LWE) problem, we show that no polynomial-time Massart halfspace learner can achieve error better than Ω(η), even if the optimal 0-1 error is small, namely OPT=2^{−log^c(N)} for any universal constant c∈(0,1). Prior work had provided qualitatively similar evidence of hardness in the Statistical Query model. Our computational hardness result essentially resolves the polynomial PAC learnability of Massart halfspaces, by showing that known efficient learning algorithms for the problem are nearly best possible.
View details
Preview abstract
We study the problem of privately computing the \emph{anonymized histogram} (aka \emph{unattributed histogram}), which is defined as the histogram without item labels. Previous works have provided algorithms with $\ell_1$ and $\ell_2$ errors of $O_\eps(\sqrt{n})$ in the central model of differential privacy (DP).
In this work, we provide an algorithm with a nearly matching error guarantee of $\tilde{O}_\eps(\sqrt{n})$ in the shuffle and pan private DP models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram! Using this algorithm as a subroutine, we show applications in estimating several symmetric properties of distributions such as the entropy and support size.
View details
Preview abstract
We give the first polynomial time and sample (epsilon, delta)-differentially private (DP) algorithm to estimate the mean, covariance and higher moments in the presence of a constant fraction of adversarial outliers. Our algorithm succeeds for families of distributions that satisfy two well-studied properties in prior works on robust estimation: certifiable subgaussianity of directional moments and certifiable hypercontractivity of degree 2 polynomials. Our recovery guarantees hold in the “right affine-invariant norms”: Mahalanobis distance for mean, multiplicative spectral and relative Frobenius distance guarantees for covariance and injective norms for higher moments. Prior works obtained private robust algorithms for mean estimation of subgaussian distributions with bounded covariance. For covariance estimation, ours is the first efficient algorithm (even in the absence of outliers) that succeeds without any condition-number assumptions. Our algorithms arise from a new framework that provides a general blueprint for modifying convex relaxations for robust estimation to satisfy strong worst-case stability guarantees in the appropriate parameter norms whenever the algorithms produce witnesses of correctness in their run. We verify such guarantees for a modification of standard sum-of-squares (SoS) semidefinite programming relaxations for robust estimation. Our privacy guarantees are obtained by combining stability guarantees with a new “estimate dependent” noise injection mechanism in which noise scales with the eigenvalues of the estimated covariance. We believe this framework will be useful more generally in obtaining DP counterparts of robust estimators. Independently of our work, Ashtiani and Liaw [AL21] also obtained a polynomial time and sample private robust estimation algorithm for Gaussian distributions.
View details
Preview abstract
We study the problem of distribution-free PAC learning a single neuron under adversarial label noise with respect to the squared loss. For a range of activation functions, including ReLUs and sigmoids,
we prove strong computational hardness of learning results in the Statistical Query model and under a well-studied assumption on the complexity of refuting XOR formulas. Specifically, we establish that no
polynomial-time learning algorithm, even improper, can approximate the optimal loss value within any constant factor.
View details
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
Guru Prashanth Guruganesh
NeurIPS (2021)
Preview abstract
We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i.e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$.
We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns.
We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest.
View details
Sample-efficient proper PAC learning with approximate differential privacy
Noah Golowich
Symposium on Theory of Computing (STOC) (2021), pp. 183-196
Preview abstract
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension d with approximate differential privacy is Õ(d^6), ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of 2^O(d) on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.
View details
Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory
Warut Suksompong
International Joint Conference on Artificial Intelligence (IJCAI) (2021) (to appear)
Preview abstract
We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the n agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to Θ(√n) goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to o(√n) goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.
View details
Google COVID-19 Vaccination Search Insights: Anonymization Process Description
Adam Boulanger
Akim Kumok
Arti Patankar
Benjamin Miller
Chaitanya Kamath
Charlotte Stanton
Chris Scott
Damien Desfontaines
Evgeniy Gabrilovich
Gregory A. Wellenius
John S. Davis
Karen Lee Smith
Krishna Kumar Gadepalli
Mark Young
Shailesh Bavadekar
Tague Griffith
Yael Mayer
Arxiv.org (2021)
Preview abstract
This report describes the aggregation and anonymization process applied to the COVID-19 Vaccination Search Insights~\cite{vaccination}, a publicly available dataset showing aggregated and anonymized trends in Google searches related to COVID-19 vaccination. The applied anonymization techniques protect every user’s daily search activity related to COVID-19 vaccinations with $(\varepsilon, \delta)$-differential privacy for $\varepsilon = 2.19$ and $\delta = 10^{-5}$.
View details
Algorithmic Persuasion with Evidence
Martin Hoefer
Alex Psomas
Innovations in Theoretical Computer Science (ITCS) (2021), 3:1-3:20
Preview abstract
We consider optimization problems faced by a sender and a receiver in a game of persuasion with evidence. The sender wishes to persuade the receiver to take one of two actions by presenting evidence. The sender’s utility depends solely on the action taken, while the receiver’s utility depends on both the action as well as the sender’s private information. We study two natural variations. The first is verification, where the sender commits to a signaling scheme and then the receiver takes an action after seeing the evidence. The second is delegation, where the receiver first commits to taking a certain action if being presented certain evidence, and then the sender presents evidence to maximize the probability that her favorite action is taken. We study these problems through the computational lens, and give hardness results, optimal approximation algorithms, as well as efficient algorithms for special cases. In particular, we provide an approximation algorithm that rounds a semidefinite program that might be of independent interest, since, to the best of our knowledge, it is the first such approximation algorithm for a natural problem in algorithmic economics.
View details
Preview abstract
We study a resource allocation setting where m discrete items are to be divided among n agents with additive utilities, and the agents’ utilities for individual items are drawn at random from a probability distribution. Since common fairness notions like envy-freeness and proportionality cannot always be satisfied in this setting, an important question is when allocations satisfying these notions exist. In this paper, we close several gaps in the line of work on asymptotic fair division. First, we prove that the classical round-robin algorithm is likely to produce an envy-free allocation provided that m = Ω(n log n/log log n), matching the lower bound from prior work. We then show that a proportional allocation exists with high probability as long as m ≥ n, while an allocation satisfying envy-freeness up to any item (EFX) is likely to be present for any relation between m and n. Finally, we consider a related setting where each agent is assigned exactly one item and the remaining items are left unassigned, and show that the transition from non-existence to existence with respect to envy-free assignments occurs at m = en.
View details
The Strongish Planted Clique Hypothesis and Its Applications
Aviad Rubinstein
Tselil Schramm
Innovations in Theoretical Computer Science (ITCS) (2021), 10:1-10:21
Preview abstract
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time n^Ω(log n) (so that the state-of-the-art runtime of n^O(log n) is optimal up to a constant in the exponent).
We provide two sets of applications of the new hypothesis. First, we show that SPCH implies (nearly) tight inapproximability results for the following well-studied problems in terms of the parameter k: Densest k-Subgraph, Smallest k-Edge Subgraph, Densest k-Subhypergraph, Steiner k-Forest, Directed Steiner Network with k terminal pairs. For example, we show, under SPCH, that no polynomial time algorithm achieves o(k)-approximation for Densest k-Subgraph. This improves upon the previous best inapproximability ratio k^o(1) from (Chalermsook et al., FOCS 2017). Furthermore, our lower bounds hold even against fixed-parameter tractable (FPT) algorithms with parameter k.
Our second application focuses on the complexity of graph pattern detection. For both induced and non-induced graph pattern detection, we prove hardness results under SPCH, which improve the running time lower bounds obtained by (Dalirrooyfard et al., STOC 2019) under ETH.
View details
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
Annual Conference on Learning Theory (COLT) (2021), pp. 2133-2146
Preview abstract
In this work, we study the problem of answering k queries with (ε, δ)-differential privacy, where each query has sensitivity one. We give a mechanism for this task that achieves an error bound of O(sqrt(k ln(1/δ))/ε), which is known to be tight (Steinke and Ullman, 2016).
A parallel work by Dagan and Kur (2020) provides a similar result, albeit via a completely different approach. One difference between our work and theirs is that our guarantee holds even when δ < 2^−Ω(k/(log k)^8) whereas theirs does not apply in this case. On the other hand, the algorithm of Dagan and Kur has a remarkable advantage that the ℓ∞ error bound of O(sqrt(k ln(1/δ))/ε) holds not only in expectation but always (i.e., with probability one) while we can only get a high probability (or expected) guarantee on the error.
View details
Tight Hardness Results for Training Depth-2 ReLU Networks
Surbhi Goel
Adam Klivans
Daniel Reichman
Innovations in Theoretical Computer Science (ITCS) (2021), 22:1-22:14
Preview abstract
We prove several hardness results for training neural networks with a single hidden layer and the ReLU activation function. Our goal is to output a one-layer neural network that minimizes the square loss with respect to a given training set. We prove that this problem is NP-hard already for a network with a single ReLU. We also prove NP-hardness for outputting a weighted sum of k ReLUs minimizing the squared error (for k > 1) even in the realizable setting (i.e., when the labels are consistent with an unknown one layer ReLU network). We are also able to obtain lower bounds on the running time in terms of 1/epsilon where epsilon is the desired additive error. To obtain our lower bounds, we use the Gap-ETH hypothesis as well as a new hypothesis regarding the hardness of approximating the well known Densest k-Subgraph problem in subexponential time (these hypotheses are used separately in proving different lower bounds). For example, we prove that under reasonable hardness assumptions, any proper learning algorithm for finding the best fitting ReLU must run in time exponential in 1/epsilon^2. This implies the first separation between proper and improper algorithms for learning a ReLU due to prior work by Geol et al. We also study the problem of properly learning a depth-2 network with ReLUs with bounded weights giving new (worst-case) upper bounds on the running time needed to learn such networks, that essentially matches our lower bounds in terms of the dependency on epsilon.
View details
Near-tight closure bounds for Littlestone and threshold dimensions
Noah Golowich
International Conference on Algorithmic Learning Theory (ALT) (2021), pp. 686-696
Preview abstract
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes H1,…,Hk of Boolean functions with bounded Littlestone (respectively, threshold) dimension, we establish an upper bound on the Littlestone (respectively, threshold) dimension of the class defined by applying an arbitrary binary aggregation rule to H1,…,Hk. We also show that our upper bounds are nearly tight. Our upper bounds give an exponential (in k) improvement upon analogous bounds shown by Alon et al. (COLT 2020), thus answering a question posed by their work.
View details
On Distributed Differential Privacy and Counting Distinct Elements
Lijie Chen
Innovations in Theoretical Computer Science (ITCS) (2021), 56:1-56:18
Preview abstract
We study the setup where each of n users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of (epsilon, delta)-differentially privacy:
- In the local setting, we prove that the additive error of any protocol is Omega(n) for any constant epsilon and any delta inverse polynomial in n. This provides the first separation between global sensitivity and error that is omega(sqrt{n}) in local differential privacy, thus answering a question of Vadhan (2017).
- In the single-message shuffle setting, we prove a lower bound of tilde{Omega}(n) on the error for any constant epsilon and for some delta inverse quasi-polynomial in n. We do so using the moment-matching method from the literature on distribution estimation.
- In the multi-message shuffle setting, we give a protocol with <= 1 message per user in expectation and with an error of tilde{O}(sqrt{n}) for any constant epsilon and delta inverse polynomial in n.
Our proof technique relies on a new notion, that we call dominated protocols, and which can be used to obtain the first non-trivial lower bounds against multi-message shuffle protocols for the well-studied problems of Selection and Parity Learning.
View details
Preview abstract
Most works in learning with differential privacy (DP) have focused on the case where each user has a single sample. In this work, we consider the setting where each user receives $m$ samples and the privacy protection is enforced at the level of each user's data. We show that, in this setting, we may learn with much few number of samples. Specifically, we show that, as long as each user receives sufficiently many samples, we can learn any privately learnable class via an $(\eps, \delta)$-DP algorithm using only $O(\log(1/\delta)/\eps)$ users. For $\eps$-DP algorithms, we show that we can learn using only $O_{\eps}(d)$ users even in the local model, where $d$ is the probabilistic representation dimension. In both cases, we show a nearly-matching lower bound on the number of users required.
A crucial component of our results is a generalization of \emph{global stability}~\cite{BunLM20} that allows the use of public randomness. Under this relaxed notion, we employ a correlated sampling strategy to show that the global stability can be boosted to be arbitrarily close to one, at a polynomial expense in the number of samples.
View details
On the Complexity of Fair House Allocation
Naoyuki Kamiyama
Warut Suksompong
Operations Research Letters, vol. 49 (4) (2021), pp. 572-577
Preview abstract
We study fairness in house allocation, where m houses are to be allocated among n agents so that
every agent receives one house. We show that maximizing the number of envy-free agents is hard to
approximate to within a factor of n^{1−γ} for any constant γ > 0, and that the exact version is NP-hard
even for binary utilities. Moreover, we prove that deciding whether a proportional allocation exists is
computationally hard, whereas the corresponding problem for equitability can be solved efficiently.
View details
Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems
Jan Marcinkowski
Szymon Dudycz
Workshop on Approximation and Online Algorithms (WAOA) (2021) (to appear)
Preview abstract
We study theMinimum Maximal Matching problem, where we are asked to find in a graph the smallest matching that cannot be extended. We show that this problem is hard to approximate with any constant smaller than 2 even in bipartite graphs, assuming either of two stronger variants of Unique Games Conjecture. The bound also holds for computationally equivalent Minimum Edge Dominating Set. Our lower bound matches the approximation provided by a trivial algorithm.
Our results imply conditional hardness of approximating Maximum Stable Matching with Ties and Incomplete Lists with a constant better than 3/2, which also matches the best known approximation algorithm
View details
Robust and Private Learning of Halfspaces
Thao Nguyen
International Conference on Artificial Intelligence and Statistics (AISTATS) (2021), pp. 1603-1611
Preview abstract
In this work, we study the trade-off between differential privacy and adversarial robustness under L2-perturbations in the context of learning halfspaces. We prove nearly tight bounds on the sample complexity of robust private learning of halfspaces for a large regime of parameters. A highlight of our results is that robust and private learning is harder than robust or private learning alone. We complement our theoretical analysis with experimental results on the MNIST and USPS datasets, for a learning algorithm that is both differentially private and adversarially robust.
View details
Linear Discrepancy is Π2-Hard to Approximate
Information Processing Letters (2021) (to appear)
Preview abstract
In this note, we prove that the problem of computing the linear discrepancy of a given matrix is Π2- hard, even to approximate within 9/8 − ε factor for any ε > 0. This strengthens the NP-hardness result of Li and Nikolov (ESA 2020) for the exact version of the problem, and answers a question posed by them. Furthermore, since Li and Nikolov showed that the problem is contained in Π2, our result makes linear discrepancy another natural problem that is Π2-complete (to approximate).
View details
Locally Private k-Means in One Round
Alisa Chang
International Conference on Machine Learning (ICML) (2021), pp. 1441-1451
Preview abstract
We study k-means clustering in the non-interactive (aka one-round) local model of differential privacy. We give an approximation algorithm that requires a single round of communication and achieves an approximation ratio arbitrarily close to the best non private approximation algorithm. To show the flexibility of our framework, we also demonstrate that it yields a similar near-optimal approximation algorithm in the (one-round) shuffle model.
View details
Generalized Kings and Single-Elimination Winners in Random Tournaments
Warut Suksompong
International Joint Conference on Artificial Intelligence (IJCAI) (2021) (to appear)
Preview abstract
Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a k-king if it can reach every other alternative in the tournament via a directed path of length at most k. In this paper, we provide an almost complete characterization of the probability threshold such that all alternatives are k-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the regime of constant k, with the
biggest change being between k = 2 and k = 3. In addition, we establish an asymptotically tight bound on the probability under which all alternatives can win a single-elimination tournament under some bracket.
View details
Differentially Private Clustering: Tight Approximation Ratios
Advances in Neural Information Processing Systems (NeurIPS) (2020)
Preview abstract
We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors.
Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.
View details
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
Ilias Diakonikolas
Daniel Kane
Advances in Neural Information Processing Systems (NeurIPS) (2020)
Preview abstract
We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on L_p perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the L_∞ perturbations case is provably computationally harder than the case 2 ≤ p < ∞
View details
Consensus Halving for Sets of Items
Paul W. Goldberg
Alexandros Hollender
Ayumi Igarashi
Warut Suksompong
Conference on Web and Internet Economics (WINE) (2020), pp. 384-397
Preview abstract
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represented by an interval, a consensus halving with at most n cuts always exists, but is hard to compute even for agents with simple valuation functions. In this paper, we study consensus halving in a natural setting where the resource consists of a set of items without a linear ordering. When agents have additive utilities, we present a polynomial-time algorithm that computes a consensus halving with at most n cuts, and show that n cuts are almost surely necessary when the agents’ utilities are drawn from probabilistic distributions. On the other hand, we show that for a simple class of monotonic utilities, the problem already becomes PPAD-hard. Furthermore, we compare and contrast consensus halving with the more general problem of consensus k-splitting, where we wish to divide the resource into k parts in possibly unequal ratios, and provide some consequences of our results on the problem of computing small agreeable sets.
View details
Pure Differentially Private Summation from Anonymous Messages
Noah Golowich
Rasmus Pagh
Information Theoretic Cryptography (ITC) (2020), 15:1-15:23
Preview abstract
The shuffled (aka anonymous) model has recently generated significant interest as a candidate dis- tributed privacy framework with trust assumptions better than the central model but with achievable error rates smaller than the local model. In this paper, we study pure differentially private protocols in the shuffled model for summation, a very basic and widely used primitive. Specifically:
• For the binary summation problem where each of n users holds a bit as an input, we give a pure ε-
differentially private protocol for estimating the number of ones held by the users up to an absolute
error of Oε(1), and where each user sends Oε(logn) messages each consisting of a single bit. This √
is the first pure differentially private protocol in the shuffled model with error o( n) for constant values of ε.
Using our binary summation protocol as a building block, we give a pure ε-differentially private protocol that performs summation of real numbers (in [0,1]) up to an absolute error of Oε(1), and where each user sends Oε(log3 n) messages each consisting of O(loglogn) bits.
• In contrast, we show that for any pure ε-differentially private protocol for binary summation in the shuffled model having absolute error n0.5−Ω(1), the per user communication has to be at least
Ωε( log n) bits. This implies (i) the first separation between the (bounded-communication) multi- message shuffled model and the central model, and (ii) the first separation between pure and approximate differentially private protocols in the shuffled model.
Interestingly, over the course of proving our lower bound, we have to consider (a generalization of) the following question which might be of independent interest: given γ ∈ (0, 1), what is the smallest positive integer m for which there exist two random variables X0 and X1 supported on {0, . . . , m} such that (i) the total variation distance between X0 and X1 is at least 1 − γ, and (ii) the moment generating functions of X0 and X1 are within a constant factor of each other everywhere? We show that the answer to this question is m = Θ(
View details
Nearly Optimal Robust Secret Sharing against Rushing Adversaries
Akshayaram Srinivasan
Prashant Nalini Vasudevan
Annual International Cryptology Conference (CRYPTO) (2020), pp. 156-185
Preview abstract
Robust secret sharing is a strengthening of secret sharing which allows the secret to be recovered even if some of the shares being used in the reconstruction have been adversarially modified. In this work, we study the setting where out of all the n shares, the adversary is allowed to adaptively corrupt and modify t shares, where n = 2t+1.
It is known that in this setting, to recover a secret of length m bits with error less than 2^-lambda, shares of size at least m + lambda bits are needed. Recently, Bishop, Pastro, Rajaraman, and Wichs (EUROCRYPT 2016) gave a construction with shares of size m + O(lambda * polylog(n, m, lambda)) bits that is secure against non-rushing adversaries. Later, Fehr and Yuan (EUROCRYPT 2019) constructed a scheme that is secure against rushing adversaries, and has shares of size m + O(lambda * n^epsilon * polylog(n, m, lambda)) bits for an arbitrary constant epsilon > 0. They also showed a variant of their construction with share size m + O(lambda * polylog(n, m, lambda)) bits, but with super-polynomial reconstruction time.
We present a robust secret sharing scheme that is secure against rushing adversaries, has shares of size m + O(lambda * log n * (log n + log m)) bits, and polynomial-time sharing and reconstruction. Central to our construction is an algorithm for a problem on semi-random graphs that arises naturally in the paradigm of local authentication of shares used by us and in the aforementioned work.
View details
To Close Is Easier Than To Open: Dual Parameterization To k-Median
Jaroslaw Byrka
Szymon Dudycz
Jan Marcinkowski
Michal Wlodarczyk
Workshop on Approximation and Online Algorithms (WAOA) (2020), pp. 113-126
Preview abstract
The k-Median problem is one of the well-known optimization problems that formalizes the task of data clustering. Here, we are given sets of facilities F and clients C, and the goal is to open k facilities from the set F, which provides the best division into clusters, that is, the sum of distances from each client to the closest open facility is minimized. In the Capacitated k-Median, the facilities are also assigned capacities specifying how many clients can be served by each facility.
Both problems have been extensively studied from the perspective of approximation algorithms. Recently, several surprising results have come from the area of parameterized complexity, which provided better approximation factors via algorithms with running times of the form f(k) · poly(n). In this work, we extend this line of research by studying a different choice of parameterization. We consider the parameter l = |F| − k, that is, the number of facilities that remain closed. It turns out that such a parameterization reveals yet another behaviour of k-Median. We observe that the problem is W[1]-hard but it admits a parameterized approximation scheme. Namely, we present an algorithm with running time 2^O(l · log(l/ε)) · poly(n) that achieves(1 + ε)-approximation. On the other hand, we show that under the assumption of Gap Exponential Time Hypothesis, one cannot extend this result to the capacitated version of the problem.
View details
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Andreas Emil Feldmann
Karthik C. S.
Euiwoong Lee
Algorithms, vol. 13(6) (2020), pp. 146
Preview abstract
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.
View details
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
Rasmus Pagh
International Conference on Machine Learning (ICML) (2020), pp. 3505-3514
Preview abstract
Differential privacy (DP) is a formal notion for quantifying the privacy loss of algorithms. Algorithms in the central model of DP achieve high accuracy but make the strongest trust assumptions whereas those in the local DP model make the weakest trust assumptions but incur substantial accuracy loss. The shuffled DP model (Bittau et al., 2017; Erlingsson et al., 2019; Cheu et al.,2019) has recently emerged as a feasible middle ground between the central and local models, providing stronger trust assumptions than the former while promising higher accuracies than the latter. In this paper, we obtain practical communication-efficient algorithms in the shuffled DP model for two basic aggregation primitives used in machine learning: 1) binary summation, and 2) histograms over a moderate number of buckets. Our algorithms achieve accuracy that is arbitrarily close to that of central DP algorithms with an expected communication per user essentially matching what is needed without any privacy constraints! We demonstrate the practicality of our algorithms by experimentally comparing their performance to several widely-used protocols such as Randomized Response (Warner, 1965) and RAPPOR (Erlingsson et al., 2014).
View details
Private Aggregation from Fewer Anonymous Messages
Rasmus Pagh
Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2020), pp. 798-827
Preview abstract
Consider the setup where n parties are each given a number x_i in F_q and the goal is to compute the sum of x_i in a secure fashion and with as little communication as possible. We study this problem in
the anonymized model of Ishai et al. (FOCS 2006) where each party may broadcast anonymous messages on an insecure channel.
We present a new analysis of the one-round "split and mix" protocol of Ishai et al. In order to achieve the same security parameter, our analysis reduces the required number of messages by a Θ(log n) multiplicative factor. We complement our positive result with lower bounds showing that the dependence of the number of messages on the domain size, the number of parties, and the security parameter is essentially tight.
Using a reduction of Balle et al. (2019), our improved analysis of the protocol of Ishai et al. yields, in the same model, an (ε, δ)-differentially private protocol for aggregation that, for any constant ε > 0 and any δ = 1 / poly(n), incurs only a constant error and requires only a constant number of messages per party. Previously, such a protocol was known only for Θ(log n) messages per party.
View details
No Results Found
