Ravi Kumar
Research Areas
Authored Publications
Sort By
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
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
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
Differentially Private Insights into AI Use
Daogao Liu
Pritish Kamath
Alexander Knop
Adam Sealfon
Da Yu
Chiyuan Zhang
Conference on Language Modeling (COLM) 2025 (2025)
Preview abstract
We introduce Urania, a novel framework for generating insights about LLM chatbot interactions with rigorous differential privacy (DP) guarantees. The framework employs a private clustering mechanism and innovative keyword extraction methods, including frequency-based, TF-IDF-based, and LLM-guided approaches. By leveraging DP tools such as clustering, partition selection, and histogram-based summarization, Urania provides end-to-end privacy protection. Our evaluation assesses lexical and semantic content preservation, pair similarity, and LLM-based metrics, benchmarking against a non-private method inspired by CLIO (Tamkin et al., 2024). Moreover, we develop a simple empirical privacy evaluation that demonstrates the enhanced robustness of our DP pipeline. The results show the framework’s ability to extract meaningful conversational insights while maintaining stringent user privacy, effectively balancing data utility with privacy preservation.
View details
Scaling Embedding Layers in Language Models
Da Yu
Yangsibo Huang
Pritish Kamath
Daogao Liu
Chiyuan Zhang
2025
PREM: Privately Answering Statistical Queries with Relative Error
Sushant Sachdeva
Cristóbal Guzmán
Alexander Knop
Pritish Kamath
COLT (2025)
Preview abstract
We introduce PREM (Private Relative Error Multiplicative weight update) a new (ε, δ)-DP mechanism for privately generating synthetic data that achieves a relative error guarantee for linear queries. Namely, for a domain X, a family F of queries f : X → {0, 1}, and ζ > 0, the mechanism on input dataset D ∈ X^n outputs a synthetic dataset D ̃ ∈ X^n such that all linear queries in F on D, namely sum_x∈D f(x) for f ∈ F, are within a 1 ± ζ multiplicative factor of the corresponding value on D ̃ up to an additive error that is polynomial in log |F|, log |X |, log n, log(1/δ), 1/ε, and 1/ζ. This is in contrast to the standard additive-error only setting considered in the literature, which is known to require polynomial error in at least one of n, |F|, or |X |. We complement the algorithm with nearly matching lower bounds.
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
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
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
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
