Search Results

Classical streaming algorithms operate under the (not always reasonable) assumption that the input stream is fixed in advance. Recently, there is a growing interest in designing robust streaming algorithms that provide provable guarantees even ...

In the current digital world, large organizations (sometimes referred to as tech giants) provide service to extremely large numbers of users. The service provider is often interested in computing various data analyses over the private data of its ...

Private everlasting prediction (PEP), recently introduced by Naor et al. [2023], is a model for differentially private learning in which the learner never publicly releases a hypothesis. Instead, it provides black-box access to a "prediction oracle" that ...

In this work we revisit an interactive variant of joint differential privacy, recently introduced by Naor et al. [2023], and generalize it towards handling online processes in which existing privacy definitions seem too restrictive. We study basic ...

A private learner is trained on a sample of labeled points and generates a hypothesis that can be used for predicting the labels of newly sampled points while protecting the privacy of the training set [Kasiviswannathan et al., FOCS 2008]. Past research ...

In adaptive data analysis, a mechanism gets n i.i.d. samples from an unknown distribution Ɗ, and is required to provide accurate estimations to a sequence of adaptively chosen statistical queries with respect to Ɗ. Hardt and Ullman [2014] and Steinke and ...

We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard (single) shuffle model, the privacy ...

The problem of learning threshold functions is a fundamental one in machine learning. Classical learning theory implies sample complexity of O(ξ⁻¹ log(1/β)) (for generalization error ξ with confidence 1−β). The private version of the problem, however, ...

We study the space complexity of the two related fields of differential privacy and adaptive data analysis. Specifically,

1. Under standard cryptographic assumptions, we show that there exists a problem P that requires exponentially more space to be ...

CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of ℓ₂-heavy hitters (keys i where v_i² > ŝ‖v‖²₂) and approximate inner products. When the inputs are not adaptive (do not ...

A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary. We establish a connection between adversarial robustness of streaming algorithms ...

Given an input that undergoes a sequence of updates, a dynamic algorithm maintains a valid solution to some predefined problem at any point in time; the goal is to design an algorithm in which computing a solution to the updated input is done more ...

We present efficient differentially private algorithms for learning unions of polygons in the plane (which are not necessarily convex). Our algorithms are $(\alpha,\beta)$--probably approximately correct and $(\varepsilon,\delta)$--differentially private ...

We revisit the fundamental problem of learning Axis-Aligned-Rectangles over a finite grid X^d ⊆ ℝ^d with differential privacy. Existing results show that the sample complexity of this problem is at most min $\min\left\{ d{\cdot}\log|X| \;,\; d^{1.5}{\cdot}\...

We give an (ε, δ)-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model with a distribution-dependent regret of $O\left(\left(\sum_{a:\Delta_a>0}\frac{\log T}{\Delta_a}\right)+\frac{k\sqrt{\log\frac{1}{\delta}}\...

Streaming algorithms are algorithms for processing large data streams, using only a limited amount of memory. Classical streaming algorithms typically work under the assumption that the input stream is chosen independently from the internal state ...

Adaptivity is an important feature of data analysis---the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all ...

We design a new algorithm for the Euclidean k-means problem that operates in the local model of differential privacy. Unlike in the non-private literature, differentially private algorithms for the k-means objective incur both additive and multiplicative ...

A private learner is an algorithm that given a sample of labeled individual examples outputs a generalizing hypothesis while preserving the privacy of each individual. In 2008, Kasiviswanathan et al. (FOCS 2008) gave a generic construction of ...

We present a differentially private learner for halfspaces over a finite grid G in ℝ^d with sample complexity ≈d^2.5 · 2^{log* |G|} which improves the state-of-the-art result of [Beimel et al., COLT 2019] by a d² factor. The building block for our learner is ...