3 citations · 13 across the 15 of their papers we have counts for
18 papers
Near Exact Privacy Amplification for Matrix Mechanisms
Christopher A. Choquette-Choo, Arun Ganesh, Saminul Haque +2
We study the problem of computing the privacy parameters for DP machine learning when using privacy amplification via random batching and noise correlated across rounds via a corre…
The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD
Thomas Steinke, Milad Nasr, Arun Ganesh +7
We propose a simple heuristic privacy analysis of noisy clipped stochastic gradient descent (DP-SGD) in the setting where only the last iterate is released and the intermediate ite…
Optimal Rates for -Smooth DP-SCO with a Single Epoch and Large Batches
Christopher A. Choquette-Choo, Arun Ganesh, Abhradeep Thakurta
In this paper we revisit the DP stochastic convex optimization (SCO) problem. For convex smooth losses, it is well-known that the canonical DP-SGD (stochastic gradient descent) ach…
Privacy Amplification for Matrix Mechanisms
Christopher A. Choquette-Choo, Arun Ganesh, Thomas Steinke +1
Privacy amplification exploits randomness in data selection to provide tighter differential privacy (DP) guarantees. This analysis is key to DP-SGD's success in machine learning, b…
Correlated Noise Provably Beats Independent Noise for Differentially Private Learning
Christopher A. Choquette-Choo, Krishnamurthy Dvijotham, Krishna Pillutla +3
Differentially private learning algorithms inject noise into the learning process. While the most common private learning algorithm, DP-SGD, adds independent Gaussian noise in each…
(Amplified) Banded Matrix Factorization: A unified approach to private training
Christopher A. Choquette-Choo, Arun Ganesh, Ryan McKenna +4
Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications in…
Faster Differentially Private Convex Optimization via Second-Order Methods
Arun Ganesh, Mahdi Haghifam, Thomas Steinke +1
Differentially private (stochastic) gradient descent is the workhorse of DP private machine learning in both the convex and non-convex settings. Without privacy constraints, second…
Private (Stochastic) Non-Convex Optimization Revisited: Second-Order Stationary Points and Excess Risks
Arun Ganesh, Daogao Liu, Sewoong Oh +1
We consider the problem of minimizing a non-convex objective while preserving the privacy of the examples in the training data. Building upon the previous variance-reduced algorith…
Why Is Public Pretraining Necessary for Private Model Training?
Arun Ganesh, Mahdi Haghifam, Milad Nasr +5
In the privacy-utility tradeoff of a model trained on benchmark language and vision tasks, remarkable improvements have been widely reported with the use of pretraining on publicly…
Differentially Private Sampling from Rashomon Sets, and the Universality of Langevin Diffusion for Convex Optimization
Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay
In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for…
Public Data-Assisted Mirror Descent for Private Model Training
Ehsan Amid, Arun Ganesh, Rajiv Mathews +6
In this paper, we revisit the problem of using in-distribution public data to improve the privacy/utility trade-offs for differentially private (DP) model training. (Here, public d…
Universal Algorithms for Clustering Problems
Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi
This paper presents universal algorithms for clustering problems, including the widely studied -median, -means, and -center objectives. The input is a metric space contain…
Privately Answering Counting Queries with Generalized Gaussian Mechanisms
Arun Ganesh, Jiazheng Zhao
We consider the problem of answering counting (i.e. sensitivity-1) queries about a database with -differential privacy. We give a mechanism such that if the true answer…
Faster Differentially Private Samplers via Rényi Divergence Analysis of Discretized Langevin MCMC
Arun Ganesh, Kunal Talwar
Various differentially private algorithms instantiate the exponential mechanism, and require sampling from the distribution for a suitable function . When the domain…
Near-Linear Time Edit Distance for Indel Channels
Arun Ganesh, Aaron Sy
We consider the following model for sampling pairs of strings: is a uniformly random bitstring of length , and is the bitstring arrived at by applying substitutions,…
Robust Algorithms for TSP and Steiner Tree
Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi
Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the e…
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh, Qiuyi Zhang
We consider the phylogenetic tree reconstruction problem with insertions and deletions (indels). Phylogenetic algorithms proceed under a model where sequences evolve down the model…
Online Service with Delay
Yossi Azar, Arun Ganesh, Rong Ge +1
In this paper, we introduce the online service with delay problem. In this problem, there are points in a metric space that issue service requests over time, and a server that…