Private Non-smooth ERM and SCO in Subquadratic Steps
Year: 2021

Abstract:
We study the differentially private Empirical Risk Minimization (ERM) and Stochastic Convex Optimization (SCO) problems for non-smooth convex functions. We get a (nearly) optimal bound on the excess empirical risk for ERM with O( 3/2 d1/8 + N 2 d ) gradient queries, which is achieved with the help of subsampling and smoothing the function via convolution. Combining this result with the iterative localization technique of Feldman et al. [FKT20], we achieve the optimal excess population loss for the SCO problem with O(min{N5/4d1/8, N d1/8 }) gradient queries. Our work makes progress towards resolving a question raised by Bassily et al. [BFGT20], giving first algorithms for private SCO with subquadratic steps. In a concurrent work, Asi et al. [AFKT21] gave other algorithms for private ERM and SCO with subquadratic steps.

text: 3/2
d1/8 + N
2
d ) gradient queries, which is achieved with the help of subsampling and smoothing the function via convolution. Combining this result with the iterative localization technique of Feldman et al. [FKT20], we achieve the optimal excess population loss for the SCO problem with O(min{N5/4d1/8, N3/2
d1/8 }) gra-
dient queries. Our work makes progress towards resolving a question raised by Bassily et al. [BFGT20], giving first algorithms for private SCO with subquadratic steps. In a concurrent work, Asi et al. [AFKT21] gave other algorithms for private ERM and SCO with subquadratic steps.

heading: 1 Introduction
text: Privacy has become an important consideration for learning algorithms dealing with sensitive data. Over the past decade, differential privacy, introduced in the seminal work of [DMNS06], has established itself as the defacto notion of privacy for machine learning problems. In this paper, we revisit Empirical Risk Minimization (ERM) and Stochastic Convex Optimization (SCO) problems, two fundamental problems in statistics and machine learning, in differential privacy setting. In the ERM problem, we are given a family of convex functions {f(·, x)}x∈Ξ over a bounded closed convex set K ⊂ Rd of diameter D, a data set S = {x1, · · · , xN} drawn from some unknown distribution P over the universe Ξ, and the objective is to
minimize F̂ (ω) := 1
N ∑ xi∈S f(ω, xi) over ω ∈ K,
The excess empirical loss with respect to a solution ω is defined by F̂ (ω) − F̂ ∗, where F̂ ∗ = minω∈K F̂ (ω). A closely related but more general problem is SCO, where the objective is to
minimize F (ω) := E x∼P f(ω, x) over ω ∈ K,
We refer F (ω) − F ∗ as the excess population loss, where F (ω) = Ex∼P f(ω, x) and F ∗ = minω∈K F (ω).
Differentially private convex optimization has been studied extensively for over a decade now [CM08, RBHT09, CMS11, KST12, JT14, TTZ14, BST14, TTZ15, KJ16, WLK+17, FTS17,
∗Algorithms Group, Microsoft Research (MSR) Redmond. jakul@microsoft.com †University of Washington and Microsoft Research. Supported by NSF awards CCF-1749609, DMS1839116, DMS-2023166, Microsoft Research Faculty Fellowship, Sloan Research Fellowship, Packard Fellowships.yintat@uw.edu
‡University of Washington. Part of the work was done while visiting Shanghai Qi Zhi Institute.dgliu@uw.edu.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
ZZMW17, WYX17, INS+19]. Both DP-ERM and DP-SCO for smooth convex functions are well understood in the sense that we know (near) linear time algorithms that achieve optimal loss; we refer the readers to [WYX17, FKT20] for more details. However, for the more general non-smooth convex loss functions our understanding is not yet complete, which is the focus of this paper.
Our algorithms for DP-SCO build upon our improvements for the DP-ERM problem, and hence we begin with DP-ERM problem. A summary of the state-of-the-art results of DP-ERM and our contributions for the non-smooth convex loss functions is given in Table 1. We will discuss the concurrent work [AFKT21] separately at the end of the introduction, and the following discussion is only limited to the previous work.
Nε }) and of Strongly Convex function is
Ω(min{G2µ , G 2d µN2ε2 }) [BST14].
[KST12] used objective perturbation method to design a DP-algorithm with O(GD √ d log(1/δ)√ Nε
) excess empirical risk. This result was improved significantly by [BST14], who first showed a lower bound of Ω(min{GD, GD √ d
Nε }) on the excess empirical risk for DP-ERM. Further, they gave an algorithm with excess empirical risk O(GD log 3 2 (N/δ) √ d log(1/δ)
Nε ), which is sub-optimal by a factor of log 3 2 (N/δ).
Their algorithm is based on a modification of SGD by adding Gaussian noise to the gradients to make it differentially private. The privacy analysis proceeds via amplification by sampling and the strong composition theorem. Roughly speaking, the logarithmic blowup in the excess empirical risk is due to two reasons: 1) The strong composition theorem requires that at each step one needs to add Gaussian noise with a larger variance; 2) They used sub-optimal convergence rate O(log T/ √ T ) for T -step SGD.
However, getting the optimal bounds with small gradient complexity for non-smooth case turns out to be a more difficult problem. This was noted by [WYX17], who raised it as an important open problem. This question was answered in [BFTT19], who gave an algorithm with almost optimal excess empirical risk. To achieve this, [BFTT19] first consider the smooth case, and give an improved privacy analysis via the Moments Accountant technique proposed by [ACG+16]. They extend their result to non-smooth case by applying Moreau-Yosida envelope technique (a.k.a. Moreau envelope smoothing) [Nes05] to make the function smooth. However, this technique is computationally inefficient and leads to O(N4.5)-gradient computations for the whole algorithm. This limitation was overcome in a recent work of [BFGT20] who gave the optimal excess empirical risk guarantee with O(N2)-gradient computations. The privacy analysis of this result also used Moments Accountant method, and they used the standard online-to-batch conversion technique [CBCG04] to prove the high-probability and expectation bound on the excess empirical error of SGD.
As we can see from Table 1, all the previously known results (except the concurrent work [AFKT21]) achieving near optimal excess empirical risk bounds require at least O(N2)-gradient computations. As Table 2 shows, a similar situation arises in Stochastic Convex Optimization (SCO), which is a closely related problem compared to ERM. Many results for SCO [BST14, BFTT19, BFGT20] are directly based on ERM; that is, solving the ERM and analyzing the generalization error. The first non-trivial result for general convex loss functions achieving excess population loss of O ( GD(d
1/4 √ N
+ √ d Nε ) ) was given by [BST14], who showed the result by first solving the ERM prob-
lem and bounding the generalization error. They used the result on universal convergence directly, namely, bounding supω∈K E[F (ω)−F̂ (ω)]. But this method has its limitations; For example, [Fel16] showed that lower bound of universal convergence is Ω( √ d/N) for some (not necessarily convex) loss functions. Later, [BFTT19], [FKT20] and [BFGT20] obtained near optimal excess population loss with significantly better running times (gradient complexity). The privacy analysis in these papers relied on recent advances in the privacy techniques such as the Moments Accountant method [ACG+16], Rényi differential privacy (RDP) [Mir17] and the Privacy Amplification by Iteration [FMTT18] and other fast stochastic convex optimization algorithms such as [JNN19]. The excess population loss bound in most of these works followed by solving a (phased) convex (regularized) ERM problem and then appealing to the uniform stability property [HRS16] or the iterative localization approach [FKT20] to do the generalization error analysis.
N2ε2 )) [BST14].
Despite these impressive improvements, as the Table 2 suggests, the previous algorithms that achieve the optimal excess population loss still require O(N2)-gradient computations. Indeed, [BFGT20] write that “ Proving that quadratic running time is necessary for general non-smooth DP-SCO is a very interesting open problem...”. Understanding if the lower bound is the right answer to the above questions or one can design algorithms with subquadratic gradient complexity is the main motivation that spurred our work.

heading: 1.1 Our Contributions
text: The first contribution of this paper is to show that we can obtain subquadratic gradient complexity bound for ERM when the dimension is super constant. In particular, for the important regime of over-parameterization (d ≥ N ), we achieve a bound of O(N1+3/8). Let Kr = {y | y = ω + z, ω ∈ K, z ∈ Rd, ∥z∥r ≤ r}. We now state the result formally. Theorem 1.1 (DP-ERM). Suppose K ⊂ Rd is a closed convex set and {f(·, x)}x∈Ξ is a family of G-Lipschitz and convex functions over Kr, where r = D √ d log(1/δ) εN 4. For ε, δ ≤ 1/2, given any sample set S consists of N samples from Ξ and arbitrary initial point ω0 ∈ K, we have a (ε, δ)-differentially private algorithm A which takes
O
( εN 3 2
d1/8 log1/4(1/δ) +
ε2N2
d log(1/δ)
)
gradient queries and outputs ωT such that E[F̂ (ωT ) − F̂ ∗] = O ( GD √ d log(1/δ)
εN
) , where D =
∥ω∗ − ω0∥2, F̂ (ω) = 1N ∑ xi∈S f(ω, xi), F̂ ∗ = minω∈K F̂ (ω), and the expectation is taken over the randomness of the algorithm.
4We only need consider the non-trivial case when √ d log(1/δ)
εN ≤ 1, or any feasible solution is good enough.
This means that r = O(D), which is a mild assumption.
Moreover, if {f(·, x)}x∈Ξ is also µ-strongly convex over Kr, we can meet the same gradient query complexity and get a solution ωT such that E[F̂ (ωT )− F̂ ∗] = O
( G2d log(1/δ)
µε2N2
) .
The main contribution of the paper is to use the above result to obtain a better gradient complexity for the SCO problem, answering the open problem in [BFGT20]. Combining our private ERM algorithm with the iterative localization technique [FKT20], we give the first algorithm achieving optimal error with strictly sub-quadratic steps for all dimensions. Theorem 1.2 (DP-SCO). Suppose ε, δ ≤ 12 and sample set S consists of N samples drawn i.i.d from a distribution P over Ξ. Suppose {f(·, x)}x∈Ξ is convex and G-Lipschitz with respect to ℓ2 norm and convex over Kr, where r = D √ d log(1/δ)
εN , there is an (ε, δ)-differentially private algorithm taking
O(N +min{√εN5/4d1/8, εN 3/2
d1/8 log1/4(1/δ) })
gradient queries to get a solution ωT such that E[F (ωT )− F (ω∗)] = O(GD( 1√N + √ d log(1/δ) Nε ). Moreover, if {f(·, x)}x∈Ξ is also µ-strongly convex over Kr, we can meet the same gradient query complexity and get a solution ωT such that E[F (ωT )− F (ω∗)] = O ( G2 µ ( d log(1/δ) ε2N2 + 1 N ) ) .
Finally, we note that with straightforward modifications, our results can also capture the regularized ERM and SCO, where there is one more simple (and convex) function h(ω) added to the objective function and the objective function takes the form 1N ∑ xi∈S f(ω, xi) + h(ω), which show up often in the previous work such as [RBHT09, KST12, WYX17, INS+19].
1.2 Our Techniques
Most of the previous works [BST14, BFTT19, BFGT20] that achieve near optimal bounds for ERM and SCO are based on adaptations of SGD to make it differentially private. The information theoretic lower bound of Ω(1/ √ T ) for T -step SGD may be one of the important reasons why we can not get subquadratic gradient complexity for non-smooth convex ERM easily. Consider the algorithm in [BFGT20] as an example. It needs to add Gaussian noise v ∼ N (0, σ2Id×d) with σ2 = G
2 log(1/δ) ε2 to each gradient. By a
standard analysis of SGD, we can only show an excess empirical risk of Θ(D
√ dσ2√ T
), which requires us to set T = Ω(N2) to get ideal bound, thus hitting the quadratic barrier.
We deviate from the above approaches for designing private algorithms for non-smooth functions. First notice that the gradient complexity O( εN 3 2
d1/8 log1/4(1/δ) + ε
2N2
d log(1/δ) ) in Theorem 1.1 is the same for both strongly convex and general non-smooth functions; same holds for DP-SCO. This is not a coincidence; We prove that if we can achieve optimal empirical risk (population loss) for one case, then we can achieve optimal empirical risk (population loss) for another with the same privacy guarantee and gradient complexity. The Figure 1 illustrates the relationship among these different problems.
Our result for the general convex non-smooth case is obtained by providing a reduction to the strongly convex non-smooth case. Thus, our task becomes designing better algorithms for the strongly convex non-smooth functions. Rather than using SGD, we let the objective function take convolution with a sphere kernel to make it smooth. We then use the accelerated stochastic approximation algorithm in [GL12] for solving strongly convex stochastic optimization problems. However, this is not enough, as the required noise that needs to be added to the gradients to make the algorithm private is too large
to get subquadratic gradient complexity, even if we use the tighter Moments Accountant technique [ACG+16]. We overcome this by increasing the batch size to an appropriate value. Combining these ideas together, we show that the amount of noise we add can be reduced to achieve the optimal excess empirical loss, and we get the gradient complexity of O(max{N3/2/d1/8, N2/d}). For SCO, we get the gradient complexity of O(min{N5/4d1/8, N3/2/d1/8}) via application of the iterative localization approach of Feldman et al [FKT20]. The intuition behind iterative localization is using private ERM to solve regularized objective functions which have low sensitivity, iteration by iteration. Each iteration reduces the distance to an approximate minimizer by a multiplicative factor, so after logarithmic number of phases we are done.

heading: 1.3 Concurrent and Independent Work
text: In an independent and concurrent work, [AFKT21] give a new analysis of private regularized mirror descent to do the private ERM. Then they combine the iterative localization approach to achieve the optimal excess population loss for SCO. Their result also achieves subquaratic gradient complexity.
0 0.5 1 1.5 2
1
1.2
1.4
1.6
1.8
2
α : dimension is Nα
β : gr ad
ie n t co m p le x it y is O (N
β )
Our Result
Result in [AFKT21] State Of Art
Trivial For α ≥ 2
More formally, they get O(logN · min(N3/2 √ log d,N2/ √ d)) for SCO in query complexity. We compare their gradient complexity with ours in the figure to right. As we see, our result is better in the important regime d ≤ N1+1/3. Same holds true for ERM. Finally, we remark that the main motivation of [AFKT21] was to study SCO problem in more general ℓp norms as much of the literature has focused on the ℓ2-norm. They also give new results in ℓp-bounded domain together with another concurrent work [BGN21].

heading: 2 Preliminaries
text: We recall some basic definitions in convex optimization and DP.
Definition 2.1 (L-Lipschitz Continuity). A function f : K → R is L-Lipschitz continuous over the domain K ⊂ Rd if the following holds for all ω, ω′ ∈ K : |f(ω)− f(ω′)| ≤ L∥ω − ω′∥2.
Definition 2.2 (β-Smoothness). A function f : K → R is β-smooth over the domain K ⊂ Rd if for all ω, ω′ ∈ K, ∥∇f(ω)−∇f(ω′)∥2 ≤ β∥ω − ω′∥2.
Definition 2.3 (µ-Strongly convex). A differentiable function f : K → R is called strongly convex with parameter µ > 0 if the following inequality holds for all points ω, ω′ ∈ K, ⟨∇f(ω) − ∇f(ω′), ω − ω′⟩ ≥ µ∥ω − ω′∥22. Equivalently, f(ω′) ≥ f(ω) +∇f(ω)⊤(ω′ − ω) + µ2 ∥ω′ − ω∥22.
Definition 2.4 (Differential privacy). A randomized mechanismM is (ε, δ)-differentially private if for any event O ∈ Range(M) and for any neighboring databases S, S′ that differ in a single data element, one has
Pr[M(S) ∈ O] ≤ exp(ε) Pr[M(S′) ∈ O] + δ.

heading: 2.1 A Meta Algorithm for DP Convex Optimization
text: Many DP convex optimization algorithms with noisy first-order information have the following simple format.
Algorithm 1: Private Meta Algorithm METADP 1 Input: Sample set S = {x1, · · · , xN}, the objective convex function F (ω) we want to
minimize, the initial point ω0, and privacy parameters ε, δ; 2 Process: for phases t = 1, · · · , T do 3 Select a random sample set St from the uniform distribution over all subsets of S of size B; 4 Let Gt = ( ∑ xi∈St ∇f(ωt−1, xi) + v)/B, where v ∼ N (0, σ2Id×d); 5 Update the result by some sub-procedure ωt ← Sub-procedure(ωt−1, Gt); 6 end 7 Output: Some function of {ωi}i≥1.
Compared to non-private algorithms, DP algorithms make two simple modifications to make it private. First, we compute gradients over a uniform sample of some size B. Next, we add a carefully calibrated Gaussian noise to these gradients and take average, before updating our results. The DP analysis then follows from a careful accounting of the privacy budget lost in each iteration, and the bound on excess empirical risk comes from the property of the optimization algorithm. The privacy analysis of the above algorithm can be done via moments account [ACG+16] or using the framework of sub-sampled Gaussian mechanism, for which we can use tCDP proposed in [BDRS18]. As this is a direct application of the main result in [BDRS18], we leave the proof of the following theorem in the full version attached as supplementary material.
Theorem 2.5. Suppose {f(·, x)}x∈Ξ is a family of G-Lipschitz and convex functions over K, for ε < c1B 2T/N2, B ≤ N/10 and 1/2 ≥ δ > 0, by setting σ = c2GB √ T log(1/δ)
εN for some constant c1 and c2, METADP is (ε, δ)-differential private.

heading: 3 Differentially Private ERM
text: In this section, we present private algorithms achieving the optimal excess empirical loss with subquadratic gradient complexity when the dimension is super constant. We consider non-smooth strongly-convex functions first, and then show how to reduce the general non-smooth case to the strongly-convex case in the last subsection. Due to space constraints, we won’t be able to provide all the proofs in the main body; the supplementary material contains the full version of the paper with all the proofs.

heading: 3.1 Non-smooth Strongly-convex Functions
text: We use the framework introduced in Section 2.1 and give a faster private algorithm. Specifically, we modify a stochastic convex optimization algorithm (AC-SA) in [GL12] to fit into our framework.
Algorithm 2: Accelerated stochastic approximation (AC-SA) algorithm 1 Input: Initial point ω0 ∈ K. 2 Initialization: Set the initial point ωag0 = ω0; 3 Set the step-size parameters αt = 2t+2 and γt = 4L t(t+1) ; 4 Process: 5 for t = 1, · · · , T do 6 Let ωmdt =
(1−αt)(µ+γt) γt+(1−α2t )µ ωagt−1 + αt[(1−αt)µ+γt] γt+(1−α2t )µ ωt−1;
7 Query Oracle Gt ≡ G(ωmdt ); 8 ωt = argminω∈K{αt[⟨Gt, ω⟩+ h(ω) + µ∥ωmdt − ω∥22] + [(1− αt)µ+ γt]∥ωt−1 − ω∥22}; 9 ωagt = αtωt + (1− αt)ωagt−1;
10 end 11 Return: ωagT .
First we recall some properties of the algorithm AC-SA. Suppose f : K → R is a convex function, and the objective is to get Ψ∗ := minω∈K{Ψ(ω) = f(ω) + h(ω)}, where K is a closed convex set and h(ω) is a simple convex function with known structure.
Theorem 3.1 (Proposition 9 in [GL12]). If the following conditions are met:
• For some L ≥ 0,M ≥ 0 and µ > 0, µ2 ∥y − ω∥22 ≤ f(y) − f(ω) − ⟨g(ω), y − ω⟩ ≤ L 2 ∥y − ω∥22 + M∥y − ω∥2, ∀ω, y ∈ K, where g(ω) ∈ ∂f(ω) and ∂f(ω) denotes the sub-differential of f at ω.
• For each call of the stochastic oracle G with the input ωt ∈ K, the stochastic oracle G can output an independent vector G(ωt) such that E[G(ωt)] ∈ ∂f(ωt).
• For any t ≥ 1 and ωt ∈ K, E[∥G(ωt)− g(ωt)∥22] ≤ V . Then, AC-SA (algorithm 2) outputs ωT after T iterations such that E[Ψ(ωT ) − Ψ∗] ≤ O (
L∥ω0−ω∗∥22 T 2 + M2+V µT ) , where ω∗ = argminω∈K Ψ(ω) and Ψ∗ = Ψ(ω∗).

heading: 3.1.1 Smoothing Function
text: From the statement of Theorem 3.1, it is clear that the algorithm in [GL12] gives much better convergence rates for smooth functions. As we are considering non-smooth functions, we need an efficient way to smooth the objective function without introducing too much error. In the next few paragraphs, we show how to achieve that. Recall that D denotes the diameter of the closed convex set K ⊂ Rd. Suppose {f(·, x)}x∈Ξ is a family of G-Lipschitz and µ-strongly convex functions over K. This implies that for any sample set S, the empirical loss function F̂ (ω) we consider is G-Lipschitz and µ-strongly convex over the domain K. We do a convolution on f(·, x), which is denoted by f(·, x) ∗ nr. The objective function after the convolution step becomes F̂nr (ω) = 1 N ∑ xi∈S Ey∼nr f(ω + y, xi), where nr is the uniform density on the ℓ2 ball of radius r. We need the following claim:
Claim 3.2. Suppose {f(·, x)}x∈Ξ is convex and G-Lipschitz over K+B2(0, r). For ω ∈ K, F̂nr (ω) has following properties: 1) F̂ (ω) ≤ F̂nr (ω) ≤ F̂ (ω) +Gr; 2) F̂nr (ω) is G-Lipschitz; 3) F̂nr (ω) is G √ d
r -Smooth; 4) For random variables y ∼ nr and x uniformly from S, one has E[∇f(ω + y, x)] = ∇F̂nr (ω) and E[∥∇F̂nr (ω)−∇f(ω + y, x)∥22] ≤ G2.
The properties 1)-3) of this claim come from Lemma 7 and Lemma 8 in [YNS12] while the forth follows from Lemma E.2 in [DBW12]. Furthermore, the convolution operation preserves strong convexity, which implies the fact below.
Fact 3.3. Let nr be the uniform density on the ℓ2 ball of radius r, and f : Kr → R be a µ-strongly convex function over Kr. Then Ey∼nr f(y + ·) is µ-strongly convex over K.

heading: 3.1.2 Algorithm
text: Recall that y ∼ nr is a d-dimension vector drawn from the uniform density on the ℓ2 ball of radius r. Our algorithm is described in Algorithm 3 below, which is a modification of Algorithm 2.
Algorithm 3: Private AC−SA 1 Input: A convex set K with diameter D, a family {f(·, xi)}i∈[N ] of G-Lipschitz and µ-strongly
convex functions over K, an initial point ω0 ∈ K, privacy parameters ε, δ, the batch size B, and the number of steps T .
2 Set r ← D Td1/4
and σ ← Θ(GB √ T log(1/δ)
εN ); 3 Run the AC−SA with the Oracle G defined below; 4 Return: The output of AC−SA
5 Oracle G(ω): 6 Select a random sample set St from the uniform distribution over all subsets of S of size B. 7 Return: (∑ xi∈St ∂f(ω + yi, xi) + v)/B, where yi ∼ nr for each i ∈ [B] and
v ∼ N (0, σ2Id×d ) .

heading: 3.1.3 Utility and Privacy
text: It is not hard to show that Private AC−SA (Algorithm 3) is an instance of METADP (see Section 2.1), so we have the following guarantee directly by Theorem 2.5. Lemma 3.4. For ε ≤ c1B2T/N2, δ ≤ 1/2, B ≤ N/10 and σ = c2GB √ T log(1/δ)
εN where c1 ≤ 1, c2 ≥ 1 are constants, Private AC−SA is (ε, δ)-DP.
Now we consider the accuracy of Private AC−SA, which is proved in the full version. Lemma 3.5. Under the assumptions defined in Algorithm Private AC−SA, after T iterations, it outputs ωT such that
E[F̂ (ωT )− F̂ ∗] = O ( G2/B + σ2d/B2
µT +
GDd1/4
T
) ,
where ω∗ = argminω∈K F̂ (ω), and F̂ ∗ = minω F̂ (ω).
Before stating the main result of this section, we need the following lemma that removes the dependence on the diameter term. Recall that the lower bound of strongly convex case is
Ω(min{G2µ , G2d log(1/δ) µε2N2 }) while for the general case is Ω(min{GD, GD √ d log(1/δ)
εN }). Therefore, we only need to think about the case when d log(1/δ)ε2N2 ≤ 1, or the bound will be trivial. The following lemma says if we can achieve sum of these two lower bounds for strongly-convex case, then we can achieve the optimal bound for the strongly-convex case, which implies we can reduce the StronglyConvex Case to General Convex Case. The following lemma follows from the reduction in Section 5.1 in [FKT20], and we try to give a more formal statement for convenience in the future.
Lemma 3.6 (Reduction to General Convex Case). Given F̂ is G-Lipschitz and µ-strongly convex. Suppose for any ε, δ < 1/2, we have an (ε, δ)-differentially private algorithm A which takes ω0 as the initial start point and outputs a solution ωT such that E[F̂ (ωT ) − F̂ ∗] = O ( G2d log(1/δ) µε2N2 + GD √ d log(1/δ) εN ) , where ω∗ = argminω∈K F̂ (ω) and D = ∥ω0−ω∗∥2. Then by
taking A as sub-procedure with some modifications on parameters, we can get an (ε, δ)-differentially private solution with excess empirical loss at most E[F̂ (ωT )−F̂ ∗] = O
( G2d log(1/δ)
µε2N2
) . Furthermore,
if A uses g(N, ε, δ) many gradients, the new algorithm uses∑i≥1 g(N, ε/2i, δ/2i) many gradients. We give the proof in the full version. Now we are ready to prove the bounds for strongly convex case of Theorem 1.1.
Proof of Theorem 1.1. By Lemma 3.5, the output ω of Private AC−SA satisfies E[F̂ (ω) − F̂ ∗] = O
( G2
B + σ2d B2
µT + GDd1/4 T
) . Setting σ = c2GB √ T log(1/δ)
εN and T = ⌈ 100εNc1d1/4 √ log(1/δ) ⌉ (c1, c2 are
defined in Lemma 3.4), one has E[F̂ (ω)−F̂ ∗] = O ( G2
µBT + G2d log(1/δ) µε2N2 + GDd1/4 T
) = O ( G2
µBT + G2d log(1/δ) µε2N2 + GD √ d log(1/δ) εN ) To ensure that Private AC−SA is (ε, δ)-DP, we set B = ⌈ √ εN2
c1T + ε
2N2
d log(1/δ)T ⌉. By our choice of T , we have B ≤ N/10 and ε ≤ c1B2T/N2. Hence, we can apply Lemma 3.4 to conclude the guarantee of (ε, δ) differential privacy. Furthermore, we get a solution ω such that
E[F̂ (ω)− F̂ ∗] = O ( G2d log(1/δ)
µε2N2 +
GD √ d log(1/δ)
εN
) .
As for the total gradient complexity of our algorithm, we are under the assumption that d log(1/δ)ε2N2 ≤ 1, which means that εN
d1/4 √ log(1/δ) ≥ d1/4, and T = ⌈ 100εN c1d1/4 √ log(1/δ) ⌉ = Θ( εN d1/4 √ log(1/δ) ). As for
the batch size, we know √ εN2
T + ε2N2 d log(1/δ)T = ω(1) and thus B = ⌈ √ εN2 T + ε2N2 d log(1/δ)T ⌉ =
Θ( √ εN2
T + ε2N2 d log(1/δ)T ), from which we get the gradient complexity is
BT = Θ
( εN 3 2
d1/8 log1/4(1/δ) +
ε2N2
d log(1/δ)
) .
By Lemma 3.6 we can adjust Private AC−SA and get a final solution ωT such that E[F̂ (ωT )− F̂ ∗] = O ( G2d log(1/δ)
µε2N2
) ,
with gradient complexity Θ( ∑log logN3
i=1 (ε/2i)N3/2 d1/8 log1/4(2i/δ) + (ε/2 i)2N2 d log(2i/δ) ) = Θ( εN 3 2 d1/8 log1/4(1/δ) +
ε2N2
d log(1/δ) ), which completes the proof.

heading: 3.2 General Non-smooth Convex Functions
text: In the general non-smooth case, we only assume that the family of functions {f(·, x)}x∈Ξ is GLipschitz and convex over K. We now give a reduction from this case to the strongly-convex case, which completes our main result for ERM. Lemma 3.7. Suppose K ⊂ Rd is a convex set of diameter D and let {f(·, x)}x∈Ξ be a family of convex functions over K, which are G-Lipschitz and µ-strongly convex. Given any sample set S consists of N samples from Ξ and other necessary inputs, suppose we have a (ε, δ)-DP
algorithm A which can output a solution ωT such that E[F̂ (ωT )− F̂ ∗] = O ( G2d log(1/δ) µε2N2 ) , where F̂ ∗ = minω∈K F̂ (ω). Then when {h(·, x)}x∈Ξ is only G-Lipschitz and convex with necessary inputs, for any sample set S of size N , we also have a (ε, δ)-DP algorithm A′ which can get a solution ωT such that E[Ĥ(ωT ) − Ĥ∗] = O ( GD √ d log(1/δ)
εN
) . where Ĥ(ω) = 1N ∑ xi∈S h(ω, xi), Ĥ ∗ =
minω∈K H(ω). The gradient complexity and privacy guarantee of A and A′ are the same. Moreover, the reduction also holds for SCO.
Proof. We only consider this lemma in the context of ERM, as we can use the nearly the same argument for SCO. Without loss of generality, we assume the intial point ω0 = 0. The proof of this reduction is rather simple: After getting {h(·, xi)}xi∈S , we only need to consider hu(ω, x) = h(ω, x) + u∥ω∥2. Then hu(·, x) is u-strongly convex and O(G + uD)-Lipschitz for any x with ∥ω∥2 ≤ D and ω ∈ K. For the case uD ≤ G, we run A on {hu(·, xi)}xi∈S to get a solution ωT with loss E[Hu(ωT ) − H∗u] = O ( G2d log(1/δ)
uε2N2 ) , where Hu(ω) = 1N ∑ xi∈S h(ω, xi) + u∥ω∥2 and H∗u = minω∈K Hu(ω).
Now by setting u = Θ ( G √ d log(1/δ)
DεN
) , one has E[Ĥ(ωT ) − Ĥ∗] = O ( G2d log(1/δ) uε2N2 + uD 2 ) =
O
( GD √ d log(1/δ)
εN
) . For the case uD ≥ G, we have GD √ d log(1/δ)
εN ≥ GD and hence we can simply output the initial point ω0 as the solution with a loss no more than GD.
The above reduction completes the main result of Theorem 1.1 for the general non-smooth case.

heading: 4 Differentially Private SCO
text: As mentioned before, for DP-SCO, we get the desired gradient complexity via an application of the iterative localization approach of Feldman et al [FKT20]. We prove the reduction theorem stated below, the proof of which is in the full version available as supplementary material. Theorem 4.1. Suppose we have an algorithm A which can solve ERM under strongly convex case and gets a solution with excess empirical loss O( G 2
µN ) by using g(N) many gradients, then we have
an algorithm A′ which can solve SCO under general case and gets a solution with excess population loss O(GD√
N ) by using ∑⌈logN⌉ i=1 g(N/2 i) many gradients.
Moreover, for ε, δ ≤ 1/2, if Aε,δ is (ε, δ)-differentially private with excess empirical loss O(G 2 µ ( 1 N + d log(1/δ) ε2N2 )) under the strongly convex case by using g(N, ε, δ) many gradients, then we can get
(ε, δ)-differentially private A′ with excess population loss O(GD( 1√ N +
√ d log(1/δ)
εN )) by querying gradients at most ∑⌈logN⌉
i=1 g(N/2 i, ε/2i, δ/2i) times.
To obtain the optimal bounds for SCO, we first notice that we can afford to obtain sub-optimal bounds for ERM (O(G 2
µ ( 1 N + d log(1/δ) ε2N2 ))), and hence fewer number of gradient queries. This observation
combined with a careful choice parameters for ERM and the above theorem, helps us prove the main result in Theorem 1.2.

Review summaries:
This paper studies the problem of differentially private ERM and SCO for non-smooth function, aiming mainly to improve the gradient query complexity of previous algorithms. The authors develop algorithms for DP-SCO and ERM that achieve the optimal rates with a subquadratic qradient query complexity which improves the complexity of prior work. The algorithms are based on smoothening the function via randomized smoothing, then applying a noisy accelerated gradient algorithms for smooth functions. 

The paper studies the empirical risk minimization and stochastic convex optimization problems under differential privacy. Previous works give private algorithms for ERM that achieve nearly-optimal utility in the convex and Lipschitz as well as the strongly convex settings but have gradient complexity that is at least quadratic in the number of samples. Thus a natural open question that has been raised in prior works is whether one can obtain an algorithm with a sub-quadratic gradient complexity. The current paper answers this question affirmatively in the regime where the dimension is a super-constant function of the number of samples. Using techniques developed in prior work, the paper extends the ERM algorithm to the more general SCO problem. 

This paper addresses the question of the gradient complexity of differentially private (DP) convex empirical risk minimization (ERM) and stochastic convex optimization (SCO). It provides substantial improvements compared to most work in the area, and it provides the best running times on some ranges of parameters.   The main results in this work are:  1. An Accelerated Stochastic Gradient method with randomized smoothing, and therefore applicable to nonsmooth losses (Lemmata 3.4 and 3.5) 2. A two-way reduction between convex and strongly convex ERM (Lemmata 3.6 and 3.7) 3. A two-way reduction between convex and strongly convex SCO (Lemmata 3.7 and 5.5)  These results are used in combination to show that both DP-ERM and DP-SCO can be solved to optimal rates with subquadratic number of gradient evaluations (with respect to sample size). This resolves an open question from a recent work of Bassily et al. (BFGT20). On the other hand, a concurrent work by Asi et al. (AFKT21) provides subquadratic algorithms in the same setting, but the current submission provides faster rates when $d\leq N^{4/3}$ (this range is interesting, as when $d$ gets closer to $N^2$ the rates for DP-ERM and DP-SCO become vacuous.