Introduction

In this paper, we consider the problem of minimizing the convex risk of a machine learning predictor, guaranteeing local differential privacy. Instead of going through the empirical risk minimization route, we directly optimize the stochastic objective of the risk via stochastic subgradients appropriately sanitized to guarantee the local differential privacy. Our proposed algorithm is a variant of stochastic subgradient descent, with the important feature of not requiring the tuning of learning rates. Yet, it guarantees the same convergence rate and local differential privacy of a stochastic subgradient descent procedure with the oracle tuning of its learning rate.

More in details, consider the risk R(w) ∶ R d → R defined as R(w) ∶= E x∼ρ X [ℓ(w, x)], where ℓ(w, x) is convex in the first argument and x represents sensitive data about an individual drawn i.i.d. from ρ X . In machine learning terms, R(w) represents the test loss that we are interested in directly minimizing, while ℓ(w, x) is the loss on a single sample x. It is well-known that, by linearity of the expectation, we can get an unbiased estimate of a subgradient of R(w) just using a subgradient w.r.t. the first argument of ℓ(⋅, x) where x is drawn i.i.d. from ρ X . Hence, we can construct sanitized subgradients simply returning a noisy version G(w) ∈ ∂ℓ(w, x) + ξ where the noise ξ guarantees the ǫ-Local Differential Privacy (ǫ-LDP), which prevents the private information from being identified. We elaborate more on the problem definition and the assumptions in Section 2.

One immediately obvious algorithm to try for ǫ-LDP is the standard stochastic subgradient descent (SGD) algorithm together with the popular choice of density p(ξ) ∝ exp(-ǫ 2 ξ ) (Song et al., 2013;2015;Wu et al., 2017). Let us consider the SGD with a constant learning rate η for simplicity. 1 The convergence rate of SGD w.r.t. the optimum w * = min w R(w) after one pass over T samples is

Notice that the convergence rate largely depends on the learning rate, and setting η = ǫ d √ T results in the rate of O( d ǫ w * 2 √ T ). While the optimal tuning w * ǫ d √ T would result in a much better rate of O( d ǫ w * √ T ), the value w * cannot be known beforehand. Therefore, practitioners need to tune the learning rate by trying out various values over multiple runs. However, this significantly increases the number of subgradient requests, which can be interpreted as the privacy cost. This also implies that, when there is a fixed budget of privacy loss, one would have to use a smaller ǫ to allow multiple runs, which slows down the convergence.

Departing from the cumbersome and privacy-costing parameter tuning, we propose a new algorithm BANCO (Betting Algorithm for Noisy COins) that enjoys the convergence rate Õ( d ǫ w * √ T ) without having to tune any parameters, where Õ hides logarithmic factors. At the heart of the algorithm is a decomposition that isolates the work of adapting to the norm of the optimum w * and delegates it to a one-dimensional stochastic optimization algorithm. We describe our algorithm and highlight the proof sketch in Section 3 and conclude with future directions in Section 4. Related work. While there is a large body of work on differentially private (DP) empirical risk minimization, there is less research on studying the generalization properties of the obtained solution. Moreover, most of the work is based on the notion of differential privacy rather than on the stronger notion of local differential privacy (LDP). We remind the readers that the DP is useful when the data provider trusts the learning agents to be DP and allows them to access sensitive data (or data provider may possess the learners internally) whereas LDP is useful when the data provider does not trust the learning agents and thus have to release sanitized version of individual data. Due to space constraints, we focus on discussing the most relevant works. The notion of LDP was introduced in Duchi et al. ( 2014) and Song et al. (2013;2015). Duchi et al. (2014) study the generalization of locally differentially private SGD, focusing on the optimal dependency on the number of dimensions, but assuming bounded domains to optimally tune the learning rates. Song et al. (2013;2015) use locally differentially private SGD to minimize the regularized ERM problems. Wu et al. (2017) study the convergence of SGD to minimize the ERM problem and guarantee differential privacy through the output perturbation method, and they also require the knowledge of the norm of the optimal solution to optimally tune the learning rates. Bassily et al. (2014) studies the generalization properties of locally differentially private SGD, but it requires a bounded domain to set the learning rates or the presence of a regularizer, that in turn must be tuned. Instead, our work gives a generalization guarantee for a locally differentially private SGD with one pass over the data and no learning rates to tune.

The problem of parameter-free ǫ-LDP SGD can be seen as a noisy version of the parameter-free SGD problem (Streeter and McMahan, 2012;Orabona and Pal, 2016;Orabona and Tommasi, 2017;Cutkosky and Orabona, 2018). However, the extension of existing (near-optimal) parameter-free SGDs to noisy gradients is not immediately clear since the noise makes the gradients unbounded while the parameter-free SGDs require bounded gradients. Specifically, naively feeding in the unbounded gradients can even make the algorithm undefined, let alone the lack of convergence guarantees; see (Jun and Orabona, 2019, Section 3) for a detailed argument. Our solution in this paper goes back to the more general version of Online Convex Optimization (OCO) (Zinkevich, 2003) and reconsider its formulation to allow unbounded noise, which is more general than the ǫ-LDP setting. In this paper, however, we focus on the LDP setting; we refer the interested readers to Jun and Orabona (2019).

Problem Definition and Preliminaries

In this section, we describe our notations and provide relevant background.

Locally Differentially Private (LDP) SGD. An ǫ-differentially private algorithm must guarantee that the log-likelihood ratio of the outputs of the algorithm under two databases differing in a single individual's data is smaller than ǫ (Dwork et al., 2006). In the stricter definition of local differential privacy (LDP) (Wasserman and Zhou, 2010;Kasiviswanathan et al., 2011;Duchi et al., 2014;Song et al., 2013;2015) an untrusted algorithm is allowed to access a perturbed version of a sensitive data point only through a sanitization interface. In particular, the sanitization mechanism must guarantee that the log-likelihood ratio of the data of two individuals x and x ′ is smaller than ǫ.

Definition 1 (Local Differential Privacy). Let D = (X 1 , . . . , X n ) be a sensitive dataset where each

where the probability is w.r.t. the randomization in the sanitization mechanism.

Algorithm 1 Betting Algorithm for Noisy COins (BANCO) for Differentially Private SGD

Receive a noisy negative subgradient ĝt such that E[ĝ t ] ∈ -∂ℓ(w t , x) where x ∼ ρ X 4:

Update magnitude:

G , 1 b , and k 1 = 0.6838 5:

Update direction:

Project direction onto L2 ball: q t+1 = q t+ 1 2 ⋅ min 1, q t+ 1 2 -1 2 7:

Update the weight vector:

Denote by ∂ℓ(w, x) the subdifferential set of ℓ w.r.t. its first argument evaluated at (w, x). The local differential setting can be specialized to SGD, as described in the introduction, by a mechanism that, upon receiving a subgradient in ∂ℓ(w, x) with x i.i.d.

∼ ρ X , returns a noisy version G(w) ∈ ∂ℓ(w, x) + ξ, where the noise ξ guarantees the ǫ-local differential privacy.

Assumptions. Throughout, we work with negative subgradients for notational simplicity. Let ĝt be the negative subgradient received at time step t. Let g t = E t [ĝ t ] be the true negative subgradient and ξ t = ĝt -E t [ĝ t ] where we use the notation

We assume that the true subgradients are bounded by G: g t 2 ≤ G. Furthermore, the noise ξ t is conditionally zero-mean and has conditional finite variance:

for some σ > 0. We also assume a tail condition such that ξ t is conditionally sub-exponential with parameters (σ 2 1D , b):

One can show that, when (2) is achieved with equality, we have σ 2 1D ≤ σ 2 . The intuition of the condition above is that the tail of the noise ξ t behaves well in any direction. This noise definition covers a wide range of distributions, including Gaussian and Laplace. If d = 1, we have σ 2 = σ 2 1D . This is not true in general and the relationship depends on the noise distribution. If ξ t ∼ N (0, s 2 I), then one can see that σ 2 1D = s 2 and σ 2 = ds 2 . As another example, the Laplace mechanism noise used in differentially-private learning satisfies the tail condition above; see Jun and Orabona (2019, Lemma 7).

Parameter-free Stochastic Optimization with Noise

We now describe BANCO that achieves essentially the convergence rate of optimally-tuned SGD without repeated runs for tuning the learning rate, thus being truly one-pass. BANCO decomposes the optimization process into two parts: one for optimizing the direction and the other for the magnitude of the solution vector. For the direction, we use projected stochastic gradient descent with adaptive learning rates (Orabona and Pál, 2018). While, for the magnitude we use a parameter-free algorithm based on coin-betting (Orabona and Pal, 2016;Jun and Orabona, 2019). We then construct the solution vector as the multiplication of the two solutions. The full pseudocode can be found in Algorithm 1. Note that m t+1 has a closed form solution as follows: with shorthands x = ∑ t s=1 ⟨ĝ s , q s ⟩ and y = t(σ 2 2 + G 2 ),

8ay 3 2 .

For improving numerical precision for computing m t+1 , we refer to (Koolen, 2015).

We now show that BANCO is a parameter-free ǫ-LDP SGD algorithm. Consider the Laplace sanitization mechanism that adds noise with probability density function ρ ξ (z) ∝ exp(-ǫ 2 z 2 ), which makes the subgradients very similar to one another. Song et al. (2015) proved that this mechanism is ǫ-locally differentially private and ensures

, satisfying (1). Further, Jun and Orabona (2019, Lemma 7) show that this mechanism satisfies (2) with σ 2 1D = 18d 2 ǫ 2 and b = ǫ 4. Theorem 2. Assume that ℓ(w, x) is convex in the first argument w ∈ R d and has its subgradients' L2-norm bounded by 1, where the subgradient is with respect to the first argument. Let the noise ĝt -E[ĝ t ] follow the density ρ(z) ∝ exp(-ǫ 2 z 2 ). Then, for any w ⋆ ∈ R d , after one pass over T samples Algorithm 1 guarantees

This convergence rate matches the private SGD of Wu et al. (2017) up to polylogarithmic terms, with the important difference that we do not need to assume the knowledge of the norm of the optimal solution w ⋆ to tune the learning rates. Furthermore, the rate in Theorem 2 is unimprovable up to logarithmic factors as shown in Jun and Orabona (2019). Finally, we remark that Algorithm 1 is in fact an instance of Jun and Orabona (2019), and more generic algorithms are available via a reduction therein, which can be of independent interest. Also, the Gaussian noise can be used as well, resulting a better dependency in the dimension of the space, but in the weaker (ǫ, δ)-LDP.

Proof Sketch

The proof is mainly concerned with regret, a standard quantity in online learning that measures the suboptimality with an arbitrary comparator u. Theorem 2 is a direct consequence of the expected regret bound we describe below using so-called the online-to-batch conversion (Cesa-Bianchi et al., 2004). Theorem 3 below shows that the expected regret of Algorithm 1 is decomposed into two expected regrets, each for the magnitude learner m t and the direction learner q t . The fact that we require the expected regret of the direction learner w.r.t. the unit norm comparator frees us from tuning its learning rate, delegating the burden of adaptation to the magnitude learner. In turn, the magnitude algorithm is parameter-free, giving the best guarantee without having to tune any learning rates. The proof is simple and immediate from Cutkosky and Orabona (2018). Hereafter, we consider linear functions that can be written as ℓ(w, x) = ⟨-g t , w⟩ for some g t without loss of generality (due to the convexity).

Theorem 3. Suppose the direction learner obtains expected regret Regret D T (u) ∶= ∑ T t=1 ⟨ĝ t , uq t ⟩ for any competitor u in the unit ball S ⊂ R d and the magnitude learner obtains expected regret Regret M T (v) ∶= ∑ T t=1 s t ⋅ (vm t ) for any competitor v ∈ R where s t = ⟨ĝ t , q t ⟩. Then, the iterates

where we define u u = 0 when u = 0.

For the direction learner, one can invoke any algorithm that guarantees the optimal regret with respect to competitors in the unit ball. Here, we have used projected online gradient descent with the scale-free learning rates in Orabona and Pál (2018). One can then immediately obtain the expected regret bound with noisy subgradients:

where (a) uses Jensen's inequality and the fact that E[ ĝt 2 ] = E[ g t 2 2 ] + σ 2 . Finally, for the magnitude learner, we have instantiated the coin betting algorithm of Jun and Orabona (2019) that has the following regret bound:

4 Future Work

Our study opens up numerous research directions. First, one immediate difference in our upper bound from the standard SGD algorithm with adaptive step size is that we do not have a data-dependent regret bound; we have (G 2 + σ 2 )T rather than E[∑ T t=1 ĝt 2 ]. It would be interesting to investigate whether data-dependent bounds are possible. Second, it would be desirable not to require the knowledge of the noise through (σ 2 , b) so we can have a single algorithm that can adapt to various types of noise. Finally, high probability regret bounds are a straightforward research direction.