Author name cluster

Shyam Narayanan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

26 papers

2 author rows

FOCS Conference 2024 Conference Paper

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation

Shyam Narayanan
Václav Rozhon
Jakub Tetek
Mikkel Thorup

Suppose we have a memory storing 0s and 1s and we want to estimate the frequency of 1s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a block of $B$ bits at unit cost; not just one bit. If the input consists of uniform blocks: either all 1s or all Os, then sampling a whole block at a time does not reduce the number of samples needed for estimation. On the other hand, if bits are randomly permuted, then getting a block of $B$ bits is as good as getting $B$ indendent bit samples. However, we do not want to make any such assumptions on the input. Instead, our goal is to have an algorithm with instance-dependent performance guarantees which stops sampling blocks as soon as we know that we have a probabilistically reliable estimate. We prove our algorithms to be instance-optimal among algorithms oblivious to the order of the blocks, which we argue is the strongest form of instance optimality we can hope for. We also present similar results for I/O-efficiently estimating mean with both additive and multiplicative error, estimating histograms, quantiles, as well as the empirical cumulative distribution function. We obtain our above results on I/O-efficient sampling by reducing to corresponding problems in the so-called sequential estimation. In this setting, one samples from an unknown distribution until one can provide an estimate with some desired error probability. Sequential estimation has been considered extensively in statistics over the past century. However, the focus has been mostly on parametric estimation, making stringent assumptions on the distribution of the input, and thus not useful for our reduction. In this paper, we make no assumptions on the input distribution (apart from its support being a bounded set). Namely, we provide non-parametric instance-optimal results for several fundamental problems: mean and quantile estimation, as well as learning mixture distributions with respect to $\ell_{\infty}$ and the so-called Kolmogorov-Smirnov distance. All our algorithms are simple, natural, and practical, and some are even known from other contexts, e. g. , from statistics in the parameterized setting. The main technical difficulty is in analyzing them and proving that they are instance optimal.

SODA Conference 2024 Conference Paper

Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree

Rajesh Jayaram
Vahab Mirrokni
Shyam Narayanan
Peilin Zhong

We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set X ⊂ ℝ d of n points, the goal is to produce a spanning tree for X with weight within a small factor of optimal. Euclidean MST is one of the most fundamental hierarchical geometric clustering algorithms, and with the proliferation of enormous high-dimensional data sets, such as massive transformer-based embeddings, there is now a critical demand for efficient distributed algorithms to cluster such data sets. In low-dimensional space, where d = O (1), Andoni, Nikolov, Onak, and Yaroslavtsev [STOC ‘14] gave a constant round MPC algorithm that obtains a high accuracy (1 + ɛ)-approximate solution. However, the situation is much more challenging for high-dimensional spaces: the best-known algorithm to obtain a constant approximation requires O (log n ) rounds. Recently Chen, Jayaram, Levi, and Waingarten [STOC ‘22] gave a O (log n ) approximation algorithm in a constant number of rounds based on embeddings into tree metrics. However, to date, no known algorithm achieves both a constant number of rounds and approximation. In this paper, we make strong progress on this front by giving a constant factor approximation in Õ (log log n ) rounds of the MPC model. In contrast to tree-embedding-based approaches, which necessarily must pay Ω(log n )-distortion, our algorithm is based on a new combination of graph-based distributed MST algorithms and geometric space partitions. Additionally, although the approximate MST we return can have a large depth, we show that it can be modified to obtain a O (log log n )-round constant factor approximation to the Euclidean Traveling Salesman Problem (TSP) in the MPC model. Previously, only a O (log n ) round was known for the problem. * The full version of the paper can be accessed at https: //arxiv. org/abs/2308. 00503.

NeurIPS Conference 2024 Conference Paper

Metric Transforms and Low Rank Representations of Kernels for Fast Attention

Timothy Chu
Josh Alman
Gary Miller
Shyam Narayanan
Mark Sellke
Zhao Song

We introduce a new linear-algebraic tool based on group representation theory, and use it to address three key problems in machine learning. 1. Past researchers have proposed fast attention algorithms for LLMs by approximating or replace softmax attention with other functions, such as low-degree polynomials. The key property of these functions is that, when applied entry-wise to the matrix $QK^{\top}$, the result is a low rank matrix when $Q$ and $K$ are $n \times d$ matrices and $n \gg d$. This suggests a natural question: what are all functions $f$ with this property? If other $f$ exist and are quickly computable, they can be used in place of softmax for fast subquadratic attention algorithms. It was previously known that low-degree polynomials have this property. We prove that low-degree polynomials are the only piecewise continuous functions with this property. This suggests that the low-rank fast attention only works for functions approximable by polynomials. Our work gives a converse to the polynomial method in algorithm design. 2. We prove the first full classification of all positive definite kernels that are functions of Manhattan or $\ell_1$ distance. Our work generalizes an existing theorem at the heart of all kernel methods in machine learning: the classification of all positive definite kernels that are functions of Euclidean distance. 3. The key problem in metric transforms, a mathematical theory used in geometry and machine learning, asks what functions transform pairwise distances in semi-metric space $M$ to semi-metric space $N$ for specified $M$ and $N$. We provide the first full classification of functions that transform Manhattan distances to Manhattan distances. Our work generalizes the foundational work of Schoenberg, which fully classifies functions that transform Euclidean to Euclidean distances. We additionally prove results about stable-rank preserving functions that are potentially useful in algorithmic design, and more. Our core new tool is called the representation theory of the hyperrectangle.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Sample-Efficient Private Learning of Mixtures of Gaussians

Hassan Ashtiani
Mahbod Majid
Shyam Narayanan

We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly $kd^2 + k^{1. 5} d^{1. 75} + k^2 d$ samples suffice to learn a mixture of $k$ arbitrary $d$-dimensional Gaussians up to low total variation distance, with differential privacy. Our work improves over the previous best result (which required roughly $k^2 d^4$ samples) and is provably optimal when $d$ is much larger than $k^2$. Moreover, we give the first optimal bound for privately learning mixtures of $k$ univariate (i. e. , $1$-dimensional) Gaussians. Importantly, we show that the sample complexity for learning mixtures of univariate Gaussians is linear in the number of components $k$, whereas the previous best sample complexity was quadratic in $k$. Our algorithms utilize various techniques, including the inverse sensitivity mechanism, sample compression for distributions, and methods for bounding volumes of sumsets.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Statistical-Computational Trade-offs for Density Estimation

Anders Aamand
Alexandr Andoni
Justin Y. Chen
Piotr Indyk
Shyam Narayanan
Sandeep Silwal
Haike Xu

We study the density estimation problem defined as follows: given $k$ distributions $p_1, \ldots, p_k$ over a discrete domain $[n]$, as well as a collection of samples chosen from a "query" distribution $q$ over $[n]$, output $p_i$ that is "close" to $q$. Recently Aamand et al. gave the first and only known result that achieves sublinear bounds in both the sampling complexity and the query time while preserving polynomial data structure space. However, their improvement over linear samples and time is only by subpolynomial factors. Our main result is a lower bound showing that, for a broad class of data structures, their bounds cannot be significantly improved. In particular, if an algorithm uses $O(n/\log^c k)$ samples for some constant $c>0$ and polynomial space, then the query time of the data structure must be at least $k^{1-O(1)/\log \log k}$, i. e. , close to linear in the number of distributions $k$. This is a novel statistical-computational trade-off for density estimation, demonstrating that any data structure must use close to a linear number of samples or take close to linear query time. The lower bound holds even in the realizable case where $q=p_i$ for some $i$, and when the distributions are flat (specifically, all distributions are uniform over half of the domain $[n]$). We also give a simple data structure for our lower bound instance with asymptotically matching upper bounds. Experiments show that the data structure is quite efficient in practice.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

$k$-Means Clustering with Distance-Based Privacy

Alessandro Epasto
Vahab Mirrokni
Shyam Narayanan
Peilin Zhong

In this paper, we initiate the study of Euclidean clustering with Distance-based privacy. Distance-based privacy is motivated by the fact that it is often only needed to protect the privacy of exact, rather than approximate, locations. We provide constant-approximate algorithms for $k$-means and $k$-median clustering, with additive error depending only on the attacker's precision bound $\rho$, rather than the radius $\Lambda$ of the space. In addition, we empirically demonstrate that our algorithm performs significantly better than previous differentially private clustering algorithms, as well as naive distance-based private clustering baselines.

ICML Conference 2023 Conference Paper

Data Structures for Density Estimation

Anders Aamand
Alexandr Andoni
Justin Y. Chen
Piotr Indyk
Shyam Narayanan
Sandeep Silwal

We study statistical/computational tradeoffs for the following density estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete domain of size $n$, and sampling access to a distribution $p$, identify $v_i$ that is "close" to $p$. Our main result is the first data structure that, given a sublinear (in $n$) number of samples from $p$, identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. (2018) that reports $v_i$ in time linear in $k$. The experimental evaluation of the latter algorithm shows that it achieves a significant reduction in the number of operations needed to achieve a given accuracy compared to prior work.

SODA Conference 2023 Conference Paper

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

Justin Y. Chen
Badih Ghazi
Ravi Kumar 0001
Pasin Manurangsi
Shyam Narayanan
Jelani Nelson
Yinzhan Xu

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 Õ ( n 2/3 /ε) in the ε-DP case and an algorithm with additive error 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 Ω ( n 1/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 in the ε-DP case and roughly in the (ε, δ)-DP case. Previously, it was only known how to obtain Õ ( n 2/3 /ε 1/3 ) additive error in the ε-DP case and 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 Õ( n 1/2+ O (1/ k ) /ε) in the ε-DP case and Õ ( n 1/3+O(1/ k ) /ε) in the (ε, δ)-DP case.

NeurIPS Conference 2023 Conference Paper

Differentially Private Approximate Near Neighbor Counting in High Dimensions

Alexandr Andoni
Piotr Indyk
Sepideh Mahabadi
Shyam Narayanan

Range counting (e. g. , counting the number of data points falling into a given query ball) under differential privacy has been studied extensively. However, the current algorithms for this problem are subject to the following dichotomy. One class of algorithms suffers from an additive error that is a fixed polynomial in the number of points. Another class of algorithms allows for polylogarithmic additive error, but the error grows exponentially in the dimension. To achieve the latter, the problem is relaxed to allow a “fuzzy” definition of the range boundary, e. g. , a count of the points in a ball of radius $r$ might also include points in a ball of radius $cr$ for some $c>1$. In this paper we present an efficient algorithm that offers a sweet spot between these two classes. The algorithm has an additive error that is an arbitrary small power of the data set size, depending on how fuzzy the range boundary is, as well as a small ($1+o(1)$) multiplicative error. Crucially, the amount of noise added has no dependence on the dimension. Our algorithm introduces a variant of Locality-Sensitive Hashing, utilizing it in a novel manner.

FOCS Conference 2023 Conference Paper

Krylov Methods are (nearly) Optimal for Low-Rank Approximation

Ainesh Bakshi
Shyam Narayanan

We consider the problem of rank-1 low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: \begin{equation*}\min _{\|u\|_{2}=1}\left\|A\left(I-u u^{\top}\right)\right\|_{\mathcal{S}_{p}}\end{equation*}where $\|M\|_{\mathcal{S}_{p}}$ denotes the $\ell_{p}$ norm of the singular values of M. Given $\varepsilon\gt 0$, our goal is to output a unit vector v such that \begin{equation*}\left\|A\left(I-v v^{\top}\right)\right\|_{\mathcal{S}_{p}} \leqslant\left(1+\varepsilon\right) \min _{\|u\|_{2}=1}\left\|A\left(I-u u^{\top}\right)\right\|_{\mathcal{S}_{p}}\end{equation*}Our main result shows that Krylov methods (nearly) achieve the information-theoretically optimal 1 number of matrix-vector products for Spectral $(p=\infty)$, Frobenius $(p=2)$ and Nuclear $(p=1)$ LRA. In particular, for Spectral LRA, we show that any algorithm requires $\Omega\left(\log (n) / \varepsilon^{1 / 2}\right)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods [40]. Our lower bound addresses Open Question 1 in [59], providing evidence for the lack of progress on algorithms for Spectral LRA and resolves Open Question 1. 2 in [5]. Next, we show that for any fixed constant p, i. e. $1 \leqslant p=O(1)$, there is an upper bound of $O\left(\log (1 / \varepsilon) / \varepsilon^{1 / 3}\right)$ matrix-vector products, implying that the complexity does not grow as a function of input size. This improves the $O\left(\log (n / \varepsilon) / \varepsilon^{1 / 3}\right)$ bound recently obtained in [5], and matches their $\Omega\left(1 / \varepsilon^{1 / 3}\right)$ lower bound, to a $\log (1 / \varepsilon)$ factor. 1 For Spectral LRA, the upper and lower bounds match up to a fixed universal constant. For Frobenius and Nuclear LRA, they match up to a $\log (1 / \varepsilon)$ factor.

FOCS Conference 2023 Conference Paper

Query lower bounds for log-concave sampling

Sinho Chewi
Jaume de Dios Pont
Jerry Li 0001
Chen Lu 0002
Shyam Narayanan

Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving $\lt$bold$\gt$lower bounds$\lt$/bold$\gt$ for this task has remained elusive, with lower bounds previously known only in dimension one. In this work, we establish the following query lower bounds: (1) sampling from strongly log-concave and log-smooth distributions in dimension $d \geq 2$ requires $\Omega(\log \kappa)$ queries, which is sharp in any constant dimension, and (2) sampling from Gaussians in dimension d (hence also from general logconcave and log-smooth distributions in dimension d) requires $\widetilde{\Omega}(\min (\sqrt{\kappa} \log d, d))$ queries, which is nearly sharp for the class of Gaussians. Here $\kappa$ denotes the condition number of the target distribution. Our proofs rely upon (1) a multiscale construction inspired by work on the Kakeya conjecture in geometric measure theory, and (2) a novel reduction that demonstrates that block Krylov algorithms are optimal for this problem, as well as connections to lower bound techniques based on Wishart matrices developed in the matrix-vector query literature.

STOC Conference 2023 Conference Paper

Robustness Implies Privacy in Statistical Estimation

Samuel B. Hopkins 0001
Gautam Kamath 0001
Mahbod Majid
Shyam Narayanan

We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.

FOCS Conference 2023 Conference Paper

The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination

Clément L. Canonne
Samuel B. Hopkins 0001
Jerry Li 0001
Allen Liu
Shyam Narayanan

We consider the question of Gaussian mean testing, a fundamental task in high-dimensional distribution testing and signal processing, subject to adversarial corruptions of the samples. We focus on the relative power of different adversaries, and show that, in contrast to the common wisdom in robust statistics, there exists a strict separation between adaptive adversaries (strong contamination) and oblivious ones (weak contamination) for this task. Specifically, we resolve both the information-theoretic and computational landscapes for robust mean testing. In the exponential-time setting, we establish the tight sample complexity of testing $\mathcal{N}(0, I)$ against $\mathcal{N}(\alpha v, I)$, where $\|v\|_{2}=1$, with an $\varepsilon$-fraction of adversarial corruptions, to be $\tilde{\Theta}\left(\max \left(\frac{\sqrt{d}}{\alpha^{2}}, \frac{d \varepsilon^{3}}{\alpha^{4}}, \min \left(\frac{d^{2 / 3} \varepsilon^{2 / 3}}{\alpha^{8 / 3}}, \frac{d \varepsilon}{\alpha^{2}}\right)\right)\right)$ while the complexity against adaptive adversaries is $\tilde{\Theta}\left(\max \left(\frac{\sqrt{d}}{\alpha^{2}}, \frac{d \varepsilon^{2}}{\alpha^{4}}\right)\right)$ which is strictly worse for a large range of vanishing $\varepsilon, \alpha$. To the best of our knowledge, ours is the first separation in sample complexity between the strong and weak contamination models. In the polynomial-time setting, we close a gap in the literature by providing a polynomial-time algorithm against adaptive adversaries achieving the above sample complexity $\tilde{\Theta}\left(\max \left(\sqrt{d} / \alpha^{2}, d \varepsilon^{2} / \alpha^{4}\right)\right)$, and a low-degree lower bound (which complements an existing reduction from planted clique) suggesting that all efficient algorithms require this many samples, even in the oblivious-adversary setting.

SODA Conference 2022 Conference Paper

Almost Tight Approximation Algorithms for Explainable Clustering

Hossein Esfandiari
Vahab Mirrokni
Shyam Narayanan

Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal of accuracy and interpretability by humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al. [11]. Specifically, we focus on the k -means and k -median problems and provide nearly tight upper and lower bounds. First, we provide an O (log k log log k )-approximation algorithm for explainable k -median, improving on the best known algorithm of O ( k ) [11] and nearly matching the known Ω(log k ) lower bound [11]. In addition, in low-dimensional spaces d ≪ log k, we show that our algorithm also provides an O ( d log 2 d )-approximate solution for explainable k -median. This improves over the best known bound of O(d log k ) for low dimensions [19], and is a constant for constant dimensional spaces. To complement this, we show a nearly matching Ω( d ) lower bound. Next, we study the k -means problem in this context and provide an O ( k log k )-approximation algorithm for explainable k -means, improving over the O ( k 2 ) bound of Dasgupta et al. and the O(dk log k ) bound of [19]. To complement this we provide an almost tight Ω( k ) lower bound, improving over the Ω(log k ) lower bound of Dasgupta et al. Given an approximate solution to the classic k -means and k -median, our algorithm for k -median runs in time O ( kd log 2 k ) and our algorithm for k -means runs in time O(k 2 d ).

NeurIPS Conference 2022 Conference Paper

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks

Anders Aamand
Justin Chen
Piotr Indyk
Shyam Narayanan
Ronitt Rubinfeld
Nicholas Schiefer
Sandeep Silwal
Tal Wagner

Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph test. In particular, they show that the WL test can be simulated by GNNs. However, those simulations involve neural networks for the “combine” function of size polynomial or even exponential in the number of graph nodes $n$, as well as feature vectors of length linear in $n$. We present an improved simulation of the WL test on GNNs with {\em exponentially} lower complexity. In particular, the neural network implementing the combine function in each node has only $\mathrm{polylog}(n)$ parameters, and the feature vectors exchanged by the nodes of GNN consists of only $O(\log n)$ bits. We also give logarithmic lower bounds for the feature vector length and the size of the neural networks, showing the (near)-optimality of our construction.

SODA Conference 2022 Conference Paper

Frequency Estimation with One-Sided Error

Piotr Indyk
Shyam Narayanan
David P. Woodruff

Frequency estimation, also known as the Point Query problem, is one of the most fundamental problems in streaming algorithms. Given a stream S of elements from some universe U = {1 … n }, the goal is to compute, in a single pass, a short “sketch” of S so that for any element i ∊ U, one can estimate the number x i of times i occurs in S based on the sketch alone. Two state of the art solutions to this problems are Count-Min and Count-Sketch algorithms. They are based on linear sketches, which means that the data elements can be deleted as well as inserted and sketches for two different streams can be combined via addition. However, the guarantees offered by Count-Min and Count-Sketch are incomparable. The frequency estimator x produced by Count-Min sketch, using O (1/ ∊ ·log n ) dimensions, guarantees that with high probability, and holds deterministically. Also, Count-Min works under the assumption that x ≥ 0. On the other hand, Count-Sketch, using O (1/ ∊ 2 · log n ) dimensions, guarantees that with high probability. A natural question is whether it is possible to design the “best of both worlds” sketching method, with error guarantees depending on the ℓ 2 norm and space comparable to Count-Sketch, but (like Count-Min) also has the no-underestimation property. Our main set of results shows that the answer to the above question is negative. We show this in two incomparable computational models: linear sketching and streaming algorithms. Specifically, we show that: Any linear sketch satisfying the ℓ p norm error guarantee with probability at least 2/3 and having the no-underestimation property must be of dimension of at least Ω( n 1–1/ p / ∊ ), even if the sketched vectors are non-negative. This bound is tight, as we also give a linear sketch of dimension O ( n 1–1/ p / ∊ ) satisfying these properties. Any streaming algorithm satisfying the ℓ p norm error guarantee with probability at least 2/3 and having the no-underestimation property must use at least Ω(n 1–1/ p / ∊ ) bits. This holds even for algorithms that only allow insertions and make any constant number of passes over the stream. This bound is tight up to a logarithmic factor. We also study the complementary problem, where the sketch is required to not over -estimate, i. e. , should hold always. We show that any linear sketch satisfying this property and having the ℓ p error guarantee with probability at least 2/3 must be of dimension at least Ω ( n 1–1/ p / ∊ ). We also show that this bound is tight up to polylogarithmic factors, by providing an appropriate linear sketch.

STOC Conference 2022 Conference Paper

Improved approximations for Euclidean k -means and k -median, via nested quasi-independent sets

Vincent Cohen-Addad
Hossein Esfandiari
Vahab Mirrokni
Shyam Narayanan

Motivated by data analysis and machine learning applications, we consider the popular high-dimensional Euclidean k -median and k -means problems. We propose a new primal-dual algorithm, inspired by the classic algorithm of Jain and Vazirani and the recent algorithm of Ahmadian, Norouzi-Fard, Svensson, and Ward. Our algorithm achieves an approximation ratio of 2.406 and 5.912 for Euclidean k -median and k -means, respectively, improving upon the 2.633 approximation ratio of Ahmadian et al. and the 6.1291 approximation ratio of Grandoni, Ostrovsky, Rabani, Schulman, and Venkat.

NeurIPS Conference 2022 Conference Paper

Near-Optimal Private and Scalable $k$-Clustering

Vincent Cohen-Addad
Alessandro Epasto
Vahab Mirrokni
Shyam Narayanan
Peilin Zhong

We study the differentially private (DP) $k$-means and $k$-median clustering problems of $n$ points in $d$-dimensional Euclidean space in the massively parallel computation (MPC) model. We provide two near-optimal algorithms where the near-optimality is in three aspects: they both achieve (1). $O(1)$ parallel computation rounds, (2). near-linear in $n$ and polynomial in $k$ total computational work (i. e. , near-linear running time when $n$ is a sufficient polynomial in $k$), (3). $O(1)$ relative approximation and $\text{poly}(k, d)$ additive error. Note that $\Omega(1)$ relative approximation is provably necessary even for any polynomial-time non-private algorithm, and $\Omega(k)$ additive error is a provable lower bound for any polynomial-time DP $k$-means/median algorithm. Our two algorithms provide a tradeoff between the relative approximation and the additive error: the first has $O(1)$ relative approximation and $\sim (k^{2. 5} + k^{1. 01} \sqrt{d})$ additive error, and the second one achieves $(1+\gamma)$ relative approximation to the optimal non-private algorithm for an arbitrary small constant $\gamma>0$ and with $\text{poly}(k, d)$ additive error for a larger polynomial dependence on $k$ and $d$. To achieve our result, we develop a general framework which partitions the data and reduces the DP clustering problem for the entire dataset to the DP clustering problem for each part. To control the blow-up of the additive error introduced by each part, we develop a novel charging argument which might be of independent interest.

ICML Conference 2022 Conference Paper

Tight and Robust Private Mean Estimation with Few Users

Shyam Narayanan
Vahab Mirrokni
Hossein Esfandiari

In this work, we study high-dimensional mean estimation under user-level differential privacy, and design an $(\varepsilon, \delta)$-differentially private mechanism using as few users as possible. In particular, we provide a nearly optimal trade-off between the number of users and the number of samples per user required for private mean estimation, even when the number of users is as low as $O(\frac{1}{\varepsilon}\log\frac{1}{\delta})$. Interestingly, this bound on the number of users is independent of the dimension (though the number of samples per user is allowed to depend polynomially on the dimension), unlike the previous work that requires the number of users to depend polynomially on the dimension. This resolves a problem first proposed by Amin et al. (2019). Moreover, our mechanism is robust against corruptions in up to $49%$ of the users. Finally, our results also apply to optimal algorithms for privately learning discrete distributions with few users, answering a question of Liu et al. (2020), and a broader range of problems such as stochastic convex optimization and a variant of stochastic gradient descent via a reduction to differentially private mean estimation.

ICLR Conference 2022 Conference Paper

Triangle and Four Cycle Counting with Predictions in Graph Streams

Justin Y. Chen
Talya Eden
Piotr Indyk
Honghao Lin
Shyam Narayanan
Ronitt Rubinfeld
Sandeep Silwal
Tal Wagner

We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, Hsu et al. (2019) and Jiang et al. (2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior “classical” algorithms that did not use oracles. In this paper, we explore the power of a “heavy edge” oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on “classical” streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.

SODA Conference 2021 Conference Paper

Improved Algorithms for Population Recovery from the Deletion Channel

Shyam Narayanan

The population recovery problem asks one to recover an unknown distribution over n -bit strings given access to independent noisy samples of strings drawn from the distribution. Recently, Ban et al. [BCF + 19] studied the problem where the noise is induced through the deletion channel. This problem generalizes the famous trace reconstruction problem, where one wishes to learn a single string under the deletion channel. Ban et al. showed how to learn ℓ -sparse distributions over strings using exp ( n 1/2 · (log n ) O ( ℓ ) ) samples. In this work, we learn the distribution using only exp ( Õ ( n 1/3 ) · ℓ 2 ) samples, by developing a higher-moment analog of the algorithms of [DOS17a, NP17], which solve trace reconstruction in exp ( Õ ( n 1/3 )) samples. We also give the first algorithm with a runtime subexponential in n, solving population recovery in exp ( Õ ( n 1/3 ) · ℓ 3 ) samples and time. Notably, our dependence on n nearly matches the upper bound of [DOS17a, NP17] when ℓ = O (1), and we reduce the dependence on ℓ from doubly to singly exponential. Therefore, we are able to learn large mixtures of strings: while Ban et al. 's algorithm can only learn a mixture of O (log n/ log log n ) strings with a subexponential number of samples, we are able to learn a mixture of n o (1) strings in exp ( n 1/3+ o (1) ) samples and time.

ICLR Conference 2021 Conference Paper

Learning-based Support Estimation in Sublinear Time

Talya Eden
Piotr Indyk
Shyam Narayanan
Ronitt Rubinfeld
Sandeep Silwal
Tal Wagner

We consider the problem of estimating the number of distinct elements in a large data set (or, equivalently, the support size of the distribution induced by the data set) from a random sample of its elements. The problem occurs in many applications, including biology, genomics, computer systems and linguistics. A line of research spanning the last decade resulted in algorithms that estimate the support up to $ \pm \varepsilon n$ from a sample of size $O(\log^2(1/\varepsilon) \cdot n/\log n)$, where $n$ is the data set size. Unfortunately, this bound is known to be tight, limiting further improvements to the complexity of this problem. In this paper we consider estimation algorithms augmented with a machine-learning-based predictor that, given any element, returns an estimation of its frequency. We show that if the predictor is correct up to a constant approximation factor, then the sample complexity can be reduced significantly, to $$ \ \log (1/\varepsilon) \cdot n^{1-\Theta(1/\log(1/\varepsilon))}. $$ We evaluate the proposed algorithms on a collection of data sets, using the neural-network based estimators from {Hsu et al, ICLR'19} as predictors. Our experiments demonstrate substantial (up to 3x) improvements in the estimation accuracy compared to the state of the art algorithm.

SODA Conference 2021 Conference Paper

On Tolerant Distribution Testing in the Conditional Sampling Model

Shyam Narayanan

Recently, there has been significant work studying distribution testing under the Conditional Sampling model. In this model, a query specifies a subset S of the domain, and the output received is a sample drawn from the distribution conditioned on being in S. In this paper, we improve query complexity bounds for several classic distribution testing problems in this model. First, we prove that tolerant uniformity testing in the conditional sampling model can be solved using Õ ( ∊ –2 ) queries, which is optimal and improves upon the Õ ( ∊ –20 )-query algorithm of Canonne et al. [CRS15]. This bound even holds under a restricted version of the conditional sampling model called the Pair Conditional Sampling model. Next, we prove that tolerant identity testing in the conditional sampling model can be solved in Õ ( ∊ –4 ) queries, which is the first known bound independent of the support size of the distribution for this problem. Next, we use our algorithm for tolerant uniformity testing to get an Õ ( ∊ –4 )-query algorithm for monotonicity testing in the conditional sampling model, improving on the Õ ( ∊ –22 )-query algorithm of Canonne [Can15]. Finally, we study (non-tolerant) identity testing under the pair conditional sampling model, and provide a tight bound of for the query complexity, where the domain of the distribution has size N. This improves upon both the known upper and lower bounds in [CRS15].

ICML Conference 2021 Conference Paper

Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering

Shyam Narayanan
Sandeep Silwal
Piotr Indyk
Or Zamir

Random dimensionality reduction is a versatile tool for speeding up algorithms for high-dimensional problems. We study its application to two clustering problems: the facility location problem, and the single-linkage hierarchical clustering problem, which is equivalent to computing the minimum spanning tree. We show that if we project the input pointset $X$ onto a random $d = O(d_X)$-dimensional subspace (where $d_X$ is the doubling dimension of $X$), then the optimum facility location cost in the projected space approximates the original cost up to a constant factor. We show an analogous statement for minimum spanning tree, but with the dimension $d$ having an extra $\log \log n$ term and the approximation factor being arbitrarily close to $1$. Furthermore, we extend these results to approximating {\em solutions} instead of just their {\em costs}. Lastly, we provide experimental results to validate the quality of solutions and the speedup due to the dimensionality reduction. Unlike several previous papers studying this approach in the context of $k$-means and $k$-medians, our dimension bound does not depend on the number of clusters but only on the intrinsic dimensionality of $X$.

FOCS Conference 2021 Conference Paper

Stochastic and Worst-Case Generalized Sorting Revisited

William Kuszmaul
Shyam Narayanan

The generalized sorting problem is a restricted version of standard comparison sorting where we wish to sort $n$ elements but only a subset of pairs are allowed to be compared. Formally, there is some known graph $G=(V, E)$ on the $n$ elements $v_{1, \ldots, v_{n}}$, and the goal is to determine the true order of the elements using as few comparisons as possible, where all comparisons ( $v_{i, v_{j}}$ ) must be edges in $E$. We are promised that if the true ordering is $x_{1 < x_{2} < \cdots < x_{n}}$ for $\{x_{i\}}$ an unknown permutation of the vertices $\{v_{i\}}$, then $(x_{i, x_{i+1})\in E}$ for all $i$: this Hamiltonian path ensures that sorting is actually possible. In this work, we improve the bounds for generalized sorting on both random graphs and worst-case graphs. For Erdős-Renyi random graphs $G(n, p)$ (with the promised Hamiltonian path added to ensure sorting is possible), we provide an algorithm for generalized sorting with an expected $O(n\ \text{lg}(np))$ comparisons, which we prove to be optimal for query complexity. This strongly improves over the best known algorithm of Huang, Kannan, and Khanna (FOCS 2011), which uses $\tilde{O(\min(n\sqrt{np}, \ n/p^{2}))}$ comparisons. For arbitrary graphs $G$ with $n$ vertices and $m$ edges (again with the promised Hamiltonian path), we provide an algorithm for generalized sorting with $\tilde{O(\sqrt{mn})}$ comparisons. This improves over the best known algorithm of Huang et al. , which uses $\min(m, \tilde{O}(n^{3/2}))$ comparisons.

STOC Conference 2019 Conference Paper

Optimal terminal dimensionality reduction in Euclidean space

Shyam Narayanan
Jelani Nelson

Let ε∈(0,1) and X ⊂ d be arbitrary with | X | having size n >1. The Johnson-Lindenstrauss lemma states there exists f : X → m with m = O (ε −2 log n ) such that ∀ x ∈ X ∀ y ∈ X , || x − y || 2 ≤ || f ( x )− f ( y )|| 2 ≤ (1+ε)|| x − y || 2 . We show that a strictly stronger version of this statement holds, answering one of the main open questions posed by Mahabadi et al. in STOC 2018: “∀ y ∈ X ” in the above statement may be replaced with “∀ y ∈ d ”, so that f not only preserves distances within X , but also distances to X from the rest of space. Previously this stronger version was only known with the worse bound m = O (ε −4 log n ). Our proof is via a tighter analysis of (a specific instantiation of) the embedding recipe of Mahabadi et al.