Collect at Once, Use Effectively:
Making Non-interactive Locally Private Learning Possible

arXiv:1706.03316v1 [cs.LG] 11 Jun 2017

Kai Zheng∗†, Wenlong Mou∗‡, and Liwei Wang§
Key Laboratory of Machine Perception, MOE,
School of EECS, Peking University
June 13, 2017

Abstract
Non-interactive Local Differential Privacy (LDP) requires data analysts to collect data from
users through noisy channel at once. In this paper, we extend the frontiers of Non-interactive
LDP learning and estimation from several aspects. For learning with smooth generalized linear
losses, we propose an approximate stochastic gradient oracle estimated from non-interactive
LDP channel using Chebyshev expansion, which is combined with inexact gradient methods
to obtain an efficient algorithm with quasi-polynomial sample complexity bound. For the highdimensional world, we discover that under ℓ2 -norm assumption on data points, high-dimensional
sparse linear regression and mean estimation can be achieved with logarithmic dependence on
dimension, using random projection and approximate recovery. We also extend our methods to
Kernel Ridge Regression. Our work is the first one that makes learning and estimation possible
for a broad range of learning tasks under non-interactive LDP model.

1

Introduction

Data privacy has become an increasingly important issue in the age of data science. Differential Privacy (DP), proposed in 2006 by Dwork et al.,[11], provide a solid foundation and rigorous standard
for private data analysis. Since then, there has been extensive literature studying the fundamental
trade-offs between differential privacy and accuracy for query answering [16, 15, 34, 40], machine
learning [4, 5, 30, 39], and statistical inference [27, 31]. For more details on DP results, please
refer to the excellent monograph written by Dwork and Roth [12]. Intuitively, a DP algorithm uses
randomized response to defend against adversary, so that change of one of data points could not be
detected.
Despite the prevailing success of this notion in academia, its applicability in data science practice could be limited. For example, if data analysts just promise to follow the differential privacy
constraints, user will not feel their privacy are preserved. The promise could not be validated; the
mechanisms are complicated; and even worse: users do not trust the data collector at all. Unfortunately, most of differential privacy algorithms are based on adding noise calibrated to stability of
loss function, which essentially requires access to original data.
∗

These two authors contributed equally
zhengk92@pku.edu.cn
‡
mouwenlong@pku.edu.cn
§
wanglw@cis.pku.edu.cn
†

1

Borrowing ideas from classical wisdom on collecting sensitive survey data [41], Local Differential
Privacy (LDP) [22, 9] was proposed as a stronger notion of privacy to resolve this problem. LDP
requires each of data points to be passed through a noisy channel during collection. This channel
will ensure one can hardly tell anything about the user based on what he have sent. The practical
advantage of LDP is obvious: users will be comfortable sending their sensitive information through
noisy channels, which are transparent and reliable; additionally, users can choose their own privacy
parameters, making it possible to associate with economic value. Therefore, this line of research
has attracted lots of attention [8, 9, 19, 1, 18].
Despite the analogy in definition, the way in which LDP achieves accurate results are fundamentally different from classical DP. Essentially, the information collected from each user is almost
completely noisy, from which one needs to obtain accurate results. The only way to do that is to
make the independently distributed noise cancel out with each other in some sense. With sand
being washed away by waves, golds begin to appear.
Two local privacy notions have been discussed in existing literature: the interactive model
allows the algorithm to collect data sequentially, and decide what to ask based on information
from previously asked users. The non-interactive model, on the contrary, requires all data to be
collected at once, with no interactive queries allowed. Apparently the non-interactive model is
strictly stronger, and prohibition on interactive queries rules out most of SGD-type approaches,
making the problem significantly harder. However, non-interactive LDP is more useful in real-world
applications, as opportunities of interactive queries may not be available in most settings.
In existing literature, learning and inference under interactive and non-interactive LDP therefore
are exhibiting different appearances. In the interactive world, LDP is promised with connection to
Statistical Query (SQ) model [25], from its very beginning [24]. SQ algorithms for a wide range of
convex ERM problems were proposed by [13], implying good risk bounds for LDP. [9] established
matching upper and lower bounds for convex risk minimization problems. On the other hand, very
few has been done in the non-interactive setting. Existing works primarily focus on basic estimation
problems such as means and discrete densities [8, 7, 1], or some function calculations [21]. Most of
important modern learning and inference tasks, including estimation in linear models and convex
ERM, are still poorly understood in non-interactive local DP settings.
For the high-dimensional world, where d ≫ n while some low-complexity constraints are imposed,
we may hope the error induced by privacy constraints to be logarithmically dependent upon d.
In classical differential privacy literature, this has been be addressed using different techniques,
guarantee error bounds logarithmically dependent on dimension [33, 32]. However, lower bounds
have been shown in local privacy model even for high-dimensional 1-sparse mean estimation, ruling
out any good guarantees [7]. The lower bound result illustrates fundamental difficulties of local
differential privacy. But if we still want to do high-dimensional learning under local privacy, are
there additional assumptions that helps?
Therefore, the starting point of this work lies on making learning possible under the noninteractive LDP setting, which is the hardest yet the most useful. We initiate the first attempt
towards a broad range of learning tasks beyond simple distribution estimation. In particular, we investigate two important classes of problems under non-interactive LDP: (1) High-dimensional sparse
linear regression and mean estimation; (2) Generalized linear models. Our focus is to design corresponding mechanisms and study their convergence rates with respect to the number and dimension
of data. One can also consider optimal mechanisms in terms of privacy parameters like [14], which
is of independent interests.
Our Contributions: In this paper, we propose several efficient algorithms for learning and
estimation problems under non-interactive LDP model, with good theoretical guarantees. In the
following we summarize our contributions.
2

(1) High Dimensional Estimation: One of exciting findings in this paper is about local
privacy for high-dimensional data. Roughly speaking, convergence rate with logarithmic dependence
on the dimension can be attained under LDP, if we assume data points are ℓ2 bounded. This is in
sharp contrast with information-theoretic lower bounds for 1-sparse mean estimation for ℓ∞ bounded
data [7]. Valid algorithms are presented for both sparse mean estimation and sparse linear regression,
respectively. Intuitively, non-interactivity doesn’t bring about additional difficulties, since the loss
functions are quadratic forms. However, if we directly add noise to each of data points and send it
to the server, the aggregated noise will lead to linear dependence on the dimension. Thus we adopt
the random projection technique, and send the noisy version of projected data to the server. Based
on the aggregated information, we can approximately recover the optimal solution via linear inverse
problem.
(2) Learning Smooth Generalized Linear Models: Generalized linear problems which
has additional smooth properties (we call the loss with respect to it as smooth generalized linear
loss (SGLL), see rigorous definition in section 2) include many common loss functions, such as
logistic loss, square loss, etc. Optimizing such losses are intuitively much more difficult in noninteractive LDP model, as the loss can be an arbitrary function w T x. This even makes it difficult
for us to obtain an unbiased estimator for objective function, or its gradient. As a result, when we
aggregate the loss of noisy data together, it is even hard to ensure it converge to the population
loss. Approximation theory techniques are introduced to tackle this problem. In particular, we use
polynomials of w T x to approximate nonlinear coefficients of gradients. Chebyshev bases, instead
of Taylor series, are used to get faster convergence within an arbitrary domain. Then we are able to
build inexact stochastic gradient oracles to arbitrarily specified accuracy. SIGM algorithm in [10]
is exploited to find the minimizer with inexact gradients.
Other Related Work: Local privacy dates back to [41], who uses random responses to protect
privacy in surveys. In recent LDP literature, both [8] and [18] studied density estimation methods
and their theoretical behaviors in LDP model. Rather than statistical setting in above two work, [1]
considered how to produce frequent items and corresponding frequencies of a dataset in local model.
Besides, [19] investigated optimality of LDP mechanisms based on information theoretical measures
for statistical discrimination.
Approximation techniques are commonly used in DP literature. [34] employed polynomials for
marginal queries. [40] leveraged trigonometric polynomials to answer smooth queries. [43] also used
polynomial approximations and get basic convergence results in standard DP model. Besides, the
random projection and recovery has also been used in DP learning [23] and local DP histogram
estimation [1].
In standard DP model, both high-dimensional sparse estimation and generalized linear model
have been intensively studied. [26] and [32] considered the convergence of private LASSO estimator
under RSC and incoherence assumptions. [33] considered constrained ERM of sparse linear regression, and obtained Õ(log d/n2/3 ) rate using private Frank-Wolfe. Above results assume ℓ∞ -bounded
data. By stronger assumption of ℓ2 bounded data, [23] gave a general framework for high dimensional empirical risk minimization (ERM) problem. There are several works to estimate generalized
linear model under DP, with a particular emphasis on logistic regression. Objective and output
perturbation are used to get low excess risks [4, 5]. Both [2] and [42] considered concrete private
algorithms to solve ERM. None of these existing results extends directly to non-interactive LDP
setting.

3

2

Preliminaries

Some notations: [p] = {1, 2, · · · , p}. Vectors are written in bold symbol, such as x, w. x represents
univariate number, which has no relation with x. For a vector x = [x1 , x2 , · · · , xd ]T , xk represents
the power of each element. B2 (r) = {x| kxk2 6 r}. Denote S+ as the semipositive matrix space,
ProjS+ (·) means projecting a matrix to S+ in terms of Frobenius norm (i.e. eliminate all negative
eigenvalues). For an univariate function f (x), f (k) (x) represents its k-th derivative, and define
R 1 (k+1)
dx. For the reason of limited space, all omitted proof can be found in the
f (k) T := −1 |f √1−x(x)|
2
supplementary.

2.1

Local Differential Privacy

Here we adopt the LDP definition given in [1].
Definition 1. A mechanism Q : V → Z is said to be (ǫ, δ)-local differential private or (ǫ, δ)-LDP,
if for any v, v ′ ∈ V, and any (measurable) subset S ⊂ Z, there is
Pr[Q(v) ∈ S] 6 eǫ Pr[Q(v ′ ) ∈ S] + δ
Just the same with basic results in DP [12], there are corresponding basic results for LDP:
Lemma 1 (Gaussian Mechanism). If V p
= {v ∈ Rd | kvk2 6 1}, then Q(v) = v + e is (ǫ, δ)-LDP,
d
2
where e ∈ R , and e ∼ N (0, σ Id ), σ = 2 2 ln(1.25/δ)/ǫ.

1 ). Let Q : V → Z be an (ǫ , δ )-LDP mechanism for i ∈
Lemma 2 (Composition Theorem
i
i
i i
Qk
[k]. Then if Q[k] : V → i=1 Zi is defined to be Q[k] (v) = (Q1 (v), . . . , Qk (v)), then Q[k] is
P
P
( ki=1 ǫi , ki=1 δi )-LDP.

The following simple mechanism add Gaussian noise to preserve LDP of a vector, which serves
as a basic tool in LDP learning and estimation.

Algorithm 1 Basic Private Vector mechanism
Input: A vector x ∈ Rd , privacy parameter ǫ, δ for LDP
Output: Private√vector z
1:

2:
3:
4:
5:

2 ln(1.25/δ)

Setting σ =
ǫ
if kxk2 > 1 then
x = x/ kxk2
end if
z ← x + e, where e ∼ N (0, σ 2 Id )

Theorem 1. Algorithm 1 preserves (ǫ, δ)-LDP.

3

High Dimensional and Non-parametric Learning via Random Projections

In this section we consider three learning problems under non-interactive LDP: Mean Estimation
and Linear Regression in High-dimensions, as well as Kernel Ridge Regression. Using random
1
Note one can also use the advanced composition mechanism [20] with a refined analysis, but the main dependence
over n and d will remain nearly the same.

4

projection techniques, we are able to get logarithmic dependence on d in high-dimensional settings,
and also to get good guarantees for Kernel version. The first problem is considered in statistical
settings, as we need to assume a sparse mean vector. The latter two problems are considered as
ERM problems, which can easily be translated to population risk using uniform convergence.

3.1

High-dimensional Mean Estimation

In this section, we propose a non-interactive LDP mechanism for high-dimensional sparse mean
estimation problem. By assuming ℓ2 bounded data points, and ℓ1 bounded population mean, we
can get error rates with logarithmic dependence on d. Our results are in sharp contrast with the
lower bound for ℓ2 -bounded general mean estimation under standard DP [2], as well as the lower
bound for ℓ∞ -bounded 1-sparse mean estimation under local DP [7]. It can be easily seen that our
method extends to mean estimation problem for arbitrary low-complexity constraint set in high
dimensions. We state our results in ℓ1 setting to keep the arguments clear. Our problem adopts a
statistical estimation setting as follows:
ℓ2 -bounded sparse mean estimation Suppose there is an unknown distribution D supported
on B(0, 1), with kED (x)k1 ≤ Λ. The ℓ2 -bounded sparse mean estimation problem requires us to
produce an estimator θ̂ that makes kθ − ED (x)k2 small with high probability.
Algorithm 2 LDP ℓ1 Constrained Mean Estimation
Input: x1 , x2 , · · · , xn ∼ i.i.d.D
Output: Estimator z
√
Set p = ⌈Λǫ n⌉, and m = ⌈18 log 1δ ⌉
Sample G ∼ √1p N (0, 1)p×d .
for User i do
Collect yi = Gxi + ri ,
Ip )
with ri ∼ i.i.d.N (0, 2 log(1.25/δ)
ǫ2
end for
for j ∈ n
{1, 2, · · · , m} do
o
(j−1)n
jn
Sj = 1 + (j−1)n
,
2
+
,
·
·
·
,
m
m
m .
1 P
Let µj = |Sj | i∈Sj yi .
end for
Let M = {µ1 , µ2 , · · · , µm }.
for j ∈ {1, 2, · · ·, m} do
Let rj = min r : |Bℓ1 (µj , r) ∩ M| ≥ m
2 .
end for
Let j∗ = arg minj rj , and u = µj∗
Solve the following convex program:
arg minkzk1
z

100p log(nd/δ)
s.t.kGz − uk1 ≤
ǫ

r

m
n

(1)

In Algorithm 2 we describe our data collection procedure and estimation algorithm. We are
primarily using two techniques: random projection and recovery from low-complexity structures;
median-of-mean estimator to boost failure probability. The privacy argument is directly implication
5

of Theorem 1.
Intuitively, adding noise to each entry of mean vector will result in error rate’s linear dependence
on d. Thus we adopt the random projection technique to send a compressed version of data vector
through the noisy channel. This locally private estimation procedure can be viewed as a variant of
noisy compressed sensing, where ℓ2 recovery rate is fundamentally controlled by the Gaussian Mean
Width of constraint set [38]. Though the distribution has bounded support, the concentration for
mean estimation is dimension-dependent, while dimension-independent Markov Inequalities hold.
To tackle this problem, we employ Median-of-Mean estimator to get exponential tails [17].
We first give the following bound on the error in projected space.
Lemma 3. Let x1 , x2 , · · · , xn ∼ i.i.d.D with µ = ED [x] and supp(D) ⊆ B(0, 1). Let G and {yi }ni=1
defined in the above procedure. For each of group Sj fixed, we have the following with probability
2/3:
!
p log(nd)
1 X
p
yi − Gµ ≤ O
(2)
|Sj |
1
ǫ
|S
|
j
y ∈S
i

j

The aggregation step in Algorithm 2 is a high-dimensional generalization of Median-of-Mean
estimator used in heavy-tailed statistics. The tail properties are guaranteed in the following lemma:

Lemma 4 (Proposition 9 in [17]). Suppose in metric space X , a set of points M = [θ1 , θ2 , · · · , θm ] ∼
i.i.d.D, with P r[dX (θi , θ) ≥ ǫ] ≤ 32 . Let θ̂ be generated from the following procedure: ri =

min r : |BX (θi , r) ∩ M| ≥ m
2 ,and θ̂ = arg minθi ri . Then we have:
m

P r[dX (θ̂, θ) ≥ 3ǫ] ≤ e− 18

Since the original data are i.i.d. samples from underlying distribution, small group with fixed
indices should also be i.i, d.. Therefore µ1 , µ2 , · · · , µk are i.i.d.. Combining Lemma 3 and Lemma 4
we get the following result:
Corollary 1. The vector u constructed in Algorithm 2 satisfies the following with probability 1 − δ:
r 

p log(nd/δ) m
(3)
ku − Gµk1 ≤ O
ǫ
n

Then we turn to the recovery of original mean estimator. The primary tool we are using are
General M ∗ bound in [38].

Lemma 5 (Theorem 6.2 in [38], High Probability Version). For unknown vector x ∈ K ⊆ Rd , let
G ∼ √1p N (0, 1)p×d . Noisy vector ν ∈ Rp with kνk1 ≤ σ. Let y = Gx + ν. By solving the following
optimization problem:
kx′ kK
arg min
′
x

s.t. kGx′ − yk1 ≤ σ

(4)

where k·kK denotes the Minkowski functional of K. Then we can get the following with probability
1−δ
!
w(K) + σ + log 1δ
′
kx − x k2 ≤ O
√
p
where w(K) denotes the Gaussian width of K.
By putting these results together we get the bound on estimation loss:
Theorem 2. Algorithm 2 outputs z satisfying the following with probability 1 − δ:
r

1 !
nd
1 Λ2 4
kz − µk2 ≤ O log
log
δ
δ ǫ2 n
6

3.2

Sparse Linear Regression

1 Pn
T
In this section, we consider empirical loss of sparse linear regression, i.e. L(w; D) = 2n
i=1 (xi w −
yi )2 , where D = {(xi , yi )|i ∈ [n]}, kxi k2 6 1, yi ∈ [−1, 1]. 2 .
Define w ∗ = argminw∈C L(w; D), where C = {w| kwk1 6 1}. We want to obtain a vector w priv ∈
C within non-interactive LDP model, such that the empirical excess risk L(w priv ; D) − L(w ∗ ; D)
has polynomial dependences on log d and n1 .
As in the case of high-dimensional mean estimation, directly manipulating in the original high
dimensional feature space will introduce large noise, hence we use a sub-Gaussian random matrix
Φ ∈ Rm×d to project original data (i.e. vectors in Rd ) into the low dimensional space (i.e. Rm )
first, then perturb each data in low dimensional space (i.e. Basic Private Vector mechanism given
in Algorithm 1) which protects local privacy, and send it to the server.
Having obtained private synopsis, the server then reconstruct an unbiased estimator for objective
function according to these private synopsis. We subtract a quadratic term to ensure unbiasedness
and project to PSD matrices to preserve convexity. To show good approximation guarantee, we make
use of RIP bounds for random projection. As the loss function is determined by inner products
between w and data, it could be uniformly preserved in projected space, which guarantees the
accuracy of solution estimated with local privacy. Apparently, our methods also imply bounds with
general low-complexity constraint set that preserves RIP.
Our private learning mechanism is given in Algorithm 3 and any random projection matrix can be
used here. The privacy argument directly follows from Private Vector Mechanism and composition.

Algorithm 3 LDP ℓ1 Constrained Linear Regression
Input: Personal data (x, y), parameter ǫ, δ, projection matrix Φ ∈ Rd×m
Output: Learned classifier w priv ∈ Rd
1: for Each user i = 1, . . . , n do
2:
zi ← Basic Private Vector (ΦT xi , ǫ/2, δ/2)
3:
vi ← Basic Private Vector (yi , ǫ/2, δ/2)
4: end for
√
2 2 ln(2.5/δ)
5: Setting Z = [z1 , · · · , zn ]T , σ =
,
ǫ
Q = ProjS+ (Z T Z − nσ 2 Im ), v = [v1 , · · · , vn ]T
6:

w priv ← argminw∈C L̂(w; Z, v), where
1
(ΦT w)T Q(ΦT w) − n1 v T ZΦT w
L̂(w; Z, v) := 2n

In fact, as original data is in L2 ball, and random projection preserves norms with high probabilty,
hence steps 2-4 in Algorithm 1 will be executed with very low probability.
2
1
Denote the true objective function in low dimensional space L̄(w; X̄, y) := 2n
X̄ΦT w −
1 T
T
T
∗
n y X̄Φ w, where X̄ = [x1 , · · · , xn ] Φ, w ∈ C. Let ŵ := argminw∈C L̄(w; X̄, y). The following
priv
lemma gives the accuracy of private solution w
when reduced into low dimensional space:
Lemma 6. Under the assumptions made in this section, given projection matrix Φ, with high
probability over the randomness of private mechanism, we have
r

m
priv
∗
L̄(w
; X̄, y) − L̄(ŵ ; X̄, y) 6 Õ
(5)
nǫ2
Now, combined with RIP bound for random projection, we can move on to prove the empirical
excess risk of sparse linear regression:
2

Our methods suits to any radius of x and y.

7

Theorem 3. Under the assumption in this section, set m = Θ
bility , there is
L(w priv ) − L(w ∗ ) = Õ



log d
nǫ2

p


nǫ2 log d , then with high proba-

1/4 !

Note [33] assume data is in L∞ ball, while both [23] and ours assume data is in L2 ball. However,
in LDP model, [7] show it was impossible to obtain polynomial dependences over log d for ℓ0 mean
estimation problem if data is in L∞ ball.

3.3

Infinite Dimension: Kernel Ridge Regression

Previous method mainly applies to data with finite dimensional features. However, it is common to
use kernel trick in practice. This brings about new difficulties for LDP learning, as we could not add
noise in the Hilbert space. In this subsection, we take kernel ridge regression as an example to show
how to use Random Fourier Features (RFF) [29] to deal with such cases caused by shift-invariant
kernels (i.e. k(x, y) = k(x − y)). Note our technique also suits to similar problems.
Fix a shift-invariant kernel k(·, ·), denote the Hilbert space implicitly defined as H, and the
corresponding feature map as Φ : Rd → H. Let the Hilbert space corresponding to the random
Fourier feature map be Ĥ ⊂ Rdp , and its feature map Φ̂ : Rd → Ĥ, where dp is the RFF projection
dimension. Given a subset X ⊂ Rd and data D = {(xi , yi )|xi ∈ X , i ∈ [n]}, for any f ∈ H, g ∈ Ĥ,
define loss functions in H and Ĥ as follows:
C X T
f Φ(xi ) − yi
2n
i
C X T
g Φ̂(xi ) − yi
LĤ (g) :=
2n

LH (f ) :=

i

2
2
2
2

+

1
kf k2H
2

(6)

+

1
kgk2Ĥ
2

(7)

where C is the regularization parameter. Denote f ∗ = argminf ∈H LH (f ), g∗ = argming∈Ĥ LĤ (g), G
as the Lipschitz constant of square loss, which depends on the bounded norm of features. Kernel
ridge regression try to optimize formula (6), while after using RFF, we try to solve formula (7) in
non-interactive LDP model, which can be easily tackled with similar mechanisms like sparse linear
regression above. Borrow the key result in [30] (restated in lemma 7 below), which used RFF to
design private mechanims for SVM in DP model, it becomes easy to prove guarantees for kernel
ridge regression in our setting (see Corollary 2).
Lemma 7 ([30]). Suppose dual variables with respect to f ∗ , g∗ are L1 norm bounded by some r > 0,
and supx1 ,x2 ∈X |Φ(x1 )T Φ(x2 )−(Φ̂(x1 ))T Φ̂(x2 )| 6 γ, then there is supx∈X |Φ(x)T f ∗ −(Φ̂(x))T g∗ | 6
p
rγ + 2 (CG + r/2)rγ.

√
Corollary 2. Algorithm 4 satisfies (ǫ, δ)-LDP, and by setting dp = Õ
dnǫ2 , with high probability,
there is

1/4 !
d
LĤ (ŵ priv )−LH (f ∗ ) 6 Õ
nǫ2
1/8 !

d
sup |Φ(x)T f ∗ −(Φ̂(x))T ŵ priv | 6 Õ
nǫ2
x∈X
8

Algorithm 4 LDP kernel mechanism
Input: Personal data (xi , yi ), i ∈ [n], random feature’s dimension dp , shift-invariant kernel
R −jsT x
1
k(x1 , x2 ) = k(x1 − x2 ) with Fourier transform f (s) = 2π
e
k(x)dx, privacy parameter ǫ, δ
Output: Private output ŵ priv ∈ Rdp
1: Draw i.i.d. samples s1 , s2 , . . . , sdp ∈ Rd from f (s) and b1 , b2 , . . . , bdp ∈ R from the uniform
distribution on [0, 2π]
2: for i = 1, . . . , n do
i
q h
Construct low dimensional random feature Φ̂(xi ) =
h q q idp
Cˆ := − d1p , d1p
⊂ Rdp

3:

1
dp

cos(sT1 xi + b1 ), . . . , cos(sTdp xi + bdp )

zi ← Basic Private Vector (Φ̂(xi ), ǫ/2, δ/2)
5:
vi ← Basic Private Vector (yi , ǫ/2, δ/2)
6: end for
√
2 2 ln(2.5/δ)
,
7: Setting Z = [z1 , · · · , zn ]T , σ =
ǫ
Q = ProjS+ (Z T Z − nσ 2 Idp ), v = [v1 , · · · , vn ]T
4:

8:

ŵ priv ← argminŵ L̂(ŵ; Z, v), where
1
L̂(ŵ; Z, v) := 2n
ŵ T Qŵ − n1 v T Z ŵ

4

Learning Smooth Generalized Linear Model

In this section, we consider learning smooth generalized linear model in non-interactive LDP setting.
Non-interactive LDP learning for this problem is essentially difficult, as it is even hard to obtain
an unbiased estimator of gradient. We resolve this problem using Chebyshev polynomial expansion,
which requires additional smoothness assumptions. Fortunately these assumptions are naturally
satisfied by a broad range of learning tasks.
We will first define the Smooth GLM loss family with appropriate assumptions. Our definition
could be shown with connection to exponential family GLM, which is commonly used in machine
learning. We also illustrate our algorithm and guarantees with logistic regression.
Definition 2. (Absolutely Smooth Functions) We say that an univariate function h(x) is absolutely
smooth, if for any r > 0, f (x) := h(rx) satisfies the following properties: there exist functions
µ1 (k; r), µ2 (k; r), which are polynomial on k and µ2 (k; r) = O(kr), such that for any k ∈ N+ , there
is:
(1) f (x), f ′ (x), . . . , f (k−1) (x) are absolutely continuous on [−1, 1];
(2)

f (k) (x)

T

6 µ1 (k; r) · µ2 (k; r)k .

Definition 3. (Smooth Generalized Linear Loss, SGLL) A loss function ℓ(w; x, y), is called smooth
generalized linear loss, if for any given data (x, y), ℓ(w; x, y) is convex and β-smooth with respect
to w, and there exist absolutely smooth functions h1 (x), h2 (x), such that ℓ(w; x, y) = −yh1 (xT w) +
h2 (xT w).
It will be convenient to consider population risk directly. Now, we adopt standard setting of learning problems, where each data point (x, y) is drawn from some underlying unknown distribution D
and kxk2 6 1. Given a SGLL ℓ(w; x, y), the population loss is defined as L(w) := E(x,y)∼D ℓ(w; x, y).
9

′

∈

For simplicity, instead of assuming w belongs to B2 (r), we use the following equivalent notation: ℓ(w; x, y) = −yh1 (rxT w) + h2 (rxT w), and the constraint set for w is C = B2 (1). Denote
G(w; x, y) = ∇ℓ(w; x, y) = rm(w; x, y)x, where m(w; x, y) = h′2 (rxT w) − yh′1 (rxT w). Suppose
E(x,y)∼D [kG(w; x, y) − g(w)k22 ] 6 σ02 , where g(w) = ∇L(w). This is a common assumption in
stochastic optimization literature, such as [3].
Given any α > 0, we hope to design a noninteractive local DP mechanism with low sample
complexity, such that the final output point w priv satisfies L(w priv ) − L(w ∗ ) 6 α.
For GLM loss functions, it is easy to see that the stochastic gradient evaluated on w with data
point xi is at the same direction with xi . So adding isotropic noise to xi provides "unbiased"
information about direction of stochastic gradient. However, the magnitude is a nonlinear function
of wT xi , making it hard for SGD even to converge to population minimizer. This is why we seek to
find polynomial approximation of the magnitude of gradients.
To estimate the magnitude of gradients, we use Chebyshev polynomials to approximate nonlinear
univariate function fi (x) = h′i (rx), where x ∈ [−1, 1]. For brevity of notations, we just use f (x)
to represent either f1 (x) or f2 (x). Denote the Chebyshev approximation with degree p as fˆp (x) =
R
Pp
2 1 f (x)T
1
√ k (x) dx is
k=1 ak Tk (x), where Tk (x) is the k-th Chebyshev polynomial, and ak = π −1
2 +
1−x2
the corresponding coefficient. According to existing results about Chebyshev approximations and
some calculations, we have the following lemma:
Lemma 8. Given any α > 0, by setting k = c ln α1 , p = ⌈k + eµ2 (k; r)⌉, where c is a constant, we
6α
have fˆp (x) − f (x)
∞

The
with degree p for fi (x) (i = 1, 2) are denoted as fˆip (x) =
Pp Chebyshev approximations
Pp
k
+ k=1 aik Tk (x) = k=0 cik x , where cik is the coefficient of term xk . Now we approximate
m(w; x, y) and G(w; x, y) as follows:
1
2

m̂(w; x, y) := − y fˆ1p (rxT w) + fˆ2p (rxT w)
=

p
X
(c2k − c1k y)(rxT w)k
k=0

Ĝ(w; x, y) :=r m̂(w; x, y)x

With these approximations, we state our mechanism in Algorithm 5, where Basic Private Vector
mechanism is given in Algorithm 1. Note an important trick in Step 6-8 of Algorithm 5, is that:
we run basic private mechanism p times, to obtain fresh private copies of the same vector x, which
are then used to calculate an unbiased estimation of Ĝ(w; x, y) with variance as low as possible
(i.e. line 8 in Algorithm 6).The LDP property of Algorithm 5 is given as follows: The privacy proof
directly follows from Basic Vector Mechanism and Composition Theorem.
Theorem 4. LDP SGLD Mechanism 5 preserves (ǫ, δ)-LDP.
Having obtained the private synopsis sent by all uers, now the server can construct a stochastic
inexact gradient oracle (defined in Defintion 4) for any point w ∈ C, as stated in Algorithm 6.
Definition 4. [10] For an objective function f (w), a (γ, β, σ) stochastic oracle returns a turple

10

Algorithm 5 LDP SGLD Mechanism - Collection
Input: Personal data (x, y), expansion order p, privacy parameter ǫ, δ
Output: Private synopsis b = {zyi , zj |i ∈ {0} ∪ [p], j ∈ [p(p + 1)/2]} sent to the server
ǫ
δ
ǫ
δ
1: Setting ǫy = 4(p+1)
, δy = 4(p+1)
, ǫ1 = p(p+1)
, δ1 = p(p+1)
2: z0 ← Basic Private Vector(x, ǫ/4, δ/4)
3: for i = 0, 1, . . . , p do
4:
zyj ← Basic Private Vector(y, ǫy , δy )
5: end for
p(p+1)
do
6: for j = 1, . . . ,
2
7:
zj ← Basic Private Vector(x, ǫ1 , δ1 )
8: end for
(Fγ,β,σ (w; ξ), Gγ,β,σ (w; ξ)), such that:
Eξ [Fγ,β,σ (w; ξ)] = fγ,β,σ (w)
Eξ [Gγ,β,σ (w; ξ)] = gγ,β,σ (w)
Eξ [kGγ,β,σ (w; ξ) − gγ,β,σ (w)k2 ] 6 σ 2
β
0 6 h(v, w) 6 kv − wk2 + γ, ∀v, w ∈ C
2
where h(v, w) = f (v) − fγ,β,σ (w) − hgγ,β,σ (w), v − wi.
Algorithm 6 LDP SGLD Mechanism - Learning
Input: Private synopsis b = {zy , zj |j ∈ {0} ∪ [p(p + 1)/2]} of each user, public coefficients
{c1k , c2k |k ∈ {0} ∪ [p]}, initial point w1
Output: Learned classifier w priv
1: for s = 1, . . . , n do
2:
\\ Construct stochastic inexact gradient
3:
\\ Denote the private synopsis of user s as b above for abbreviation
4:
Set t0 = 1
5:
for j = 1, . . . , p do
Qj(j+1)/2
6:
tj = i=j(j−1)/2+1 (wsT zi )
7:
end for
!
p
X
(c2k − c1k zyj )tk r k+1 z0
8:
G̃(ws ; b) ←
k=0

\\ One update via SIGM
10:
Run one iteration of SIGM algorithm with G̃(ws , b) and obtain ws+1
11: end for
12: Set w priv := wn+1
9:

For any (x, y) in the domain, as loss function ℓ(w; x, y) is convex and β-smooth with respect to
w, we can prove the following lemma:
(k; r)⌉, then Algorithm 6 outputs a
Lemma 9. For any γ > 0, setting k = c ln 4r
γ , p = ⌈k + 2µ2

2p+1 (4r)p+1
(γ, β, σ) stochastic oracle defined in Definition 4, where σ = Õ σ0 + γ + p ǫp+2
.
11

Based on above (γ, β, σ) stochastic oracle, and the algorithm proposed in SIGM paper [10]
(omitted here, due to the limitation of space), our complete learning algorithm is given in Algorithm
6. Before proving our sample complexity, we state the basic convergence result of SIGM algorithm:
Lemma 10 ([10]). Assume a function f (w) (suppose constrain set is W) is endowed with a (γ, β, σ)
stochastic oracle, then the sequence wk (corresponds to yk in the original paper) generated by the
SIGM algorithm satisfies:


σ
∗
E[f (wk )] − f (w ) 6 O √ + γ
k
where expectation is over the randomness of the stochastic oracle and w ∗ = argminw∈W f (w).
The accuracy results directly follows from the quality of inexact stochastic gradient oracle we
constructed, and the convergence result of SIGM.
Theorem 5. Consider smooth generalized linear loss. For any setting α > 0, by setting γ = α2 , k =
c ln 4r
γ , p = ⌈k + 2µ2 (k; r)⌉ in Algorithm 5, 6, if
8r
n > O ( )4r ln ln(8r/α)
α



4r
ǫ

2cr ln(8r/α)+2 

1
2
α ǫ2

!

,

we can achieve loss guarantee L(w priv ) − L(w ∗ ) 6 α
As we can see, learning in non-interactive LDP model is more difficult than interactive form,
especially when loss is highly nonlinear, we even can not obtain an unbiased estimation either for
objective function or gradients. However, our method shows it possible to learn smooth GLM with
quasi-polynomial sample complexity.

4.1

Example: Learning Logistic Regression

Either from the view of exponential family generalized linear model or the concrete loss function, it
is not difficult to see logistic lossbelongs to SGLL. For example,
in logistic regression, ℓ(w; x, y) =

Tx
Tx
y T 
1 T
−yw
−w
log(1 + e
) = − 2 w x + 2 w x + ln(1 + e
) . So we let h1 (x) = x2 , h2 (x) = x2 + ln(1 +
e−x ). As we know logistic loss is convex and β-smooth for some parameter β, and the absolutely
smooth property of linear function is obvious, hence once we prove f (x) = ln(1 + e−x ) is absolutely
smooth, then logistic loss satisfies the definition of SGLL.
√
Proposition 1. f (x) = ln(1 + e−x ) is absolutely smooth with µ1 (k; r) = r 4kπ 3 , µ2 (k; r) = rk
e
Hence, we can use private mechanisms (5,6) to learn logistic regression.
Theorem 6. Consider Logistic regression problem with ℓ(w; x, 
y) = log(1 + exp(−yw T x)) For any


8r 4r ln ln(8r/α) 4r 2cr ln(8r/α)+2
1
α > 0, by setting γ = α2 , k = c ln 4r
,
p
=
⌈k+2µ
(k;
r)⌉,
if
n
>
O
(
)
2
γ
α
ǫ
α2 ǫ2

in Algorithm 5, 6, we can achieve L(w priv ) − L(w ∗ ) 6 α.

5

Conclusions

In this paper, we consider how to design efficient algorithms for common learning and estimation
problems under non-interactive LDP model. In particular, for sparse linear regression and mean
12

estimation problem, we propose efficient algorithms and prove the polynomial dependence of excess
risk or square error over log d and n1 , which is exactly to be expected in high dimensional case. We
also extend our methods to nonparametric case and show good bounds for Kernel Ridge Regression.
For more difficult smooth generalized linear loss optimization problems, we use private Chebyshev approximations to estimate gradients of the objective loss, combined with existing inexact
gradient descent methods to obtain final outputs. The sample complexity of our mechanism is
quasi-polynomial with respect to α1 , where α is the desired population excess risk.
An interesting open problem is whether our theoretical guarantees are optimal. If not, how
to improve them while preserving the efficiency in non-interactive LDP model. We think these
problems are critical to understand LDP in the future.

13

References
[1] Raef Bassily and Adam Smith. Local, private, efficient protocols for succinct histograms. In
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages
127–135. ACM, 2015.
[2] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization:
Efficient algorithms and tight error bounds. In Foundations of Computer Science (FOCS), 2014
IEEE 55th Annual Symposium on, pages 464–473. IEEE, 2014.
[3] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and
Trends R in Machine Learning, 8(3-4):231–357, 2015.
[4] K. Chaudhuri and C. Monteleoni. Privacy-preserving logistic regression. In Conference on Neural
Information Processing Systems, British Columbia, Canada, December, pages 289–296, 2008.
[5] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk minimization. The Journal of Machine Learning Research, 12:1069–1109, 2011.
[6] Sjoerd Dirksen. Dimensionality reduction with subgaussian matrices: a unified theory. Foundations of Computational Mathematics, 16(5):1367–1396, 2016.
[7] John Duchi, Martin Wainwright, and Michael Jordan. Minimax optimal procedures for locally
private estimation. arXiv preprint arXiv:1604.02390, 2016.
[8] John Duchi, Martin J Wainwright, and Michael I Jordan. Local privacy and minimax bounds:
Sharp rates for probability estimation. In Advances in Neural Information Processing Systems,
pages 1529–1537, 2013.
[9] John C Duchi, Michael I Jordan, and Martin J Wainwright. Local privacy and statistical minimax
rates. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on,
pages 429–438. IEEE, 2013.
[10] Pavel Dvurechensky and Alexander Gasnikov. Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. Journal of Optimization Theory and Applications,
171(1):121–145, 2016.
[11] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private
data analysis. In Theory of cryptography, pages 265–284. Springer, New York, USA, 2006.
[12] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends R in Theoretical Computer Science, 9(3–4):211–407, 2014.
[13] Vitaly Feldman, Cristóbal Guzmán, and Santosh Vempala. Statistical query algorithms for
mean vector estimation and stochastic convex optimization. In Proceedings of the Twenty-Eighth
Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1265–1277. Society for Industrial
and Applied Mathematics, 2017.
[14] Quan Geng and Pramod Viswanath. The optimal mechanism in differential privacy. In Information Theory (ISIT), 2014 IEEE International Symposium on, pages 2371–2375. IEEE, 2014.
[15] M. Hardt, K. Ligett, and F. Mcsherry. A simple and practical algorithm for differentially
private data release. In Advances in Neural Information Processing Systems, pages 2339–2347,
2012.
14

[16] M. Hardt and G. N. Rothblum. A multiplicative weights mechanism for privacy-preserving
data analysis. In IEEE Symposium on Foundations of Computer Science, pages 61–70, 2010.
[17] Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails.
Journal of Machine Learning Research, 17(18):1–40, 2016.
[18] Peter Kairouz, Keith Bonawitz, and Daniel Ramage. Discrete distribution estimation under
local privacy. In Proceedings of The 33rd International Conference on Machine Learning, pages
2436–2444, 2016.
[19] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. In Advances in neural information processing systems, pages 2879–2887, 2014.
[20] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential
privacy. In Proceedings of The 32nd International Conference on Machine Learning, pages 1376–
1385, 2015.
[21] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Secure multi-party differential privacy.
In Advances in Neural Information Processing Systems, pages 2008–2016, 2015.
[22] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can
we learn privately? In IEEE Symposium on Foundations of Computer Science, pages 531–540,
2008.
[23] Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk minimization
for high-dimensional learning. In Proceedings of The 33rd International Conference on Machine
Learning, pages 488–497, 2016.
[24] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam
Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011.
[25] Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM
(JACM), 45(6):983–1006, 1998.
[26] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. Journal of Machine Learning Research, 1(41):3–1, 2012.
[27] J. Lei. Differentially private m-estimators. In Advances in Neural Information Processing
Systems, pages 361–369, 2011.
[28] MA Qazi and QI Rahman. Some coefficient estimates for polynomials on the unit interval.
Serdica Mathematical Journal, 33(4):449p–474p, 2007.
[29] Ali Rahimi, Benjamin Recht, et al. Random features for large-scale kernel machines. In NIPS,
volume 3, page 5, 2007.
[30] B. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft. Learning in a large function space:
Privacy-preserving mechanisms for svm learning. Journal of Privacy and Confidentiality, 4(1):4,
2012.
[31] A. Smith. Privacy-preserving statistical estimation with optimal convergence rates. In ACM
Symposium on Theory of Computing, STOC, pages 813–822, 2011.

15

[32] Adam Smith and Abhradeep Thakurta. Differentially private model selection via stability
arguments and the robustness of the lasso. J Mach Learn Res Proc Track, 30:819–850, 2013.
[33] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly optimal private lasso. In Advances
in Neural Information Processing Systems, pages 3025–3033, 2015.
[34] J. Thaler, J. Ullman, and S. Vadhan. Faster algorithms for privately releasing marginals. In
International Colloquium on Automata, Languages, and Programming, volume 7391, pages 810–
821. 2012.
[35] Lloyd N Trefethen. Is gauss quadrature better than clenshaw–curtis? SIAM review, 50(1):67–
87, 2008.
[36] Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and
Trends R in Machine Learning, 8(1-2):1–230, 2015.
[37] Roman Vershynin. A note on sums of independent random matrices after ahlswede-winter.
Lecture notes, 2009.
[38] Roman Vershynin. Estimation in high dimensions: a geometric perspective. In Sampling theory,
a renaissance, pages 3–66. Springer, 2015.
[39] Y. Wang, S. E. Fienberg, and A. J. Smola. Privacy for free: Posterior sampling and stochastic
gradient monte carlo. In International Conference on Machine Learning, pages 2493–2502, 2015.
[40] Z. Wang, C. Jin, K. Fan, J. Zhang, J. Huang, Y. Zhong, and L. Wang. Differentially private
data releasing for smooth queries. Journal of Machine Learning Research, 17(51):1–42, 2016.
[41] Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer
bias. Journal of the American Statistical Association, 60(309):63–69, 1965.
[42] Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth
objectives. arXiv preprint arXiv:1703.09947, 2017.
[43] Jun Zhang, Zhenjie Zhang, Xiaokui Xiao, Yin Yang, and Marianne Winslett. Functional
mechanism: regression analysis under differential privacy. Proceedings of the VLDB Endowment,
5(11):1364–1375, 2012.

A
A.1

Appendix
Omitted Proofs in Section 3

Lemma 3. Let x1 , x2 , · · · , xn ∼ i.i.d.D with µ = ED [x] and supp(D) ⊆ B(0, 1). Let G and {yi }ni=1
defined in the above procedure. For each of group Sj fixed, we have the following with probability
2/3:
!
p log(nd)
1 X
p
yi − Gµ ≤ O
(8)
1
|Sj |
ǫ |Sj |
y ∈S
i

j

16

Proof. Apparently

1
|Sj |

P

2 log(1.25/δ)
Id ). So we have k |S1j |
i∈Sj ri ∼ N (0,
|Sj |ǫ2

P

i∈Sj ri k1 ≤ O

with probability 91 . We then turn to bound the loss incurred by random sample of data.
1 X
xi
E µ−
|Sj |

2

i∈Sj

1
≤
|Sj |

d
X
l=1



p√
log n
ǫ |Sj |



d

1 X
=
var(x1l )
|Sj |
l=1

(9)

1
.
E[x21l ] ≤
|Sj |

According to Markov Inequality, we have


1 X
P
µ−
xi

|Sj |
i∈Sj

2


9  1
≥
≤
|Sj |  9

Given x1 , x2 , · · · , xn fixed under this event, we can easily derive upper bounds on entries
q of
d
1 P
1 P
T
G(µ − |Sj | i∈Sj xi ): for g ∼ N (0, Id ) and q = µ − |Sj | i∈Sj xi , we have |g q| ≤ 12 log
|Sj |

with probability 1 −

1
9d .

By union bound we have the following with probability 92 :
1 X
xi )
G(µ −
|Sj |
i∈Sj

1

≤O

s

p log d
|Sj |

!

.

Putting the two inequalities together using union bound, we get the result.
Lemma 6. Under the assumptions made in Section 3.2, given projection matrix Φ, with high probability over the randomness of private mechanism, we have

r
m
priv
∗
(10)
L̄(w
; X̄, y) − L̄(ŵ ; X̄, y) 6 Õ
nǫ2
pm
Proof. Note, once we prove the uniform convergence of |L̂(w; Z, v) − L̄(w; X̄, y)| 6 O
for
nǫ2
any w ∈ C, then the conclusion holds directly. Now, we will prove the uniform convergence. Note
Z = X̄ + E, where E ∈ Rn×m , and each entry eij ∼ N (0, σ 2 ), v = y + r, where r ∼ N (0, σ 2 In ).
Denote w̄ = ΦT w.
L̂(w; Z, v) − L̄(w; X̄, y)

1 T
1 T
w̄ (Q − X̄ T X̄)w̄ −
v Z w̄ − y T X̄ w̄
2n
n
1 T
1
Q − X̄ T X̄ 2 kw̄k22 +
v Z w̄ − y T X̄ w̄
6
2n
n
1
1
6
Q − X̄ T X̄ F kw̄k22 + |v T Z w̄ − y T X̄ w̄|
2n
n
1
T
2
T
6 2n Z Z − nσ Im − X̄ X̄ F kw̄k22 + n1 |v T Z w̄ − y T X̄ w̄|
1
1
6
E T E − nσ 2 Im F kw̄k22 +
X̄ T E F kw̄k22 +
2n
n

1
E T y 2 + X̄ T r 2 + E T r 2 kw̄k2
n
=

17

From the property of random projection, we know kw̄k2 6 1 with high probability. Besides, as
1
E T E − nσ 2 Im 2 6
each entry in E is i.i.d. Gaussian, and E[E T E] = nσ 2 Im , thus we have 2n
 q

q
m
1
O σ lognm with high probability according to lemma 11, hence 2n
E T E − nσ 2 Im F 6 O(σ m log
)
n

with high probability. P
Pm
2
(qjT ei )2 ), where qj , ei are the j-th and i-th column of X̄ and E
As n12 X̄ T E F = n12 m
j=1 ( i=1
P
T
2
respectively. For each j ∈ [m], n12 m
Chi-square distribution (with some scaling),
i=1 (qj ei ) obeys


P
mkq
k2 σ2
m
j
1
thus with high probability, n2 i=1 (qjT ei )2 6 O
. Therefore, by union bound, we have
n2
 P



P
Pm
2
m j kqj k2 σ2
2
1 Pm
T
2
, as j kqj k2 = X̄ F 6 n. Hence, there
= O mσ
j=1 ( i=1 (qj ei ) ) 6 O
n
n2
n2
q

1
mσ2
T
is n X̄ E F 6 O
with high probability. Using similar augument, we have n1 Ē T y 2 6
n
q
q


mσ2
mσ2
1
T
O
, n Ē r 2 6 O
with high probability. For n1 X̄ T r , according to matrix
n
n
 
concentration inequality (Theorem 4.1.1 in [36]), we have n1 X̄ T r 2 6 O √1n .
Combine all these results together, we obtain the desired conclusion.

Lemma 11 ([37]). Suppose x ∈ Rd be a random vector satisfies E[xxT ] = Id . Denote kxkφ1 = M ,
where k·kψ1 represents Orlicz ψ1 -norm. Let x1 , . . . , xn be independent copies of x, then for every
ǫ ∈ (0, 1), we have
!
n
1X
2
2
xi xTi − Id > ǫ 6 de−nǫ /4M
Pr
n
i=1

2

Theorem 3. Under the assumption in this section, set m = Θ
high probability , there is
L(w priv ) − L(w ∗ ) = Õ



log d
nǫ2

p


nǫ2 log d for β > 0, then with

1/4 !

Proof. On one hand,
L(w priv ) − L(w ∗ )

=L(w priv ) − L̄(w priv ) + L̄(w priv ) − L̄(ŵ ∗ )

+ L̄(ŵ ∗ ) − L̄(w ∗ ) + L̄(w ∗ ) − L(w ∗ )


6 L(w priv ) − L̄(w priv ) + L̄(w ∗ ) − L(w ∗ )
+ L̄(w priv ) − L̄(ŵ ∗ )

6G[max{| w priv , xi − ΦT w priv , ΦT xi |}
i

+ max{| hw ∗ , xi i − ΦT w ∗ , ΦT xi |}]
i

+ [L̄(w priv ) − L̄(ŵ ∗ )]

(where G is the Lipschitz constant)

18

(11)

On the other hand, for ∀w ∈ C, ∀x ∈ D, there is
| hw, xi − ΦT w, ΦT x |
2

2

=

kΦT (w+x)k2 −kΦT (w−x)k2

6

kΦT (w+x)k2 −kw+xk22

4

2

4

−

kw+xk22 −kw−xk22
4
2

+

kΦT (w−x)k2 −kw−xk22
4

According to the results of random projection w.r.t. additive error [6], we know with high
q
log d
, for ∀w ∈ C, ∀x ∈ D. Therefore, the
probability, there is | hw, xi − ΦT w, ΦT x | 6 O
m
q

log d
first term in equation (11) is less than O
.
m
pm
holds with high probability. Combine
From lemma 6, we know L̄(w̄ priv ) − L̄(w̄ ∗ ) 6 Õ
nǫ2
these two inequalities, it is easy to determine the optimal m, then obtain the conclusion.
Corollary 2. Algorithm LDP kernel mechanism satisfies (ǫ, δ)-LDP, and with high probability, there
is
 !

d 1/4
priv
∗
LĤ (ŵ
) − LH (f ) 6 Õ
nǫ2
1/8 !

d
sup |Φ(x)T f ∗ − (Φ̂(x))T ŵ priv | 6 Õ
nǫ2
x∈X
Proof. Algorithm satisfies local privacy is obvious. For excess risk, as LĤ (ŵ priv ) − LH (f ∗ ) =
LĤ (ŵ priv ) − LĤ (g∗ ) + LĤ (g ∗ ) − LH (f ∗ ), follow
qnearly
 the same proof of lemma 5 of sparse linear
dp
regression, we have LĤ (ŵ priv ) − LĤ (g∗ ) 6 Õ
. On the other hand, nearly borrow the proof
nǫ2
of Lemma 17 in [30] and property of RRF , we have
∗

∗

LĤ (g ) − LH (f ) 6 Õ

s

d
dp

!


√
dnǫ2 , we obtain the first inequality
Combine above two inequalities, and choose optimal dp as Õ
of the conclusion. Then combine lemma 7 in this paper, it is easy to obtaint the second inequality.

A.2
A.2.1

Omitted contents and proofs in Section 4
Relations between smooth generalized linear losses (SGLL) and generalized
linear models (GLM)

Note that a model is called GLM, if for x, w ∗ ∈ Rd , label y with respect to x is given by a
distribution which belongs to the exponential family:


yθ − b(θ)
∗
+ c(y, Φ)
(12)
p(y|x, w ) = exp
Φ
19

where θ, Φ are parameters, and b(θ), c(y, Φ) are known functions. Besides, there is an one-to-one
continuous differentiable transformation g(·) such that g(b′ (θ)) = xT w ∗ .
According to the key equality g(b′ (θ)) = xT w ∗ , usually we can obtain smooth function θ =
h1 (xT w ∗ ), b(θ) = h2 (xT w ∗ ), and what’s more, univariate function hi (x)(i = 1, 2) satisfies the
absolutely smooth property.
For such GLM, if we consider optimizing the expected negative logarithmic probability −E(x,y)∼D log p(x, y; w),
once discarding unrelated terms to w, we obtain the new population loss, L(w) := E(x,y)∼D ℓ(w; x, y),
where ℓ(w; x, y) = −yh1 (xT w) + h2 (xT w), exactly the form of smooth generalized linear loss defined in section 4. Hence our SGLL is a natural loss defined by GLM with additional smoothness
assumptions.
A.2.2

Omitted proofs

Lemma 8. Given any α > 0, by setting k = c ln α1 , p = ⌈k + eµ2 (k; r)⌉, where c is a constant, we
6 α.
have fˆp (x) − f (x)
∞

Proof. As f, f ′ , · · · , f (k−1) are absolutely continuous over [−1, 1], and f (k)
according to the results in [35], we have
fˆp (x) − f (x)

T

6 µ1 (k; r)µ2 (k; r)k ,

2 f (k) T
πk(p − k)k
2µ1 (k; r)
6
πkek
6

∞

(13)

It is easy to see there exists c > 0, such that the term (13) is less than α with chosen k, hence the
conclusion holds.
Lemma 9. For any γ > 0, setting k = c ln 4r
(k; r)⌉, then algorithm 7 outputs a
γ , p = ⌈k + 2µ
2

p2p+1 (4r)p+1
.
(γ, β, σ) stochastic oracle, where σ = Õ σ0 + γ +
ǫp+2

Proof. According to lemma 8, we know the approximation error, |m̂(w; x, y) − m(w; x, y)| 6
γ
2r . For any fixed (x, y), from the construction of stochastic inexact gradient oracle, there is
E[G̃(w; b)|x, y] = Ĝ(w; x, y). Denote ĝ(w) = E(x,y)∼D [Ĝ(w; x, y)], thus we have
E



G̃(w; b) − ĝ(w)

2





2



G̃(w; b) − Ĝ(w; x, y)


2
+ E Ĝ(w; x, y) − ĝ(w)

=E

For above two terms, combined with results given in lemma 12, we we obtain



2 !
2
r(2rp)p+1
E G̃(w; b) − g(w)
6 Õ
+ γ + σ0
ǫp+2
.
As L(v) − L(w) − ĝ(w)T (v − w) = L(v) − L(w) − g(w)T (v − w) + (g(w) − ĝ(w))T (v − w),
and from the approximation error, we know |(g(w) − ĝ(w))T (v − w)| 6 γ2 . What’s more, as L(w)

20

is convex and β-smooth, that is 0 6 L(v) − L(w) − g(w)T (v − w) 6
inequalities, we obtain
− γ2 6 L(v) − L(w) − ĝ(w)T (v − w) 6

β
2

β
2

kv − wk2 . Combined these

kv − wk2 +

⇐⇒0 6 L(v) − (L(w) − γ2 ) − ĝ(w)T (v − w) 6

β
2

γ
2
2

kv − wk + γ

Note the function value oracles in the stochastic oracle definition (either Fγ,β,σ (·) or fγ,β,σ (·)) do
not play any role in the optimization algorithm, hence we can set it as L(w) − γ2 , though we do not
know how to calculate.
Lemma 12. Based on above statements, we have


 4p+2

2
p
(4r)2p+2
6 Õ
E G̃(w; b) − Ĝ(w; x, y)
ǫ2p+4


2
E Ĝ(w; x, y) − ĝ(w)
6 (γ + σ0 )2
Qj(j+1)/2
Proof. First, we calculate the variance of each tk , var(tj ) 6 i=j(j−1)/2+1 (var(w T zi )+(E[w T zi ])2 ) 6


2j .
Õ ( p(p+1)
)
ǫ
Next, we upper bound
Pp the coefficient ck (as it is the same for c1k and c2k , hence we use ck
for short). Note ck = m=k am bmk , where am is the coefficient of original function represented
by Chebyshev basis, bmk is the coefficient of order k monomial in Chebyshev basis Tm (x), where
0 6 k 6 m. According to the formula of Tm (x) given in [28] and well-known Stirling’s approximation,
after some translation, we have
m 


√
(1 − θ)1−θ
|bmk | 6 max O
m· θ
θ (1 − 2θ)1−2θ
θ∈(0, 21 )
√ m
6O m2
Besides, from the absolutely
smooth property
of h′i (x)(i ∈ {1, 2}) and the convergence results in

P
p
[35], we have am 6 O m12 , thus ck = m=k am bmk 6 O (2p ). Hence, there is
i
i
h
h
var (c2k − c1k zy )tk r k+1 6r 2k+2 E ((c2k − c1k zy )tk )2
 4k+2

p
(4r)2p+2
6O
ǫ2k+2

As each (c2k − c1k zy )tk r k+1 is independent with each other (for different k), which leads to
" p
#
 4p+2

X
p
(4r)2p+2
k+1
var
6O
(c2k − c1k zy )tk r
ǫ2p+2
k=0

Moreover, var(z0 ) 6 O


1

ǫ2

E



. Therefore,
G̃(w; b) − Ĝ(w; x, y)

2

21



6 Õ



p4p+2 (4r)2p+2
ǫ2p+4



For second inequality in the conclusion, there is


2
E Ĝ(w; x, y) − ĝ(w)
6E



Ĝ(w; x, y) − G(w; x, y) + G(w; x, y) − g(w) + g(w) − ĝ(w)

6γ 2 + σ02 + 2σ0 γ = (γ + σ0 )2

2



√
Proposition 2. f (x) = ln(1 + e−x ) is absolutely smooth with µ1 (k; r) = r 4kπ 3 , µ2 (k; r) =

rk
e

Proof. For any r, k > 0, the absolutely continuous of f (k) (rx) is obvious, now consider f (k+1) (rx)
f

(k+1)
T

=

Z

1

−1

T

:

|f (k+2) (rx)|
√
dx
1 − x2

6π f (k+2) (rx)
6πrk+2
6πr k+2

Pk+1

∞

k+j A
j
k+1,j−1 f (1
j=1 (−1)

k+1
X

− f )k+2−j

∞

Ak+1,j−1

j=1

6π(k + 1)!r k+2
√
6 4π 3 r k+2 (k + 1)k+3/2 e−k−1


p
r(k + 1) k+1
3
=r 4π (k + 1)
e
Theorem 6. For any α > 0, set γ = α2 , k = c ln 4r
, p = ⌈k + 2µ2 (k; r)⌉, if
 γ



2cr
ln(8r/α)+2
1
4r ln ln(8r/α) 4r
, using Algorithms 5 and 6, then we have L(w priv )−
n > O ( 8r
α)
ǫ
α2 ǫ2
L(w ∗ ) 6 α.
Proof. According
oracle, SIGM algorithm
converges 
with
 to lemma 10 , with a (γ,
 β, σ) stochastic

 4p+2

p
(4r)2p+2
σ
σ
√
√
+ γ . In order to have O
+ γ 6 α, it suffices if n > O
=
rate O
α2 ǫ2p+4
n

 n
 2p+1 p+1 


2cr
ln(8r/α)+2
p
(4r)
1
4r ln ln(8r/α) 4r
O ( 8r
, as σ = O
according to lemma 9 (ignoring
α)
ǫ
α2 ǫ2
ǫp+2
negligible σ0 , γ).

22

