Publications (34)
Learning with User-Level Privacy
Daniel Levy, Ziteng Sun, Kareem Amin +4
We propose and analyze algorithms to solve a range of learning tasks under user-level differential privacy constraints. Rather than guaranteeing only the privacy of individual samp…
Private federated discovery of out-of-vocabulary words for Gboard
Ziteng Sun, Peter Kairouz, Haicheng Sun +2
The vocabulary of language models in Gboard, Google's keyboard application, plays a crucial role for improving user experience. One way to improve the vocabulary is to discover fre…
Inference under Information Constraints III: Local Privacy Constraints
Jayadev Acharya, Clément L. Canonne, Cody Freitag +2
We study goodness-of-fit and independence testing of discrete distributions in a setting where samples are distributed across multiple users. The users wish to preserve the privacy…
Estimating Sparse Discrete Distributions Under Local Privacy and Communication Constraints
Jayadev Acharya, Peter Kairouz, Yuhan Liu +1
We consider the problem of estimating sparse discrete distributions under local differential privacy (LDP) and communication constraints. We characterize the sample complexity for…
Multi-Mixer Models: Flexible Sequence Modeling with Shared Representations
Kevin Y. Li, Asher Trockman, Ananda Theertha Suresh +1
Softmax attention is the cornerstone of modern large language models, but its memory scales linearly and compute quadratically with sequence length. Linear recurrent models, such a…
Subset-Based Instance Optimality in Private Estimation
Travis Dick, Alex Kulesza, Ziteng Sun +1
We propose a new definition of instance optimality for differentially private estimation algorithms. Our definition requires an optimal algorithm to compete, simultaneously for eve…
Interactive Inference under Information Constraints
Jayadev Acharya, Clément L. Canonne, Yuhan Liu +2
We study the role of interactivity in distributed statistical inference under information constraints, e.g., communication constraints and local differential privacy. We focus on t…
Robust Testing and Estimation under Manipulation Attacks
Jayadev Acharya, Ziteng Sun, Huanyu Zhang
We study robust testing and estimation of discrete distributions in the strong contamination model. We consider both the "centralized setting" and the "distributed setting with inf…
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters
Jayadev Acharya, Ziteng Sun
We consider the problems of distribution estimation and heavy hitter (frequency) estimation under privacy and communication constraints. While these constraints have been studied s…
Block Verification Accelerates Speculative Decoding
Ziteng Sun, Uri Mendlovic, Yaniv Leviathan +4
Speculative decoding is an effective method for lossless acceleration of large language models during inference. It uses a fast model to draft a block of tokens which are then veri…
Unified lower bounds for interactive high-dimensional estimation under information constraints
Jayadev Acharya, Clément L. Canonne, Ziteng Sun +1
We consider distributed parameter estimation using interactive protocols subject to local information constraints such as bandwidth limitations, local differential privacy, and res…
INSPECTRE: Privately Estimating the Unseen
Jayadev Acharya, Gautam Kamath, Ziteng Sun +1
We develop differentially private methods for estimating various distributional properties. Given a sample from a discrete distribution , some functional , and accuracy and p…
Differentially Private Assouad, Fano, and Le Cam
Jayadev Acharya, Ziteng Sun, Huanyu Zhang
Le Cam's method, Fano's inequality, and Assouad's lemma are three widely used techniques to prove lower bounds for statistical estimation tasks. We propose their analogues under ce…
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
Jayadev Acharya, Clément L. Canonne, Yanjun Han +2
We study goodness-of-fit of discrete distributions in the distributed setting, where samples are divided between multiple users who can only release a limited amount of information…
Advances and Open Problems in Federated Learning
Peter Kairouz, H. Brendan McMahan, Brendan Avent +56
Federated learning (FL) is a machine learning setting where many clients (e.g. mobile devices or whole organizations) collaboratively train a model under the orchestration of a cen…
Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
Lynn Chua, Badih Ghazi, Ravi Kumar +3
We study the problem of Stochastic Convex Optimization (SCO) under the constraint of local Label Differential Privacy (L-LDP). In this setting, the features are considered public,…
The importance of feature preprocessing for differentially private linear optimization
Ziteng Sun, Ananda Theertha Suresh, Aditya Krishna Menon
Training machine learning models with differential privacy (DP) has received increasing interest in recent years. One of the most popular algorithms for training differentially pri…
Asymptotics of Language Model Alignment
Joy Qiping Yang, Salman Salamatian, Ziteng Sun +2
Let denote a generative language model. Let denote a reward model that returns a scalar that captures the degree at which a draw from is preferred. The goal of language…
Concentration Bounds for Discrete Distribution Estimation in KL Divergence
Clément L. Canonne, Ziteng Sun, Ananda Theertha Suresh
We study the problem of discrete distribution estimation in KL divergence and provide concentration bounds for the Laplace estimator. We show that the deviation from mean scales as…
Can You Really Backdoor Federated Learning?
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh +1
The decentralized nature of federated learning makes detecting and defending against adversarial attacks a challenging task. This paper focuses on backdoor attacks in the federated…
InfAlign: Inference-aware language model alignment
Ananth Balashankar, Ziteng Sun, Jonathan Berant +9
Language model alignment is a critical step in training modern generative language models. Alignment targets to improve win rate of a sample from the aligned model against the base…
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
Jayadev Acharya, Ziteng Sun, Huanyu Zhang
We study the problem of estimating -ary distributions under -local differential privacy. samples are distributed across users who send privatized versions of th…
: Faster Test-Time Scaling through Speculative Drafts
Mert Cemri, Nived Rajaraman, Rishabh Tiwari +6
Scaling test-time compute has driven the recent advances in the reasoning capabilities of large language models (LLMs), typically by allocating additional computation for more thor…
CoDistill-GRPO: A Co-Distillation Recipe for Efficient Group Relative Policy Optimization
Soo Min Kwon, Ziteng Sun, Ananda Theertha Suresh +2
Group Relative Policy Optimization (GRPO) has emerged as a powerful algorithm for improving the reasoning capabilities of language models, but often fails to improve small models d…
Correlated quantization for distributed mean estimation and optimization
Ananda Theertha Suresh, Ziteng Sun, Jae Hun Ro +1
We study the problem of distributed mean estimation and optimization under communication constraints. We propose a correlated quantization protocol whose leading term in the error…
Estimating Entropy of Distributions in Constant Space
Jayadev Acharya, Sourbh Bhadane, Piotr Indyk +1
We consider the task of estimating the entropy of -ary distributions from samples in the streaming model, where space is limited. Our main contribution is an algorithm that requ…
CafeQ: Calibration-free Quantization via Learned Transformations and Adaptive Rounding
Ziteng Sun, Adrian Benton, Samuel Kushnir +4
Post-training quantization is an effective method for reducing the serving cost of large language models, where the standard approach is to use a round-to-nearest quantization leve…
Context-Aware Local Differential Privacy
Jayadev Acharya, Keith Bonawitz, Peter Kairouz +2
Local differential privacy (LDP) is a strong notion of privacy for individual users that often comes at the expense of a significant drop in utility. The classical definition of LD…
SpecTr: Fast Speculative Decoding via Optimal Transport
Ziteng Sun, Ananda Theertha Suresh, Jae Hun Ro +3
Autoregressive sampling from large language models has led to state-of-the-art results in several natural language tasks. However, autoregressive sampling generates tokens one at a…
Federated Heavy Hitter Recovery under Linear Sketching
Adria Gascon, Peter Kairouz, Ziteng Sun +1
Motivated by real-life deployments of multi-round federated analytics with secure aggregation, we investigate the fundamental communication-accuracy tradeoffs of the heavy hitter d…
Discrete Distribution Estimation under User-level Local Differential Privacy
Jayadev Acharya, Yuhan Liu, Ziteng Sun
We study discrete distribution estimation under user-level local differential privacy (LDP). In user-level -LDP, each user has samples and the privacy of all $…
LAPRAS : Learning-Augmented PRivate Answering for linear query Streams
Pranay Mundra, Adam Sealfon, Ziteng Sun +1
Modern database workloads are highly predictable: query streams are dominated by recurring jobs and templates, even when their arrival order is not known in advance. This motivates…
The Role of Interactivity in Structured Estimation
Jayadev Acharya, Clément L. Canonne, Ziteng Sun +1
We study high-dimensional sparse estimation under three natural constraints: communication constraints, local privacy constraints, and linear measurements (compressive sensing). Wi…
Differentially Private Testing of Identity and Closeness of Discrete Distributions
Jayadev Acharya, Ziteng Sun, Huanyu Zhang
We study the fundamental problems of identity testing (goodness of fit), and closeness testing (two sample test) of distributions over elements, under differential privacy. Whi…