74 citations · 172 across the 28 of their papers we have counts for
29 papers
Faster Rates for Private Adversarial Bandits
Hilal Asi, Vinod Raman, Kunal Talwar
We design new differentially private algorithms for the problems of adversarial bandits and bandits with expert advice. For adversarial bandits, we give a simple and efficient conv…
AdaBoN: Adaptive Best-of-N Alignment
Vinod Raman, Hilal Asi, Satyen Kale
Recent advances in test-time alignment methods, such as Best-of-N sampling, offer a simple and effective way to steer language models (LMs) toward preferred behaviors using reward…
On Privately Estimating a Single Parameter
Hilal Asi, John C. Duchi, Kunal Talwar
We investigate differentially private estimators for individual parameters within larger parametric models. While generic private estimators exist, the estimators we provide repose…
Tracking the Best Expert Privately
Aadirupa Saha, Vinod Raman, Hilal Asi
We design differentially private algorithms for the problem of prediction with expert advice under dynamic regret, also known as tracking the best expert. Our work addresses three…
PREAMBLE: Private and Efficient Aggregation via Block Sparse Vectors
Hilal Asi, Vitaly Feldman, Hannah Keller +2
We revisit the problem of secure aggregation of high-dimensional vectors in a two-server system such as Prio. These systems are typically used to aggregate vectors such as gradient…
Faster Algorithms for User-Level Private Stochastic Convex Optimization
Andrew Lowy, Daogao Liu, Hilal Asi
We study private stochastic convex optimization (SCO) under user-level differential privacy (DP) constraints. In this setting, there are users (e.g., cell phones), each possess…
Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
Hilal Asi, Daogao Liu, Kevin Tian
We study the problem of differentially private stochastic convex optimization (DP-SCO) with heavy-tailed gradients, where we assume a -moment bound on the Lipschitz…
Wally: Batched Private Nearest Neighbor Search at Scale
Hilal Asi, Fabian Boemer, Nicholas Genise +8
We present Wally, a batched private nearest-neighbor search protocol that uses differential privacy to break the linear computation barrier of fully-oblivious schemes. In Tiptoe, t…
Private Online Learning via Lazy Algorithms
Hilal Asi, Tomer Koren, Daogao Liu +1
We study the problem of private online learning, specifically, online prediction from experts (OPE) and online convex optimization (OCO). We propose a new transformation that trans…
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
Hilal Asi, Vitaly Feldman, Jelani Nelson +3
We study the problem of private vector mean estimation in the shuffle model of privacy where users each have a unit vector . We propose a new multi-mes…
DP-Dueling: Learning from Preference Feedback without Compromising User Privacy
Aadirupa Saha, Hilal Asi
We consider the well-studied dueling bandit problem, where a learner aims to identify near-optimal actions using pairwise comparisons, under the constraint of differential privacy.…
User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Rates
Hilal Asi, Daogao Liu
We study differentially private stochastic convex optimization (DP-SCO) under user-level privacy, where each user may hold multiple data items. Existing work for user-level DP-SCO…
Fast Optimal Locally Private Mean Estimation via Random Projections
Hilal Asi, Vitaly Feldman, Jelani Nelson +2
We study the problem of locally private mean estimation of high-dimensional vectors in the Euclidean ball. Existing algorithms for this problem either incur sub-optimal error or ha…
Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime
Hilal Asi, Vitaly Feldman, Tomer Koren +1
We consider online learning problems in the realizable setting, where there is a zero-loss solution, and propose new Differentially Private (DP) algorithms that obtain near-optimal…
From Robustness to Privacy and Back
Hilal Asi, Jonathan Ullman, Lydia Zakynthinou
We study the relationship between two desiderata of algorithms in statistical inference and machine learning: differential privacy and robustness to adversarial data corruptions. T…
Private optimization in the interpolation regime: faster rates and hardness results
Hilal Asi, Karan Chadha, Gary Cheng +1
In non-private stochastic convex optimization, stochastic gradient methods converge much faster on interpolation problems -- problems where there exists a solution that simultaneou…
Private Online Prediction from Experts: Separations and Faster Rates
Hilal Asi, Vitaly Feldman, Tomer Koren +1
Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algori…
How many labelers do you have? A closer look at gold-standard labels
Chen Cheng, Hilal Asi, John Duchi
The construction of most supervised learning datasets revolves around collecting multiple labels for each instance, then aggregating the labels to form a type of "true" label. We q…
Optimal Algorithms for Mean Estimation under Local Differential Privacy
Hilal Asi, Vitaly Feldman, Kunal Talwar
We study the problem of mean estimation of -bounded vectors under the constraint of local differential privacy. While the literature has a variety of algorithms that achiev…
Adapting to Function Difficulty and Growth Conditions in Private Optimization
Hilal Asi, Daniel Levy, John Duchi
We develop algorithms for private stochastic convex optimization that adapt to the hardness of the specific function we wish to optimize. While previous work provide worst-case bou…
Private Adaptive Gradient Methods for Convex Optimization
Hilal Asi, John Duchi, Alireza Fallah +2
We study adaptive methods for differentially private convex optimization, proposing and analyzing differentially private variants of a Stochastic Gradient Descent (SGD) algorithm w…
Stochastic Bias-Reduced Gradient Methods
Hilal Asi, Yair Carmon, Arun Jambulapati +2
We develop a new primitive for stochastic optimization: a low-bias, low-cost estimator of the minimizer of any Lipschitz strongly-convex function. In particular, we use a…
Private Stochastic Convex Optimization: Optimal Rates in Geometry
Hilal Asi, Vitaly Feldman, Tomer Koren +1
Stochastic convex optimization over an -bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differe…
Near Instance-Optimality in Differential Privacy
Hilal Asi, John C. Duchi
We develop two notions of instance optimality in differential privacy, inspired by classical statistical theory: one by defining a local minimax risk and the other by considering u…