11 papers
Phantoms and Disclosures: A Statistical Framework for Auditing Privacy in Synthetic Data
Kareem Amin, Rudrajit Das, Alessandro Epasto +4
The rapid adoption of generative AI and Large Language Models (LLMs) has spurred interest in synthetic data as a privacy-preserving alternative to sensitive real-world datasets. Ho…
Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
Alessandro Epasto, Xin Lyu, Pasin Manurangsi
We study the computational cost of differential privacy in terms of memory efficiency. While the trade-off between accuracy and differential privacy is well-understood, the inheren…
Differentially Private Synthetic Data Release for Topics API Outputs
Travis Dick, Alessandro Epasto, Adel Javanmard +5
The analysis of the privacy properties of Privacy-Preserving Ads APIs is an area of research that has received strong interest from academics, industry, and regulators. Despite thi…
Private Training & Data Generation by Clustering Embeddings
Felix Zhou, Samson Zhou, Vahab Mirrokni +2
Deep neural networks often use large, high-quality datasets to achieve high performance on many machine learning tasks. When training involves potentially sensitive data, this proc…
Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model
Rachel Cummings, Alessandro Epasto, Jieming Mao +3
The turnstile continual release model of differential privacy captures scenarios where a privacy-preserving real-time analysis is sought for a dataset evolving through additions an…
Self-Boost via Optimal Retraining: An Analysis via Approximate Message Passing
Adel Javanmard, Rudrajit Das, Alessandro Epasto +1
Retraining a model using its own predictions together with the original, potentially noisy labels is a well-known strategy for improving the model performance. While prior works ha…
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures
Alina Ene, Alessandro Epasto, Vahab Mirrokni +4
In the maximum coverage problem we are given subsets from a universe , and the goal is to output subsets such that their union covers the largest possible number of di…
Sublinear Space Graph Algorithms in the Continual Release Model
Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee +1
The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of edge updates where new private solut…
Retraining with Predicted Hard Labels Provably Increases Model Accuracy
Rudrajit Das, Inderjit S. Dhillon, Alessandro Epasto +5
The performance of a model trained with noisy labels is often improved by simply \textit{retraining} the model with its \textit{own predicted hard labels} (i.e., 1/0 labels). Yet,…
Measuring Re-identification Risk
CJ Carey, Travis Dick, Alessandro Epasto +8
Compact user representations (such as embeddings) form the backbone of personalization services. In this work, we present a new theoretical framework to measure re-identification r…
On a Model for Integrated Information
Alessandro Epasto, Enrico Nardelli
In this paper we give a thorough presentation of a model proposed by Tononi et al. for modeling \emph{integrated information}, i.e. how much information is generated in a system tr…