Faster Rates of Private Stochastic Convex Optimization

In this paper, we revisit the problem of Differentially Private Stochastic Convex Optimization (DP-SCO) and provide excess population risks for some special classes of functions that are faster than the previous results of general convex and strongly convex functions. In the first part of the paper, we study the case where the population risk function satisfies the Tysbakov Noise Condition (TNC) with some parameter $\theta>1$. Specifically, we first show that under some mild assumptions on the loss functions, there is an algorithm whose output could achieve an upper bound of $\tilde{O}((\frac{1}{\sqrt{n}}+\frac{\sqrt{d\log \frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$ for $(\epsilon, \delta)$-DP when $\theta\geq 2$, here $n$ is the sample size and $d$ is the dimension of the space. Then we address the inefficiency issue, improve the upper bounds by $\text{Poly}(\log n)$ factors and extend to the case where $\theta\geq \bar{\theta}>1$ for some known $\bar{\theta}$. Next we show that the excess population risk of population functions satisfying TNC with parameter $\theta\geq 2$ is always lower bounded by $\Omega((\frac{d}{n\epsilon})^\frac{\theta}{\theta-1}) $ and $\Omega((\frac{\sqrt{d\log \frac{1}{\delta}}}{n\epsilon})^\frac{\theta}{\theta-1})$ for $\epsilon$-DP and $(\epsilon, \delta)$-DP, respectively. In the second part, we focus on a special case where the population risk function is strongly convex. Unlike the previous studies, here we assume the loss function is {\em non-negative} and {\em the optimal value of population risk is sufficiently small}. With these additional assumptions, we propose a new method whose output could achieve an upper bound of $O(\frac{d\log\frac{1}{\delta}}{n^2\epsilon^2}+\frac{1}{n^{\tau}})$ for any $\tau\geq 1$ in $(\epsilon,\delta)$-DP model if the sample size $n$ is sufficiently large.

for -DP and ( , δ)-DP, respectively when θ ≥ 2, here n is the sample size and d is the dimension of the space. Then we address the inefficiency issue, improve the upper bounds by Poly(log n) factors and extend to the case where θ ≥θ > 1 for some knownθ. Next we show that the excess population risk of population functions satisfying TNC with parameter θ ≥ 2 is always lower bounded by Ω(( d n ) θ θ−1 ) and Ω(( √ d log(1/δ) n ) θ θ−1 ) for -DP and ( , δ)-DP, respectively, which matches our upper bounds. In the second part, we focus on a special case where the population risk function is strongly convex. Unlike the previous studies, here we assume the loss function is non-negative and the optimal value of population risk is sufficiently small. With these additional assumptions, we propose a new method whose output could achieve an upper bound of O( d log(1/δ)

Introduction
Preserving the privacy of training data has become an important consideration and now is a challenging task for machine learning algorithms. To address the privacy issue, Differential Privacy (DP) (Dwork et al., 2006), which roots in cryptography, is a strong mathematical scheme for privacy preserving. It allows for rich statistical and machine learning analysis, and is now becoming a de facto notation for private data analysis. Methods to guarantee differential privacy have been widely studied, and recently adopted in industry (Tang et al., 2017;Ding et al., 2017).
As one of the most important problems in Machine Learning and Differential Privacy community, the Empirical Risk Minimization problem in the DP model, i.e., DP-ERM, has been studied quite well in the last decade, starting from (Chaudhuri et al., 2011), such as (Bassily et al., 2014;Wang et al., 2017Wang et al., , 2019aWu et al., 2017;Kasiviswanathan and Jin, 2016;Kifer et al., 2012;Smith et al., 2017;Wang et al., 2018aWang et al., , 2019bAsi et al., 2021a). Besides DP-ERM, its population (or expected) version, namely Differentially Private Stochastic Convex Optimization (DP-SCO), has received much attention in recent years, starting from (Bassily et al., 2014). Specifically, (Bassily et al., 2019) first provides the optimal rate of DP-SCO with general convex loss functions in ( , δ)-DP, which is quite different from the optimal rate in DP-ERM. Later, (Feldman et al., 2020) extends this problem to strongly convex and (or) non-smooth cases by providing a general localization technique. Moreover, their methods have linear time complexity if the loss functions are smooth. For non-smooth loss functions, (Kulkarni et al., 2021) recently proposes a new method which only need subquadratic gradient complexity. While there are already a large number of studies on DP-SCO, the problem is still far from well understood. A key observation is that, all of the previous works only focus on the the case where the loss functions are either general convex or strongly convex. However, there are also many problems that are even stronger than strongly convex functions, or fall between convex and strongly convex functions. In the non-private counterpart, various studies have attempted to get faster rates by imposing additional assumptions on the loss functions. And it has been shown that it is indeed possible to achieve rates that are faster than the rates of general convex loss functions (Yang et al., 2018;Koren and Levy, 2015;van Erven et al., 2015), or it could even achieve the same rate as in the strongly convex case even if the function is not strongly convex (Karimi et al., 2016;Liu et al., 2018;Xu et al., 2017). Motivated by this, our question is, For the problem of DP-SCO with special classes of population risk functions, is it possible to achieve faster rates of the excess population risk than the optimal ones of general convex and (or) strongly convex cases?
In this paper, we provide an affirmative answer by studying some classes of population risk functions. Particularly, we will mainly focus on the case where the population risk satisfies the Tysbakov Noise Condition (TNC) 1 , which includes strongly convex functions, SVM and linear regression as special cases. Our contributions can be summarized as follows.
• In the first part of the paper, we study the problem where the population risk satisfying TNC with parameter θ and propose three methods. When θ ≥ 2, we first propose a method that could achieve an excess population risk of O(( 1 √ n + d n ) θ θ−1 ) and O(( 1 √ n + √ d log(1/δ) n ) θ θ−1 ) in -DP and ( , δ)-DP model respectively under the assumption that the loss function is smooth and Lipschitz, where n is the sample size of the data and d is the dimension of the space. We then propose another method to resolve the inefficiency issue under the assumption that θ is known. Moreover, we propose an improved method. Compared with previous two methods, it improves the upper bounds of error by Poly(log n) factors. And it only needs a relaxed assumption of θ ≥θ > 1 for some knownθ instead of θ being known or θ ≥ 2. Moreover, it outperforms the previous methods practically. Next, we focus on the lower bounds of the excess population risk. Specifically, for any θ ≥ 2, we show that there is a population risk function satisfying TNC with parameter θ such that for any -DP (( , δ)-DP) algorithm, its output achieves an excess risk of Ω(( d n ) θ θ−1 ) ( Ω(( √ d log(1/δ) n ) θ θ−1 )) with high probability.
• In the second part of the paper, we will focus on the problem where the population risk function is strongly convex, which is a special case of TNC functions with θ = 2. Unlike the previous studies, here we assume the loss function is non-negative and the optimal value of the population is sufficiently small. With these additional assumptions, we propose a new method whose output could achieve an upper bound of O( d log(1/δ) n 2 2 + 1 n τ ) and O( d 2 n 2 2 + 1 n τ ) for any τ > 1 in ( , δ)-DP and -DP model respectively if the sample size n is sufficiently large. These rates circumvent their corresponding lower bounds for general strong convex functions in (Feldman et al., 2020), i.e., Θ( d 2 n 2 2 + 1 n ) for -DP and Θ( d log(1/δ) n 2 2 + 1 n ) for ( , δ)-DP.
Due to the space limit, all the experiments (Appendix B) and proofs are included in Appendix.

Related Work
Starting from (Chaudhuri et al., 2011), a long list of works have attacked the problems of DP-ERM from different perspectives: (Bassily et al., 2014;Iyengar et al., 2019;Zhou et al., 2020;Song et al., 2020;Wang et al., 2017;Zhang et al., 2017) studied the problems in the low dimensional case and the central model, (Kasiviswanathan and Jin, 2016;Kifer et al., 2012;Talwar et al., 2015;Wang and Gu, 2020;Cai et al., 2020) considered the problems in the high dimensional sparse case and the central model, (Smith et al., 2017;Duchi et al., 2013;Wang et al., 2020a;Duchi et al., 2018) focused on the problems in the local model. However, almost all of these works only focus the case where the empirical risk function is either general convex or strongly convex. For special class of functions, (Wang et al., 2017) studies the empirical risk functions satisfying Polyak-Lojasiewicz (PL) condition, which is weaker than strongly convexity and show that it is possible to achieve an excess empirical risk of O( d log(1/δ) n 2 2 ), which is the same as the strongly convex loss. As we will mention in Remark 16, the PL condition is equivalent to TNC with parameter θ = 2. Thus, in this paper we extend the result from the empirical risk to the population risk function.
For DP-SCO, besides the related work we mentioned in the previous section, there is another direction which studies some special cases of DP-SCO. For example, (Bassily et al., 2021) and (Asi et al., 2021a) consider the case where the underlying constraint set W has specific geometric structures, such as polyhedron. (Guzmán et al., 2021) studies the (non)smooth and (non)convex generalized linear loss. (Wang et al., 2020b) and(Kamath et al., 2021) focus on the case where the distribution of the data or the gradient of the loss function is heavy-tailed. However, none of these works study the case where the population risk satisfies TNC. (Liu et al., 2021) recently studies the theoretical guarantees of the PATE model (Papernot et al., 2016) under the assumption that the population risk function satisfies TNC and shows that it is possible to achieve faster rates than in the convex case (Bassily et al., 2018). However, since here we focus on a different problem, their results cannot be used to DP-SCO.
Concurrent Work: We notice that (Asi et al., 2021b) also studies DP-SCO with TNC population risk functions concurrently. However, compared with its results there are several critical differences.
1) The idea of Algorithm 2 in (Asi et al., 2021b) is similar to Algorithm 2 in our paper. However, the idea of proof and the choice of parameters are quite different.
2) The same as Algorithm 2, Algorithm 2 in (Asi et al., 2021b) is also inefficient and has poor performance in practice. To resolve the issue, we also develop two other algorithms (Algorithm 3 and 5).
3) For ( , δ)-DP model, (Asi et al., 2021b) only shows the worst-case lower bound of Ω(( √ d log(1/δ) n ) θ θ−1 ) under the assumption θ ≥ 1 + c for some constant c > 0 while in this paper we also extend the result to θ ≥ 2. Although the hard instance in (Asi et al., 2021b) is similar to ours, the proofs of lower bounds are different. 4) In this paper, we also provide experimental results on the problem which has not been studied in (Asi et al., 2021b). 5) Besides TNC population risk functions, in this paper we also provide faster rates of DP-SCO with strongly convex loss function with additional assumptions which also has not been studied in (Asi et al., 2021b).

Preliminaries
Definition 1 (Differential Privacy (Dwork et al., 2006)) Given a data universe X , we say that two datasets S, S ⊆ X are neighbors if they differ by only one entry, which is denoted as S ∼ S . A randomized algorithm A is ( , δ)-differentially private (DP) if for all neighboring datasets S, S and for all events E in the output space of A, the following holds Pr(A(S) ∈ E) ≤ e Pr(A(S ) ∈ E)+δ.
Definition 4 (DP-SCO (Bassily et al., 2014)) Given a dataset S = {x 1 , · · · , x n } from a data universe X where x i are i.i.d. samples from some unknown distribution D, a convex loss function f (·, ·), and a convex constraint set W ⊆ R d , Differentially Private Stochastic Convex Optimization (DP-SCO) is to find w priv so as to minimize the population risk, i.e., F (w) = E x∼D [f (w, x)] with the guarantee of being differentially private. The utility of the algorithm is measured by the (expected) excess population risk, that is E A [F (w priv )] − min w∈W F (w), where the expectation of A is taken over all the randomness of the algorithm. Besides the population risk, we can also measure the empirical risk of dataset S: Definition 7 A function F : W → R is λ-strongly convex over the domain W if, for all w, w ∈ W,F (w) + ∇F (w), w − w + λ 2 ||w − w|| 2 2 ≤ F (w ). Let w * = arg min w∈W F (w) be the minimizer, strongly convexity implies (Hazan and Kale, 2011): Previous work on DP-SCO only focused on case where the loss function is either convex or strongly convex (Bassily et al., 2019;Feldman et al., 2020). In this paper, we will mainly study the case where the population risk satisfies the Tysbakov Noise Condition (TNC) (Ramdas and Singh, 2012;Liu et al., 2018), which has been studied quite well and has been shown that it could achieve faster rates than the optimal one of general convex loss functions in the non-private case. Below we provide the definition of TNC.
Definition 8 For a convex function F (·), let W * = arg min w∈W F (w) denote the optimal set and for any w ∈ W, let w * = arg min u∈W * u − w 2 denote the projection of w onto the optimal set W * . Function F satisfies (θ, λ)-TNC for some θ > 1 and λ > 0 if for any w ∈ W the following inequality holds From the definition of TNC and (1) we can see that for a λ-strong convex function it is (2, λ 2 )-TNC. Moreover, if a function is (θ, λ)-TNC, then it is also (θ , λ)-TNC for any θ < θ . Throughout the whole paper we will assume that θ is a constant and thus we will omit the term of c θ in the Big-O notation if c is a constant.

Upper Bounds of Excess Population Risk
In this section, we will concentrate on the case where the population risk function is (θ, λ)-TNC and provide some upper bounds of its excess population risk. To provide a clear intuition of our methods, we will first assume that the loss functions are smooth. Later we will extend to the non-smooth case.
We first consider an easier case, where the TNC parameter θ satisfies θ ≥ 2. Our algorithm is based on the localization technique proposed by (Feldman et al., 2020), which provides an algorithm, namely Phased-SGD (Algorithm 1) for DP-SCO with general convex loss functions and shows that the algorithm could achieve the optimal rate of excess population risk. } and if η ≤ 1 β (i.e., n is sufficiently large), then Algorithm 1 will be ( , δ)-DP for all ≤ 2 log(1/δ).

The output satisfies
β , then Algorithm 1 will be -DP. Moreover, the output satisfies Algorithm 1: Phased-SGD(w 0 , η, n, W) algorithm (Feldman et al., 2020) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, step size η (will be specified later), privacy parameter and (or) δ. Set k = log 2 n . Partite the whole dataset S into k subsets {S 1 , · · · , S k }. Denote n i as the number of samples in S i , i.e., |S i | = n i , where n i = 2 −i n .
We propose our adaptive stochastic approximation algorithm, which is presented in Algorithm 2. The updates are divided into m stages. At each stage, the Phased-SGD algorithm is applied with n 0 samples. Each employment of the Phased-SGD algorithm is warm-started by the initial point that is returned from the last stage.
with centerŵ k−1 and radius R k−1 . The Phased-SGD runs on the k-th subset S i . end returnŵ m The following theorem states that, the output of Algorithm 2 achieve an excess population risk for -DP and ( , δ)-DP, respectively, if the population risk function satisfies TNC with θ ≥ 2.
Theorem 11 Assume that F (·) satisfies (θ, λ)-TNC and f (·, x) is convex, β-smooth and L-Lipschitz for each x. Then Algorithm 2 is -DP or ( , δ)-DP based on different stepsizes {γ k } m k=1 and noises if γ k ≤ 1 β . Moreover, if n is sufficiently large such that n ≥ 256, for ( , δ)-DP we have In practice, the main difficulty on implementing Algorithm 2 is the projection onto the ball W ∩ B(ŵ k−1 , R k−1 ) in each iteration of the Phased-SGD in each phase. In practice, this could be solved by using the Dykstra's algorithm (Dykstra, 1983;Boyle and Dykstra, 1986), which studied the best approximation problem: given m closed and convex sets W 1 , · · · , W m ⊆ R d and a point y ∈ R d , we seek the point in W 1 · · · W m (assumed nonempty) closest to y, and solve min u∈W 1 ··· Wm u−y 2 . However, in theory, the theoretical guarantee of Theorem 11 may not be held if we use the Dykstra's algorithm under the privacy constraint. The main reason is that, Dykstra's algorithm can only provide an approximate solution of the projection step. However, the approximate solution may not have the same 2 (or 1 )-norm sensitivity as the exact solution. Thus, from this view, Algorithm 2 lacks of efficiency. Instead of using the Dykstra's algorithm, motivated by (Xu et al., Algorithm 3: Phased-SGD-SC(w 0 , γ, , δ) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, privacy parameter and (or) δ. D is a constant satisfying D ≥ w 0 − w * 2 . Partite the data S into k disjoint subsets {S 1 , · · · , S k }, where k = log log n and for each i ∈ [k], |S i | = n i = 2 i−2 n/ log n . for t = 1, · · · , k do Let w t = Phased-SGD(w t−1 , η t , n t , W), where the Phased-SGD runs on the t-th subset S i with loss function f (w, , in the following, we present a new algorithm which only needs the projection onto W. Briefly speaking, instead of considering the original stochastic function, we focus on the problem with an additional strongly convex regularization, i.e., min w∈W F (w) + 1 2γ w − w 1 2 2 , where w 1 ∈ W is some reference point and γ is some parameter. Specifically, the same as in Algorithm 2, we first divide the whole algorithm into m stages. In each stage we hope to find a private estimator w k such that w k ≈ arg min w∈W F (w) + 1 2γ k w − w k−1 2 2 with γ k changing with k. Specifically, we use Algorithm 3 to get such private estimator. Note that due to the additional 2 regularization, now the function is strongly convex. Thus, instead of using the original Phased-SGD (Algorithm 1) for general convex loss, here we use a strongly convex version of Phased-SGD, which is adopted from (Feldman et al., 2020). Moreover, since now we have an additional 2 -norm regularization, here we do not need the projection onto the balls W ∩ B(ŵ k−1 , R k−1 ) during updates compared with Algorithm 2.
Theorem 12 Assume that F (·) satisfies (θ, λ)-TNC and f (·, x) is convex, β-smooth and L-Lipschitz for each x. If n is sufficiently large such thatθ ≥ 2 log log n log n , then Algorithm 4 is -DP or ( , δ)-DP Algorithm 4: Private Stochastic Approximation-II(w 0 , n, R 0 ) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, privacy parameter and (or) δ. χ 0 is a constant such that . So far we have proposed two algorithms. However, there are still several issues: First, both of the previous methods need strong assumption on θ. Algorithm 4 needs θ to be known in advance while Algorithm 2 needs to assume θ ≥ 2. Thus, can we develop a method that only needs a weaker assumption on θ? Secondly, both of the previous two algorithms could achieve rates for -DP and ( , δ)-DP, respectively. Can we further improve these bounds? Thirdly, the two methods are either impractical or inefficient. Specifically, for Algorithm 4, as we can see from our theoretical analysis, we need to exactly set γ 0 )) in the ( , δ)-DP model, which is quite large and is difficult to get. And we can see that in Theorem 12 we can only guarantee there exists a w k that achieves the upper bound of error, it is still unknown how to find such w k privately with the same theoretical guarantees. For Algorithm 2, as we will see in the experiment part, it even does not outperform the previous Phased-SGD method (Algorithm 1), which means that its performance is quite poor. Thus, how to design improved methods both theoretically and practically? In the following we will focus on these three issues by developing a new method.
The idea of our algorithm is as the following: assuming that the value of θ is unknown, but θ is lower bounded by some known constantθ > 1, namely θ ≥θ > 1. We first divide the whole dataset into k = (logθ 2) · log log n disjoint subsets, where the i-th subset has n i = 2 i−1 n/(log n) logθ 2 samples; then we repeat the Algorithm 1 for k times where each phase runs on the i-th subset and is initialized at the output of the previous phase. See Algorithm 5 for details.
Remark 13 Although both Algorithm 5 and 2 partite the data into several parts and perform the Phased-SGD several times. There are several differences: First, the sizes of subsets in Algorithm Algorithm 5: Iterated Phased-SGD(w 1 , n, W,θ) end return w k 2 are equal, while we partite the data aggressively in Algorithm 5. Secondly, in each phase of Algorithm 5, the convex set to be projected is invariant while in Algorithm 2 we constantly replace it to W ∩ B(ŵ k−1 , R k−1 ), which is necessary based on our theoretical analysis.
Theorem 14 Assume that F (·) is (θ, λ)-TNC with θ ≥θ > 1 for some known constantθ, and f (·, x) is convex, β-smooth and L-Lipschitz for each x. If the sample size n is sufficiently large such thatθ ≥ 2 log log n (log n)−1 , then Algorithm 5 is either -DP or ( , δ)-DP for any ≤ 2 log(1/δ), based on different step sizes and noises under the assumption that η t ≤ 1 β . Moreover, for ( , δ)-DP, the output Remark 15 Compared with the previous results, we can see the upper bounds in Theorem 14 improve factors of Poly(log n) in both -DP and ( , δ)-DP models. Moreover, instead of θ ≥ 2, we only need the assumption of θ ≥θ for some knownθ > 1 in Theorem 14. And as we will see in the experimental part, Algorithm 5 outperforms all previous methods.
Remark 16 We can see that it is possible to get faster rates than the rates of strongly convex loss if θ < 2. For example, when θ = 3 2 , the upper bound of error becomes ) 3 ) in the ( , δ)-DP model. Moreover, when θ > 1, then the bounds will be always higher than the optimal rate for general convex loss as θ θ−1 > 1. When θ = 2, we have an excess population risk for -DP and ( , δ)-DP respectively, which matches the optimal rate of DP-SCO with strongly convex function (Feldman et al., 2020). Besides strongly convex functions, there are other problems that satisfy (2, λ)-TNC, such as the functions satisfying Weak Strong Convexity, Restricted Secant Inequality (RSI), Error Bound (EB) and Polyak-Lojasiewicz (PL) conditions (see Section 2.1 in (Karimi et al., 2016) for details). Thus, Theorem 14 with θ = 2 could be seen as a generalization of the strongly convex case. For Polyak-Lojasiewicz (PL) functions, (Wang et al., 2018b) shows an upper bound of O( d log(1/δ) n 2 2 ) for the empirical risk. However, their method cannot be extended to the population risk. In the following we provide some examples that satisfy TNC with θ = 2.
Lemma 17 (Quadratic Problem (Liu et al., 2018)) Consider the quadratic problem (1)) and W is a bounded polyhedron (e.g., 1 -norm or ∞ -norm ball), then the population risk function will be TNC with θ = 2 and the problem will satisfy the assumptions in Theorem 14.
By Lemma 17 we can see that for the linear regression problem where F (w) = E(x T w − y) 2 over a bounded polyhedron W. It is possible to achieve an upper bound of O( 1 n + d log(1/δ) n 2 2 ) and O( 1 n + d 2 n 2 2 ) for the excess population risk in the ( , δ)-DP and -DP model, respectively. Lemma 18 (SCO over 2 -norm ball (Liu et al., 2018)) Consider the problem of SCO over 2 -norm ball min is convex, smooth and Lipschitz, and min w∈R d F (w) < min w 2 ≤B F (w). Then the population risk is TNC with θ = 2 and satisfies the assumptions in Theorem 14.
So far, we provided several methods for TNC population risk functions under the assumption that the loss function is smooth. We can extend the previous methods to the non-smooth case, see Appendix A for details.

Lower Bounds of Excess Population Risk
In the previous section, we provide an algorithm whose output could achieve an excess population for -DP and ( , δ)-DP respectively. The question is, can we further improve these bounds? In this section, we show that for all θ ≥ 2, the θ θ−1 ) cannot be further improved. We consider the following loss function. Define Theorem 19 (Lower bound of ( , δ)-DP ) Let n, d ∈ N, θ ≥ 2, > 0 and δ = o( 1 n ) such that n ≥ Ω( √ d } d such that with probability at least 1 3 over the randomness of the algorithm, its output w priv satisfies where loss function is given by (3)  Theorem 20 (Lower bound of -DP ) Let n, d ∈ N, θ ≥ 2 and > 0 such that n ≥ Ω( √ d } d such that with probability at least 1 3 over the randomness of the algorithm, its output w priv satisfies where loss function is given by (3) which is O(1)-Lipschitz, and the population risk satisfies (θ, O(1))-TNC.
Remark 21 From the above theorems, we can see that for the case where θ = 2, the loss function in (3) is reduced to the squared loss, which was used to the lower bound proof of strongly convex loss in (Bassily et al., 2014).

Improved Rates for Strongly Convex Loss
In the previous section, we showed upper and lower bounds of the excess population risk for general TNC population risk functions. Moreover, from Theorem 26 we can see that we get asymptotically the same bound for smooth and non-smooth loss functions in the ( , δ)-DP model. However, in the non-private case, it has been shown that for the strongly convex loss functions, it is possible to get an improved rate compared with the non-smooth ones (Zhang and Zhou, 2019). Thus, our question is, can we get improved rates if the loss functions have additional properties? In the following we will study the strongly convex loss case. Specifically, we will show that when the loss function f (·, x) has additional assumptions on non-negativity and if the optimal value F (w * ) is sufficiently small, it is possible to achieve an upper bound of O( d log(1/δ) n 2 2 + 1 n τ ) for any τ > 1 if the sample size n is sufficiently large.
There are two parts in the algorithm. In the first part, we perform the original Iterated Phased-SGD (Algorithm 5) on the first half of the data to get a good solution to the optimal parameter w * . After that we perform a new method, namely Epoch-DP-SGD (Algorithm 6) on the second half of the data, which may also be used in other problems. We note that although Algorithm 6 and Algorithm 1 both perform the original DP-SGD algorithm in (Bassily et al., 2014) for several phases or epochs.
They are quite different: First, as the phase/epoch increases, we decrease the size of the subset (or the number of iterations) in Algorithm 1. While in Algorithm 6 we will increase the size of the subset (or the number of iterations). As we will see in the proof, this increase is necessary. Secondly, the initial size of the subset in Algorithm 1 is n 2 while it is 2 2τ +3 κ in Algorithm 6, where κ is the condition number κ = β/λ of the population risk functions.
For -DP, the output returned by algorithm 7 satisfies We note that recently (Wang et al., 2020b) also showed that when the loss function is non-negative and the optimal value of the population risk is small, it is possible to get a non-trivial upper bound for DP-SCO. However, there are some differences: Firstly, (Wang et al., 2020b) only studied the case of DP-SCO with heavy-tailed data while here we study DP-SCO with strongly convex functions. Thus, the problems are different. Moreover, their method is based on the sample-and-aggregate framework, which is impractical, and their result is O( d 3 F (w * ) n 4 ) under the assumption that ∇F (w * ) = 0, which may not hold in the case where W is a close set. Compared with their work, we do not need such strong assumption and in general our bound is much smaller than theirs for F (w * ) = O(1).
Remark 24 Theorem 23 implies that when n = Ω(κ τ ), the output of Algorithm 7 achieves excess population risks of O( d log(1/δ) n 2 2 + F (w * ) n + 1 n τ ) and O( d 2 n 2 2 + F (w * ) n + 1 n τ ) for ( , δ)-DP and -DP, respectively, which are faster than the optimal rates of O( 1 n + d log(1/δ) n 2 2 ) and O( d 2 n 2 2 + 1 n ) for general strongly convex loss functions, under the assumption that the optimal risk F (w * ) is relatively small. It is also notable that the bounds in Theorem 23 have exponential dependence on the parameter τ , which means τ also cannot be very large. Moreover, due to the large (hidden) constant in the upper bound, the practical performance of Theorem 23 is poor. We leave the problem of designing more practical algorithms for future research.

Conclusion
In this paper, we studied DP-SCO with special classes of population functions. In the first part of the paper, we study the case where the population function satisfies TNC with the parameter θ > 1. Specifically, we first provided several methods which could achieve upper bounds of for -DP and ( , δ)-DP, respectively. Then we showed that for any θ > 1, there is a population risk function satisfies TNC with θ such that for any -DP (( , δ)-DP) algorithm, the excess population risk of its output is lower bounded by Ω(( d n ) θ θ−1 ) and Ω(( for -DP and ( , δ)-DP, respectively. In the second part of the paper, we revisited DP-SCO with strongly convex loss functions. We claimed that when the loss function is non-negative and the optimal value of the population function is small enough, it is possible to achieve an upper bound of O( d log(1/δ) n 2 2 + 1 n τ ) and O( d 2 n 2 2 + 1 n τ ) for any τ > 1 in ( , δ)-DP and -DP model respectively if the sample size n is sufficiently large.
Besides the open problems we mentioned in the previous parts, there are other unsolved problems: 1) From the theoretical results in this paper, we can see there is still a gap of O( 1 n θ 2(θ−1) ) between upper bounds and lower bounds in both -DP and ( , δ)-DP models. Thus, the optimal rates of excess population risk is still unknown. 2) In this paper we provide faster rates of DP-SCO with special class of functions, especially for TNC population functions. However, besides TNC, there are other special classes of functions which have faster rates in the non-private case, such as exponential concave loss (Koren and Levy, 2015). It is still unknown whether we can get faster rates under the differential privacy constraint. We will leave these problems for future research.

Appendix A. Extension to Non-smooth Loss
In the previous section, we provided several methods for TNC population risk functions under the assumption that the loss function is smooth. However, we constantly meet the case where the loss is non-smooth. In this section, we will extend the previous methods to the non-smooth case. The observation is that, in both Algorithm 5 and Algorithm 2, we use the Phased-SGD (Algorithm 1) as a sub-routine for several phases. And we need the smoothness condition in Phased-SGD to get the upper bounds in Lemma 10. Thus, to extend to the non-smooth case, the most direct way is to change Phased-SGD to a non-smooth version in both Algorithm 5 and Algorithm 2. (Feldman et al., 2020) provided non-smooth version of Phased-SGD based on proximal mapping for ( , δ)-DP model, namely Phased-ERM, which is shown in Algorithm 8.
Algorithm 8: Phased-ERM(w 0 , η, n, W) algorithm (Feldman et al., 2020) Input: Dataset S = {x 1 , · · · , x n }, convex function f : W × X → R, initial point w 0 ∈ W, step size η (will be specified later), privacy parameters , δ. Set k = log 2 n . Partite the whole dataset into k subsets By using Algorithm 8 as subroutine in Algorithm 5 and 2 we have the following result, which is similar to Theorem 14 and 11.
Theorem 26 Assume that F (·) is (θ, λ)-TNC and f (·, x) is convex and L-Lipschitz for each x. For any 0 < , δ < 1, if we replace the Phased-SGD with Phased-ERM in Algorithm 5 and 2 (we also change the stepsizes), then the two algorithms are ( , δ)-DP. Moreover, in Algorithm 5, the output satisfies If n is sufficiently large such that n ≥ 256, in Algorithm 2, the output satisfies In the following we provide some examples that satisfy TNC with θ = 2 and with non-smooth loss.
Lemma 27 (Hinge Loss (Xu et al., 2017)) Consider the SVM problem with hinge loss where W is an 1 -norm or ∞ -norm ball and | w, x | ≤ 1 for all x and w ∈ W. Then F (·) satisfies TNC with θ = 2.

Appendix B. Experiments
In this section, we provide some experimental studies to compare the effectiveness of the proposed methods for population risk functions satisfying TNC.

Experimental Settings and Baseline Methods
For the problems satisfying TNC, we first consider the population risk with squared loss, which is mentioned in Lemma 17, min As we mentioned in the previous section, this problem satisfies TNC with parameter θ = 2. For this problem, we use Phased-SGD (Algorithm 1) as our baseline method, which could be seen as the state-of-the-art method (Feldman et al., 2020). We will use PSA (Algorithm 2) and iterated SGD (Algorithm 5) withθ = 1.5 and 2 for comparisons. Note that here we will not compare with Algorithm 4. As we can see that, theoretically it involves quite large constants which impedes the algorithm to be practical. Moreover, since strongly convex functions satisfy (2, λ)-TNC, we also perform our methods on strongly convex function. Here we will use Phased-SGD-SC (Algorithm 3) (Feldman et al., 2020), which is known to have the optimal rate of error, as the baseline method. For this case, we will consider the population risk function with squared logistic loss and an additional l 2 -norm regularization: which is λ-strongly convex and satisfies (2, λ)-TNC. We set the parameter λ = 0.001. For the compared methods, as we could see from Figure 1 and 3, the performance of PSA (Algorithm 2) is quite poor. Moreover, we find that the error of Faster-DPSGD-SC (Algorithm 7) is also quite large. Thus, to have a better comparison with Phased-SGD-SC, here we will not show the results of PSA and Faster-DPSGD-SC for the regularized logistic regression problem.

Dataset and Parameter Settings
We will implement our methods on four real-world datasets from the libsvm website 3 , namely a8a, a9a, ijcnn1 and w7a. For ijcnn1 dataset, although the training set and test set are explicitly provided, the training set is relatively small while test set is relatively too large. Thus, we randomly select 8 × 10 4 samples in the test data and combine them to the training data, i.e., we will leave 11,701 samples for testing while 115,000 samples for training.
Since it is difficult to get the exact value of the population risk function, here we will use the testing error to approximate it, which is the value of the empirical risk on test data. In the experimental part, we study the above mentioned two TNC problems (5), (6) and their corresponding testing errors with various sample sizes and privacy budgets . When performing the results for different sample sizes, we will fix 2 √ log(1/δ) = 2. When performing the results for different privacy budgets , we will use n = 10 4 samples. We will set δ = 1 n 1.1 for all experiments. Note that all the algorithms presented in the experiments are conducted for 20 random runs and we take the their averaged testing error over the 20 runs.  Figure 2 and 4 are for the 2 -norm regularized squared logistic regression. As we can see the from these results: 1) The previous method Phased-SGD outperforms our first method PSA in all the cases, which contradicts to our previous theoretical results. We conjecture that this may be due to that we use the Dykstra's algorithm in PSA to get an approximate solution of the projection step, which may destroy our theoretical guarantees, another reason may be that the sample size is still not large enough, as we can see when the sample size gets larger the two methods get closer. 2) We can see that, unlike PSA, our third method, Iterated SGD, outperforms Phased-SGD in all the experiments. Moreover, either the sample size or the privacy parameter gets larger, the testing error of Iterated SGD decreases faster, which supports our previous theoretical analysis. 3) From Iterated SGD withθ = 2 andθ = 1.5 we can see that the method is quite flexible. This is due to that we showed that Theorem 14 will hold as long as θ ≥θ > 1. However, we note that the performance could still be different forθ = 1.5 andθ = 2, and we find thatθ = 1.5 is better thanθ = 2. We conjecture it is because the hidden constant in the upper bound of Theorem 14 in the case ofθ = 1.5 is relatively smaller than the case ofθ = 2.

Appendix C. Omitted Proofs
Proof [Proof of Theorem 11] For convenience here we only show the proof of ( , δ)-DP. The proof of -DP is almost the same by replacing the term ( 1 The guarantee of ( , δ)-DP is just followed by Lemma 10 and the parallel theorem of Differential Privacy. In the following we will focus on the utility.
where the third inequality is given by throwing away the √ d log(1/δ) · n m term and substituting m in term 1 √ n m with 1 2 log 2 2n log 2 n − 2. Below, we consider the following two cases.
Assume (8) is true for some k > 1, then we have Which is (9). By the definition of TNC, we have Thus (8) is true for k + 1. Now we prove (10). Referring to Lemma 10, we know that Here completes the proof of the lemma.
Now we proceed to prove theorem 11 in this case.
Case 2 If λ < µ 0 , then By a similar argument process as in Case 1, we have Combining the two cases, we conclude that Theorem 12] Before our proof, we provide some notations. We denote F * = min w∈W F (w). For a given error ρ, we denote L ρ the ρ-level set of function F (W ) and S ρ the ρ-sublevel set F (w), respectively, i.e., L ρ = {w ∈ W : F (w) = F * + ρ}, S ρ = {w ∈ W : F (w) ≤ F * + ρ}. For any w ∈ W, we denote w + ρ as the closet point in the ρ-sublevel set to w, i.e., Using the KKT condition, it is easy to check that when w ∈ S ρ then w + ρ ∈ L ρ . We first recall the following lemma, given by (Yang and Lin, 2018).
Lemma 30 (Lemma 1 in (Yang and Lin, 2018)) For any w ∈ W and ρ > 0 we have where W * = {w : w ∈ arg min w∈W F (w)} and dist(w + ρ , W * ) is the distance from the point w + ρ to the set W * .
Lemma 31 If f (·, x) is convex, β-smooth and L-Lipschitz for each x and γ ≥ W 2 L , where W 2 is the diameter of the set W, i.e., W 2 = max w,w ∈W w − w 2 . Based on different noises and stepsizes in Algorithm 3, Algorithm 3 is ( , δ) or -DP if η ≤ 1 β . Given w 0 ∈ W, for the output w k in Algorithm 3. In the case of ( , δ)-DP, we have In the case of -DP, we have whereF (w) = F (w) + 1 2γ ||w − w 0 || 2 2 and w 0 is the initial point.
Next we start our proof. For convenience here we only focus on ( , δ)-DP, the proof of -DP is almost the same. The guarantee of ( , δ)-DP is simply followed by Lemma 31. We also note that Lemma 31 implies that for any w ∈ W, We assume that for all Otherwise we have proved the theorem.
We will show by induction that If this is true then when w = m we have . In the following we will show (17). For k = 0, by the definition of χ, it is true. Now, consider the k-th phase. By (15) we have Thus, where the last equality is due to (16).
For term B, we have where the first equality is due to (16). Thus, in total we have Proof [Proof of Theorem 14] In the following we only consider the ( , δ)-DP case. It is almost the same for -DP. The guarantee of ( , δ)-DP is just followed by Lemma 10 and the parallel theorem of Differential Privacy. In the following we will focus on the utility.
Since k = (logθ 2) · log log n , then k ≤ (logθ 2) · log log n, namely 2 k ≤ (log n) logθ 2 and 2 k −1 (log n) logθ 2 ≤ 1. Observe that the total sample number used in the algorithm is when we take expectations at both sides, namely Thus, we have where the first inequality comes from Lemma 10 and the second inequality uses (18). Denote Then (19) can be simplified as Notice that n i /n i−1 = 2, then E i−1 E i ≤ ( n i n i−1 ) θ = 2 θ , namely: Then we can rearrange the above inequality as where the first inequality uses (20) and the second inequality applies (21).
Thus we have θ θ−1 log n − log c 1 ≤ θ k−1 log C 1 , which is equivalent to our object n θ θ−1 As a result, we hold a solution with error: where we use the fact that n k = 2 k−1 (log n) logθ 2 ≥ 1 2 n and (a + b) 2 ≤ 2(a 2 + b 2 ).
Remark 32 To perform valid Phased SGD (Subroutine of Iterated Phased-SGD) for k times, it should satisfy n i = 2 i−1 n (log n) logθ 2 ≥ 2 for any i ∈ [k]. Otherwise, the Phased SGD cannot function properly to get the bound in Lemma 10. As a result, n should be sufficiently large such that θ ≥ 2 log log n (log n)−1 .

Proof [Proof of Theorem 19]
Based on the fact that a lower bound on excess empirical risk implies nearly the same lower bound on the excess population risk (Bassily et al., 2019), here we consider the empirical risk, then we can use the boosting technique to the population loss. See (Bassily et al., 2019) for details.
For any dataset S = {x 1 , · · · , x n } with data point drawn from √ d } d , and any w ∈ W, we define the empirical risk function as the following, In the following, we first show that there is a point w * satisfying ||w * || 2 ≤ 1, s.t. ∇F (w * ; S) = 0.
If (24) holds, then Recall the following lemma. such that for every ( , δ)- For the sake of contradiction, we consider such S described in the above lemma, with probability more than 2 3 , (24) holds. Let A be an ( , δ)-differentially private algorithm that first runs A on the data and then outputs ||Z|| θ−2 θ−1 2 w priv , and let n be sufficiently large that n ≥ √ By the boosting technique in (Bassily et al., 2019), we have with probability at least 1 3 , Proof [Proof of Theorem 20] The proof of Theorem 20 is almost the same as the proof of Theorem 19. Instead of using Lemma 33 we use the following lemma: Lemma 34 (Lemma 5.1 in (Bassily et al., 2014)) Let n, d ∈ N, > 0 such that n ≥ Ω( d ). There is a number M = Ω min n, d such that for every ( , δ)-differentially private algorithm A, there is a dataset S = {x 1 , · · · , x n } ⊆ x i || 2 = Ω min 1, d n .
Proof [Proof of Theorem 22] For simplicity, here we only focus on ( , δ)-DP. It is almost the same for -DP.
In the first step we perform Algorithm 1, which is ( , δ)-DP. Thus, it is sufficient to show that Algorithm 6 is also ( , δ)-DP, i.e., each epoch is ( , δ)-DP. To prove this, we first revoke the stability of One -Pass Projected SGD for strongly convex loss functions, which is given by (Hardt et al., 2015).
Lemma 35 [Theorem 3.9 in (Hardt et al., 2015)] Assume the loss function f (·, x) is λ-strongly convex and β-smooth with respect to w ∈ W for all x. Let S i and S i be two samples of size n i differing in only a single element. Denote w t i and w t i as the outputs of the projected stochastic gradient method (4) on datasets S i and S i respectively, then if η ≤ 1 β we have Recall that in each epoch we perform projected gradient descent for n i steps using n i samples, according to Lemma 35, we can bound the sensitivity of w t i for each t and we have ||w t i − w t i || ≤ 2L 2 λn i for all t, where w t i and w t i correspond to the solution of two neighboring dataset S i and S i that differs in one sample.
Thus, the sensitivity of w i = 1 n i n i t=1 w t i is also 2L 2 λn i . By the Gaussian mechanism, adding Gaussian noise with σ i = 8L 2 √ log(1/δ) n i λ will preserve ( , δ)-DP.
Proof [Proof of Theorem 23] For convenience here we only focus on ( , δ)-DP, the proof is almost the same as for -DP.
Lemma 36 (Lemma 1 in (Zhang and Zhou, 2019)) Assume f (·, x) is non-negative and β-smooth for all x and F (·) is convex. Apply n i iterations of (4), i.e., w t+1 i = W (w t i − η i ∇ w f (w t i , x t i )) with η i < 1/(2β). Then for any w ∈ W, we have Since f (·, x) is β-smooth for all x, we have Take expectations on both sides w.r.t the data and ξ i we get Combining with Lemma 36, we have Based on the above result, we establish the following result of excess population risk of each epoch in Epoch-DP-SGD (Algorithm 6).
Thus the lemma holds for e + 1 which completes the proof. Now we go back to our proof. The number of epochs made is given by the largest e which satisfies e i=1 n i ≤ n 2 , i.e., e i=1 n i = n 1 (1 + 2 + · · · + 2 e−1 ) = n 1 (2 e − 1) ≤ n 2 which means the largest value is E = log 2 ( n 2n 1 + 1) and the final solution is w = w E .