Om Thakkar
Senior Research Scientist
Google
Mountain View, CA, USA
Email :
omthkkr "at" google.com
I am a Senior Research Scientist at Google, working in the team of
Françoise Beaufays. My research is in privacy-preserving data analysis, with a specific focus on differential privacy and its applications to machine learning, deep learning, and adaptive data analysis.
Before joining Google, I graduated with a Ph.D. in Computer Science from Boston University (BU) in 2019. I was very fortunate to be advised by
Dr. Adam Smith. At BU, I was a part of the
Security group, and the
Theoretical Computer Science group. I completed the first 3.5 years of my Ph.D. in the Department of Computer Science and Engineering at
the Pennsylvania State University, advised by Dr. Adam Smith. Before joining Penn State, I completed my B.Tech. in Information and Communication Technology from the Dhirubhai Ambani Institute, India in 2014.
- Our paper titled Practical and Private (Deep) Learning without Sampling or Shuffling has been accepted to appear at ICML 2021.
- Our paper titled Understanding Unintended Memorization in Federated Learning has been accepted to appear at PrivateNLP (NAACL 2021).
- Our paper titled Evading the Curse of Dimensionality in Unconstrained Private GLMs has been accepted to appear at AISTATS 2021.
- Three papers accepted to appear in PPML 2020 (Neurips 2020), with the work on Training Production Language Models without Memorizing User Data accepted for an oral presentation.
- Our paper titled Privacy Amplification via Random Check-Ins has been accepted to appear at NeurIPS 2020.
- Three papers accepted to appear in TPDP 2020 (CCS 2020), with the work on Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems accepted for an oral presentation.
- Our paper titled Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis has been accepted to appear in AISTATS 2020.
- I joined Google, in the team of Françoise Beaufays, on September 30, 2019.
- I successfully defended my dissertation titled Advances in Privacy-Preserving Machine Learning on August 1, 2019.
- My most recent resume (last updated in May, 2021) can be found here.
- A Method to Reveal Speaker Identity in Distributed ASR Training, and How to Counter It.
Trung Dang, Om Thakkar, Swaroop Ramaswamy, Rajiv Mathews, Peter Chin, and Françoise Beaufays. (In order of contribution)
- Training Production Language Models without Memorizing User Data.
Swaroop Ramaswamy*, Om Thakkar*, Rajiv Mathews, Galen Andrew, Brendan McMahan, and Françoise Beaufays. (In order of contribution)
*Equal contribution.
- Differentially Private Learning with Adaptive Clipping.
Galen Andrew, Om Thakkar, Swaroop Ramaswamy, and Brendan McMahan. (In order of contribution)
Papers available here may be subject to copyright, and are intended for personal, non-commercial use only.
Unless specifically indicated, all publications have authors listed in the alphabetical order of last names (as per the convention in theoretical computer science).
- Practical and Private (Deep) Learning without Sampling or Shuffling. Abstract▼
We consider training models with differential privacy (DP) using mini-batch gradients. The existing state-of-the-art, Differentially Private Stochastic Gradient Descent (DP-SGD), requires privacy amplification by sampling or shuffling to obtain the best privacy/accuracy/computation trade-offs. Unfortunately, the precise requirements on exact sampling and shuffling can be hard to obtain in important practical scenarios, particularly federated learning (FL). We design and analyze a DP variant of Follow-The-Regularized-Leader (DP-FTRL) that compares favorably (both theoretically and empirically) to amplified DP-SGD, while allowing for much more flexible data access patterns. DP-FTRL does not use any form of privacy amplification.
- Evading the Curse of Dimensionality in Unconstrained Private GLMs. Abstract▼
We revisit the well-studied problem of differentially private empirical risk minimization (ERM). We show that for unconstrained convex generalized linear models (GLMs), one can obtain an excess empirical risk of $\tilde O\left(\sqrt{\texttt{rank}}/\epsilon n\right)$, where $\texttt{rank}$ is the rank of the feature matrix in the GLM problem, $n$ is the number of data samples, and $\epsilon$ is the privacy parameter. This bound is attained via differentially private gradient descent (DP-GD). Furthermore, via the \emph{first lower bound for unconstrained private ERM}, we show that our upper bound is tight. In sharp contrast to the constrained ERM setting, there is no dependence on the dimensionality of the ambient model space ($p$). (Notice that $\texttt{rank}\leq \min\{n, p\}$.)
Besides, we obtain an analogous excess population risk bound which depends on $\texttt{rank}$ instead of $p$.
For the smooth non-convex GLM setting (i.e., where the objective function is non-convex but preserves the GLM structure), we further show that DP-GD attains a dimension-independent convergence of $\tilde O\left(\sqrt{\texttt{rank}}/\epsilon n\right)$ to a first-order-stationary-point of the underlying objective.
Finally, we show that for convex GLMs, a variant of DP-GD commonly used in practice (which involves clipping the individual gradients) also exhibits the same dimension-independent convergence to the minimum of a well-defined objective. To that end, we provide a structural lemma that characterizes the effect of clipping on the optimization profile of DP-GD.
- Privacy Amplification via Random Check-Ins. Abstract▼
Differentially Private Stochastic Gradient Descent (DP-SGD) forms a fundamental building block in many applications for learning over sensitive data. Two standard approaches, privacy amplification by subsampling, and privacy amplification by shuffling, permit adding lower noise in DP-SGD than via naïve schemes. A key assumption in both these approaches is that the elements in the data set can be uniformly sampled, or be uniformly permuted — constraints that may become prohibitive when the data is processed in a decentralized or distributed fashion. In this paper, we focus on conducting iterative methods like DP-SGD in the setting of federated learning (FL) wherein the data is distributed among many devices (clients). Our main contribution is the random check-in distributed protocol, which crucially relies only on randomized participation decisions made locally and independently by each client. It has privacy/accuracy trade-offs similar to privacy amplification by subsampling/shuffling. However, our method does not require server-initiated communication, or even knowledge of the population size. To our knowledge, this is the first privacy amplification tailored for a distributed learning framework, and it may have broader applicability beyond FL. Along the way, we improve the privacy guarantees of amplification by shuffling and show that, in practical regimes, this improvement allows for similar privacy and utility using data from an order of magnitude fewer users.
- Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis. Abstract▼
We design a general framework for answering adaptive statistical queries that focuses on providing explicit confidence intervals along with point estimates. Prior work in this area has either focused on providing tight confidence intervals for specific analyses, or providing general worst-case bounds for point estimates. Unfortunately, as we observe, these worst-case bounds are loose in many settings --- often not even beating simple baselines like sample splitting. Our main contribution is to design a framework for providing valid, instance-specific confidence intervals for point estimates that can be generated by heuristics. When paired with good heuristics, this method gives guarantees that are orders of magnitude better than the best worst-case bounds. We provide a Python library implementing our method.
- Advances in Privacy-Preserving Machine Learning.
Ph.D. Thesis, BU, September 2019. Supervisor: Dr. Adam Smith.
- Towards Practical Differentially Private Convex Optimization. Abstract▼
Building useful predictive models often involves learning from sensitive data. Training models with differential privacy can guarantee the privacy of such sensitive data. For convex optimization tasks, several differentially private algorithms are known, but none has yet been deployed in practice.
In this work, we make two major contributions towards practical differentially private convex optimization. First, we present Approximate Minima Perturbation, a novel algorithm that can leverage any off-the-shelf optimizer. We show that it can be employed without any hyperparameter tuning, thus making it an attractive technique for practical deployment. Second, we perform an extensive empirical evaluation of the state-of-the-art algorithms for differentially private convex optimization, on a range of publicly available benchmark datasets, and real-world datasets obtained through an industrial collaboration. We release open-source implementations of all the differentially private convex optimization algorithms considered, and benchmarks on as many as nine public datasets, four of which are high-dimensional.
- Model-Agnostic Private Learning. Abstract▼
We design differentially private learning algorithms that are agnostic to the learning model assuming access to a limited amount of unlabeled public data. First, we provide a new differentially private algorithm for answering a sequence of $m$ online classification queries (given by a sequence of $m$ unlabeled public feature vectors) based on a private training set. Our algorithm follows the paradigm of subsample-and-aggregate, in which any generic non-private learner is trained on disjoint subsets of the private training set, and then for each classification query, the votes of the resulting classifiers ensemble are aggregated in a differentially private fashion. Our private aggregation is based on a novel combination of the distance-to-instability framework, and the sparse-vector technique. We show that our algorithm makes a conservative use of the privacy budget.
In particular, if the underlying non-private learner yields a classification error of at most $\alpha\in (0, 1)$, then our construction answers more queries, by at least a factor of $1/\alpha$ in some cases, than what is implied by a straightforward application of the advanced composition theorem for differential privacy. Next, we apply the knowledge transfer technique to construct a private learner that outputs a classifier, which can be used to answer an unlimited number of queries. In the (agnostic) PAC model, we analyze our construction and prove upper bounds on the sample complexity for both the realizable and the non-realizable cases. Similar to non-private sample complexity, our bounds are completely characterized by the VC dimension of the concept class.
- Differentially Private Matrix Completion Revisited. Abstract▼
We provide the first provably joint differentially private algorithm with formal utility guarantees for the problem of user-level privacy-preserving collaborative filtering. Our algorithm is based on the Frank-Wolfe method, and it consistently estimates the underlying preference matrix as long as the number of users $m$ is $\omega(n^{5/4})$, where $n$ is the number of items, and each user provides her preference for at least $\sqrt{n}$ randomly selected items. Along the way, we provide an optimal differentially private algorithm for singular vector computation, based on the celebrated Oja's method, that provides significant savings in terms of space and time while operating on sparse matrices. We also empirically evaluate our algorithm on a suite of datasets, and show that it provides nearly same accuracy as the state-of-the-art non-private algorithm, and outperforms the state-of-the-art private algorithm by as much as 30%.
- Max-Information, Differential Privacy, and Post-Selection Hypothesis Testing. Abstract▼
In this paper, we initiate a principled study of how the
generalization properties of approximate differential privacy can be
used to perform adaptive hypothesis testing, while giving
statistically valid $p$-value corrections. We do this by observing
that the guarantees of algorithms with bounded approximate
max-information are sufficient to correct the $p$-values of
adaptively chosen hypotheses, and then by proving that algorithms that
satisfy $(\epsilon,\delta)$-differential privacy have bounded
approximate max-information when their inputs are drawn from a product
distribution.
This substantially extends the existing connection between differential privacy and max-information, which previously was only known to hold for (pure) $(\epsilon,0)$-differential privacy. It also extends our understanding of max-information as a partially unifying measure controlling the generalization properties of adaptive data analyses. We also show a lower bound, proving that (despite the strong composition properties of max-information), when data is drawn from a product distribution, $(\epsilon,\delta)$-differentially private algorithms can come first in a composition with other algorithms satisfying max-information bounds, but not necessarily second if the composition is required to itself satisfy a nontrivial max-information bound. This, in particular, implies that the connection between $(\epsilon,\delta)$-differential privacy and max-information holds only for inputs drawn from particular distributions, unlike the connection between $(\epsilon,0)$-differential privacy and max-information.
- Training Production Language Models without Memorizing User Data.
Swaroop Ramaswamy*, Om Thakkar*, Rajiv Mathews, Galen Andrew, Brendan McMahan, and Françoise Beaufays. (In order of contribution)
In the Privacy Preserving Machine Learning (PPML) 2020 workshop (NeurIPS 2020). Accepted for an oral presentation. *Equal contribution.
- Privacy Amplification via Random Check-Ins.
Borja Balle, Peter Kairouz, Brendan McMahan, Om Thakkar, and Abhradeep Thakurta.
In the Theory and Practice of Differential Privacy (TPDP) 2020 workshop (CCS 2020).
- Understanding Unintended Memorization in Federated Learning.
Abstract▼
Recent works have shown that generative sequence models (e.g., next word prediction models) have a tendency to memorize rare or unique sequences in the training data. Since useful models are often trained on sensitive data, it is critical to identify and mitigate such unintended memorization. Federated Learning (FL) has emerged as a novel framework for large-scale distributed learning tasks. It differs in many aspects from the well-studied central learning setting where all the data is stored at the central server, and minibatch stochastic gradient descent is used to conduct training. This work is motivated by our observation that next word prediction models trained under FL exhibited remarkably less propensity to such memorization compared to the central learning setting. Thus, we initiate a formal study to understand the effect of different components of FL on unintended memorization in trained models.
Our results show that several differing components of FL play an important role in reducing unintended memorization. To our surprise, we discover that the clustering of data according to users---which happens by design in FL---has the most significant effect in reducing such memorization. Moreover, using the method of Federated Averaging with larger effective minibatch sizes for training causes a further reduction. We also demonstrate that training in FL with a user-level differential privacy guarantee results in models that can provide high utility while being resilient to memorizing out-of-distribution phrases with thousands of insertions across over a hundred users in the training set.
- Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems.
Shuang Song, Om Thakkar, and Abhradeep Thakurta.
In the Theory and Practice of Differential Privacy (TPDP) 2020 workshop, and the Privacy Preserving Machine Learning (PPML) 2020 workshop (NeurIPS 2020). Accepted for an oral presentation at TPDP 2020 (CCS 2020).
- Visiting Graduate Student in the Data Privacy program at the Simons Institute, Berkeley during Spring'19.
- Research Intern at Google Brain, Mountain View, CA during Summer 2018. Mentor: Úlfar Erlingsson.
- Visiting Student Researcher at University of California, Berkeley, CA during Fall 2017. Host: Dr. Dawn Song.
- Research Intern at Google, Seattle, WA during Summer 2017. Mentors: Brendan McMahan, and Martin Pelikan.
- Research Intern in the CoreOS: Machine Learning team at Apple, Cupertino, CA during Summer 2016.
- Towards Training Provably Private Models via Federated Learning in Practice @ the Workshop on Federated Learning and Analytics 2020 (Google) on July 29, 2020.
- Privacy Amplification via Random Check-Ins @ the Ph.D. Intern Research Conference 2020 (Google) on July 22, 2020.
- Towards Practical Differentially Private Convex Optimization
- Model-Agnostic Private Learning,
- Building Tools for Controlling Overfitting in Adaptive Data Analysis, @ the Adaptive Data Analysis workshop, Simons Institute, Berkeley on July 7, 2018.
- Differentially Private Matrix Completion Revisited
- A brief introduction to Concentrated Differential Privacy, @ CSE Theory Seminar, Penn State on April 14, 2017.
- Max-Information, Differential Privacy, and Post-selection Hypothesis Testing
- @ INSR Industry Day, Penn State on April 24, 2017. (Poster)
- @ SMAC Talks, Penn State on December 2, 2016.
- @ CSE Theory Seminar, UCSD on November 7, 2016.
- @ CSE Theory Seminar, Penn State on October 14, 2016.
- Max-Information and Differential Privacy, @ CSE Theory Seminar, Penn State on May 5, 2016.
- The Stable Roommates Problem with Random Preferences, @ CSE Theory Seminar, Penn State on April 10, 2015.
- The Multiplicative Weights Update Method and an Application to Solving Zero-Sum Games Approximately, @ CSE Theory Seminar, Penn State on November 3, 2014.
- Teaching assistant:
- CMPSC 465 Data Structures and Algorithms, Spring 2017 @ Penn State.
- CMPSC 360 Discrete Mathematics for Computer Science, Spring 2015 @ Penn State.
- IT 114 Object Oriented Programming, Spring 2014 @ DA-IICT.
- IT 105 Introduction to Programming, Fall 2013 @ DA-IICT.
-
Program committee member for TPDP 2020.
-
Reviewer for TSC 2020, JPC 2019, T-IFS 2019, JMLR 2018.
-
Reviewer for NIST's The Unlinkable Data Challenge: Advancing Methods in Differential Privacy.
-
Reviewer for S&P (2017, 2019, 2022), ICML (2018, 2021), PETS (2017-2021), NeurIPS (2019-2020), IJCAI 2019, CCS (2018-2019), STOC (2016, 2018), ACSAC 2017, FOCS 2017, WABI 2015.
-
Report on Node-differentially Private Algorithms for Graph Statistics. It includes joint work with Ramesh Krishnan.
