Arrow Research search

Author name cluster

Edith Cohen

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.

35 papers
2 author rows

Possible papers

35

ICML Conference 2025 Conference Paper

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries

  • Edith Cohen
  • Mihir Singhal
  • Uri Stemmer

Cardinality sketches are compact data structures that efficiently estimate the number of distinct elements across multiple queries while minimizing storage, communication, and computational costs. However, recent research has shown that these sketches can fail under adaptively chosen queries, breaking down after approximately $\tilde{O}(k^2)$ queries, where $k$ is the sketch size. In this work, we overcome this quadratic barrier by designing robust estimators with fine-grained guarantees. Specifically, our constructions can handle an exponential number of adaptive queries, provided that each element participates in at most $\tilde{O}(k^2)$ queries. This effectively shifts the quadratic barrier from the total number of queries to the number of queries sharing the same element, which can be significantly smaller. Beyond cardinality sketches, our approach expands the toolkit for robust algorithm design.

Details

NeurIPS Conference 2025 Conference Paper

Scaling Embedding Layers in Language Models

  • Da Yu
  • Edith Cohen
  • Badih Ghazi
  • Yangsibo Huang
  • Pritish Kamath
  • Ravi Kumar
  • Daogao Liu
  • Chiyuan Zhang

We propose SCONE (**S**calable, **C**ontextualized, **O**ffloaded, **N**-gram **E**mbedding), a new method for extending input embedding layers to enhance language model performance. To avoid increased decoding costs, SCONE retains the original vocabulary while introducing embeddings for a set of frequent $n$-grams. These embeddings provide contextualized representation for each input token and are learned with a separate model during training. After training, embeddings are precomputed and stored in off-accelerator memory; during inference, querying them has minimal impact on latency due to the low complexity of embedding lookups. SCONE enables two new scaling strategies: increasing the number of $n$-gram embeddings and scaling the model used to learn them, both while maintaining fixed accelerator usage during inference (in terms of FLOPS and memory). We show that scaling both aspects enables a model with 1B accelerator-resident parameters to outperform a 1. 9B-parameter baseline across diverse corpora, while using only about half the FLOPS and accelerator memory during inference.

PDF Details

NeurIPS Conference 2025 Conference Paper

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation

  • Sara Ahmadian
  • Edith Cohen
  • Uri Stemmer

Dimensionality reduction via linear sketching is a powerful and widely used technique, but it is known to be vulnerable to adversarial inputs. We study the \emph{black-box adversarial setting}, where a fixed, hidden sketching matrix $A \in \mathbb{R}^{k \times n}$ maps high-dimensional vectors $\boldsymbol{v} \in \mathbb{R}^n$ to lower-dimensional sketches $A\boldsymbol{v} \in \mathbb{R}^k$, and an adversary can query the system to obtain approximate $\ell_2$-norm estimates that are computed from the sketch. We present a \emph{universal, nonadaptive attack} that, using $\tilde{O}(k^2)$ queries, either causes a failure in norm estimation or constructs an adversarial input on which the optimal estimator for the query distribution (used by the attack) fails. The attack is completely agnostic to the sketching matrix and to the estimator—it applies to \emph{any} linear sketch and \emph{any} query responder, including those that are randomized, adaptive, or tailored to the query distribution. Our lower bound construction tightly matches the known upper bounds of $\tilde{\Omega}(k^2)$, achieved by specialized estimators for Johnson–Lindenstrauss transforms and AMS sketches. Beyond sketching, our results uncover structural parallels to adversarial attacks in image classification, highlighting fundamental vulnerabilities of compressed representations.

PDF Details

NeurIPS Conference 2025 Conference Paper

Tight Bounds for Answering Adaptively Chosen Concentrated Queries

  • Emma Rapoport
  • Edith Cohen
  • Uri Stemmer

Most work on adaptive data analysis assumes that samples in the dataset are independent. When correlations are allowed, even the non-adaptive setting can become intractable, unless some structural constraints are imposed. To address this, Bassily and Freund [2016] introduced the elegant framework of *concentrated queries*, which requires the analyst to restrict itself to queries that are concentrated around their expected value. While this assumption makes the problem trivial in the non-adaptive setting, in the adaptive setting it remains quite challenging. In fact, all known algorithms in this framework support significantly fewer queries than in the independent case: At most $O(n)$ queries for a sample of size $n$, compared to $O(n^2)$ in the independent setting. In this work, we prove that this utility gap is inherent under the current formulation of the concentrated queries framework, assuming some natural conditions on the algorithm. Additionally, we present a simplified version of the best-known algorithms that match our impossibility result.

PDF Details

ICML Conference 2024 Conference Paper

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs

  • Sara Ahmadian
  • Edith Cohen

Cardinality sketches are popular data structures that enhance the efficiency of working with large data sets. The sketches are randomized representations of sets that are only of logarithmic size but can support set merges and approximate cardinality (i. e. , distinct count) queries. When queries are not adaptive, that is, they do not depend on preceding query responses, the design provides strong guarantees of correctly answering a number of queries exponential in the sketch size $k$. In this work, we investigate the performance of cardinality sketches in adaptive settings and unveil inherent vulnerabilities. We design an attack against the “standard” estimators that constructs an adversarial input by post-processing responses to a set of simple non-adaptive queries of size linear in the sketch size $k$. Empirically, our attack used only $4k$ queries with the widely used HyperLogLog (HLL++) Flajolet et al. , 2007; Heule et al. , 2013) sketch. The simple attack technique suggests it can be effective with post-processed natural workloads. Finally and importantly, we demonstrate that the vulnerability is inherent as any estimator applied to known sketch structures can be attacked using a number of queries that is quadratic in $k$, matching a generic upper bound.

Details

STOC Conference 2023 Conference Paper

Optimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization

  • Edith Cohen
  • Xin Lyu 0002
  • Jelani Nelson
  • Tamás Sarlós
  • Uri Stemmer

The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of O (ξ −1 log(1/β)) (for generalization error ξ with confidence 1−β). The private version of the problem, however, is more challenging and in particular, the sample complexity must depend on the size | X | of the domain. Progress on quantifying this dependence, via lower and upper bounds, was made in a line of works over the past decade. In this paper, we finally close the gap for approximate-DP and provide a nearly tight upper bound of O (log * | X |), which matches a lower bound by Alon et al (that applies even with improper learning) and improves over a prior upper bound of O ((log * | X |) 1.5 ) by Kaplan et al. We also provide matching upper and lower bounds of Θ(2 log * | X | ) for the additive error of private quasi-concave optimization (a related and more general problem). Our improvement is achieved via the novel Reorder-Slice-Compute paradigm for private data analysis which we believe will have further applications.

Details

NeurIPS Conference 2023 Conference Paper

The Target-Charging Technique for Privacy Analysis across Interactive Computations

  • Edith Cohen
  • Xin Lyu

We propose the \emph{Target Charging Technique} (TCT), a unified privacy analysis framework for interactive settings where a sensitive dataset is accessed multiple times using differentially private algorithms. Unlike traditional composition, where privacy guarantees deteriorate quickly with the number of accesses, TCT allows computations that don't hit a specified \emph{target}, often the vast majority, to be essentially free (while incurring instead a small overhead on those that do hit their targets). TCT generalizes tools such as the sparse vector technique and top-k selection from private candidates and extends their remarkable privacy enhancement benefits from noisy Lipschitz functions to general private algorithms.

PDF Details

AAAI Conference 2023 Conference Paper

Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs

  • Edith Cohen
  • Jelani Nelson
  • Tamas Sarlos
  • Uri Stemmer

CountSketch and Feature Hashing (the ``hashing trick'') are popular randomized dimensionality reduction methods that support recovery of l2 -heavy hitters and approximate inner products. When the inputs are not adaptive (do not depend on prior outputs), classic estimators applied to a sketch of size O(l / epsilon) are accurate for a number of queries that is exponential in l. When inputs are adaptive, however, an adversarial input can be constructed after O(l) queries with the classic estimator and the best known robust estimator only supports ~O(l^2) queries. In this work we show that this quadratic dependence is in a sense inherent: We design an attack that after O(l^2) queries produces an adversarial input vector whose sketch is highly biased. Our attack uses ``natural'' non-adaptive inputs (only the final adversarial input is chosen adaptively) and universally applies with any correct estimator, including one that is unknown to the attacker. In that, we expose inherent vulnerability of this fundamental method.

PDF Details DOI

ICML Conference 2022 Conference Paper

FriendlyCore: Practical Differentially Private Aggregation

  • Eliad Tsfadia
  • Edith Cohen
  • Haim Kaplan
  • Yishay Mansour
  • Uri Stemmer

Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or to the large number of data points that is required for accurate results. We propose a simple and practical tool $\mathsf{FriendlyCore}$ that takes a set of points ${\cal D}$ from an unrestricted (pseudo) metric space as input. When ${\cal D}$ has effective diameter $r$, $\mathsf{FriendlyCore}$ returns a “stable” subset ${\cal C} \subseteq {\cal D}$ that includes all points, except possibly few outliers, and is guaranteed to have diameter $r$. $\mathsf{FriendlyCore}$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy. Surprisingly, $\mathsf{FriendlyCore}$ is light-weight with no dependence on the dimension. We empirically demonstrate its advantages in boosting the accuracy of mean estimation and clustering tasks such as $k$-means and $k$-GMM, outperforming tailored methods.

Details

ICML Conference 2022 Conference Paper

On the Robustness of CountSketch to Adaptive Inputs

  • Edith Cohen
  • Xin Lyu 0002
  • Jelani Nelson
  • Tamás Sarlós
  • Moshe Shechner
  • Uri Stemmer

The last decade saw impressive progress towards understanding the performance of algorithms in adaptive settings, where subsequent inputs may depend on the output from prior inputs. Adaptive settings arise in processes with feedback or with adversarial attacks. Existing designs of robust algorithms are generic wrappers of non-robust counterparts and leave open the possibility of better tailored designs. The lowers bounds (attacks) are similarly worst-case and their significance to practical setting is unclear. Aiming to understand these questions, we study the robustness of \texttt{CountSketch}, a popular dimensionality reduction technique that maps vectors to a lower dimension using randomized linear measurements. The sketch supports recovering $\ell_2$-heavy hitters of a vector (entries with $v[i]^2 \geq \frac{1}{k}\|\boldsymbol{v}\|^2_2$). We show that the classic estimator is not robust, and can be attacked with a number of queries of the order of the sketch size. We propose a robust estimator (for a slightly modified sketch) that allows for quadratic number of queries in the sketch size, which is an improvement factor of $\sqrt{k}$ (for $k$ heavy hitters) over prior "blackbox" approaches.

Details

ICML Conference 2021 Conference Paper

Differentially-Private Clustering of Easy Instances

  • Edith Cohen
  • Haim Kaplan
  • Yishay Mansour
  • Uri Stemmer
  • Eliad Tsfadia

Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify k cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentrially private clustering algorithms when the the data is "easy, " e. g. , when there exists a significant separation between the clusters. For the easy instances we consider, we have a simple implementation based on utilizing non-private clustering algorithms, and combining them privately. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and k-means. We complement our theoretical algorithms with experiments of simulated data.

Details

ICML Conference 2020 Conference Paper

Composable Sketches for Functions of Frequencies: Beyond the Worst Case

  • Edith Cohen
  • Ofir Geri
  • Rasmus Pagh

Recently there has been increased interest in using machine learning techniques to improve classical algorithms. In this paper we study when it is possible to construct compact, composable sketches for weighted sampling and statistics estimation according to functions of data frequencies. Such structures are now central components of large-scale data analytics and machine learning pipelines. However, many common functions, such as thresholds and $p$th frequency moments with $p>2$, are known to require polynomial size sketches in the worst case. We explore performance beyond the worst case under two different types of assumptions. The first is having access to noisy \emph{advice} on item frequencies. This continues the line of work of Hsu et al. (ICLR 2019), who assume predictions are provided by a machine learning model. The second is providing guaranteed performance on a restricted class of input frequency distributions that are better aligned with what is observed in practice. This extends the work on heavy hitters under Zipfian distributions in a seminal paper of Charikar et al. (ICALP 2002). Surprisingly, we show analytically and empirically that "in practice" small polylogarithmic-size sketches provide accuracy for "hard" functions.

Details

NeurIPS Conference 2020 Conference Paper

WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement

  • Edith Cohen
  • Rasmus Pagh
  • David Woodruff

Weighted sampling is a fundamental tool in data analysis and machine learning pipelines. Samples are used for efficient estimation of statistics or as sparse representations of the data. When weight distributions are skewed, as is often the case in practice, without-replacement (WOR) sampling is much more effective than with-replacement (WR) sampling: It provides a broader representation and higher accuracy for the same number of samples. We design novel composable sketches for WOR {\em $\ell_p$ sampling}, weighted sampling of keys according to a power $p\in[0, 2]$ of their frequency (or for signed data, sum of updates). Our sketches have size that grows only linearly with sample size. Our design is simple and practical, despite intricate analysis, and based on off-the-shelf use of widely implemented heavy hitters sketches such as \texttt{CountSketch}. Our method is the first to provide WOR sampling in the important regime of $p>1$ and the first to handle signed updates for $p>0$.

PDF Details

NeurIPS Conference 2019 Conference Paper

Sampling Sketches for Concave Sublinear Functions of Frequencies

  • Edith Cohen
  • Ofir Geri

We consider massive distributed datasets that consist of elements modeled as key-value pairs and the task of computing statistics or aggregates where the contribution of each key is weighted by a function of its frequency (sum of values of its elements). This fundamental problem has a wealth of applications in data analytics and machine learning, in particular, with concave sublinear functions of the frequencies that mitigate the disproportionate effect of keys with high frequency. The family of concave sublinear functions includes low frequency moments ($p \leq 1$), capping, logarithms, and their compositions. A common approach is to sample keys, ideally, proportionally to their contributions and estimate statistics from the sample. A simple but costly way to do this is by aggregating the data to produce a table of keys and their frequencies, apply our function to the frequency values, and then apply a weighted sampling scheme. Our main contribution is the design of composable sampling sketches that can be tailored to any concave sublinear function of the frequencies. Our sketch structure size is very close to the desired sample size and our samples provide statistical guarantees on the estimation quality that are very close to that of an ideal sample of the same size computed over aggregated data. Finally, we demonstrate experimentally the simplicity and effectiveness of our methods.

PDF Details

ICML Conference 2019 Conference Paper

Self-similar Epochs: Value in arrangement

  • Eliav Buchnik
  • Edith Cohen
  • Avinatan Hassidim
  • Yossi Matias

Optimization of machine learning models is commonly performed through stochastic gradient updates on randomly ordered training examples. This practice means that each fraction of an epoch comprises an independent random sample of the training data that may not preserve informative structure present in the full data. We hypothesize that the training can be more effective with self-similar arrangements that potentially allow each epoch to provide benefits of multiple ones. We study this for “matrix factorization” – the common task of learning metric embeddings of entities such as queries, videos, or words from example pairwise associations. We construct arrangements that preserve the weighted Jaccard similarities of rows and columns and experimentally observe training acceleration of 3%-37% on synthetic and recommendation datasets. Principled arrangements of training examples emerge as a novel and potentially powerful enhancement to SGD that merits further exploration.

Details

AAAI Conference 2018 Conference Paper

Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS

  • Edith Cohen
  • Shiri Chechik
  • Haim Kaplan

Clustering of data points is a fundamental tool in data analysis. We consider points X in a relaxed metric space, where the triangle inequality holds within a constant factor. A clustering of X is a partition of X defined by a set of points Q (centroids), according to the closest centroid. The cost of clustering X by Q is V (Q) = x∈X dxQ. This formulation generalizes classic k-means clustering, which uses squared distances. Two basic tasks, parametrized by k ≥ 1, are cost estimation, which returns (approximate) V (Q) for queries Q such that |Q| = k and clustering, which returns an (approximate) minimizer of V (Q) of size |Q| = k. When the data set X is very large, we seek efficient constructions of small samples that can act as surrogates for performing these tasks. Existing constructions that provide quality guarantees, however, are either worst-case, and unable to benefit from structure of real data sets, or make explicit strong assumptions on the structure. We show here how to avoid both these pitfalls using adaptive designs. The core of our design are the novel one2all probabilities, computed for a set M of centroids and α ≥ 1: The clustering cost of each Q with cost V (Q) ≥ V (M)/α can be estimated well from a sample of size O(α|M| −2 ). For cost estimation, we apply one2all with a bicriteria approximate M, while adaptively balancing |M| and α to optimize sample size per quality. For clustering, we present a wrapper that adaptively applies a base clustering algorithm to a sample S, using the smallest sample that provides the desired statistical guarantees on quality. We demonstrate experimentally the huge gains of using our adaptive instead of worst-case methods.

PDF Details

TCS Journal 2005 Journal Article

Performance aspects of distributed caches using TTL-based consistency

  • Edith Cohen
  • Eran Halperin
  • Haim Kaplan

The web is the largest distributed database deploying time-to-live-based weak consistency. Each object has a lifetime-duration assigned to it by its origin server. A copy of the object fetched from its origin server is received with maximum time-to-live (TTL) that equals its lifetime duration. In contrast a copy obtained through a cache have shorter TTL since the age (elapsed time since fetched from the origin) is deducted from its lifetime duration. A request served by a cache constitutes a hit if the cache has a fresh copy of the object. Otherwise, the request is considered a miss and is propagated to another server. It is evident that the number of cache misses depends on the age of the copies the cache receives. Thus, a cache that sends requests to another cache would suffer more misses than a cache that sends requests directly to an authoritative server. In this paper, we model and analyze the effect of age on the performance of various cache configurations. We consider a low-level cache that fetches objects either from their origin servers or from other caches and analyze its miss-rate as function of its fetching policy. We distinguish between three basic fetching policies, namely, fetching always from the origin, fetching always from the same high-level cache, and fetching from a “random” high-level cache. We explore the relationships between these policies in terms of the miss-rate achieved by the low-level cache, both on worst-case sequences, and on sequences generated using particular probability distributions. Guided by web caching practice, we consider two variations of the basic policies. In the first variation the high-level cache uses pre-term refreshes to keep a copy with lower age. In the second variation the low-level cache uses extended lifetime duration. We analyze how these variations affect the miss-rates. Our theoretical results help to understand how age may affect the miss-rate, and imply guidelines for improving performance of web caches.

Details DOI

STOC Conference 2003 Conference Paper

Optimal oblivious routing in polynomial time

  • Yossi Azar
  • Edith Cohen
  • Amos Fiat
  • Haim Kaplan
  • Harald Räcke

A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial time. We give a polynomial time construction that guarantee's Racke's bounds, and more generally gives the true optimal ratio for any network.

Details

FOCS Conference 1997 Conference Paper

Learning Noisy Perceptrons by a Perceptron in Polynomial Time

  • Edith Cohen

Learning perceptrons (linear threshold functions) from labeled examples is an important problem in machine learning. We consider the problem where labels are subjected to random classification noise. The problem was known to be PAC learnable via a hypothesis that consists of a polynomial number of linear thresholds (due to A. Blum, A. Frieze, R. Kannan, and S. Vempala (1996)). The question of whether a hypothesis that is itself a perceptron (a single threshold function) can be found in polynomial time was open. We show that indeed, noisy perceptrons are PAC learnable with a hypothesis that is a perceptron.

Details

FOCS Conference 1994 Conference Paper

Estimating the Size of the Transitive Closure in Linear Time

  • Edith Cohen

Computing transitive closure and reachability information in directed graphs is a fundamental graph problem with many applications. The fastest known algorithms run in O(sm) time for computing all nodes reachable from each of 1/spl les/s/spl les/n source nodes, or, using fast matrix multiplication, in O(n/sup 2. 38/) time for computing the transitive closure, where n is the number of nodes and m the number of edges in the graph. In query optimization in database applications it is often the case that only estimates on the size of the transitive closure and on the number of nodes reachable from certain nodes are needed. We present an O(m) time randomized algorithm that estimates the number of nodes reachable from every node and the size of the transitive closure. We also obtain a O/spl tilde/(m) time algorithm for estimating sizes of neighborhoods in directed graphs with nonnegative weights, avoiding the O/spl tilde/(mn) time bound of explicitly computing these neighborhoods. Our size-estimation algorithms are much faster than performing the actual computations and improve significantly over previous estimation methods. >

Details

FOCS Conference 1993 Conference Paper

Fast algorithms for constructing t-spanners and paths with stretch t

  • Edith Cohen

The distance between two vertices in a weighted graph is the weight of a minimum-weight path between them. A path has stretch t if its weight is at most t times the distance between its end points. We consider a weighted undirected graph G=(V, E) and present algorithms that compute paths with stretch 2/spl les/t/spl les/log n. We present a O/spl tilde/((m+k)n/sup (2+/spl epsiv///t)) time randomized algorithm that finds paths between k specified pairs of vertices and a O/spl tilde/((m+ns)n/sup 2(1+log(n)/ /sup m+/spl epsiv/)/t/) deterministic algorithm that finds paths from s specified sources to all other vertices (for any fixed /spl epsiv/>0), where n=|V| and m=|E|. This improves significantly over the slower O/spl tilde/(min{k, n}m) exact shortest paths algorithms and a previous O/spl tilde/(mn/sup 64/t/+kn/sup 32/t/) time algorithm by Awerbuch et al. A t-spanner of a graph G is a set of weighted edges on the vertices of G such that distances in the spanner are not smaller and within a factor of t from the corresponding distances in G. Previous work was concerned with bounding the size and efficiently constructing t-spanners. We construct t-spanners of size O/spl tilde/(n/sup 1+(2+/spl epsiv///t)) in O/spl tilde/(mn/sup (2+/spl epsiv///t)) expected time (for any fixed /spl epsiv/>0), what constitutes a faster construction (by a factor of n/sup (3+2//t)) of sparser spanners than was previously attainable. We also provide efficient parallel constructions. Our algorithms are based on new structures called pairwise-covers and a novel approach to construct them efficiently. >

Details

FOCS Conference 1992 Conference Paper

Approximate Max Flow on Small Depth Networks

  • Edith Cohen

The author considers the maximum flow problem on directed acyclic networks with m edges and depth r (length of the longest s-t path). The main result is a new deterministic algorithm for solving the relaxed problem of computing an s-t flow of value at least (1- epsilon ) of the maximum flow. For instances where r and epsilon /sup -1/ are small (i. e. , O(polylog(m))), this algorithm is in NC and uses only O(m) processors, which is a significant improvement over existing parallel algorithms. As one consequence, he obtains an NC O(m) processor algorithm to find a bipartite matching of cardinality (1- epsilon ) of the maximum (for epsilon /sup -1/ = O(polylog(m))). The parallel bounds are based on a novel approach to the blocking flow problem that produces fractional valued flow augmentations even when capacities are integral. She shows that a fractional flow on any network with integral capacities can be rounded in polylogarithmic time to an integral flow of no smaller value using O(m) processors. Hence, within the same resource bounds, an integral flow can be obtained when desired. >

Details
v2026.09.13