Badih Ghazi
I am a Research Scientist in the Algorithms & Optimization Team at Google. Here's a link to my personal webpage
Research Areas
Authored Publications
Sort By
Preview abstract
We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth of the query family’s incidence graph. Our algorithms attain optimal error rates across all regimes and are realized by two different approaches: the first is based on linear programming (LP) and the FPT of the separation problem for the LP dual; the second is based on a subsampled private multiplicative weights method, where we obtain FPT for sampling from Gibbs distributions. Both approaches are unified by a dynamic programming framework over a tree decomposition.
View details
Preview abstract
In this work, we prove computational lower bounds against differentially private (DP) coreset. Specifically, assuming the existence of one-way functions, we show that no polynomial-time $(\epsilon, 1/n^{\omega(1)})$-DP algorithm can compute $(\alpha, \beta)$-coreset for $k$-means in the $\ell_\infty$ metric for some constant $\alpha > 1$. For the Euclidean metric, we show a similar result but only for $\alpha = 1 + \Theta\left(\frac{1}{d^2}\right)$ where $d$ is the dimension.
View details
Online Differentially Private Clustering: Private to Non-Private Reduction
Vadym Doroshenko
Pritish Kamath
Alexander Knop
Ethan Leeman
Adam Sealfon
NeurIPS (2026)
Preview abstract
We study differentially private k-mean/median clustering in the online streaming setting where a point arrive at each time step and we need to output a set of k centers that optimize the k-mean/median objective of all the points so far. We give a generic transformation that turns the sensitive stream into a differentially private stream, which is a semi-coreset of the original stream and allows us to run any (non-private) online clustering algorithm as a post-processing step. Our algorithm is efficient in terms of errors, space and running time compared to existing algorithms (Epasto et al., 2023; Dupr{\'{e}} la Tour, 2024). Furthermore, our reduction allows us to inherit properties of the non-private clustering, such as consistency (Lattanzi and Vassilvitski, 2017), which was not satisfied by previous DP algorithms.
View details
VaultGemma
Lynn Chua
Prem Eruvbetine
Chiyuan Zhang
Thomas Mesnard
Borja De Balle Pigem
Daogao Liu
Amer Sinha
Pritish Kamath
Yangsibo Huang
Christopher A. Choquette-Choo
George Kaissis
Tris Warkentin
Armand Joulin
Andreas Terzis
Da Yu
Ryan McKenna
Ruibo Liu
arxiv (2025)
Preview abstract
In this work, we present VaultGemma 1B, a model based on the Gemma family of models fully trained with differential privacy. VaultGemma 1B is 1 billion parameter pretrained model based on the Gemma 2 series of models and uses the same dataset for training. We will be releasing a tech report and the weights of this model.
View details
Preview abstract
The conventional approach in differential privacy (DP) literature formulates the privacy-utility tradeoff with a "privacy-first" perspective: for a predetermined level of privacy, a certain utility is achievable. However, practitioners often operate under a "utility-first" paradigm, prioritizing a desired level of utility and then determining the corresponding privacy cost.
Wu et al. [2019] initiated a formal study of this ``utility-first'' perspective by introducing ex-post DP. They demonstrated that by adding correlated Laplace noise and progressively reducing it on demand, a sequence of increasingly accurate estimates of a private parameter can be generated, with the privacy cost attributed only to the least noisy iterate released. This led to a Laplace mechanism variant that achieves a specified utility with minimal privacy loss. However, their work, and similar findings by Whitehouse et al. [2023], are primarily limited to simple mechanisms based on Laplace or Gaussian noise.
In this paper, we significantly generalize these results. In particular, we extend the findings of Wu et al. [2019] and Liu and Talwar [2019] to support any sequence of private estimators, incurring at most a doubling of the original privacy budget. Furthermore, we demonstrate that hyperparameter tuning for these estimators, including the selection of an optimal privacy budget, can be performed without additional privacy cost. Finally, we extend our results to ex-post R'{e}nyi DP, further broadening the applicability of utility-first privacy mechanisms.
View details
Preview abstract
User-level differentially private stochastic convex optimization (DP-SCO) has garnered significant attention due to the paramount importance in safeguarding user privacy in large-scale machine learning applications. Current methods, such as those based on Differentially Private Stochastic Gradient Descent (DP-SGD), often struggle with high noise accumulation and suboptimal utility due to the need to privatize every intermediate iterate. In this work, we introduce a novel linear-time algorithm that leverages robust statistics, specifically the geometric median and trimmed mean, to overcome these challenges. Our approach uniquely bounds the sensitivity of all intermediate iterates of SGD with gradient estimation based on robust statistics, thereby significantly reducing the gradient estimation noise and enhancing the privacy-utility trade-off. By sidestepping the repeated privatization required by previous methods, our algorithm not only achieves an improved theoretical privacy-utility balance but also maintains computational efficiency. This work sets the stage for more robust and efficient privacy-preserving techniques in machine learning, with implications for future research and application in the field.
View details
On the Differential Privacy and Interactivity of Privacy Sandbox Reports
Charlie Harrison
Pritish Kamath
Alexander Knop
Ethan Leeman
Vikas Sahu
PETS (2025)
Preview abstract
The Privacy Sandbox initiative from Google includes APIs for enabling privacy-preserving advertising functionalities as part of the effort to limit third-party cookies. In particular, the Private Aggregation API (PAA) and the Attribution Reporting API (ARA) can be used for ad measurement while providing different guardrails for safeguarding user privacy, including a framework for satisfying differential privacy (DP). In this work, we provide an abstract model for analyzing the privacy of these APIs and show that they satisfy a formal DP guarantee under certain assumptions. Our analysis handles the case where both the queries and database can change interactively based on previous responses from the API.
View details
Balls-and-Bins Sampling for DP-SGD
Lynn Chua
Charlie Harrison
Pritish Kamath
Ethan Leeman
Amer Sinha
Chiyuan Zhang
AISTATS (2025)
Preview abstract
We introduce the Balls-and-Bins sampling for differentially private (DP) optimization methods such as DP-SGD. While it has been common practice to use some form of shuffling in DP-SGD implementations, privacy accounting algorithms have typically assumed that Poisson subsampling is used instead. Recent work by Chua et al. (2024) however pointed out that shuffling based DP-SGD can have a much larger privacy cost in practical regime of parameters. We show that the Balls-and-Bins sampling achieves the “best-of-both” samplers, namely, the implementation of Balls-and-Bins sampling is similar to that of Shuffling and models trained with Balls-and-Bins based DP-SGD achieve utility comparable to those trained with Shuffle based DP-SGD at the same noise multiplier, and yet, Balls-and-Bins sampling enjoys similar-or-better privacy amplification as compared to Poisson subsampling.
View details
Preview abstract
We study differential privacy (DP) in a multi-party setting where each party only trusts a (known) subset of the other parties with its data. Specifically, given a trust graph where vertices correspond to parties and neighbors are mutually trusting, we give a DP algorithm for aggregation with a much better privacy-utility trade-off than in the well-studied local model of DP (where each party trusts no other party). We further study a robust variant where each party trusts all but an unknown subset of at most t of its neighbors (where t is a given parameter), and give an algorithm for this setting. We complement our algorithms with lower bounds, and discuss implications of our work to other tasks in private learning and analytics.
View details
Crosslingual Capabilities and Knowledge Barriers in Multilingual Large Language Models
Lynn Chua
Yangsibo Huang
Pritish Kamath
Amer Sinha
Chulin Xie
Chiyuan Zhang
COLM (2025)
Preview abstract
Large language models (LLMs) are typically multilingual due to pretraining on diverse multilingual corpora. But can these models relate corresponding concepts across languages, i.e., be crosslingual? This study evaluates state-of-the-art LLMs on inherently crosslingual tasks. We observe that while these models show promising surface-level crosslingual abilities on machine translation and embedding space analyses, they struggle with deeper crosslingual knowledge transfer, revealing a crosslingual knowledge barrier in both general (MMLU benchmark) and domain-specific (Harry Potter quiz and TOFU benchmark) contexts. Since simple inference-time mitigation methods offer only limited improvement, we propose fine-tuning of LLMs on mixed-language data, which effectively reduces these gaps, even when using out-of-domain datasets like WikiText. Our findings suggest the need for explicit optimization to unlock the full crosslingual potential of LLMs. Our code is available at https://github.com/google-research/crosslingual-knowledge-barriers.
View details
