Private Stochastic Convex Optimization:
Efficient Algorithms for Non-smooth Objectives

Modern machine learning systems often leverage data that are generated ubiquitously and seamlessly through devices such as smartphones, cameras, microphones, or user’s weblogs, transaction logs, social media, etc. Much of this data is private, and releasing models trained on such data without serious privacy considerations can reveal sensitive information (Narayanan and Shmatikov, 2008; Sweeney, 1997). Consequently, much emphasis has been placed in recent years on machine learning under the constraints of a robust privacy guarantee. One such notion that has emerged as a de facto standard is that of differential privacy.

Informally, differential privacy provides a quantitative assessment of how different are the outputs of a randomized algorithm when fed two very similar inputs. If small changes in the input do not manifest as drastically different outputs, then it is hard to discern much information about the inputs solely based on the outputs of the algorithm. In the context of machine learning, this implies that if the learning algorithm is not overly sensitive to any single datum in the training set, then releasing the trained model should preserve the privacy of the training data. This requirement, apriori, seems compatible with the goal of learning, which is to find a model that generalizes well on the population and does not overfit to the given training sample. It seems reasonable then to argue that privacy is not necessarily at odds with generalization, especially when large training sets are available.

We take the following stochastic optimization view of machine learning, where the goal is to find a predictor that minimizes the expected loss (aka risk)

based on i.i.d. samples from the source distribution $\mathcal{D}$, and full knowledge of the instantaneous objective function $f(\cdot,\cdot)$ and the hypothesis class ${\mathcal{W}}$. We are particularly interested in convex learning problems where the hypothesis class is a convex set and the loss function $f(\cdot,\mathrm{z})$ is a convex function in the first argument for all $\mathrm{z}\in{\mathcal{Z}}$. We seek a learning algorithm that uses the smallest possible number of samples and the least runtime and returns $\tilde{\mathrm{w}}$ such that $F(\tilde{\mathrm{w}})\leq\inf_{\mathrm{w}\in{\mathcal{W}}}F(\mathrm{w})+\alpha$, for a user specified $\alpha>0$, while guaranteeing differential privacy (see Section 2.2 for a formal definition).

A natural approach to solving Problem 1 is sample average approximation (SAA), or empirical risk minimization (ERM), where we instead minimize an empirical approximation of the objective based on the i.i.d. sample. Empirical risk minimization for convex learning problems has been studied in the context of differential privacy by several researchers including Bassily et al. (2019) who give statistically efficient algorithms with oracle complexity matching that of optimal non-private ERM.

An alternative approach to solving Problem 1 is stochastic approximation (SA), wherein rather than form an approximation of the objective, the goal is to directly minimize the true risk. The learning algorithm is an iterative algorithm that processes a single sample from the population in each iteration to perform an update. Stochastic gradient descent (SGD), for instance, is a classic SA algorithm. Recent work of Feldman et al. (2020) gives optimal rates for convex learning problems (Problem 1) using stochastic approximation for smooth loss functions; however, they leave open the question of optimal rates for non-smooth convex learning problems which include a large class of learning problems, including, for example, support vector machines. In this work, we focus on non-smooth convex learning problems and propose a simple algorithm which achieves nearly optimal rates in the special case where the privacy guarantee scales inversely with the number of observed samples. There are alternative approaches¹¹1We became aware of it in a private communication with Raef Basilly.; for further discussion we refer the reader to Section 6.

We consider the general learning setup of Vapnik (2013). Let ${\mathcal{Z}}$ be the sample space and let ${\mathcal{D}}$ be an unknown distribution over ${\mathcal{Z}}$. We are given a sample $\mathrm{z}_{1},\mathrm{z}_{2},\ldots,\mathrm{z}_{n}$ drawn identically and independently (i.i.d) from ${\mathcal{D}}$ – the samples $\mathrm{z}_{i}$ may correspond to (feature, label) tuples as in supervised learning, or to features in unsupervised learning. We assume that loss $f:{\mathcal{W}}\times{\mathcal{Z}}\rightarrow\mathrm{R}$ is a convex function in its first argument $\mathrm{w}$ and the hypothesis set ${\mathcal{W}}$ is a convex set. Given n samples, the goal is to minimize the population risk (Problem 1).

We assume that the hypothesis class $\mathcal{W}$ is a convex, closed and bounded set in $\mathrm{R}^{d}$ equipped with norm $\left\|{\cdot}\right\|$, such that $\|\mathrm{w}\|\leq D$ for all $\mathrm{w}\in{\mathcal{W}}$. We recall that the dual space of $(\mathrm{R}^{d},\left\|{\cdot}\right\|)$ is the set of all linear functionals over it; the dual norm, denoted by $\left\|{\cdot}\right\|_{*}$, is defined as $\left\|{h}\right\|_{*}=\min_{\left\|{w}\right\|\leq 1}h(\mathrm{w})$, where $h$ is a element of the dual space $(\mathrm{R}^{d},\left\|{\cdot}\right\|_{*})$. In general we will use $\|\cdot\|$ to denote the $\ell_{2}$ norm when there is no risk of confusion.

We do not assume that $f(\mathrm{w},\mathrm{z})$ is necessarily differentiable and will denote an arbitrary sub-gradient as $\nabla f(\mathrm{w},\mathrm{z})$. We assume that $f(\cdot,\mathrm{z})$ is $L$-lipschitz with respect to the dual norm $\left\|{\cdot}\right\|_{*}$, i.e., $\left|{f(\mathrm{w}_{1},\mathrm{z})-f(\mathrm{w}_{2},\mathrm{z})}\right|\leq L\left\|{\mathrm{w}_{1}-\mathrm{w}_{2}}\right\|$ for all $\mathrm{z}$. For convex $f$, this implies that sub-gradients with respect to $\mathrm{w}$, are bounded as $\left\|{\nabla f(\mathrm{w},\mathrm{z})}\right\|_{*}\leq L,\ \forall\ \mathrm{w}\in\mathcal{W},\mathrm{z}\in\mathcal{Z}$. A popular instance of the above is the $\ell_{p}/\ell_{q}$ setup, which considers $\ell_{p}$ norm in primal space and the corresponding $\ell_{q}$ norm in the dual space such that $\frac{1}{p}+\frac{1}{q}=1$. A function $g(\cdot)$ is $\beta$-strongly smooth (or just $\beta$-smooth) if $\left\|{\nabla g(\mathrm{w}_{1})-\nabla g(\mathrm{w}_{2})}\right\|_{*}\leq\beta\left\|{\mathrm{w}_{1}-\mathrm{w}_{2}}\right\|,\forall\mathrm{w}_{1},\mathrm{w}_{2}\in{\mathcal{W}}$. For convex functions, this is equivalent to the condition $g(\mathrm{w}_{2})\leq g(\mathrm{w}_{1})+\langle\nabla g(\mathrm{w}_{1}),\mathrm{w}_{2}-\mathrm{w}_{1}\rangle+\frac{\beta}{2}\|\mathrm{w}_{1}-\mathrm{w}_{2}\|^{2},\forall\mathrm{w}_{1},\mathrm{w}_{2}\in\mathcal{W}$. A function $g$ is $\lambda$-strongly convex if $g(\mathrm{w}_{2})\geq g(\mathrm{w}_{1})+\langle\nabla g(\mathrm{w}_{1}),\mathrm{w}_{2}-\mathrm{w}_{1}\rangle+\frac{\lambda}{2}\left\|{\mathrm{w}_{1}-\mathrm{w}_{2}}\right\|^{2},\forall\mathrm{w}_{1},\mathrm{w}_{2}\in{\mathcal{W}}$. Finally, we use $\tilde{O}(\cdot)$ to suppress poly-logarithmic factors in the complexity.

In convex learning and optimization, the following four classes of functions are widely studied: (a) $L$-lispchitz convex functions, (b) $\beta$-smooth and convex functions, (c) $\lambda$-strongly convex functions, and (d) $\beta$-smooth and $\lambda$-strongly convex functions. In the computational framework of first order stochastic oracle, algorithms with optimal oracle complexity for all these classes of functions have long been known (Agarwal et al., 2009). However, the landscape of known results changes with the additional constraint of privacy. We can trace two approaches to solving the private version of Problem 1. The first is private ERM (Chaudhuri et al., 2011; Bassily et al., 2014; Feldman et al., 2018; Bassily et al., 2019) and the second is private stochastic approximation (Feldman et al., 2020). Chaudhuri et al. (2011) begin the study of private ERM by constructing algorithms based on output perturbation and objective perturbation. Under the assumption that the stochastic gradients are $\beta$-Lipschitz continuous, the output perturbation bounds achieve excess population risk of $O(LD\max(1/\sqrt{n},d/(n\epsilon),d\sqrt{\beta}/(n^{2/3}\epsilon)))$, where $L$ is the Lipschitz constant of the loss function and $D$ measures the diameter of the hypothesis class in the respective norm. The objective perturbation bounds have a similar form. Bassily et al. (2014) showed tight upper and lower bounds for the excess empirical risk. They also showed bounds for the excess population risk when the loss function does not have Lipschitz continuous gradients, achieving a rate of $O(d^{1/4}/(\sqrt{n}\epsilon))$. Their techniques appeal to uniform convergence i.e. bounding $\sup_{\mathrm{w}\in{\mathcal{W}}}F(\mathrm{w})-\widehat{F}(\mathrm{w})$, and convert the guarantees on excess empirical risk to get a bound on the excess population risk. These guarantees, however, were sub-optimal. Bassily et al. (2019) improved these to get optimal bounds on excess population risk, leveraging connections between algorithmic stability and generalization. The algorithms given by Bassily et al. (2019) are sample efficient but their runtimes are superlinear (in the number of samples), whereas the non-private counterparts run in linear time. In a follow-up work, Feldman et al. (2020) improved the runtime of some of these algorithms without sacrificing statistical efficiency; however, the authors require that the stochastic gradients are Lipschitz continuous. Essentially, the statistical complexity of private stochastic convex optimization has been resolved, but some questions about computational efficiency still remain open. We begin with a discussion of different settings for the population loss in subsequent paragraphs, describe what is already known, and what are the avenues for improvement.

In this section, we describe the proposed algorithm and provide convergence guarantees.

Recall that we are given a set of $n$ samples $(\mathrm{z}_{1},\ldots,\mathrm{z}_{n})$ drawn i.i.d. from ${\mathcal{D}}$. We consider an iterative algorithm, wherein, at time $t$, we sample index $Y_{t}$ uniformly at random from the set of indices, $[n]$. Note that $Y_{t}$ is a random variable; we denote the realization of $Y_{t}$ as $y_{t}$. Through the run of the algorithm, we maintain a set, $F_{t}$, of indices observed until time $t$, i.e., $F_{t}=\{y_{\tau}\mid\tau<t\}.$

If $y_{t}\notin F_{t}$, i.e., $\mathrm{z}_{y_{t}}$ is a fresh sample that has not been seen and processed prior to the $t^{\textrm{th}}$ iteration, then we proceed with a projected gradient descent step using the noisy gradient $\nabla f(\mathrm{w}_{t},\mathrm{z}_{y_{t}})+\xi_{t}$. If $y_{t}\in F_{t}$, then the algorithm simply perturbs the current iterate, $\mathrm{w}_{t}$, and projects on to the set ${\mathcal{W}}$. We remark that the noise-only step is important for the privacy analysis, as it allows for privacy amplification by sub-sampling.

The algorithm terminates when half of the points in the training set have been processed at least once, i.e., the size of $F_{t}$ is greater than or equal to $n/2$. We denote this stopping time by $\tau$. We refer the reader to Algorithm 1 for the pseudo-code.

Next, we establish the utility guarantee for Algorithm 1. We first show that $\tau$ is finite almost surely and bounded by $O(n)$ with probability $1-O(\operatorname{exp}\left(-n\right))$. The proof follows a standard bins-and-balls argument.

We proceed with bounding the regret of Algorithm 1. Given a sequence of convex functions $\tilde{f}_{t}:\mathcal{W}\rightarrow\mathbb{R}$, where $f_{t}(\cdot)=f(\cdot,\mathrm{z})$, we bound the regret

where the expectation is with respect to any randomness in the algorithm and randomness of $\tilde{f}_{t}$’s. We assume full access to the gradient of $\tilde{f}_{t}$ and that the diameter of $\mathcal{W}$ is $D$, i.e., $\forall\mathrm{w},\mathrm{v}\in\mathcal{W},\|\mathrm{w}-\mathrm{v}\|\leq D$.

Our setup fits the popular framework of Online Stochastic Mirror Descent (OSMD) algorithm, wherein, given a strictly convex potential $\Phi:\mathbb{R}^{d}\rightarrow\mathbb{R}$, the updates are given as

We utilize the following result.

For any fixed $\tau<\infty$, we can view Algorithm 1 as an instance of OSMD, with $\Phi\equiv\frac{1}{2}\|\cdot\|_{2}^{2}$, and $\tilde{f}_{t}(\cdot)$ defined as

and $f_{t}(\mathrm{w})=\mathbb{E}_{\xi_{t}}[\tilde{f}_{t}(\mathrm{w})]$. Theorem 1 implies that for any $\mathrm{z},\mathrm{y}\in\mathbb{R}^{d}$ $D_{\Phi^{*}}(\mathrm{z}||\mathrm{y})\leq 1/\alpha\|\mathrm{z}-\mathrm{y}\|_{*}^{2}$, where $\alpha$ is the strong-convexity parameter of the potential (in this case $\alpha=1$) – using this result with Theorem 3, and taking expectation with respect to the randomness in $\tau$ and $\xi_{t},t\in[\tau]$, we have that for any $\mathrm{u}\in{\mathcal{W}}$

Since $\xi\sim\mathcal{N}(0,\sigma\mathrm{I})$, we have the following corollary.

The result now follows using the Corollary above and the following lemma.

Corollary 1 with Lemma 1 gives the utility guarantee.

In this section, we establish the differential privacy of Algorithm 1. The privacy proof essentially follows the analysis of noisy-SGD in Bassily et al. (2014), but stated in full detail, for completeness and to provide a self-contained presentation. The basic idea is as follows. We view Algorithm 1 as a variant of noisy stochastic gradient descent on the ERM problem over $n$ samples $\{\mathrm{z}_{i}\}_{i=1}^{n}$. Indeed, but for the step where we update the iterate only with noise and do not compute a gradient, the proposed algorithm would be exactly equivalent to noisy SGD. Prior work shows that using noisy SGD to solve the ERM problem enjoys nicer differential privacy due to privacy amplification via subsampling. Intuitively, Algorithm 1 should also benefit from privacy amplification, and the algorithm should not suffer from privacy loss in steps where we use the zero gradient. We formalize this intuition using the standard analysis for Rènyi differential privacy (Wang et al., 2019) and properties of Rènyi divergence (Mironov, 2017).

We first introduce additional notation. Let ${\mathcal{M}}_{i}:{\mathcal{W}}\times[n]^{*}\times S\rightarrow{\mathcal{W}}\times[n]^{*}$ be a function which describes the $i^{\text{it}}$ iteration of the algorithm – it takes as input, an iterate $\mathrm{w}_{i}\in{\mathcal{W}}$, a set, $F_{i}\subseteq[n]^{*}$, of indices of data points, and a subset $S_{i}\subseteq S$; it outputs an iterate $\mathrm{w}_{i+1}\in{\mathcal{W}}$ and set of indices $F_{i+1}\subseteq[n]^{*}$. We assume that $S$ is totally ordered according to the indices of the datapoints. Further let $\mathfrak{S}_{i}$ denote the set of indices of datapoints in $S_{i}$. Let ${\mathcal{M}}_{i}^{1}$ and ${\mathcal{M}}_{i}^{2}$ denote the first and second outputs of ${\mathcal{M}}_{i}$, i.e., ${\mathcal{M}}_{i}^{1}(\mathrm{w}_{i},F_{i},S)=\mathrm{w}_{i+1}$ and ${\mathcal{M}}_{i}^{2}(\mathrm{w}_{i},F_{i},S)=F_{i+1}$. Note that in the algorithm, the ${\mathcal{M}}_{i}$’s are composed – we initialize $F_{1}=\emptyset$ and $\mathrm{w}_{1}$ is fixed, therefore, ${\mathcal{M}}_{1}(\mathrm{w}_{1},\emptyset,S)=(\mathrm{w}_{2},F_{2})$. ${\mathcal{M}}_{2}$ acts on the output of ${\mathcal{M}}_{1}(\mathrm{w}_{1},\emptyset,S)$ as ${\mathcal{M}}_{2}(({\mathcal{M}}_{1}(\mathrm{w}_{1},\emptyset,S)),S)=(\mathrm{w}_{3},F_{3})$. In general, we have that

Formally, given $\mathrm{w}\in\mathcal{W},m\in\mathbb{N}$, and $F\in[n]^{*}$, we define random variable ${\mathcal{M}}_{i}(\mathrm{w},F,S):{\mathbb{R}}^{d}\times[n]^{m}\rightarrow{\mathcal{W}}\times[n]^{*}$ as

where $\mathrm{g}_{i}$ is the following gradient operator:

In Algorithm 1, $m=1$, and in general $m$ is just the size of the sub-sampled set from $S$, which we use to construct a mini-batched gradient.

The input space of $\mathcal{M}_{i}(\mathrm{w}_{i},F_{i},S)$, which is ${\mathbb{R}}^{d}\times[n]^{m}$ has measure ${\mathcal{N}}(0,\sigma^{2}{\mathbb{I}})\times\text{Unif}([n],m)$, where $\text{Unif}([n],m)$ is the sub-sampling measure, which sub-samples $m$ out of $n$ data points uniformly randomly. We now construct a vector concatenating the first outputs of all these ${\mathcal{M}}_{i}$’s. Let

We claim that $\mathbf{M}_{\tau}(\mathrm{w}_{1},S)$ is differentially private.

To prove the above theorem we are first going to show that the first coordinate of each $\mathcal{M}_{i}$ is sufficiently differentially private.

We can now prove Theorem 5.