Differentially Private Algorithms for Smooth Nonconvex ERM
Authors: Changyu Gao
Stephen Wright
Venue: Submitted to ICLR 2023 (2023)
Keywords: differential privacy
optimization
machine learning
ERM

Abstract: We develop simple differentially private optimization algorithms that move along directions of (expected) descent to find approximate second-order necessary solution for non-convex ERM problems. We use line search, mini-batching, and a two-phase strategy to improve the speed and practicality of the algorithm. Numerical experiments demonstrate the effectiveness of these approaches.

DIFFERENTIALLY PRIVATE OPTIMIZATION FOR SMOOTH NON- CONVEX ERM
Anonymous authors Paper under double-blind review
ABSTRACT
We develop simple differentially private optimization algorithms that move along directions of (expected) descent to find approximate second-order necessary solution for non-convex ERM. We use line search, mini-batching, and two-phase strategy to improve the speed and practicality of the algorithm. Numerical experiments demonstrate the effectiveness of these approaches.
1 INTRODUCTION
Privacy protection has become central issue in machine learning algorithms, and differential privacy (Dwork & Roth 2014) is a rigorous and popular framework for quantifying privacy. In our paper, we propose differentially private optimization algorithm that finds an approximate second-order necessary solution for ERM problems. We proposed several techniques to improve the practical performance of the method, including backtracking line search, mini-batching, and heuristic to avoid the effects of conservative assumptions made in the analysis.
For given f Rdd > IR, consider the following minimization problem,
min f(w). woRd
We want to find an approximate second-order necessary solution, defined formally as follows. Definition ((gg CH )-2N)) For given positive values of Cg and cHs We say that w an (Cgs CH (H) approxmmate second-order necessary solution (abbreviated as (Eyp )-)-NNS) if
[V=(l S Cg>
Amin (V2f(w)) 2 -H-
We mostly interested in the of cy and cH VMa, that is, seek an (a, VMa)-2NS, where M is the Lipschitz constant for V.
We will focus on the empirical risk minimization (ERM) problem, defined follows, Definition (ERM). Given a dataset D (x1,..., )n) and a loss function Iww, .)) we seek the parameter w E Rd that minimizes the empirical risk
(ww) M(w D) = 72
l (w, m.))
ERM a classical problem in machine learning that has been studied extensively; see, for example Shalev-Shwards & Ben-David 2014). In this paper, describe differentially private (DP) techniques for solving ERM.
Previous research on DP algorithms for ERM and optimization has focused mainly on convex loss functions. Recent
research differentially private algorithms for non-convex ERM (Wang et al. 2018a Wang & Xu 2019 Zhang
al. 2017) targets an approximate stationary point, which satisfies only the first condition in (I). Wang & Xu (2021
proposes trust-region type (DP-TR) algorithm that gives an approximate second-order necessary solution for ERM,
satisfying both conditions in (T). for particular choices of fg and ı This work requires the trust-region subproblem to
be solved exactly each iteration, and fixes the radius of the trust region small value, akin "short step" in
line-search method. An earlier work (Wang et al.) (219)) proposed the DP-GD algorithm, which takes short steps in a noisy gradient direction, then sorts through all the iterates so generated find one that satisfies second-order

---

necessary conditions. Our work matches the sample complexity bound in DP-GD, which is O /+vp for p-2CDP
or O dv/n(1/0)) for (e, 8)-DP for finding an (a, VMa)--NS, and has an iteration complexity of ((a Our a²e
contributions can be summarized as follows.
Our algorithm is elementary and is based on a simple (non-private) line-search algorithm for finding an approximate second-orde necessary solution. It evaluates second-order information (a noisy Hessian matrix) only when insufficient progress can be made using first-order (gradient) information alone. By contrast, DP-GD uses the (noisy) Hessian only for checking the second-order approximate condition, while DP-TR requires the noisy Hessian to be calculated at every iteration.
Our algorithm is practical and fast. DP-TR has slightly better sample complexity bound than our method, depending on a -T/1 rather than o 2 However, since our analysis is based on the worst case, we can be more aggressive with step sizes (see below). DP-TR requires solving the trust-region subproblem exactly, which is relatively expensive and unnecessary when the gradient is large enough to take productive step. Experiments demonstrate that our algorithm requires fewer iterations than DP-TR, does less computation on average at each iteration, and thus runs significantly faster than DP-TR. Moreover, we note that the mini-bater version of DP-TR has sample complexity O(a ?), matching the sample complexity of the mini-batch version of our algorithm.
We use line search and mini-batching to accelerate the algorithm. Differentially private line search algorithms have been proposed by (Chen & Lee 2020). We use the same sparse vector technique as used by their work, but provide a tighter analysis of the sensitivity of the query for checking sufficient decrease condition. In addition, we provide rigorous analysis of the guaranteed function decrease with high probability.
To complement our worst-case analysis, we propose heuristic that can obtain much more rapid convergence while retaining the guarantees provided by the analysis.
The remainder of the paper is structured as follows. In Section 2, we review basic definitions and properties from differential privacy, and make some assumptions about the function f to be optimized. Section 3, we describe our algorithm and its analysis. We will discuss the basic short step version of the algorithm in Section 1,1, and an extension to a practical line search method in Section 3.2. A mini-batch adaptation of the algorithm described in Section 3.3. In Section 4, we present experimental results and demonstrate the effectiveness of our algorithms.
2 PRELIMINARIES
We use several variants of DP for the need of our analysis, including (e. 6)-DP (Dwork & Roth 2014). (a.c)-RD) RDDP (Mironov 2017), and =CDP (Bun & Steinke 2016). We review their definitions and properties in Appendix A
We make the following assumptions about the smoothness of the objective function f-
Assumption 1. We assume is lower bounded by f. Assume further that f is G-smooth and has M M-Lipschitz Hessian, that is, for all W1, W2 dom(f),
[V/(w - V (w2) - Gl|w - -wll: [V2 - 2 (ww)) < M M|[ -wall:
(2)
(3)
where || denotes the vector 2-norm and the matrix 2-norm respectively. We use this notation throughout the paper. For the ERM version of f (see Definition 2) we make additional assumptions.
Assumption 2. For the ERM setting, we assume the loss function is l(u, x) is G-smooth and has M-Lipschitz Hessian with respect to w. Thus T(W,, D) (the average loss across samples) is also G-smooth and has M-Lipschitz Hessian with respect to w. In addition, we assume 1(w, 2) has bounded function values, gradients, and Hessians. That is, there are constants B, Bg. and Bи such that for any w, we have,
0 [( x) < B, Ww xw), s BB,
II x)|| Bu-
As consequence, the 12 sensitivity of L(w, D) and (L(w, D) is bounded by B/n and 2By/ / respectively. We have
| D) - L2 D')lE S Vdllv? D) - V2I(w, D'Il < 2B Vd
2

---

To simplify notation, we defin g(w)= := ( and H(w) = flw) From the definition 20 of ez-sensitivity, we have that the sensitivities f. 9. and H are
B
Bg
2B vd
D =
Ag =
AH
(4)
3
MAIN RESULTS
Our algorithmic starting point is the elementary algorithm described in Wright & Recht (2022 Chapter 3.6) that has convergence guarantees to points that satisfy approximate second-order necessary conditions. For simplicity, we use the following notation to describe and analyze the method:
fk : f(wx), 9k := g(wx) - V((w)), H2: = H (wx)) v2 f(wx).
We employ the Gaussian mechanism to perturb gradients and Hessians, and denote
gk gh + Eki Hs 11, Ex:
where E (O, Ta) for some chosen parameter og and F.. is symmetric matrix in which each entry on and above its diagonal is i.i.d. as N (0, );), for some chosen value of ø Let X denote the minimum eigenvalue of H3 with Pa the corresponding eigenvector, with sign and norm chosen to satisfy
P 1 and (p%) Ok S O.
(5)
Algorithm specifiie the general form of our optimization algorithm. We will discuss two strategies - a "short step" strategy and one based on backtracking line search directions 9k and pk. respectively. For each variant, we define a quantity MIN DDC to be the minimum decrease, and use it together with specific lower bound on f to define an upper bound T of the required number of iterations. In each iteration, we take a step in the negative of the perturbed gradient direction Ok if [[ fg. Otherwise, we check the minimum eigenvalue Å of the perturbed Hessian Hx. If d₁ < -CH we take step along the direction Pk. In the remaining case, we have ||0x || S fg and À 2 -,,,, so the approximate second-order necessary conditions are satisfied and we output the current iterate Wi as 2NS solution.
choose the step sizes "Kkgg and "N, be taken along the
The quantities ff, g-- 0H determine the amount of noise added to function, gradient, and Hessian evaluations, respectively, with the goal of preserving privacy via Gaussian Mechanism. We can target certain privacy level for the overall algorithm (p in p-zCDP, for example), find upper bound on the number of iterations required by whatever variant Algorithm|[] (ee we are using, and then choose o, gg. and он to ensure this level of privacy. Conversely, we can choose positive values for o,, gg. and σh and then determine what level of privacy be ensured by this choice. We can keep track of the privacy leakage as the algorithm progresses, leading to the possibility of adaptive schemes for choosing the o' o's.)
3.1
SHORT STEP
In the short step version of the algorithm, we make choices for the step sizes that are independent of k:
2| M
kkgg G' 7hH =
The choices of MIN MIN and the noise parameters o, og. and 0н are discussed in the following results.
First, we discuss the privacy guarantee and its relationship to the noise variances and the number of iterations.
Theorem 1. Let the noise variances f. gg. Tn be given. Suppose a run of Algorithm takes ky gradient steps and
1 + ki negative curvature steps. Then the run is p-zCDP where p p= 2 03
ky tk
+
kg 0
Recall that T is the maximum number of iterations defined in 66. Let p = 1
7/
)
We always have p 2 p.
so the algorithm is P-2CDP. Conversely, for given > O and Pj E (0, p). we can choose
T
0f
0 = o = PS
(8)
2pr
to ensure that the algorithm p-zCDP.
3

---

Algorithm DP Optimization with Second-Order Guarantees
Given: minimum decrease per iteration MIN_ RRN, tolerances eg and er, noise parameters oy, og and 0F Initialize w and sample 2 ~ (N (o,))
Compute upper bound of the required number of iterations follows
f(w") + |2| - -
T
(6)
MIN_DEC
Set 0g and using T (See theorems for details)
for k == 1, .,, T do Sample S . (0. TT) Compute the perturhed gradient Øs = 9k + Ek
if [[ák] || Eg then
Choose "k,9 and set Wi+1 f- Wk Kk.99k
P Gradient step
else
Sample Eg such that Eg a x d symmetric matrix in which each entry on and above its diagonal is i.i.d as N (0, ())) Compute perturbed Hessian Hr = H + Ex and (Ak, pk)
if ' -H then
Choose " > and set wh+1 t wkk + NH.HPs
> Negative curvature step
else
return Wkk end if
end if'
end for
Proof. The proof follows directly from the zCDP guarantee for the Gaussian mechanism combined with postprocessing and composition of =CDP.
our algorithm, the actual noise is scaled by the corresponding sensitivity A defined in We the same for later algorithms. In practice, we expect most steps to be gradient steps, so f an overestimate of the actual privacy level p. can be more aggressive in choosing the noise variances. We discuss a two-phase approach in Section 3.4
Remark.
We now discuss guarantees of the output of Algorithm I
First, analyze MIN DEC in each short step.
Lemma 2. With the short step size choices
(7), if the noise satisfies the following conditions for some positive constants
G, Ct, and 0g such that ej < 2 and 02 <
|| s min (c1Eg> 22 M (1))
(9a)
| S CEH,
(9b)
then the amount of decrease in each step is at least
MIN DEC min (1-20) 201
(
CH
2G Eg.
(10)
(2G
M
The true gradient and true minimum eigenvalue of the Hessian satisfy the following,
I19x|l S (1) ll A -(1 [1 A)
(11)
The constants c, C1, and in the conditions estimates are. MIN DEC is smaller when we choose smaller constants. We will also have a tighter solution as demonstrated in the corollary below. However, translates to a larger required sample size n for our ERM problem, as we will see Theorem
Remark.
9 above control how accurate our noisy gradient and Hessian
need smaller noise to satisfy the conditions ( which in turn
Corollary 3. Assuming the noise satisfies at each iteration, the short step version (using will output a ((1 + ei ci (1 + C)EH) -2NS.
10 of the algorithm
With the results above, we now analyze the guarantees of the fixed step-size algorithm under the ERM setting.
4

---

Theorem 4 (Sample complexity of the short step algorithm), Consider the ERM setting. Suppose that the number of samples n satisfies a 2 Omins where
V2dBBo, log T
CVdBμон log T
Pmmin
max
min (CiEg:
2 M H
сCH
With probability at least {(1- - (11-)((1)))))) - C Cex (- (-cCd))) where and C are universal constants in Lemma D.7 the
output of the short step version (using 77. (10)) of the algorithm is ((1 + Ei) (1 + c)eH)-2NS.
With the choice of a 's in (8) using Ps = cfp os E (0, 1), hiding logarithmic terms and constants, the asymptotic dependence of pmin on (Eg) p and d, is
d vp
0(max
E ::1 c k))1))
7min
(12)
When (eg: (a, VMa), the dependence simplifies to d VP
Ō(a
Remark. When the conditions ( do not hold, the algorithm could fail to converge to ((1 + (1)gg (1 + ())en))-NS First, the noise in the perturbed gradient and Hessian can be so large that the step is not a descent direction. Second, due to the noise, we may terminate early or fail to terminate timely when checking the approximate second-order conditions. If the noise is not excessive, the solution is still acceptable since the noisy evaluations satisfy the termination conditions.
3.2 LINE SEARCH ALGORITHM
Instead of using a conservative fixed step size, we can do a line search using backtracking. The backtracking line search requires an initial value "oo decrease parameter 3 (0, 1) for the step size, and constants Cy (0, c1),
CH E (0, 1- / (022 that determine the amount decrease we need. Each line search tries in succession the values Yo: 3h, 1o...........................1 until value found that satisfies sufficient decrease condition. For gradient steps, the condition is
f(w 79) S (w) c
(SD1)
while for negative curvature steps it is
[(w (w) S s(w) - =
(SD2)
To make line search differentially private, we use the sparse vector technique from (Dwork & Roth 2014). We define queries according to (SDT) and (SD2):
9 w) = f(w) - f(w - -gg) - "1,13
(13a)
1
@ w) = f(w) - f(w 7D) c 21,,,
(13b)
whose nonnegativity is equivalent each of the sufficient decrease conditions.
Algorithm 2 specifies the differentially private line search algorithm using SVT, which is adapted from AboveThresholl algorithm (Dwork & Roth 2014).
By satisfying the sufficient decrease conditions, we try to get a more substantial improvement in the function value than for the short step algorithm. As a fallback strategy, we use step sizes similar to the short step values (differing only by constant factor) if the line search fails, yielding a similar decrease to the short-step case. We state the complete algorithm enhanced with line search in Algorithm In the algorithm, we compute the fall back step size & and use a multiplier (b > 1) of them as the initial step size by for the line search. We compute the query sensitivity Ay accordingly and call the private line search subroutine to find a step size 7 that satisfies the sufficient decrease conditions.
We have the following privacy guarantees.
Theorem 5. Suppose that f. ag. Tn, and are given. Suppose an actual run of the line search algorithm takes kig gradient steps and kn negative curvature steps. The run is P-2CDP where = 07
kg-ka
KH
kgg.
kg
0
X
5

---

Algorithm Private backtracking line search using SVT
Given: query and its sensitivity Ag. initial step size multiplier 6, fall back step size y, decrease parameter 3, privacy parameter A
function DP-LINESEARCHOA 4g jnit 7,8,A)
Initialize 7 1 m
Sample { ~ Lap g)
for 1, .... max [log 7m11
+ do
Sample V/ ~ Lap (4)4g) q)
Evaluate 9: {(7) and d: 9: + Vi
if q: 2 { then
HALT and output 7
else
Set 7 < By
end if
end for
HALT and output 7.
end function
Algorithm DP Optimization algorithm with Second-Order Guarantees and Backtracking Line Search
noise bound parameters C1s C2 C, sufficient decrease parameters Cy. Cи and initial step size multipliers bg by. line search decreasing parameters Sg. ßh, tolerances and éн, noise parameters o, Tg. σh and ÄSvt Initialize wO, sample ~ (O, 7} and compute MIN LDC according to (17
Given:
[(wu)+
Compute an upper bound of the required number of iterations T MIN DEC
Cg) /G for k + 1.2...... do Sample Sx ~ - (0. TTa Compute the perturbed gradient ØR = 9k + Ek
Set 7g + (1
perturbeddoo.
if
[ > Eg then
Define 9k.g (7) = (Wx) - f(wk 7gk))
Cg 11
Set 7k.9
innt + byfig. Auso + n 1k. By 111lákl1
Line search query sensitivity Backtracking line search
Tk.a DP-LINESEARCIIQQ.. Aac.. Th.s Jo Bg ÀSvT)
wk+1
wi 9k.99k
> Gradient step
else
Sample F& such that Eg is a d x d symmetric matrix in which each entry and above its diagonal is i.i.d. N (0, o Compute perturbed Hessian H H₂ Eg
Compute the minimum eigenvalue of H2 and the corresponding eigenvector (Ne. pk) satisfying S
if d < -EH then Define qu, (7) f(wx) s(w + YDu) 1
Set THH < to Aa//M, init <- bHT Agn, + 2 init Bg TKHH
1R
N <- DP- DE-LENESEARCH(QH Agey HR 7.. BH \Svr)
Backtracking line search
Wk+1 +- HP,
& Negative curvature step
else
return wt end
end if end for
Recall that T is the maximum number of iterations defined in (6). Let p 2
07
+
T
5,
o
x
We always have
P 2 p. the algorithm is p-zCDP. Conversely, for given p 0 and Pʃ E (0. p). we can choose
3T
2pf
0 g
H
x2
2(p - 05)
(14)

---

to ensure that algorithm is p-zCDP.
Proof. We know that SVT is (1/A)-DP. Thus, satisfies (1/(2X²))- CDP The result follows directly from the >CDP
guarantee for the Gaussian mechanism combined with postprocessing and composition of 2CDP.
]
We now discuss the guarantee of the output of the algorithm. We first derive necessary conditions for sufficient decrease.
Lemma 6. Assume the same bounded noise conditions (9 as before. With the choice of sufficient decrease coefficients
Cg -1), E (0,1-c (22) ler 79 21 c1 -1-cg) cy) /G and 7и t2lA//M as defined Algorithm 3
the sufficient decrease conditions (SDI) and (SD2) are satisfied when S iig and r E ((1/62) ) respectively, where 0 < t < t2 are solutions to the following quadratic equation (given our choice of c, C22 CH, real solutions exist).
r(1) = -
6 2 - cB) -- 02 =0
Explicitly, we have
t1, 12
3 (1 c cH) + 3
1 -1-
4
1
22.
2
(15)
In particular, we have 9o 2 and qu (7 2
We now derive the minimum amount of decrease for each iteration.
Lemma 7. Using DP line search Algorithm 3 assume the same bounded noise conditions (9) as before. With
the choice of sufficient decrease coefficients Cg E =00,1 - cı), cH E (0,1- c v (22)). define ig and Sn as
(0,1-ca),cp
before. Choose initial step size multipliers by. by 1 and decrease parameters Bg (0, 1),1),8 3H E (t//t,, 1). Let Imax = [log max(by. by)l + 1. If satisfies the following:
n 2 16A (log imax + log ) max
Bg
B.M 12ene
2bg
AbH
(16)
2 H
Cgtg
with probability least 1 - E/T, the amount of decrease in a single step is at least
MIN DEC min (11-a--c)en
1 2
cHtz 4 M²
(17)
With the results above, we can now analyze the guarantees of the line search algorithm under ERM settings. Theorem 8 (Sample complexity of the line search algorithm). Assuming the same conditions in the previous lemma, with probability at least {(1 - {1 C exp (-oCd))(1 - E/T))T, suppose the number of samples n satisfies
n Z Amin where
T 7 2d log
CydBnon log T 7
161 log imax + log( 2)) max
Bg Cgeg
B&M 1yCH
Rymin = max
min
22 (1) (CiEg
CEH
26
4bи
2 H
(18)
The output of the algorithm is ((1 + c))cg (1 + c)cH) -NSS. With the choice of o and X in terms and constants, the asymptotic dependence of Amin on (cg. CHr) and p.
14 hiding logarithmic
(6- -1 1-2
gg 18:50 cg EH cH 72))
Tomin
max
(19)
When (cg, (a, v Ma), the dependence simplifies to J -))
Proof. The proof is similar to Theorem 4 (see Appendix D.4 using Lemma 17 We have an additional term our success probability due the SVT line search step. For the asymptotic bound of Munin note that MIN DEC (17). T. Oy and HH are the same as those of the short step algorithm, up to a constant. The additional requirement (16 for n is
Since we choose À = ag. it is in the same order as the first term inside the max expression 7a in 18). Thus, the asymptotic bound of Rumin the same as that of the short step algorithm.
O
AlogT
maxie, +t
7

---

3.3
MINI- BATCHIITHIGG
We can use mini-batching to speed up the algorithm. Specifically, in each iteration k, we sample mn data points from D without replacement, forming the mini-batch Sg. The objective now only computes the average risk over set Sk, that is,
fk.se
: m
Σ &
e (w, x.)..
Likewise, we modify all the prior algorithms by evaluating the gradients and Hessians over the mini-batch Sg. We show that the sample complexity of the mini-batch version of the algorithm remains Ö doddyiinn //ln(1/6) when (cg: (a, VMa) for (e, The details are in the Appendix B
ea?
3.4 DISCUSSION: PRACTICAL IMPROVEMENT AND EIGENVALUE COMPUTATION
The estimate of T in 66) is pessimistic, based on MIN DEC obtained from our worst-case analysis. we now propose two-phase strategy to speed up the algorithm. In the first phase, we use a fraction (say 3/4) of the privacy budget to try out smaller T, which corresponds to less noise and quicker convergence. If we are unable to find desired solution, we fall back to the original algorithm with the remaining privacy budget and use the last iterate as a warm start.
In the actual implementation, we can use Lanczos method to compute the minimum eigenvalue and eigenvector: This will slightly change our analysis. See Appendix Ofpe a discussion. We comment that Lanczos method only requires Hessian- vector product and thus the full Hessian is not required. We can use automatic differentiation or finite differencing to obtain Hessian-vectt vector product efficiently, reducing the time complexity of this step to ((d) from (dd))
4 EXPERIMENTS
We earry out numerical experiments to demonstrate the performance of our DP optimization algorithms, following similar experimental protocols to (Wang & Xu 2021). We use Covertype dataset and perform necessary data pre- processing. Details of the dataset and additional experiments can be found in the Appendix E
Let x; be the feature vector and y/ E ([11++1 be the binary label. We investigate the non-convex ERM los
min WERP
Σ
log (1 + exp (-9s (z,, + r(w),
where r(w)= = Σi=
Auc W
is the non-convex regularizer. In our experiments, we choose À 10-3
We implement our algorithms and DP-TR in Python using PyTorch. F To make the results comparable, we modify DP-TR so that it explicitly checks approximate second-order necessary conditions and stop if these conditions are satisfied, in the same way as in our algorithms. We run the experiment under two settings:
Finding a loose solution: cg = 0.060 and En R= 0.245. In this setting, our requirement for the 2NS is loose. This translates to a large sample size n compared to the required sample complexity.
Finding a tight solution: Eg = 0.030 and eµ A 0.173. In this setting, our requirement for the 2NS is tight. We have a small sample size compared to the required sample complexity.
For each setting, we pick different levels of privacy budget e and run each configuration with five different random seeds. We convert differential privacy schemes to (e, 8)-DP when necessary for the comparison. We present the aggregated results in the tables below. In each entry, we report mean + standard deviation of the values across five runs. If any of the five runs failed to find solution, or it found solution but failed to terminate due to the noise, we report the runtime with x. Here, the runtime is expressed in a unit determined by the Python function time werf__ounteeeee ().
In the table, we use acronyms for methods: TR for DP-TR, OPT for our proposed algorithms and 20PT for their two-phase variants, OPT-LS for our proposed algorithms with line search, and the ones with "-B" use mini- bathhbatching.
We still evaluate noisy Hessians in our implementation, since there is no optimized support of this in PyTorch. UUon checking, the loss has Lipschitz gradients and Hessians as long as the feature vector x, 's are bounded. We implement DP-GD but cannot produce practical results using the algorithmic parameters described in the DP-GD paper.
8

---

Table 1: Covertype: finding loose solution: (cg, (H) (0.060, (0.060,0.245)
0.2
0.6
1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.729 + 0.028
10.1 = 9.9
0.729 0.026
8.3 = 8.6
0.729 + 0.026
9.5 9.1
TR-B
0.729 + 0.029
2.2 = 2.0
0.728 = 0.027
2
0.729 + 0.028
2.5 2.4
OPT
0.581 + 0.057
0.712 = 0.018
0.2
0.712 = 0.017
0.5 0.2
OPT-B
0.712 + 0.018
3.1 = 2.9
0.712 0.018
3.0
0.712 = 0.018
2.9 2.9
OPT-LS
0.577 = 0.032
X
0.687 = 0.028
0.4
0.699 = 0.018
0.4
2OPT
0.626 + 0.078
0.712 + 0.017
0.6
0.712 + 0.018
0.6 0.2
20PT-B
0.712 +: 0.018
1.4 = 0.3
0.712 + 0.018
1.4 0.4
0.712 + 0.018
2.0 1.7
2OPT-LS
0.699 = 0.018
0.5 0.2
0.699 = 0.018
0.5 = 0.2
0.699 = 0.018
0.5
Table 2: Covertype: finding tight solution: (Cg. <H) (0.030, 0.173)
0.2
0.6
1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.516 0.005
X
0.607 + 0.007
99.6 32.2
0.607 0.005
90.8 21.6
TR-B
0.517 = 0.005
X
0.603 + 0.005
32.6 + 7.9
0.607 + 0.003
33.4 = 14.4
OPT
0.506 0.001
X
0.535 + 0.015
0.592 + 0.003
1.8 = 0.5
OPT-B
0.597 = 0.003
1.3 + 0.3
0.597 = 0.003
1.3 0.2
0.597 0.003
1.4 = 0.3
OPT-LS
0.525 = 0.009
X
0.527 = 0.009
0,549 + 0.006
X
2OPT
0.502 0.001
X
0.513 + 0.003
0.519 + 0.003
20PT-B
0.597 = 0.003
2.1 0.4
0.597 + 0.003
2.3 + 0.5
0.597 + 0.003
2.3 = 0.6
2OPT-LS
0.577 = 0.008
2.1 1.0
0.591 + 0.001
0.6
0.1
0.591 0.001
0.8 0.2
Experimental results show that for finding loose solution under high privacy budgets & = 0.6, 1.0, our short step algorithm OPT outperforms TR, with much less runtime and lower final loss. Under the low privacy budget = 0.2, although OPT can fail to terminate with success, we see that the final loss is even lower than TR. The reason is as follows, due to the conservative estimate of the decrease, the per iteration privacy budget is low, so cannot check 2NS conditions accurately enough due to the noise. In practice, we can stop early and the solution is still acceptable despite the failure of the termination. Heuristics may be employed to spend extra privacy budget to check 2NS conditions.
Line search and mini-batching improve upon the short step algorithm, especially when combined with our two-phase more conservative theoretical minimum decrease. The
strategy. We remark that similar OPT, OPT-LS has two-phase strategy, using an aggressive estimate of the decrease, complements line search. We observe that 20PT-LS performs consistently well across all privacy budget levels and under two settings. Finally, remark that the number of Hessian evaluations is minimal. See Appendix E.3 for details.
5 CONCLUSION
We develop simple differentially private optimization algorithms based on an elementary algorithm for finding an approximate second-order optimal point of smooth nonconvex function. The proposed algorithms take noisy gradient steps or negative curvature steps based on a noisy Hessian on nonconvex ERM problems. To obtain a method that is more practical than conservative short-step methods, employ line searches, mini-batching, and two-phase strategy. We track privacy leakage using =CDP (RDP for mini-batching). Our work matches the sample complexity of DP-GD, but with a much simplified analysis. Although DP-TE has a better sample complexity, mini-batched version has the same complexity as ours. Our algorithms have a significant advantage over DP-TR in terms of runtime. 20PT-LS, which combines the line search and the two-phase strategy, consistently outperform DP-TR in numerical experiments.

---

REFERENCES
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences, November 2018.
Mark Bun and Thomas Steinke, Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. arXiv:1605.0200 02065 [cs, math), May 2016.
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal on Optimization, 28())1751-1772, 2018, doi: 10.1137/17M1 [RLtts:::///oii
N0.1137/17M1111
Chen Chen and Jaewoo Lee. Stochastic Adaptive Line Search for Differentially Private Optimization. arXiv:2008.07978 [cs, stat], August 2020.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends@ in
Theoretical Computer Science, 9(3 (13-4):211 14:21141:00 1-771, August 2014. ISSN 1551-305X. doi: 10.1561/0400000042..
Jonas Moritz Kohler and Aurelien Lucchi. Sub-sampled Cubic Regularization for Non-convex Optimization. arXiv:1705.05933 [cs, math, stat], July 2017.
Ilya Mironov. Renyi Differential Privacy. 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pp. 263-275, August 2017. doi: 10.1 2011.0.1
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, Cambridge, 2014. ISBN 978-1-107-05713-55 doi: 10. 0007/CCB99781107298800
Terence Tao. Topics in Random Matrix Theory. American Mathematical Soc., March 2012. ISBN 978-0-8218-7430-11
Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2018. ISBN 978-1-108- 41519-4. doi:
Di Wang and Jinhui Xu. Differentially Private Empirical Risk Minimization with Smooth Non-Convex Loss Functions: A -on-Station View. Proceedings of the AAAI Conference Artificial Intelligence, (3(01):1182 1189, July 2019. ISSN 2374-3468. doi: 10. 10.1609/aaii.voo v33ioi...3333333 133011 1182.
Di Wang and Jinhui Xu. Escaping Saddle Points of Empirical Risk Privately and Scalably via DP-Trust Region Method. In Frank Hutter, Kristian Kersting, Jefrey Lijffijt, and Isabel Valera (eds.), Machine Learning and Knowledge Discovery Databases, Lecture Notes in Computer Science, pp. 90-106, Cham, 2021. Springer International Publishing. ISBN 378-3-030-67664--, doi:
3-111778---00--7766--333 6.
Di Wang, Minwei Ye, and Jinhui Xu. Differentially Private Empirical Risk Minimization Revisited: Faster and More General. arXiv:1802.0522 05251 [cs, stat), February 2018a.
Di Wang. Changyou Chen, and Jinhui Xu. Differentially Private Empirical Risk Minimization with Non-convex Loss Functions. In Proceedings of the 36th International Conference on Machine Learning, pp. 6526-6533 6535. PMLR, May 2019.
Yu-Xiang Wang, Borja Balle, and Shiva Kasiviswanathan. Subsampled RV RVenyi Differential Privacy and Analytical Moments Accountant. urXiv:/80s 00088 [cs, star], December 2018 8b.
Stephen J. Wright and Benjamin Recht. Optimization for Data Analysis. Cambridge University Press, Cambridge, doi:
2022. ISBN 978-1-316-51888-4
Jiaqi Zhang, Kai Zheng, Wenlong Mou, and Liwei Wang. Efficient Private ERM for Smooth Objectives. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, pp. 3922-3928, Melbourne, Australia, August 2017. International Joint Conferences on Artificial Intelligence Organization. ISBN 978-0-9992411-0-2 doi: 10. 10.24963/iccai.20117/444
10

---

A A QUICK REVIEW OF DIFFERENTIAL PRIVACY
Definition A.1 ((e, 6)-DP Dwork & Roth, 2014)). A randomized algorithm A is (e, 6)-DP if for all neighboring datasets D, D' and for all events the output space of A, the following holds:
Pr (A(D) E 5) < ef Pr (A((') E +
When d = O, we say A is e-DP. DP-ERM, we say D' is neighboring dataset of D if they differ on just one data point, that is, by changing data point 23 D to z/ obtain dataset D'.
Rényi-DP (RDP) was introduced by Mironov relaxation of the original DP. Definition A.2 (Rényi divergence). For two prohability distributions P and Q defined over R. the Rényi divergence of order is
(P(l)) 1 log Ev
P(w) Q(w)
Definition A.3 ((a, R)-RDP (Mironov 2017)). A randomized algorithm M D + R is (a,c)-RDP if for all neighboring dataset pairs D, D', the following holds
Da(M(D))M(())) 6
Another notion of differential privacy is Zero-Concentrated Differential Privacy (=CDP), which requires linear bound for the divergence of all orders.
Definition A.4 (=CDP (Bun & Steinke 2016)). A randomized algorithm M: D R satisfies (E,p)==CDP if for all neighboring dataset pairs D, D' and a E (1, 0o), the following holds:
Da(M(D))IM('')) S pa.
Equivalently, a randomized algorithm M satisfies CD>CDP if for all E (o), M satisfies (a, & pa)) If this definition holds for & O, we use the term p-zCDP instead.
RDP and cCDP have some properties in common (Mironov 2017
Bun & Steinke 2016).
Proposition A.1 (Composition of RDP). Suppose that Mi D + R1 is (a, (1) RDP and M2 R1x D - R₂ is
(a, RDD.. Then the mechanism defined as (X, Y), where X ~ (D) and Y ~ M2(X, D) is (1 + +22--DDP
Proposition A.2 (Composition of =CDP). Suppose that Mi : D - Ri is PDPPCDP and M2 Rix D + R2 is P2-=CDP. Then the mechanism defined (X, Y), where X ~ (D) and Y M2(X, D) (0) + p2)-=CDP.
Proposition A.3 (Preservation under Postprocessing). Consider the mappings M : D + R and g : R R'. We observe that D (PIIQ) Z Da (P)))l((( by the analog of the data processing inequality. This shows that if M(.) is (a, e) RDP. so is g(M())) Similarly, MM-) (p)-:CDP, so ((M()).
We convert easily from one notion of differential privacy another.
Proposition A.4 (RDP (E,6)-DP). If M is an (a,e)-RDP mechanism, then it is (e+ a-1 8) for any
1/6
0 0< 1.
Proposition A.5 (e-DP to =CDP), If M is an e-DP mechanism, then it is also (fe2
Proposition A.6 (=CDP to (s, 8)-P). Suppose that M D R is (5. P)-2CDP Then M is also (c, 0)-DP for all and
E == p + v 101gg
Thus to achieve (s, 6DDP guarantee for given and 8, suffices to satisfy p),DD)P with
(8 g)
p == (Ve - log(1/6) - Vlog(1/6)) log(L//))
4 loo
A common way achieve differential privacy is add Gaussian noise the output.
11

---

Proposition A.7 (Gaussian Mechanism). Given any function h X - RR, the Gaussian Mechanism is defined as:
G2h(D) h(D) + (0, A2
where A denotes the fz-sensitivity of the function h, defined as
A sup D-D
[l((D) - -b(D))
(20)
The Gaussian Mechanism G satisfies (a, // (202)))) for all a E [1, 00) and thus also satisfies (1/2o?)=:CDP.
We defer results for (c, 6)-DP to Appendix B.2
B ANALYSIS OF THE MINI-BATCH ALGORITHMS
For the line search version of the algorithm, we need additional assumptions if we want to check the sufficient decrease conditions using the mini-bated loss. For simplicity, we only consider the short version of the algorithm in this section.
B.1 RDP ANALYSIS
(In this section, we use m/n to denote the sample fraction.) We evaluate the gradient and the Hessian similarly the mini-batch Sk, which we will write Sk.Sk, Hk.s, and let Sk.St HR.9, be their perturbed versions respectively. The other parts the algorithm remain unchanged. The sensitivity Ag. ft as stated in (4 will be scaled accordingly by replacing in their denominator by the mini-batch size (m.
Let 9le and Hg be the gradient and the Hessian evaluated on the full dataset D. We can decompose the deviation of their noisy approximation follows, l gull S 15..s 9k.8s + 11 9xll
(21a)
Me... H1a < HR... - HR.s. + || H&
(21b)
where the first term in the bound is due to the added Gaussian noise, and the second term due subsampling. We will bound two terms separately with high probability.
We have the following subsampling concentration results from (Kohler & Lucchi 2017 Lemma B.1 (Gradient deviation bound). We have with probability at least 7 that
log(2d/n) n) + 1/4
11gk.s -9ell S 4V2BBy
[Scl
Lemma B.2 (Hessian deviation bound). We have with probability at least 1 that
log(2d/n)
H H1ll < 4BH
[5al
For the subsampling error 21). we use Gaussian concentration results described before to bound the first term, and subsampling results stated above to bound the second term. For iteration h, with probability at least (1 (1 Cee (-cCd))(1 n//T), we have that
T llāx.s. - gull S o log S 4V2B,, log(2dT/n)
log(2dT + 1/4
|S
(22)
HR.s. He CVdnnon + +4Bn
|S+1
It suffices to require that each term in the right-hand sides of the bound above is bounded by 1/2 of the corresponding term in the right-hand sides of (9), so that we can use similar analysis.
12

---

For deviation due to subsampling we need,
(2g( /n) + 1/4
1
4v 4V2B,
min
cieg M HH]
(23a)
Shal
2
log(2d' /n)
1
AB
JCCH
(23b)
[Sk
2
Rearranging the terms, we have the condition for the size of the mini-batch,
|S 2 max
(logg())))) + 1/4) max -- '=²²=""
M
,332' log(2dT/n)) 2 "E7²
(24)
The following convergence result is immediate, based the same analysis in the full-batch case (cf. Theorem g
Theorem B.3. With probability at least ((1- (csp((cCd)( n satisfies 2 Amin where
suppose the number of samples
2v 2v2dB log T 2CVdBBoH log T Ç L2 (1Egg
Pmmia
max
min
M
CEH
(25)
M -4) (
s (GA 1/4) max
Ci
22
E
EH
: 12B33 (2d() BedT//n) 2 2EM²
The output of the mini- batch short step algorithm is a ((1+c))en (1 c)+H))))-2N)) -2NS. With the choice of o in hiding logarithmic terms and constants, the asymptotic dependence of Tmin ( and p. is
Pumin
max (5g 1
6 , cH x2)
(26)
We now discuss privacy guarantees. is impossible to deal with subsampling using 2-CD,, but under RDP, Wang al. (2088) provides generalized analysis for subsampling.
Theorem B.4 (RDP for Subsampled Mechanisms), Given a dataset of n points drawn from a domain X and a (randomized) mechanism M that takes an input from x for S n, let the randomized algorithm M subsample be defined as (1) subsample: subsample without replacement m datapoints of the dataset (with sampling fraction m/n), and (2) apply M: randomized algorithm taking the subsampled dataset as the input. For all integers a 2 2, if M is (a, -(a)))DDPP then this new randomized algorithm M subsample obeys (a, (((a))-RDP where,
1 52 (2)a) min { (((0())-1)
(2) min (2, 2, (errxc) -1) -))
(a) < a
log
a elo-1)a(t) min {2, (e<eee)) (eetx))-1) (27)
j=3
For the Gaussian mechanism, we have
E(a) 202¹
CM((o) and the bound simplifies
c((a) < log 1 + s² a min {a (2100-1) 2e/2// 1/02
Σ
28
=: s)
/=3
which we denote as o)) When is small and is large, we can discard higher-order terms and write the right-hand side as
( -
1
$2 (2 1)
1-1
1
2g a
(28)
0²
where we use the approximation et ~ 11 for small t.
13

---

Theorem B.5. Consider the short step version of the algorithm using subsampling. Given the choice of oj gr HH X and sampling fruction 8. Suppose an actual run of the subsampled algorithm takes kig gradient steps and kB negalive curvature steps. The run is date-dependent (a, < ((o)) where
<(a)
+ (Ri + ( 8) kné 207
Let
20² ((a) = a + T<x((a;a).)) + (e Té
(29)
We always have E(o)= 2 e(o)), so the algorithm (a,, ((a)))
Given the complexity in the subsampled privacy guarantee, e'y 0, 8), we do not have an explicit formula to set parameters gg, Ør. However, given (e, 8D-D privacy budget, we can optimize the parameters to meet the privacy guarantee. Recall the conversion from (a, e(a))) (DD)) to (EDP, ÓDP)-DP, given ó, we solve
EDP(C(-)) = min (((a) + log 1/0pP
a-1
So we can optimize the parameters o, gg oH, such that the following objective is minimized max (ÉDP =Epr((()),
(30)
where D is the target privacy budget and we replace E(.) with their corresponding versions (29
B.2 SAMPLE COMPLEXITY USING (s, D)
Under the (e, 8DD scheme, subsampling is easier to deal with and we will derive sample complexity bound. We first introduce some useful results in (s, D)DP.
Proposition B.1 (Composition of (e. dD-D). Suppose that Mi : D - Ri is (si, 6, DDP and M2 + R2 is (e2, DDP. Then the mechanism defined (X, Y). where X ~M,(D) and Y M2(X, D) (61 D2)-DDP
Definition B.1 (Gaussian Mechanism for (s, 6)-D)) Given any function h X Rd, the Gaussian Mechanism is defined as:
GDD(D) h(D) N
where An be the fg-sensitivity of the function h and v 22 Then, the Gaussian Mechanism G.h.
satisfies (e, d)ddifferential privacy.
Theorem B.6 (Privacy amplification via subsampling (Balle et al.) 2018). Given dataset of n points drawn from a domain X and (randomized) mechanism M that takes input from x for m n, let the randomized algorithm M o subsample be defined as: (1) subsample; subsample without replacement m datapoints of the dataset (sampling parameter n/n), and (2) apply M: randomized algorithm taking the subsampled dataset as the input. M is (E,8)-DP, then M subsample is -')DD, where = log (1 + s(c 1) S s(e - 1)) and 8' = sô.
Theorem B.7 (Advanced Composition). For all Eu, 8g. 5 2 0, the class of (Ea, (o))ddiffrentiale private mechanisms satisfies (s, kō + -differrenll privacy under k-fold adaptive composition for:
/ In (1/8') ke (e 1).
As corollary, for 0 < < 1, it suffices to choose = 2 2k to ensure the composition is k8 + 8'D-DP. In particular, we can in addition choose 8' 8 5/2 and do 6/kkk to satisfy (DP
We have the following privacy guarantee for the algorithm using sampling without replacement,
Theorem B.8. Consider the short step version of the algorithm using subsampling. Given privacy param-
eters E, o, E (0,1) such that Ej < and 8, < 8. subsampling parameter s. Let Eo (E
E, e/)/(8s 2T (n( - 84))) and 5y = (5 (0-85)/(44sT) where T is estimated as before in (6. Set \2 0g TH
2 (111//2//
The algorithm is (s, 8D-P
14

---

Proof. By Gaussian mechanism, the step for estimating T is (E,, D-D.. It suffices to show the remaining steps are (e EG- - )5). Using advanced composition, we only need show that each iteration is (48E0; -
Consider a single iteration without subsampling. From the usage of Gaussian mechanism and sparse vector technique, we know that computing the perturbed gradient step and the perturbed Hessian step are both (Eo, 6-)-PP, whereas the backtracking line search step is eo-DP. By composition, we know that the whole iteration is (250, 26o) -DP. Applying
the Privacy Amplification Theorem B.6 we know that each iteration using subsampling (4s50; )
Since (as earlier) expect most steps be gradient steps, rather than negative curvature steps, we overestimate the privacy leakage.
Theorem B.9. For E (0, 1), setting E₁ = and ōy = cjò, under the choice of parameters og. OH in Theorem B.3 the asymptotic dependence of Rmin in Theorem B.3 on (Eg. EH), (E,8),
7min Ō dd (dVin(1/o) max ( e 'n
(31)
When (Eg. cH) (a, VMa), the dependence simplifies to Ō dy (m((1/) Eo
matching the result in full-batch version of using Proposition A.6
the algorithm by converting p-zCDP to (e, DD via v/p O
de (n1(11/)
Proof. As before, we have VT = =(mmax(<; 1). After simplification, the order of og and is
s /VT/L((25T/0)) = Ô ( max = (333)) /))))
The asymptotic dependence of amin follows by substituting By and σF into (55
C COMPUTATION OF THE SMALLEST EIGENVALUE USING LANCZOS METHOD
In our algorithms, we need to compute the smallest eigenvalue of the perturbed Hessian. This can be done effectively using the randomized Lanczos algorithm. We have the following result from (Carmon al. 2018).
Lemma C.1. Suppose that the Lanczos method is used estimate the smallest eigenvalue of H starting with random vector uniformly generated on the unit sphere, where | S M. For any ó E 10, this approach finds the smallest eigenvalue of H absolute precision of e/2, together with corresponding direction in most
1
M
min 1 +
- In (2.75n/62
iterations
2
with probability at least 1 - 8.
To use Lanczos method in our algorithm, we output an estimate À of Amin (H) along with the corresponding eigenvector, provided that < -CH/2 2. If X > -cH/2 / we declare that Amiu (F) 2 -CH, with an eтror probability at most 8z. Our analysis and convergence results still hold with си /2/2 replacing си and adding the success probability of the Lanezos algorithm 1 ôg to the product of the success probability in each iteration.
D MISSING PROOFS
D.1 PROOF OF 2
Lemma D.I. With the short step size choices if the noise satisfies the following conditions for some positive
constants Ci and C2 such that C₁ < 1/2 and C2 5/2
C2 ||E < min (1Eg M
21
(32a)
Ex S cem,
(32b)
15

---

then the amount of decrease in each step is at least
MIN_DEC min (1-20)
|2G 2G
"g:
2
2
3 02
M
H
(33)
The true gradient and true minimum eigenvalue of the Hessian satisfy the following,
|| S (1 (1) ll
A > -1 c)\
(34)
Proof. We will use the following two standard bounds, which follow from the smoothness assumptions on f:
G
f(w + p) - (w) + V p +
2 llpl
(35)
1 =0" ((w)p
f(w + p) S f(w) + ( p+ For simplicity, we drop the iteration number / in the analysis below.
M |pll
(36)
For gradient steps we have ||ا|| > Eg. We write g = ÿ - e. Using ||||| S cIE < c1 |0 I, follows from 35 that
G
f(w 799) S f 70 ")²' +
3 11
1
5) g+ 2G
G 1
$ f 2G
10
+
| |6
G
$ f 2G
101l
+ c|lاا|
1
f 2G
2c,) |
1
2G (1 2c,) eg.
while the true gradient satisfies
II & |لهl| + ||l|| S (1 + 101-
When negative curvature steps are taken, we have ī < - By assumption we have ||e|| | I сен < c/Al. Recall the definition (5) of and we write
S
24
1712 and
M
H, = H E. From 36 we have
[(w vHδ) S 1 "nn T p
2 THP T Hp-
M 3 || 3
= nHğ" p +
-T' ip THP
Mr ||
7He T
2 2HPP" Ep
2
2
2|
1
2|
2|
2 2 M
ss+
(-1-l) + -M
ETD P
1" Ep
M
M
M
21
||:|| +
||
3
M
M
M
2
202
2c
3
M
2
f
202
2c
3
M
provided that C2 + c < 1/3. Let X denote the minimum eigenvalue of H. It follows from Weyl's Inequality that
j y | < c/A,,
and thus,
A> A - c/1l 2 (Á)
16

---

PROOF OF LEMMA 6
Lemma D.2. Assume the same bounded noise conditions ② as before. With the choice of sufficient decrease coefficients
Cg E (0,1- ei),er en E (0, 10,1-- 1 -- 02), 71 - 21 - ci cg) /G and Yt /22 as defined Algorithm 3
the sufficient decrease conditions (SD1) and (SD2) are satisfied when y 9ig and y E (t1/t2)fiz Ru), respectively, where O < t < t2 are solutions to the following quadratic equation (given our choice of e, C22 CH, real solutions exist),
- 0 21 - -H) 02 02 =0
1
r(1) =
Explicitly, we have
3 (1 cH) + 3
(1- cH)²
2
t1 22
-302
(37)
2
In particular, we have (g( and qıI (5r)
Proof. The analysis is similar to that of Lemma 2 Again for simplicity we drop iteration indices k.
For gradient steps we have ||ق|| > Eg. We write g = 9 E. Using ||=||
S Cic
< c1 1/]
follows from 35 that
G
f(w - 73) $ f(w) 70 - 2) T g +
2 ? ?|1l1?
$ ((w) (1
G
2 ?
|ل|| + +
S f(w) - |
||"|"
2 ci
It follows by definition of 7 that (SDI) holds when S 7/ and
When negative curvature steps are taken, we have À < -EH. By assumption, we have ||=|| S M
1Ā12 and
||||| S cen < c/. Recall the definition (5) of ý and we write g = و - e, H = E. From (36). we have for 7 > that
f(w + 7p) - f(w) + 10" p 2 2
1
Hp +
6 M |||| - -E² 55- - "200" Ep
s f(w)
/ 2 + My² + || 2 >
1
1
1 (57 (|/1))111 - 7 -/ 1//2 - 1
- My3
s f(w)
g(>)
dAA By reparameterizing & = M we obtain
g(7) - - = (
1
- 1 (1- ---cc-e)e--o
[513
[7/3
= r(t)
2
M
M
Note that (D22 holds when g(7) 2 21/1 The result follows from the fact that r()) 2 0 for / E (41,4)
D.2 PROOF OF LEMMA 7
Lemma D.3. Using DP line search Algorithm 3 assume the same bounded noise conditions 9 as before. With
the choice of sufficient decrease coefficients Cg E (0, c))cH E (0, 1 - c v (22) define Fg and Sh as
before. Choose initial step size multipliers bg by > 1 and decrease parameters B, E (0, 10,11,8n, E (11/12, 1). Let imax = [log max(by, by) + 1. If satisfies the following:
By
B&M
72 > 16A (log max + log(TTE)) max
2b Cggg
4bb
(38)
lnc 2
17

---

with probability at least 1 - E/TT, the amount of decrease in single step is at least
cy)o (1- 1
cn 2 f
MIN DEC = min
(39)
M
Proof.
The analysis is similar to that of Lemma] 2
Again for simplicity we drop iteration indices k.
For gradient steps have ||ğ|| > Eg. We write g = Using
||||| city
l/ it follows from 35 that
f(w -0) S f(w) 70 - 8) T g 2 ?|
$ f(w) (1
G
2 "²
| ||
G
S f(ww) - 1 -
2 ? c
l|
It follows by definition of 7g that (SDI) holds when 7 - 7i and
When negative curvature steps are taken, we have X < - By assumption, we have ||||| < 3 < 1 and
|E|| I сCи < c/Al. Recall the definition (5) of p and write g 9 E, H = H - E. From (36) have for y 0
that
f(w + 7D) S f(w) + nī" p
1
p2p Hp
My
75
2 "0"0"Ep
1
2
6
1
1
s f(w)
2 7 [^ My
+ ||
2
$ f(w)
2 e)\
1
- M
1ز12
1
My3
9(
d]] obtain
By reparameterizing 7
g(t) -
2 c = ( - c1-c-een (1--2-cc-
1
c2t)
M = r(t)
[i/3
M
Note that (S22) holds when g(7) 2 21x1 The result follows from the fact that r(t) 2 0 for t tz].
D.3 PROOF OF COROLLARY
Corollary D.4. Assuming the noise satisfies (9) at each iteration, the short step version (using 7 (00) of the algorithm will output a ((1 ( c c)em) 2NS. )-NS.
Proof. From the minimum decrease (10 we just derived, it follows that the algorithm will terminate in 7 iterations, where
f(wo)= f MIN_DEC
T
Our choice 7f (6 is an upper bound 7 and thus the algorithm will halt within iterations. In the iteration when the algorithm halts, we have | S E, and d 2 -EH- It follows from IT that the output is a ((1+c))eg (1 + c)EH) 2NS.
D.4 PROOF OF THEOREM
Theorem D.5 (Sample complexity of the short step algorithm). Consider the ERM setting. Suppose that the number of samples n satisfies 2 Tmmin where
V2dBga, log T CVdBnon log T
Pmin
max
min (c1Eg) M (
CCH
18

---

With probability at least {(1- (1 - C exp
=C where e and C are universal constants in Lemma D.7 the ouipul of the short step version (using 7 (10 of the algorithm ((1 + ei es (1 + e)
With the choice of a' 's in (8) using Pf c&p for es E (0, (), hiding logarithmic terms and constants, the asymptotic dependence of mmin on (Cgs CH), p and is
d _
ò (max vp
(5) 50g E1 1 ,11))))1))) (/
mmin
(40)
When (cg, (a, VMa), the dependence simplifies to concentration results.
Ō(a 2). Before proving Theorem 4 introduce two d vp
Lemma D.6 (Gaussian concentration, Veershynin 2018 ). For N (0, La),, with probability least 1 17 foror any
> 0, we have
| S 2d log
r7
Lemma D.7 (Upper tail estimate for Wigner ensembles (Tao 2012 110)), Let M = (muj)isassa be an x d random symmetric matrix. Suppose that the coefficients may of M1 are independent for i, mean zero, and have uniform Gaussian tails. There exist universal constants C, c >> such that for all 2 C, we have
P
[M > AVd) S C'ex(--Add).
Proof. It follows from concentration results that, in iteration k with probability at least (1 $) C Cexp (-cCd)), we have
T
||E S v2d4 log
(41a)
| CVаднон-
(41b)
We need to find condition that ensures that the right- hand sides are less than the right-hand sides of (9). We substitute for Ag and Aи from ( and solve for mmin by rearranging the terms. The result then follows from Corollary 3
if the concentration results hold for all iterations.
Now let us calculate the success probability. For each iteration, we have a probability of at least (1 - (1-5)(1 Cexp (-cCd)) that the concentration results hold (if do not compute the perturbed Hessian, the probability is higher with least 1 f. Using conditional probability, the overall success probability {[1 {) C Ceep (-cCd))} conditioned on the number of iterations т. Since - < T, the overall success probability is at least {(1 {1 C Cexp (-cCd)))
For the second part, recall from 8 that 0g on vT /V-V With 110 and our choice of T in 6 we have
VT = (max((g 3//2)). We obtain the asymptotic bound of Mumin by plugging in og and d
E EXPERIMENTAL SETTINGS AND ADDITIONAL EXPERIMENTS
We first remark that all experiments were run cluster with 36-core Intel Xeon Gold 6254 3.1GHz CPU, utilizing 8 CPU cores for each run.
E. DATASETS
The Covertype datase contains n = 581012 data points. Each data point has the form (x, y). where x is a 54- dimensional feature vector (first 10 are dimensions numerical, column 11 14 is the WildernessArea one-hot vector, and last 40 columns are the SoilType one-hot vector), and y being the label, is one of (1,2....,77)
DDtt source: UCI Machine Learning Repository httph::/
usi htt.://ww...i//////ttttttt//eeee
19

---

For preprocessing, we normalize the first 10 numerical columns, and keep only those samples for which 1.2. The number of samples remaining in this restricted set is n = 495141. We recode y =
so that y (-1,1)
The IJCNN datase coaataiion n. = 4999 data points.
Each point consists of (ar, y), where z 22-2222-e2e 12-dimensional feature vector (first 10 are one hot and column 11 22 are numerical, and being the label is binary. For preprocessing, we normalize the data.
For privacy accounting of RDP, which is used in the hini-bacched algorithm, we use the autodp packagd m
Below we repeat the same experiment using the IJCNN dataset.
E.2 IJCNN EXPERIMENT USING LOSS IN SECTION
Table 3: IJCN: finding loose solution: (Cg. (H) (0.040, 0.200)
0.2
E 0.6
E = 1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.621 = 0.009
0.71 + 0.025
1.3 + 1.5
0.718 + 0.019
0.8 + 1.1 1.3 + 1.6
TR-B
0.622 0.009
X
0.718 + 0.046
0.4 0.4
0.72 + 0.043
OPT
0.603 + 0.012
X
0.644 0.014
X
0.702 + 0.015
0.1 0.0 2.8 2.3
OPT-B
0.71 + 0.022
2.7 + 2.4
0.71 0.022
2.6 + 2.5
0.71 0.022
OPT-LS
0.671 + 0.03
X
0.593 + 0.02
0.658 + 0.019
2OPT
0.631 + 0.052
X
0.679 + 0.048
0.676 + 0.056
20PT-B
0.71 + 0.022
1.0 = 0.3
0.71 + 0.022
1.0 0.3
0.71 + 0.022
1.1 + 0.3
2OPT-LS
<NA>
<NA>
0.696 = 0.013
0.045 + 0.005
0.693 = 0.013
0.047 + 0.005
Table 4: IJCNN finding a tight solution: (Eg, E = (0.020, 0.141)
0.2
8 0.6
8 1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.625 + 0.008
X
0.59 + 0.009
X
0.57 + 0.009
X
TR-B
0.625 + 0.009
0.591 0.009
0.574 + 0.009
OPT
0.643 = 0.011
0.583 0.019
0.515 + 0.039
X
OPT-B
0.667 + 0.013
1.1 + 0.3
0.667 0.013
0.9 + 0.1
0.667 + 0.013
1.0 + 0.1
OFT-LS
0.835 + 0.069
X
0.635 0.022
X
0.598 + 0.024
X
2OPT
0.537 + 0.027
X
0.522 0.074
X
0.552 + 0.091
X
20PT-B
0.666 + 0.014 1.1 0.4
0.666 0.014
1.3 0.6
0.666 + 0.014
1.1 + 0.3
20PT-LS
<NA>
<NA>
0.623 + 0.06
x
0.649 + 0.004
0.1 + 0.1
We remark that for 2OPT-LS under E = 0.2, the result is unavailable (reported as <NA>) because due to numerical issues, the package autodp cannot handle subsampling with very low privacy budget.
E.3 ADDITIONAL EXPERIMENTS
Additionally, we consider the logistic loss
1 n 12
Vi(w)
+ |w|/
+ exp (- (r,, w))
'Daa source: LIBSVM data wtw.wwwwwwwh.........ooooooooota
st status status=active
'Open source repo: httpp://gitthn http:://h..ttuboooooo///////////
20

---

and repeat our experiments on the aforementioned datasets with À = 10 We can verify that the two chosen losses have Lipschitz gradients and Hessians as long as the feature vector x; are bounded.
In this set of experiments, we find solutions (cg. (H) (0.040, 0.200) and (<g: (H) ) = (0.020, 0.141). We also show the aggregated results for the number of noisy Hessian evaluations. We note that the number of noisy Hessian evaluations required in our algorithm is very low, whereas DP-TR needs evaluate the noisy Hessian every iteration.
E.3.1 COVERTYPE EXPERIMENT USING LOGISTIC LOSS
Table 5: Covertype (logistic loss): finding a loose solution: (cg.cH) (H) = (0.040,0.200)
E = 0.2
E = 0.6
= 1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.425 + 0.009
0.388 + 0.001
X
0.381 + 0.001
X
TR-B
0.425 0.009
0.388 0.002
0.382 0.001
OPT
0.442 = 0.006
0.539 + 0.022
0.3 + 0.1
0.539 + 0.022
0.4 0.1
OPT-B
0.539 = 0.022
11.1 + 1.7
0.539 + 0.022
10.6 0.4
0.539 = 0.022
10.6
OPT-LS
0.385 = 0.002
x
0.455 + 0.014
X
0.539 = 0.022
0.4
2OPT
0.539 + 0.022
0.3 0.1
0.539 + 0.022
0.3
0.539 + 0.022
0.4
20PT-B
0.539 0.022
1.0
0.539 0.022
1.0
0.539 0.022
1.0
20PT-LS
0.539 = 0.022
0.4
0.539 + 0.022
0.3 0.1
0.539 + 0.022
0.4
Table 6: Covertype Hess evals (logistic loss): finding loose solution: (eg, EH)
(0.040, 0.200)
0.2
0.6
1.0
method
Hess evals
runtime
Hess evals
runtime
Hess evals
runtime
TR TR-B
375.0 + 0.0
375.0 + 0.0
375.0 + 0.0
X
375.0 + 0.0
X
375.0 + 0.0
X
375.0 + 0.0
X
OPT
190.6 + 32.3
X
1.0 + 0.0
0.3 + 0.1
1.0 1.0+00 0.0
0.4 + 0.1
OРT-B
1.0
11.1 1.7
0.0
10.6 + 0.4
1.0 0.0
10.6 0.4
OPT-LS
0.0 + 0.0
X
282.4 + 174.252
X
1.0
0.4
20PT
1.0 0.0
0.1
1.0
0.3 + 0.1
1.0
0.4
20PT-B
1.0 1.0=00 0.0
1.0
1.0
1.0 1.0 0.1
1.0 0.0
1.0+0.1
2OPT-LS
1.0 0.0
0.1
1.0 1.0 0.0
0.3 0.1
1.0 0.0
0.4
Table 7: Covertype (logistic loss): finding a tight solution: (Eg. (H) (0.020, 0.141)
0.2
0.6
1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.408 + 0.004
X
0.381 + 0.0
X
0.378 0.0
X
TR-B
0.408 + 0.004
X
0.381 + 0.0
X
0.378 + 0.0
x
OPT
0.379 + 0.001
0.38 + 0.001
0.39 + 0.002
OPT-B
0.454 + 0.004
1.3 + 0.2
0.454 + 0.004
1.4 + 0.4
0.454 + 0.004
1.5 0.6
OPT-LS
0.41 + 0.005
X
0.381 0.001
0.378 0.0
20PT
0.386 + 0.006
X
0.378 0.0
X
0.377
X
20PT-B
0.454 + 0.004
2.0 + 0.2
0.454 + 0.004
2.0 + 0.3
0.454 + 0.004
1.8 + 0.2
2OPT-LS
0.441 + 0.007
X
0.447 0.009
0.6 + 0.2
0.447 + 0.008
0.7 = 0.2
21

---

Table 8: Covertype Hess evals (logistic loss): finding tight solution: (Cy: (H) (0.020,
0.2
0.6
1.0
method
Hess evals
runtime
Hess evals
runtime
Hess evals
runtime
TR TR-B
1061.0 = 0.0
1061.0 = 0.0
1061.0 = 0.0
X
1061.0 = 0.0
X
1061.0 0.0
X
1061.0 0.0
X
OPT
0.0 + 0.0
X
58.6 + 24.765
X
372.6 = 141.077
X
OPT-B
1.0
1.3 + 0.2
1.0 0.0
1.4 = 0.4
1.0 0.0
1.5 0.6
OPT-LS
0.0
X
0.0 0.0
X
1.0
X
20PT
0.0
0.0
0.2 0.447
X
20PT-B
1.0
2.0 0.2
1.0
2.0 = 0.3
1.0
1.8 = 0.2
20PT-LS
33.0 = 6.745
1.0
0.6 = 0.2
1.0
0.7 0.2
E.3.2 IJCNN EXPERIMENT USING LOGISTIC LOSS
Table 9: IJCNN (logistic loss): finding loose solution: (eg, E = (0.040, 0.200)
8 = 0.2
8 0.6
1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.477 + 0.01
X
0.454 + 0.006
X
0.446 + 0.004
X
TR-B
0.477 + 0.01
0.454 + 0.006
x
0.446 + 0.004
x
OPT
0.46 + 0.01
0.439 + 0.002
X
0.463 = 0.005
X
OPT-B
0.501 + 0.008
8.6 + 0.2
0.501 = 0.008
11.0 4.9
0.501 = 0.008
9.0 = 1.0
OPT-LS
0.607 + 0.076
x
0.473 + 0.012
X
0.454 + 0.004
x
2OPT
0.493 + 0.022
0.501 + 0.008
0.0
+ 0.0
0.501 + 0.008
0.0 + 0.0
20PT-B
0.501 + 0.008
1.0 + 0.0
0.501 + 0.008
1.4 0.9
0.501 = 0.008
1.1 0.3
20PT-LS
1.002 + 0.321
0.501 + 0.008
0.0 0.0
0.501 + 0.008
0.0 0.0
Table 10: IJCNN Hess evals (logistic loss): finding loose solution: ( <H) (0.040, 0.200)
0.2
0.6
1.0
method
Hess evals
runtime
Hess evals
runtime
Hess evals
runtime
TR
375.0 0.0
375.0 + 0.0
375.0 + 0.0
TR-B
375.0 + 0.0
375.0 + 0.0
X
375.0 + 0.0
OPT
0.0
0.5 0.577
85.25 + 47.647
OPT-B
1.0
8.6 - 0.2
1.0 0.0
11.0 4.9
1.0 - 0.0
9.0 1.0
OPT-LS
0.0
0.0
0.25 + 0.5
2OPT
6.5
1.0
0.0
+.0
0.0
20PT-B
1.0
1.0 + 0.0
1.0
1.4
1.0
1.1
20PT-LS
0.25 0.5
1.0 0.0
0.0
1.0 1.0+0.00
- 0.0
22

---

Table 11: JJCN (logistic loss): finding tight solution: (fg) Em)
001020,0.141
= 0.2
0.6
1.0
method
final loss
runtime
loss
runtime
loss
runtime
TR
0.478 + 0.01
x
0.454 + 0.005
0.446 + 0.003
x
TR-B
0.479 + 0.01
X
0.454 0.005
0.446 + 0.003
x
OPT
0.484 = 0.012
X
0.447 0.007
X
0.44 =: 0.003
X
OPT-B
0.501 + 0.007
7.9 + 6.3
0.501 + 0.007
7.8 + 6.2
0.501 + 0.007
9.2 + 7.4
OPT-LS
0.761 + 0.066
X
0.553 0.037
x
0.492 + 0.016
X
2OPT
0.527 = 0.024
X
0.462 + 0.013
0.501 + 0.007
0.0 + 0.0
20PT-B
0.502 = 0.007
1.5 + 0.4
0.502 0.007
1.3 0.1
0.502 + 0.007
1.6 0.3
2OPT-LS
3.504 + 0.98
X
0.798 + 0.081
0.459 + 0.01
0.4
Table 12: JINN Hess evals (logistic loss): finding a tight solution: (Eg, E = (0.020, 0.141)
0.6
e 1.0
method
Hess evals
runtime
Hess evals
runtime
Hess evals
runtime
TR
1061.0 + 0.0
X
1061 0 + 0.0
X
1061.0 + 0.0
x
TR-B
1061.0 + 0.0
X
1061.0 + 0.0
1061.0 + 0.0
OPT
0.0 0.0
X
0.0 0.0
X
0.0 0.0
OPT-B
1.0 + 0.0
7.9 = 6.3
1.0 + 0.0
7.8 + 6.2
1.0 0.0
9.2 + 7.4
OPT-LS
0.0 + 0.0
X
0.0
X
0.0
2OPT
0.0 0.0
X
3.0 1.581
X
1.0
0.0 0.0
20PT-B
1.0 0.0
1.5 = 0.4
1.0 1.0+00 0.0
1.3 + 0.1
1.0
1.6
20PT-LS
0.0
X
0.4 + 0.548
X
4.8 + 4.97
0.4 0.4
23


Reviews:
[{"review_id": "uzcRoxpqu4W", "reviewer": "Reviewer_8RwJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "In this paper, the authors proposed differentially private optimization algorithms for empirical risk minimization. To improve the speed and practicality of the algorithm, the authors proposed to use several simple yet effective strategies such as line search and mini-batching. The effectiveness of the proposed approach is validated through numerical experiments. ", "summary_of_the_review": "see above", "strength_and_weaknesses": "Strength:\n The problem studied in the paper is important and interesting. The proposed algorithm makes sense. \n\nWeaknesses:\n\n1. The presentation of the paper could be further improved. For instance, the benefits of using nonconvex loss functions should be clarified in the introduction section. In Assumptions 1 and 2, restrictions on loss functions are imposed. Further remarks, including loss functions that satisfy the assumptions, are expected here. \n\n2. I think more details regarding the numerical experiments should be provided. For example, how the tuning parameters were selected is not clear to me. And it is also not clear why this particular loss function is chosen in numerical experiments. I expect more extensive simulation results. \n\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pNVfKmx7aLB", "reviewer": "Reviewer_LsJR", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper studies the problem of differentially private nonconvex ERM. More specifically, the authors propose a differentially private method aiming to find the approximate second-order necessary solution. The proposed method is a straightforward extension of the existing nonprivate method by injecting random Gaussian noise into the objectives, gradients, and Hessians. The authors provide the convergence guarantee of the proposed method, and an experiment validates the effectiveness of the proposed method.", "summary_of_the_review": "The problem considered in this paper is very relevant and interesting. However, the proposed method seems to be incremental. In addition, the requirement for the sample seems to be very strong, and it is unclear how to determine the privacy related parameters in practice.", "strength_and_weaknesses": "The strength of the paper:\n1. The proposed method is able to find the 2NS of the nonconvex ERM with privacy guarantees.\n2. The convergence guarantee is established.\n3. A line search-based algorithm is developed, which could be of independent interest.\n\nThe Weaknesses of the paper:\n1. The proposed method seems to be a straightforward extension of the existing nonprivate method by injecting random Gaussian noise to objectives, gradients, and Hessians. What is the key challenge when you derive the theoretical guarantees compared with the nonprivate counterpart?\n2. To control the error introduced by the random noise, the proposed method require a stringent condition on the sample complexity. This condition could be violated in practice. Therefore, a more meaningful question could be: given a fixed sample size $n$ and the privacy budget $\\rho$, what is the best $(\\epsilon_{g},\\epsilon_{H})$-2NS one can achieve using your proposed method.\n3. The proposed method needs to compute the Hessian matrix, which could be time-consuming.\n4. It seems that there is no advantage in terms of sample complexity when we use line search-based algorithm.\n5. A single experiment with a small dataset is not enough to validate the effectiveness of the proposed method. The authors should consider experiments using neural networks.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "N8G4G3PKvfQ", "reviewer": "Reviewer_2L65", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_paper": "The paper provides formal guarantees for finding second order stationary points of nonconvex loss functions under differential privacy and certain (standard) smoothness assumptions on the loss function. The paper provides a formal analysis for a noisy version of the \"gradient descent with negative curvature steps\" algorithm. Privacy is ensured via noisy versions of the gradient or Hessian at each step. The paper also analyzes a DP line search (for step sizes) variant of the algorithm which guarantees privacy via the sparse vector technique. Finally, the paper provides experiments for a nonconvex loss function to study the effectiveness of their method.", "summary_of_the_review": "The paper is well written and proposes a new algorithm/analysis for finding second order stationary points. However, the results obtained by this analysis do not improve over existing methods.", "strength_and_weaknesses": "Strengths:\n\nThe paper provides sound and precise proofs and theorem statements. The paper provides both a simple and more involved (line search) version of their algorithm, which makes the overall analysis easier to follow and provides a deeper look into their method. The authors provide experiments to support the rational for using line search, and show that this method leads to faster running time.\n\nWeaknesses: \n\nThe results of the paper may be of limited interest. The rates achieved by the algorithm for obtaining a second order stationary point do not improve upon existing rates and are in fact worse than DPTR as the authors themselves note. The authors argue that their algorithm is more practical than DPTR, because less Hessian evaluations are needed. While this is true, the algorithm seems no more practical than the the DP-GD algorithm of (Wang et al., 2019), as there too the Hessian would only need to be evaluated after first order stationarity is checked. Further, DP-GD achieves the same rate. The authors do propose a line search variant to further improve the practical running time, but the fact that any Hessian computations are still needed limits the reach of this improvement. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BYmjfBXthO", "reviewer": "Reviewer_CxW8", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper presents differentially private algorithms to find approximate solutions with second-order guarantees for nonconvex problems, i.e., solutions with small gradients and almost positive definite Hessian matrices. The paper first develops an algorithm with step size depending on some parameters of problems, and then extends it to the algorithms with line search. A minibatch variant is also discussed. Experimental results are also presented to show the effectiveness of the proposed algorithm.\n", "summary_of_the_review": "The paper considers a challenging problem of finding the second-order approximate solutions for smooth ERM problems. The analysis seems to be challenging and interesting. There is a gap between theory and experiments: the theoretical analysis requires a bounded gradient assumption, which does not hold for the problem considered in the experiments. ", "strength_and_weaknesses": "**Strength**\n\nMost of the DP algorithms focus on finding first-order approximate solutions of ERM problems. This paper aims to find second-order approximate solutions, which are much more challenging.\n\nBoth theoretical and experimental analysis are presented for the proposed algorithm with and without line search.\n\n**Weakness**\n\nThe paper only discusses results on sample complexity. There is no analysis on the computation complexity for the proposed algorithm, which is also an important issue.\n\nThe sample complexity is of the order $O(\\alpha^{-2})$, which is worse than the state of the art $O(\\alpha^{-7/4})$.\n\nThe theoretical analysis assumes a bounded gradient assumption on the loss function. In the experiments, the function involves a regularizer $\\sum_i\\lambda w_i^2/(1+w_i^2)$, whose gradients are not bounded. Therefore, the theoretical analysis and experimental analysis are not consistent.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject