Private Non-smooth ERM and SCO in Subquadratic Steps
Authors: Janardhan Kulkarni
Yin Tat Lee
Daogao Liu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Differential Privacy
Stochastic convex optimization
Empirical risk minimization

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(\frac{N^{3/2}}{d^{1/8}}+ \frac{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. \cite{fkt20}, we achieve the optimal excess population loss for the SCO problem with $O(\min\{N^{5/4}d^{1/8},\frac{ N^{3/2}}{d^{1/8}}\})$ gradient queries.
Our work makes progress towards resolving a question raised by Bassily et al. \cite{bfgt20}, giving first algorithms for private SCO with subquadratic steps. 
In a concurrent work, Asi et al. \cite{afkt21} gave other algorithms for private ERM and SCO with subquadratic steps.

Private Non-smooth ERM and SCO in Subquadratic Steps
Janardhan Kulkarni'
Yin Tat Lee
Daogao Liu
Abstract
We study the differentially private Empirical Risk Minimization (ERM) and Stochastic Convex Optimization (SCO) problems for non oon-tmoth convex func- tions. We get (nearly) optimal bound on the excess empirical risk for ERM with 0(N5/2
0 27/5 + N² gradient queries, which is achieved with the help of subsampling and smoothing the function via convolution. Combining this result with the iter- ative localization technique Feldman et al. [FKT20], we achieve the optimal
excess population loss for the SCO problem with (min (miin(NO/ /8/4///8 N²/2 d1/s }) gra- dient queries. Our work makes progress towards resolving a question raised by Bassily 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.
Introduction
Privacy has become important consideration for learning algorithms dealing with sensitive data. Over the past decade, differential privacy, introduced in the seminal work of [DMNS06], has estab- lished itself the defacto notion of privacy for machine learning problems. In this paper, revisit Empirical Risk Minimization (HRM) and Stochastic Convex Optimization (SCO) problems, two fundamental problems in statistics and machine learning, differential privacy setting. the ERM problem, we are given a family of convex functions {f(- hee= over bounded closed convex set K. C Rd of diameter D, a data set = {.1,-... ........ N.N } drawn from some unknown distribution P over the universe E. and the objective is
minimize F(w) = Σ f(, over K. 3,E8
The excess empirical loss with respect solution is defined by F(w) f., where f mineek F(w). A closely related but more general problem SCO, where the objective is
minimize F(w) := E anp
f(w.z) over E K,
We refer F(w)= - F as the excess population loss, where F(w) = Ezep fw, and F mingek ((w)..
Differentially private convex optimization has been studied extensively for over a decade now [CM08, RBHT09, CMS11, KST12, JT14, TTZ14, BST14, TTZ15, KJ16, WLK+ FTS17,
Algorithms Group, Microsoft Research (MSR) Redmond. jakul www.w/iiccctt.oooooooooo com University of Washington and Microsoft Research. Supported by NSF awards CCF-1749609, DMS- 1839116. DMS-2023166. Microsoft Research Faculty Fellowship, Sloan Research Fellowship. Packard Fellow-
ships.yintat&ur surtaattuu.edd edu UUniversity of Washington.
Part of the work done while visiting Shanghai Qi Zhi Insti-
tute.dgliudw..ed
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

ZZMW17. WYX17, INS 191. 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, FKT200 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.
Gradient
General Convex
Strongly Convex
Complexity
[KST12]
GDvding(L/
6" (1/
N/A
[BST14]
GD 7 y1
6" "log" (o7)))
N²
[BFTT19]
GD//
0 (2dlog(1/8)
N4.5
[BFGT20]
GP /Pg/1//(1/66
N²
[AFKT21]
(og(/6)
6 (/dl)g(/6))
N²/Vā
JNN222
Ours
/D
Ne
Table 1: DP-ERM. Comparisons with previous (e, 3)ddifferential private algorithms when objective function is G-Lipschitz and convex (or justrooggy convex) over convex set K. R of diameter D. The results are stated asymptotically and the big O notation is hidden for simplicity. The lower bound of General Convex function is Mminn(GD CDVd }) and of Strongly Convex function is (mmin| G² G'd pN }) [BST14].
[KST12) used objective perturbation method to design DP-algorithm with O GDVdlog(1/5) empirical risk. This result was improved significantly by [BST14], who first showed a lower bound of Mminn GDVa }) on the excess empirical risk for DP-ERM. Further, they gave algorithm with
VNo excess
..Dlog log dlog))/) ), which is sub-optimal by a factor of log (N/8). 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 due to two reasons: 1) The strong composition theorem requires that each step one needs to add Gaussian noise with a larger variance; 2) They used aub-optimal convergence rate Ollog T/ /T) for T-step SGD.
excess empirical risk O GD
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 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] inefficient and leads to O(N44. ) -graadient 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) 3-gadient computations. The privacy analysis of this result also used Moments Accountant method, and they used the standard online-to-batee conversion technique [CBCG04] to prove the high-probability and expectation bound on the excess empirical error of SGD.
make the function smooth. However, this technique is computationally
As 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 -gga)ggga computations. As Table 2 shows, a similar situation arises in Stochastic Convex Optimization (SCO), which is 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 non-trivial result for general convex loss functions achieving excess population loss of 2/4
GD
was given by [BST14), 4], who showed the result by first solving the ERM prob- Ne

---

lem and bounding the generalization error. They used the result on universal convergence directly, namely, bounding sup (w) [(w]] But this method has its limitations; For example, [Fel16] showed that lower bound of universal convergence is Q Q(Vd/NV 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 these papers relied on recent advances in the privacy techniques such as the Moments Accountant method IACG+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 pop- ulation 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] do the generalization error analysis.
General Convex
Strongly Convex
Gradient Complexity
[BSTI4]
CD
17 logla/6) 1h (n//6)))))))
N/A G
N
VN
[BFTT19]
CDI vR
Veloz(1/0))
1
dlog(1/b)
N 2
[FKT20]]
GD
V
C²
d Booil (0)
N log(1/6)
N'***
[BFGT20]
GDI
/elooua//on
Ne
G
+
ellogg 16)
Ni
N²
[AFKT21]
GD(
/alog(1/0)
+
dloogt//0)
min (N4/2 N3/vd)
J6
Ours
/D
dlog(1/66
min
Ne
J
Table DP-SCO. Comparisons with previous (s, J--differential private algorithms when objective function is G-Lipschitz and convex (or p-strongly convex) over convex set K. Rd of diameter D. The results are stated asymptotically and the big O notation is hidden for simplicity. The lower bound of General Convex function is S2GDD VN + )) and of Strongly Convex function is 2 G² (N +
dllo((1/))) [BST14]. N2ga
Despite these impressive improvements, as the Table 2 suggests, the previous algorithms that achieve the optimal excess population loss still require O )-gradientt computations. Indeed, [BFGT20] write that Proving that quadratic running time necessary for general mon-smooth DP-SCO is 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.
1.1 Our Contributions
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 pnerpearamttrizzation (d 2 N), we achieve a bound of ((N1+3/8) Let K,, = (v y = w + w E K, E R4, ||=||/ S r.. We now state the result formally.
Theorem 1.1 (DP-ERM). Suppose K. C I& is closed convex set and (s(, JEEE is family
of G-Lipschitz and convex functions over Kr, where r D 4, For e, < 1/2, given eN
any sample set S consists of N samples from E and arbitrary initial point wo E K. we have (e, diifffrrrntl private algorithm A which takes
o
E d1/8 log (1/8))
+ N²
d dloo(118)
gradient queries and outputs wT such that B[F(wr)) - Fr = o GDD/dlog(1/8)
where D
eN
l|w" - wollz, F(w) En fw, x;), Ft minwer F(w), and the expectation taken over the randomness of the algorithm.
/elog(1/8) NN < 1. or any feasible solution is good enough.
We only need consider the non-trivial case when This means that O(D), which is mild assumption.
3

---

Moreover, if (f x) tee is also p-strongly convex over Ky, we can meet the same gradient query complexity and get a solution wT such that B[F(wr) Fr] O
('dlog(1/6) pE
The main contribution of the paper is to use the above result to obtain 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 E, 6 S 1/2 and sample set consists of N samples drawn i..d from Joez distribution P over E. Suppose (f(;, Jaez is convex and G-Lipschitz with respect to l norm and
convex over Ke, where r D D//log(1/88) there is an (e, -ddifferretliallyy private algorithm taking cN
eN3/2
O(N min /in
})
d log 1/4 (1/6)
gradient queries to get a solution wr such that B[F F(w")] O(DD(
/dlog(1/8)
VN
Moreover, if {f(;,z) (<em is also p-strongly convex over K,,, we can meet the same gradient query complexity and get a solution wT such that [[[(wT) - F(w')) = _2 N' + +2))
d
Finally, we note that with straightforward modifications, results can also capture the regularized ERM and SCO, where there is one more simple (and convex) function h(w) added to the objective function and the objective function takes the form & Enyes fww ..)) + h(w), which show up often in the previous work such [RBHT09, KST12, WYX17, INS 19].
1.2 Our Techniques
Most 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 Q21 ((/vVT) 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 ~ o
Lemmna 3.7
(private) ERM:
couvex
strongly convex
Lemma 3.6
Theorem 4.1
Temma 3.7
with 2² G² (6)(1/8) to each gradient. By standard analysis of SGD, we can only show an excess empirical risk of O DVV02 which requires to set T S(N2) get ideal bound, thus hitting the quadratic barrier.
(private) SCO:
COnVEX
strongly convex
Lemma 5.5
Reductions between ERM and SCO for general convex and strongly convex cases. Lemma 5.5 is in the full version in the supplementary ma- terial
Figure I:
We deviate from the above approaches for de- signing private algorithms for non-smooth fune- tions. First notice that the gradient complexity
O 2:78 (11// + [Tog(1/4) 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 we can achieve optimal empirical risk (population loss) for one case, then
N222
achieve optimal empirical risk (population loss) for another with the same privacy guarantee and gradient complexity. The Figure illustrates the relationship among these different problems.
Our result for the general convex non- non-smooth case obtained by providing reduction 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 [GL.12] for solving strongly convex stochastic optimization problems. However, this 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 (max ///////////// /d /0/////2////0 /N/dd))
For SCO, we get the gradient complexity of O (mmin{ // / _/3//////// /N3/2/dd//] via application of the iterative localization approach of Feldman et al [FKT20]. The intuition behind iterative localization using private ERM to solve regularized objective functions which have low sensitivity, iteration by iteration. Each iteration reduces the distance an approximate minimizer by multiplicative factor, so after logarithmic number phases we are done.
1.3 Concurrent and Independent Work
In an independent and concurrent work, [AFKT21] give 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.
More formally, they get Ollog N (N3//2 d, N2 /Vd) for SCO in
grddent companiity & 0,99))
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 S N1+1/3 Same holds true for ERM. Finally, we remark that the main motivation of [AFKT21] was to study SCO problem more general Ep norms as much of the literature has focused on the fn-norm. They also give new results in Ep bp-bounded domain together with another concurrent work [BGN2I].
18-
Trivial For 2
16
Our Remit
Banalt in [AFKT22]
State Of Art
0.5
1.5
0. didimnsion is A
Preliminaries
We recall some basic definitions in convex optimization and DP.
Definition 2.1 (I-Lipschitz Continuity), A function / K. i L-Lipschitz continuous over the domain K. Rdd if the following holds for all w. w' E K
S L|l - w'll2-
Definition 2.2 (--Smoohnness). A function f K. - E is 3-smooth over the domain K. c IR if for all w,w' E K., [V](() - Vf(w")l2 S Bl|w - 22
Definition 2.3 (u-Strongly convex). differentiable function f K
called strongly con-
vex with parameter μ 0 if the following inequality holds for all points w, E K. (Vi(w) Vf(w"), - w²) 2 p||l w' Equivalently, f(w') 2 f(w) + Vf(w) (w> w) + + w
Definition 2.4 (Differential privacy). randomized mechanism M (c. -)-differentially private for any event O E Range(M) and for any neighboring databases S, S' that differ in single data element, one has
Pr(M(S) E <
<xx()) (ex((()
2.1 A Meta Algorithm for DP Convex Optimization
Many DP convex optimization algorithms with noisy first-order information have the following simple format.
5

---

Algorithm 1:
Private Meta Algorithm METApp
Input:
Sample set S { EN J. the objective convex function F ((w) we want to minimize, the initial point w/, and privacy parameters 6;
2
Process:
for phases 1,... do
Select random sample set St from the uniform distribution over all subsets of S of size B;
Let G2 es. ff(we-1, 24) /) where oN Update the result by some sub-procedure
Sub-procedure(ww--1 G.);
end
7 Output: Some function of (wiJ211
Compared to non-private algorithms, DP algorithms make two simple modifications to make private. First, compute gradients calibrated Gaussian noise to these gradients and take average, before updating our results. The DP analysis then follows from 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] using the framework of sub-samp sub-sampled Gaussian mechanism, for which we can use tCDP proposed in [BDRS18] 18.. As this is direct application the main result in [BDRS18] we leave the proof of the following theorem in the full version attached as supplementary material.
uniform sample of some size B. Next, we add carefully
Theorem 2.5. Suppose xf(;,)))ed FEE is family of G-Lipschitz and convex functions over K, for E < ei CTTT/N2 B < N/10 and 1/2 2 > 0, by setting a czGB /TGB//loo(//// log(1/6) for some constant C1 and c2, METADp is (e, deifferiirrllntiall private.
eN
3 Differentially Private ERM
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-conver case in the last subsection. Due to space constraints, we won't '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.
3.1 Non-smooth Strongly-conve Functions
We the framework introduced in Section 2.1 and give faster private algorithm. Specifically, modify stochastic convex optimization algorithm (AC-SA) [GL12] to fit into our framework.
Algorithm 2: Accelerated stochastic approximation (AC-SA) algorithm
Input:
Initial point wi K.
Initialization: Set the initial point w/t wo:
3 the step-size parameters O; 142 and 7/- ((++1)
Process:
5 for 1 1,... .' do (1=a)x+t)) Let wind 2 afth w + all(I-a W:-15
7c+(1-af))
Query Oracle G. = (wmmtd)
Wi arg min ( { ( w) + h(w) - kllwondd w|| + [[1 az) hdllu-- - w1
wit .g
onwi + (1 - 01 1
10
end
11
Return: w
First we recall some properties of the algorithm AC-SA. Suppose f K. + R is convex function, and the objective to get V²* == minwek { (w) f(w) + h(w)), where IC is a closed convex set and h(w) is a simple convex function with known structure.
Theorem 3.1 (Proposition 9 in [GL12]). the following conditions met:

---

For some L 2 M, 2 0 and > O, file - - S f(y) - f(w) - (g(w).v - w) f lly - w11 M (yy w|12, Yu,y K. where g(w) E Of(w) and of denotes the lub-differential of f at w.
each call of the stochastic oracle with the inpur wi K. the stochastic oracle g can output an independent vector (wwz) such that ([G( E @f(w).
For any 2 1 and Wt E [[l(((w) - ((()) SV.
Then, AC-SA (algorithm 2) outputs wr after T iterations such that B(V(wrr) Vi S MV+ where w" = arg min (w) and Ap* (ww)..
0 Liwwa Ailww-"""
3.1.1 Smoothing Function
From the statement of Theorem 3.1, it is clear that the algorithm in [GL12] gives much better convergence rates for smooth functions. As efficient way to smooth the objective function without introducing too much error. In the next few paragraphs, show how achieve that. Recall that D denotes the diameter of the closed convex set IC C Rdd. Suppose {) 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(w) we consider is G-Lipschitz and j-strongly convex over the domain K. We a convolution on f((xz), which is denoted by f(),r) nty- The objective function after the convolution step becomes Fn, (w) = 1 Ex,es Es yyon, f(w y, 2,), where n, is the uniform density on the l ball of radius r. We need
considering non-smooth functions, need an
the following claim:
Claim 3.2. Suppose (f(, x)) Jeez is convex and G-Lipschilz over K. + B2(0,r). For w E K,K, (w) has following properties:
1) ((w)= & F.,(W) & F(w) + Gr;
2) F., (w) is G-Lipschitz:
3) Fr, (w) Gvd -Smooth;
4) For random variables y and uniformly from S, one has fw y,,)] VFn, (w) and B n.. (w) VWw v,,))13) G
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 [DBWI2). Furthermore, the convolution operation preserves strong convexity, which implies the fact below.
Fact 3.3. Let n, be the uniform density the E ball of radius and f Krr - R be p-strongly concct over K,,.. Then Eyon, fly +.) is p-strongly convex over K.
3.1.2 Algorithm
Recall that y n, is d-dimension vector drawn from the uniform density the fg ball of radius Our algorithm described in Algorithm 3 below, which a modification of Algorithm
Algorithm 3: Private AC-SA
Input: A convex set I.' with diameter D, a family (f(,, of G-Lipschitz and p-strongly convex functions over K. an initial point wo E K., privacy parameters e, ó, the batch size B, and the number of
steps T.
Tair and a + O GB GBV/Too((/0)) eN
2 Set +
D
3 Run the AC-SA with the Oracle 9 defined below; Return: The output of AC-SA
5 Oracle ((w):
Select random sample set St from the uniform distribution all subsets of S of size B.
Return: (Enes, 0.(w 2,) v)/B, where yi n, for each i [B] and v ~ NO, Iaxx))

---

3.1.3 Utility and Privacy
It is not hard 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 e S eI B9T/N2, < 1 1/2, B < N/10 and o c2GB B.GB/Tlog(1/5) where Ci S
eN
1, 2 1 are constants, Private AC-SA SA is (e, 8)-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 output wr such that
E [[F(WT) ]= =0 (G/B++Ad/ (
GDd
Pf
T
where w" arg ein F(w), and F min F(w).
Before stating the main result of this section, need the following lemma that removes the dependence on the diameter term. Recall that the lower bound of strongly convex case is Qmmin , (' while for the general case is Q(min(GD, GDV/llo(110) }). Therefore,
only need think about the case when d'lo(11/8) 1, the bound will be trivial. The following x² 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
reduce the Strongly- Convex Case to General Convex Case. The following lemma follows from the reduction in Section 5.1 in [FKT20], and we try give more formal statement for convenience in the future.
Lemma 3.6 (Reduction to General Convex Case). Given F is G-Lipschitzz and p-strongly con- vex. Suppose for any e, 5 < 1/2, we have an (e, ddifferrrtel private algorithm A which takes wo as the initial start point and outputs a solution wr such that E[F(wr) - -F1
O G'dlog(1/A) + GDvd/og(1//) where wn = arg minwex F(ww) and D = -wwo - w2 Then by N²
eN
taking A as sub-procedure with some modifications on parameters, we can get an (e, -idfferrret
private solution with excess empirical loss most [(F(wz) F-1 = ( (odlog(1/88)
p=²N2 Furthermore, if A uses 6,) many gradients, the new algorithu uses Σ ((N,,/22,00)) 6/22) 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 w of Private AC-SA satisfies [[(((w) - Fr]
G2
P +
22
GDd
Setting o c2GB T1g((1/8)
and T = [ 100e.N
(C1, C2 are
T
eN
0/4 (1o((188)
defined in Lemma 3.4), has
[[F(w)-Fi F+ = =0 O
G²
(dllo((15)) Ne
@DA2/4 =0
G
G'dlog(1/8) No
GDV/log(11/
+
NBT
NBT
cN
To ensure that Private AC-SA (e, 8D- we set B
IV
eN22 T
$ N2
By our choice T,
we have B < N/10 and S BTTT222 Hence, we can apply Lemma 3.4 to conclude the guarantee of (s, 8) differential privacy. Furthermore, get solution such that
(oddlg(11/0) ( GDVdlog(L/0) 2u2222
-
eN
As for the total gradient complexity of our algorithm, we are under the assumption that dlog(1/8) < 1, which means that eN
N2N2
a1/4 a1/4 al/4/oog11/)) 2 d//4 and T = ey di/4 log(11/8)
100eN
O
cN
As for
21/4 (log(1/)) /

---

the batch size, we know
E2N T
(1/6 = w(1) and thus B =
TV EN
T
+
dlog(1/667
Na
CN2 o T
dlog(1/ayT from which we get the gradient complexity is
Na
e
e² N2
BT =
d3/8 log 1/4 (1/0)
d (1
By Lemma 3.6 we can adjust Private AC-SA and get a final solution wr such that
(
(_dlog(1/0) MeRN2
[[F(WT) - F*1 0
with gradient complexity e
i= log No
(e/2")N3/2
+ (e/29)222
O ((1/)/)))))))))
eN 21/"log"
log (2116)
d 221g(2)/5))
(log(178) ) which completes the proof.
Na
3.2 General Non-smooth Convex Functions
In the general non-smooth case, we only assume that the family of functions (ʃ(, x)EE is G- Lipschitz and convex over K. We now give reduction from this case to the strongly-convex case, which completes our main result for ERM.
Suppose K. Rd is a convex set of diameter and let {f(;,)))2E be a family of convex functions over K. which are G-Lipschitz and p-strongly convex. Given any sample set S consists of N samples from Ear and other necessary inputs, suppose we have a (
Lemma 3.7.
(G'dlog(1/8) algorithm A which can output solution wr such that [[(((u)) F*] = F=]= ( pe-N2
where
F. = -minwe F(w). Then when (h(-, [h(-,))]aez is only G-Lipschitz and convex with necessary inputs, for any sample set S of size N, we also have a (e, DDD algorithm A' which can get a solution
wr such that (WT) [I*1 =0 @DVdlog(1/8)
where H H() Ex,es hlw, 22), H minwer (w)). 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 wp = The proof of this reduction is rather simple: After getting (0((;z;))zzee we only need to consider (w, x). h(w, 22 + 1/| Then (,,))) u-strongly convex and O + uDj-Lipschitz for any x with ||ll|2 < D and E K.
For the case uD G. run A (1u((;2;;)),, to get a solution wt with loss E[Hn(wT)
H O (ddlog((//)) where Hu(w) 3 En,sshWws h(w, u|| and H. min Hy(w).
G (dllo((1/)) one has (((( Aim] O dlolog(1/8) uD² DEN
Now by setting
us=N2
GD GD (aloo(11) For the case wD G. have GD > GD and hence we can eN
O
eN
simply output the initial point wp as the solution with loss no more than GD.
The above reduction completes the main result of Theorem 1.1 for the general non- non-smooth case.
4 Differentially Private SCO
As mentioned before, for DP-SCO, we get the desired gradient complexity via application of the iterative localization approach of Feldman et [FKT20]. We prove the reduction theorem stated below, the proof of which is in the full version available supplementary material.
Theorem 4.1. Suppose we have an algorithm A which can solve ERM under strongly convex case and gets solution with excess empirical loss O G ) by using g(N) many gradients, then have nN

---

an algorithm A' which can solve SCO under general case and gets a solution with excess population loss O GD VN
by using Σ Elag N1 g( many gradients.
Moreover, for 8, 6 S 1/2, Ac, is (s, 8) diifferrent private with excess empirical loss O Ue ( dlog(1/6)) under the strongly convex case by using g(N,e, many gradients, then we can get N
V by querying (e, 6) differentiilly private A' with excess population loss O JN
gradients at most D(1og N1 g (NN/2,, 1//22////2) times.
To obtain the optimal bounds for SCO, we first notice that can afford to obtain sub-optimal bounds for ERM (0($ # ( + .'N²
2 ))), 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.
References
[ACG 16] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 308 318, 2016.
[AFKT21] Hilal Asi. Vitaly Feldman. Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates & geometry. arXiv preprint arXiv:2 2021.
[BDRS18] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74-86 84-86,22 2018.
[BFGT20] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochas- tic gradient descent nonsmooth convex losses. arXiv preprint arXiv:2006.06914, 2020.
[BFTT19] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradcep Guha Thakurta. Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, pages 11282-11291 1121,, 2019.
[BGN21] Raef Bassily, Cristóbal Guzmán, and Anupama Nandi. Non-cuclidean differentially private stochastic convex optimization. arXiv preprint arXiv:2103.01272 2021.
[BST14] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473. IEEE, 2014.
[CBCG04] Nicolo Cesa-Biancha Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):2050- 2057, 2004.
[CM08] Kamalika Chaudhuri and Claire Monteleoni. Privacy-preserving logistic regression. In NIPS, volume 8, pages 289-296. Citeseer, 2008
[CMS11] Kamalika Chaudhuri, Claire Monteleoni. and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
[DBW12] John C Duchi, Peter L Bartlett, and Martin J Wainwright. Randomized smoothing for stochastic optimization. SIAM Journal on Optimization, 22(2):674-701, 2012
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[Fel16] Vitaly Feldman. Generalization erm in stochastic convex optimization: The dimension strikes back. arXiv preprint arXiv:1608.0444 2016.
10

---

[FKT20] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 439-449, 2020.
[FMTT18] Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplifi- cation by iteration. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages 521-532. IEEE, 2018.
[FTS17] Kazuto Fukuchi, Quang Khai Tran, and Jun Sakuma. Differentially private empirical risk minimization with input perturbation. In International Conference on Discovery Science, pages 82-90. Springer, 2017.
[GL.12] Saeed Ghadimi and Guanghui Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22(4):1469-1499 2012.
[HRS16] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234. PMLR, 2016.
[INS 19] Roger Iyengar, Joseph Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP). pages 299-316. IEEE, 2019.
[JNN19] Prateek Jain, Dheeraj Nagaraj. and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pages 1752-1755. PMLR, 2019.
[T14]] Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differentially private learning. In International Conference on Machine Learning. pages 476-484, PMLR, 2014.
[KJ16] Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk min- imization for high-dimensional learning. In International Conference on Machine Learning, pages 488-497. PMLR, 2016.
[KST12] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
[Mir17] Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275. IEEE, 2017.
[Nes05] Yu Nesterov. Smooth minimization of non-smooth functions. Mathematical program- ming, 1022 2005.
[RBHTO9] Benjamin IP Rubinstein, Peter L Bartlett, Ling Huang, and Nina Taft. Learning in large function space: trivacy-preservee mechanisms for svm learning. arXiv preprint 10..:00911.5008. 2009.
[TTZ14] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Private empirical risk minimization beyond the worst case: The effect of the constraint set geometry. arXiv preprint arXiv:141 1.5417, 2014.
[TTZ15] Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Nearly-optimal private lasso. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume Volume 2, pages 3025-3033 2015.
[WLK+17] Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-based analytics. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1307-1322, 2017.
11

---

[WYX17] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, pages 2722-2731, 2017.
[YNS12] Farzad Yousefian, Angelia Nedić, and Uday V Shanbhag. On stochastic gradient and subgradient methods with adaptive steplength sequences. Automatica, 48(1):56-67, 67, 2012.
[ZZMW17] Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient private erm for smooth objectives. arXiv preprint arXiv: 0ee.17033.99999 2017.
12


Reviews:
[{"review_id": "BNa8VYjUMFs", "reviewer": "Reviewer_45fX", "summary": "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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper provides nice progress on the problems of DP-ERM and DP-SCO where the authors obtain improved gradient query complexity compared to prior work. Prior work has mainly obtained complexity $O(n^2)$ and this papers achieves $O(n^{1+3/8})$ when $d=n$ (which is currently the best known complexity for this setting). Moreover, the algorithmic techniques are interesting therefore I recommend to accept the paper.\n\nSome of the techniques in the paper has appeared in prior work and this should be mentioned. For example, the combination of smoothening and accelerated algorithms has appeared in [DBW12] in the (non-private) optimization literature. The algorithms in this paper can therefore be seen as a noisy variant of the algorithm in [DBW12] (similarly to noise SGD). Moreover, some of the reductions in the paper has also appeared in prior and concurrent work. The reduction from strongly convex DP-SCO to convex DP-SCO appeared in [FKT20] and the reduction from DP-SCO to DP-ERM appeared in [AFKT21].\n\n\n\nOther comments:\n\n1. The paper is in general clearly-written though some theorem statements could be further improved. For example, the first part of theorem 4.1 can be removed as it is not a crucial part of the theorem. Other theorem statements can be shortened too.\n\n2. In algorithm 3, the randomized smoothing noise (y in line 7) should not be the same for different indices $i$. This is important to enable the variance calculations in the proof (line 303 in appendix).\n\n3. Typo in line 23 in the definition of $F(w)$\n\n4. Maybe use $n$ instead of $N$ for sample size as common in DP optimization literature.\n\n5. line 54: It was actually [FKT20] that first gave $O(n^2)$ gradient complexity for non-smooth functions (not [BFGT20]).\n\n6. Theorem 3.1: the theorem statement says \"there is an algorithm that has\" but I guess this should be \"algorithm 2 has\".\n\n7. Typo in lower bounds in lines 249 and 250.\n\n8. Reduction to convex case (lemma 3.6): doesn't this result follow directly from the reductions of [FKT20] (section 5.1)?\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "8vfVZeyrG_", "reviewer": "Reviewer_qrbc", "summary": "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. \n\nThe main results in this work are:\n\n1. An Accelerated Stochastic Gradient method with randomized smoothing, and therefore applicable to nonsmooth losses (Lemmata 3.4 and 3.5)\n2. A two-way reduction between convex and strongly convex ERM (Lemmata 3.6 and 3.7)\n3. A two-way reduction between convex and strongly convex SCO (Lemmata 3.7 and 5.5)\n\nThese 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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results of this paper are definitely interesting for the NeurIPS community. Arguably, there is not huge novelty in the methods used, but the idea of accelerated randomized smoothing seems novel in the context of differential privacy (this idea has been used in non private SCO and online learning).\n\nI now elaborate further on my comments above:\n\n- Regarding contributions 2 and 3 stated in my previous point, they seem to follow quite directly from the cited work FKT20. This leads to my comment on please being careful on citing the preceding work: It seems to me that Lemma 4.7 in the supplementary follows quite closely Thm 5.1 in FKT20 (the arXiv version). \n\n- Unfortunately, the concurrent work AFKT21 is already capable of obtaining major improvements in complexity. However, the current submission points out that that is not the end of the story, and currently the complexity of DP-ERM and DP-SCO looks quite complex. \n\nFinally, I would like to make some minor comments and questions:\n\n- Does AC-SA provide optimal rates for smooth DP-ERM? If so, what is its complexity? Even if this problem has already been solved (with linear complexity) I thought it could be interesting to consider methods based on acceleration.\n\n- Have the authors tried a higher sampling rate for the randomized smoothing? Right now, a single stochastic evaluation is used, so I was wondering if decreasing the variance of this randomization by using more random directions could improve the complexity.\n\n- In the introduction the term 'universal convergence' is used. I believe 'uniform convergence' is a much more standard term, so I would recommend adopting it. In a related note, the work Fel16 proves lower bounds for uniform convergence in stochastic convex optimization, whereas the paper says 'not necessarily convex.' That should be corrected.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "0arfl4-rZ4f", "reviewer": "Reviewer_fSmY", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overview of the approach/techniques: The main result for ERM is obtained by carefully putting together techniques from convex optimization as well as differential privacy. The algorithm follows the general template of DP algorithms, and the privacy analysis follows readily from prior works. The improvement in the running time comes from utilizing faster convex optimization algorithms as well as a careful setting of the parameters such as batch size to control the noise added to ensure privacy. Specifically, the algorithm uses the standard reduction from the general convex to the strongly convex setting where one adds a strongly convex quadratic term to the objective. In order to leverage acceleration, the algorithm uses a technique from prior work that smoothens the objective via a convolution with a sphere kernel. The resulting objective is now smooth and strongly convex (with some appropriate smoothness and strong convexity), and one can employ an accelerated gradient descent algorithm to optimize it. The algorithm uses the ACSA algorithm and its analysis as a black box for this purpose. After putting together these pieces, the main task is to carefully analyze the utility/convergence tradeoff and find suitable settings for the parameters such as the batch size.\n\nSignificance: The paper addresses fundamental problems in optimization with privacy. The paper shows for the first time that sub-quadratic running time is possible and paves the way towards further improvements. On the negative side, the approach seems to be primarily a proof of concept that faster running time is possible by piecing together existing techniques, rather than an approach that could eventually lead to the ideal nearly-linear running time. \n\nNovelty/originality: Although there is some novelty to the overall approach, the main results are obtained via a careful combination of existing techniques. The paper does not introduce any substantial new techniques.\n\nQuality: Overall this is a solid result and a valuable contribution to differentially private optimization.\n\nClarity: The clarity could be improved by fixing typos. The paper could be made more readable by providing signposting in the technical sections and some further guidance and intuition for the proofs.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "I did not track the hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new algorithm for differentially private stochastic convex optimization and ERM with non-smooth convex losses. Previous algorithms for the problem required a quadratic number of gradient computations. This work uses a combination of a new idea and existing techniques in optimization to reduce the number of steps to essentially $N^{11/8}$. This is a significant progress on a fairly basic question in DP optimization. Therefore I recommend acceptance.
Decision: Accept (Spotlight)