Faster Differentially Private Convex Optimization via Second-Order Methods
Authors: Arun Ganesh
Mahdi Haghifam
Thomas Steinke
Abhradeep Guha Thakurta
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
logistic regression
optimization
Newton's method
second-order methods
TL;DR: In this paper, we show that the second-order information of the loss function can be used to accelerate DP convex optimization.

Abstract: Differentially private (stochastic) gradient descent is the workhorse of DP private machine learning in both the convex and non-convex settings. Without privacy constraints, second-order methods, like Newton's method, converge faster than first-order methods like gradient descent. In this work, we investigate the prospect of using the second-order information from the loss function to accelerate DP convex optimization. We first develop a private variant of the regularized cubic Newton method of Nesterov and Polyak, and show that for the class of strongly convex loss functions, our algorithm has quadratic convergence and achieves the optimal excess loss. We then design a practical second-order DP algorithm for the unconstrained logistic regression problem. We theoretically and empirically study the performance of our algorithm. Empirical results show our algorithm consistently achieves the best excess loss compared to other baselines and is 10-40x faster than DP-GD/DP-SGD for challenging datasets.

Faster Differentially Private Convex Optimization via Second-Order Methods
Arun Ganesh Google Research
Mahdi Haghifam University of Toronto, Vector Institute
Thomas Steinke Google DeepMind
Abhradeep Thakurta Google DeepMind
Abstract
Differentially private (stochastic) gradient descent the workhorse of DP private machine learning in both the convex and non-convex settings. Without privacy constraints, second-order methods, like Newton's method, converge faster than first-order methods like gradient descent. In this work, we investigate the prospect using the second-order information from the loss function to accelerate DP convex optimization. We first develop a private variant of the regularized cubic Newton method of Nesterov and Polyak [NP06]. and show that for the class of strongly convex loss functions, achieves the optimal excess loss. We then design a practical second-order DP algorithm for the unconstrained logistic regression problem. We theoretically and empirically study the performance our algorithm. Empirical results show our algorithm consistently achieves the best excess loss compared to other baselines and is 10-40x faster than DP-GD/DP-SGD for challenging datasets.
algorithm has quadratic convergence and
Introduction
Many machine learning tasks reduce convex optimization problem. More precisely, given dataset S, = (#1,..., 2n) ) E Z", closed, convex set W S IRd. and loss function f W x 2 - IR such that, for every z Z. f(w, 2) is a convex function in w, our goal is to compute an approximation arg min (e(w, Sw) & Eie(n) f(w,z)) In this paper, we are interested in the problem of designing optimization algorithms in the scenario that the dataset S,, contains private information. Differential privacy (DP) [DMNS06]
formal standard for privacy-preserving data analysis that provides framework for ensuring that the output of an analysis on the data does not leak this private information. This problem known as private convex optimization: Design an algorithm A: n W that is both DP and ensures low excess loss - ((A(S,), S.)) - min f(w, S,).
The predominant algorithm for private convex optimization is DP (stochastic) gradient descent IDP-GD/D--SGD) This is a firtt iterative method. Le.. we start with an initial value wo and iteratively update it using the gradient of the loss V Ew, S,) following the update rule Wt+1- = Wi - 77- (V.,, (,,,,,,)++)) where 1) > 0 is constant and & Gaussian noise ensure privacy. The number of iterations T also determines the amount of noise at each iteration, i.c., the scale of & is proportional to /T due to the composition of DP. Note that we assume || V E(w,, S,)ll S 1.
One of the major drawbacks of DP-(S)GD is slow convergence. The choice of (17. T) exhibits tradeoff in terms of the excess loss: if 1) T is small, the algorithm cannot reach the optimal solution; on the other hand, the magnitude of noise at each iteration VT, which cannot be too large. Therefore, to maximize 77 T and minimize 7)- vT, implementations of DP- err on the side of
This work was carried out while the author was an intern at Google Research, Brain Team. m. m.hghiifa northeasterm.dd edu (arunganesh steinke athakurta @ @google.com
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

large T and small 77, which results in long, slow path to convergence. This fact has been shown theoretically as well: for the class of 3-smooth convex functions, the optimal instantiations of DP-GD use step size of max(1/vn, v ed] [BFTG19] while in the non-private setting the stepsize for GD is set to 1/B. Smaller step size requires more steps (i.e. more iterations) to converge. This slowness is exacerbated by the facts that (1) DP-SGD requires large batch sizes for good performance [PHKX+23] and (2) the hyperparameter tuning of DP-(S)GD, and generally DP algorithms, is challenging task (PS22). Can we design a DP optimization algorithm which accelerates DP-(S)GD by choosing the step size dynamically based the local geometry of the loss function?
We draw inspiration from the non- non-private optimization literature: To address the slow convergence of GD and of first-order methods in general, class of algorithms based on preconditioning the gradient using second-order information has been developed (Nes88; NW99). This class of algorithms is based on successively minimizing a quadratic approximation of the function, i.e., W[+1 = Wt + D (H₂) Vi(we, Sx)- Here, H, is a scaling matrix which provides curvature information about the loss S.) at wt- For instance, Newton's 'ss method uses the Hessian He Vil(w, Sn). Second-order algorithms significantly improve over the convergence speed of GD, and key to their success is that at each step they automatically tune the stepsize along each dimension based on the local curvature.
where A, arg minA {f(w,, S,) + (Vé(w,, S,), + 1/2 (He A, A)}
In this paper, our goal to accelerate DP convex optimization. In particular, the current paper revolves around the following questions: Can the second-order information accelerate private convex optimization while achieving optimal excess error? What is the best way to privatize second-order information, e.g., the Hessian matrix? How does the achievable privacy-utllit- compare with first-order methods such as DP-GD? We show that second-order information can accelcrate DP optimization while achieving excess loss that matches improves on DP-GD. Our main contributions are both theoretical and empirical:
tradeoff
1.1 Provably Optimal Algorithm for Strongly Convex Functions
Newton's 's method is a second-ordes optimization technique that is well-known for its rapid con- vergence for strongly convex and smooth functions in non-private optimization. Specifically, to achieve an excess loss of the method only requires O(log log(1/a) iterations, which is provably faster than the convergence rate of any first-order method. One natural question whether it is possible to design second-order DP convex optimization algorithm that can achieve the optimal minmax excess error err in O(log log(1/ ()/eer)))))) iterations? We provide an affirmative answer to this question in Section by designing a second-order DP algorithm based on the cubic regularized Newton's 's method of Nesterov and Polyak [NP06]. At each step i, we compute a cubic upper bound f(w+A (.,+)SS,) < (w,,,,,,,, (V S,), A VV S.) A.A) ( (I) We minimize this cubic upper bound using any DP convex optimization subroutine; the minimizer becomes the next iterate W Since the cubic is universal upper bound, our algorithm converges globally
1.2 Fast Practical Algorithms for DP Logistic Regression
DP logistic regression is a popular approach for private classification, with DP-GD/DP-SGI being the predominant class of algorithms for this task. As we numerically show, DP-GD/DP-SCC exhibit slow convergence for this task (See Figure D]. In Section 5 we develop a practical algorithm that injects carefully designed noise into Newton S update rule as follows:
1++1 = Wiy - ((t (V (w.
+G,
(1)
In particular, we inject noise twice: Êt, privatizes the gradient and ε privatizes the direction. The function w modifies the Hessian to ensure that the eigenvalues are not small; this is essential for bounding the sensitivity and, hence, the scale of 2.22 We consider two types of modifica- tion based on eigenvalue clipping and eigenvalue adding. For eigenvalue clipping, ((V2 (022:((w,,, (W., replaces the eigenvalues A; of i. (S, with max Aj >o), where An > O is a carefully chosen constant. For eigenvalue adding, (VV2 w. (.)) V (W, + Ao Using we can control the sensitivity and still have fast conver- gence, since important curvature information is generally
wwotlops So S1 "JOP
llotin with Cipckng
18-1
QUI with Clicking
Excos Lon
0.5
3.2
Timm
Figure 1: Excess loss versus runtime of DP-GD & our algorithms.
2

---

contained in the larger cigenvalues/vectors of the Hessian. We prove the local convergence of the update rule (T) in Section 5.3]and and perform thorough empirical evaluation Section We demonstrate that our algorithm outperforms existing baselines on variety of benchmarks.
Ensuring Global Convergence. One limitation of the update rule in Equation [ is it does not converge globally (even without noise added for DP). That is, if the initial point wo is too far from the optimal solution, then the iterates may diverge. To address this problem, we propose variant of Newton's 's update rule where we replace the Hessian with a different form of second-order information which gives a Quadratic Upperbound (QU) on the logistic loss. This is guaranteed to converge globally, like the cubic Newton approach. And we show numerically that this algorithm converges almost as fast as the regular Newton's 's method in the private setting. Figure shows the convergence speed of our algorithms and DP-GD in terms of real wall time for the task of logistic regression on the Covertype dataset for (e, 6) (1, (num. samples) - --DP.. Despite DP-GD having lower per-iteration cost, our algorithm is 30x faster than DP-GD and achieves better excess loss.
Stochastic Minibatch Variant. We also show that our algorithms naturally extend to the minibatch setting where gradient and second-order information are computed on a subset of samples. We numerically compare with DP-SGD and show that has faster convergence.
2
Related Work
DP optimization is a well-studied topic [e.g.. SCS13; MRTZ17 ACGM+16 STU17 WLKC+17
Most similar to work, Avella- Medina, Bradshaw, and Loh [ABL2I] consider second-ore order methods for DP convex optimization. We provide a detailed comparison between our results and theirs in Remark and Section showing that our algorithms relax restrictive assumptions and provide better excess error for logistic regression.
(19++19,/STT00 [STTT2| GTU22 GLL22 BFTG19| BST14..
There are numerous non-private second-order optimization methods in the literature. The choice of method depends primarily on the values of n and d. When n is large, several works consider various sampling techniques for constructing second-order information, see [RM19] XYRRM16 Erd15 EMI5). When is large, various methods are proposed in the literature for efficient approximation of the Hessian matrix, see [ABH17 Erd13] EM15 XYRRMI6 GKLR19]. There is also family of algorithms based on the estimation of the curvature from the change in gradients. These algorithms generally known quasi-Newter methods stemming from the seminal BFGS algorithm (M233)
3 Preliminaries
Let d E N. For a vector x E Rd, ||>||| denotes the & norm of x. Let n, m E N. For a matrix A E _= ||A||| = supzeR==||e]|S1 Ax denotes the operator norm, and ||Al] r & / traceeA"" AA) denotes the Frobenius norm of A where trace denotes the trace operator. Ia E Rdxd denotes the identity matrix. ( denotes the standard inner product in Rd. For convex and closed subset W C Rd let Tw Rdd -> W be the Euclidean projection operator, given by Iw = arg yew |y x||2- For a (measurable) space R, MM (R) denotes the set of all probability measures on R. Note that the statements in the paper about random variables hold almost surely. We will skip such declarations to aid readability. Let Z be the data and let W C Rd be the parameter space. Let ʃ : W x Z + be a loss function. Throughout the paper, we assume f is doubly continuous, a convex function in w, and W is closed and convex set. We say (1) ʃ is Ly-Lipschiz
iff there exists Lo E R such that Vz2 E Z, Vu, e E W: If(w, 2) - f(e, < La ||w l|w--ll (2) is L1 -mooohh iff there exists
E such that V2 E Z, Vw, v E W : fV,,w2))
-V(u,2)] S
L1 [|w - v|I. (3) f has a L2- Lipisschttzz Hessian iff there exists L2 E R such that Vz E Z, Y.w u W ||V2 f(w, 2) V2 fu, z)|l L2 ||w ell. (4) f is p-strongly convex iff for all w, v E W and 2 E Z we have f(v, 2 f(w,2) 2) + (VS 2), v - w) + ||0 w
3.1 Zero-Concentrated DP
For our privacy analysis, we use concentrated differential privacy [DR16 BS16), as it provides a simpler composition theorem the privacy parameter p adds up when we compose.
3

---

Definition 3.1 (BS16, Def. 1.1D. A randomized mechanism A 2 + (M(R) is p-zCDP, iff, for every neighbouring dataset (i.e., addition or removal) S, 2" and S E 2", and for every E (1)),,, it holds D, (A.S,))IA((S)))))) S por, where (A (S (Am))lAA(S)) is the a-Renyi divergence between An (Sa) and An (S,))
We should think of E:: to attain (E, 6D-P, it suffices set p (
e²
BS16 Lem. 3.5].
Lemma 3.2 [BS16 Prop. 1.3)). Assume we have randomized mechanism A: Z M1(R) that satisfies p-2CDP, then for every 8 > 0, i (p + p
4 Optimal Algorithm for the Class of Strongly Convex Functions
In this section, we present a DP variant of the cubic-regularized Newton's 's method of Nesterov and Polyak [NP06]. To motivate the idea behind our algorithm, we revisit DP gradient descent (DP-GD) for the class of Lo-Lipschitz and L -moooh convex loss functions.
Let {w [TE(T) be the iterates of DP-GD. The smoothness of & lets us construct global quadratic upper bound on the function [Nes98] Thm. 2.1.5] as follows Vw E W and S, E g":
L1 A(w, Sn) S (w) & fm S.) + (Vi(w,)) Sn), w w (D) +
||
w
(2)
2
Then, DP-GD can be seen as a two-step process:
(Step I) U141 = arg min ge (v) - un -L -L- Vi Sw), (Step II)
GD wi11
Iw(444 + &t),
where & = NV with o² =
La so that w satisfies p-ZCDP BS16 Lem. 2.5]. That is, in
2pm
each iteration of DP-GD, we find minimum of the quadratic upper bound qi (w) and then project back to W. (In the unconstrained setting where W = IRd we do not need the second projection step.)
Consider the class of Læ-Lipschitz Hessian convex loss functions. Nesterov and Polyak [NP06] Lem. 1J show that we can construct a global cubic upper bound exploiting the second-order informa- tion (i.e., Hessian) as follows: for all w and Wx, {(W, 5,)5sc di (ww) where
L2 w.)
(w) 2 (w,, ( S,), w.) + ( (.
W well
(3)
6
Their non-private algorithm is based on the exact minimization of de (w), i.e., the next iterate is W1+1 = arg min (tr). Note that arg min (w)) does not admit a closed form solution, as opposed to the quadratic upper bound (2). Similar to the intuition for DP-GD smooth loss functions (2). our algorithms in this section are based on privately minimizing de (w) at each iteration. Our algorithm is shown in Algorithm I In each iteration the algorithm makes an oracle call to obtain (f(w,, S,,,, Vi S,), V'E(w, 5,)). Then, the algorithm calls an efficient DPSolver for privately optimizing the cubic upper bound (3) The privacy analysis of Algorithm is direct application of the composition property of zCDP [BS16 Lemma 2.3]; the output of DPSolver at each iteration satisfies p/ DCDDP where p is the total privacy budget and T is the total number of iterations.
Remark 4.1. DPSolver in Algorithm]] does not affect the oracle complexity of Algorithm as is applied to the proxy loss (w),, rather than the underlying loss l(w. S,).
Algorithm 2 DPSolver
Algorithm I Meta Algorithm
1: Input: function @ W + R x(0) = e+ (g. 0 Oo) + ( 6o), (0 0o)) + 12 110 lull" privacy bud-
I: Input: training set Sn E z", privacy budget p-zCDP, initialization wo E W. number of iter- ations T.
get PCZCPP initialization A..
2: N = 28 D',,
NL
2: for t 0, 0,...,, -o....,T-11.. - do
D
2p
3: for = 0, O.....N
do
3: Query k(w,, S.., VE(W,, S.), ( S.)
4:
4: Construct Φi (w) from Equation 3
5: We+1 = DPSoolver()((w)) p/T, we)
5: grad, = g + (0. 0o) + 1/2 110 Boll (0. Bu).
6: Output wr.
6:
0.+1 = Ilw (gradd + ~N -V(00021.)))
7: Return >N11 2 0
N(N+1)

---

Theorem 4.2. Let f be Lo- Lo-Lipschita. L1 L1-smooth Ly-Lipschitz Hessian, and y-strongly convex function. Also, assume that W C E. has finite diameter D. Let w* arg min (w,, S.). Then, for every > 0, 3 E 1), and Sn E 2 for sufficiently large n, by setting the number of iterations in Algorithm 10
vL2 1
nVP
T O (e(wa, S.) (--"-("",, (S)) + log log
/log(1/3)d
and using Algorithm 2 as DPSolver, we have the following: The output of Algorithm i.e., WT, satisfies p-zCDP and with probability at least 1 - 3
E(wr, S,) - E(w", S,) - 0 d(Lo + L,
(BLLOD) )a
ppp?
Remark 4.3. The lower bound on the excess error of any DP algorithm for the class of strongly convex functions [BST14, Thm. 5.5] implies that the achievable excess error in Theorem 4.2 is optimal in terms of the dependence on d, p. and n. Also, the oracle complexity of our algorithm an exponential improvement over the oracle complexity
first-order methods [STU17].
Remark 4.4. The proof of Theorem 4.2 suggests that Algorithm Thas two phases. First, while wy is far from w*, the convergence rate is 1774. Second, when w, is close to w", the algorithm exhibits the convergence rate of exp(exp(-TT). Notice that Algorithm [ is agmostic to this transition in the sense that we do not have an explicit switching step in Algorithm to note that the transition happens when ||w, - =I'1 S 3p/ 4L2.
Jand and Algorithm 2
It is also interesting
Remark 4.5 (Comparison with [ABL2T].) .). [ABL2T] $4), the authors propose a DP variant of Newton's 's method. Their main idea is to add independent noise directly to the Hessian matrix and the gradient vector using the Gaussian mechanism. They also require that the Hessian be a rank- I matrix. The issue with adding noise directly to a full-rank Hessian matrix is that the noise scales with the dimension d, which can lead to a suboptimal excess loss. In contrast, our algorithm has a global convergence without placing restrictions on the rank of the Hessian matrix the initialization.
Remark 4.6. We showed in Theorem 4.2 that our algorithm has an exponentially smaller oracle complexity than the first-order methods in terms of the dependence to n. For the class of convex, smooth, Lipschitz, and strongly convex, [ZZMW17] proposes first-order algorithm with oracle complexity of Ti = @ (vL1/ + log differs from result, making direct comparison challenging. It is an interesting question to develop a second-order DP algorithm with a smaller oracle complexity than both the algorithms proposed in (ZZMW17) and ours in Algorithm
+lgllog(m)))) (n)). It is important to note that the constant term in Ti
Remark 4.7. The cubic Newton method has non-private convergence rate of T for the class of convex (but not strongly convex) functions (NP06) Thm. 4]. We leave it as an open question whether there exists a DPSolver such that Algorithm achieves optimal excess error and oracle complexity for convex functions. However, this can be achieved by a DP variant of the first-order accelerated Nesterov's method Nes98 NJLS09 GL122 ; see Appendix A.2
5 DP Logistic Regression using Second-Order Information
The main limitation of our cubic Newton's method (Algorithm [ is that each iteration requires solving nontrivial subproblem. So, despite low oracle complexity, it is computationally expensive. Moreover, many loss functions, such as logistic loss, are not strongly convex in the unconstrained setting. In this section, we aim to develop fast second-order algorithm for unconstrained logistic regression avoiding this issue. many real-world classification tasks, the logistic loss is the loss of choice. The logistic loss is convex surrogate of the 0-1 loss, and satisfies many regularity conditions that give rise to various practical optimization algorithms [Bac 10; Erd15] KSJ18). Also, note that our results in this section can readily be extended to the class of smooth and convex GLMs.
First, we recall the logistic loss function. Let d N and Z (1) {-1, 1, 1] be the dimension and data space, where (1) = (x TR || S 1) is the unit ball in Rd. Let fLL. : Rdd 2 IR. denote the logistic loss function defined as [w,(W, (x, v)) log(1 exp(-y xw))))).
(4)
The gradient and Hessian of ft. are given by
V fLL,WW (I, v)) 1+exply (w)
-ry
V (Lw
r.
(5)
(exp(-
(ur,z)
+exp
(1.2z)
))²
2
2
5

---

Newton's 's method [V044 $9.5] is based on successively minimizing a local second-order Taylor approximation on the function. Newton's method does not guarantee global convergence [TT16]; the reason is that the second-orde! Taylor approximation of the logistic loss can greatly underestimate the function. Next we show that is possible to obtain a quadratic global upper bound on the logistic loss function. We will use this to develop an algorithm that converges globally.
Lemma 5.1. For every U E R4, E IRd, E RR, and y E {[1, we have
1 (w, (z, v)) - fuL(U, v)) + (V (z. w w- u) + (Haw (x,
(x, - f))lww--,,eee w u)
tanh (2.u1/2) xx E Rddd
where Hqu(v, (I. y))
2 (x
Remark 5.2. Since fLL is --smooth, we can construct a simpler global quadratic upper-bound
as follows Nes98 Thm. 2.1.5]: fi. (x, S fLL(U, (x.y)) + (V fLL(V, (I. y) v).. w v)
|| - ul Lemma is tighter than this, since Hqu (v, (x. < I2; see Appendix B.2
Remark 5.3. The second-order Taylor approximation and our upper bound in Lemma 5.1 both provide
a quadratic approximation of the logistic loss. the remainder of the paper, we write H(, (x)
to refer to both V (LL(",, (z, v)) and (v, (x. v)). We refer to H(u, (zz, y)) as the second-order information (SOI) and to Hqu as quadratic upperbound SOI. Finally, notice both V fLL(C, (e, (z, v))
and Hqu (z, v)) are PSD rank-l matrices, with maximum eigenvalue S |||=||| < 4.
5.1 Algorithm Description
We are given a dataset Sn = ((21, B1)....... (I,) (en.:y) yn)) E (L) x (-1,+13) and we aim to minimize (w, S.) & 1 Eiejnn fLL(W, v.). Our algorithm iteratively minimizes a quadratic approximation of (w,, S.). Consider
1 (HW,,, Sw) - -we, (w wx)) (e(w) A fuI,(Wr, Sn) + (Vln, Sa), w- we) + -2
(6)
where H Hw,,, S.) A + [ (wi, (Ii, 9:)). In the non-private setting the next iterate is set to W arg min... ge (((w) w,- H(w,, -V)LL S,)). To develop a private variant of Newton's 's method, we need to characterize the sensitivity of this update rule. Our key observation that the directions corresponding to small eigenvalues of HI (w,, Sn) are more sensitive than the directions corresponding to large eigenvalues. To overcome this issue, we modify the eigenvalues of H (ww, Sn) to ensure minimum eigenvalue 2 Ag. where À > 0 a carefully chosen constant. We show how to adaptively tune Åo in Section 5.2 This procedure yields the desired stability with respect neighbouring datasets. Formally, the modification operator is defined as follows:
Definition 5.4. Let A E Iddxd be a positive semi-definite (PSD) matrix and λo 2 Define
d
d
maxt Ao Ar Ju.uT (A, = Σ (A: + Aouuuay A + dola- V (A, clip) = Σ
i=1
where A = Ed i=1 nunny is the eigendecompositiion of A - i.e., 0 < \1 S ... S ds are the eigenvalues and U1 ..,..., Ud E Rd are the eigenvectors, which satisfy vi # j ||u,]| = 1A (u,, u,> 0.
Algorithm describes our algorithm. First, we state the privacy guarnatee of Algorithm 3 whose proof can be found in Appendices B.3
and B.4
Theorem 5.5. Assume in Algorithu
3 we choose add for the SOI modification. Then, for every
training set Sn E (IRd x f-11, +1))" wo E W. No > 0, T = N. p E R4, and 0 E (0, 1), by setting
/T VT and 02 [4nA] + 2pp) Wr satisfies p-zCDP. 01 202
Theorem 5.6. Assume in Algorithm 3 we choose clip for the SOI modification. Then, for every training set Sn E (Rd -1+))) Wo W. No > T E N. p E Rt, and (0, 1) such that
4hg by setting 01 = " -V2p(1-9)
/T and 02 (Am Ao)
/T
WT satisfies p-PCDP.

---

Algorithm 3 Newton Method with Double noise
Our DP algorithm differs from the non- non-private Newton's method in three ways: (1) We first privatize the gradient by adding noise. (2) We modify H (w,, Sn) to ensure its eigenvalues are not too small. And (3) we add a second noise to the update computed using the noised gradient and modified second-order information (SOI).
I: Imputs:
training S, 2", A 0, 0 (0, 1), privacy budget p-zCDP, initialization wo, number iterations T, SOI modification E {clip, add}.
2: Set 01 =1/2(110)
VT
3: if SOI modification Add then
vT 4: 02 (AmA) Ae)
5: else if SOl modification Clip then vT 22p
Notice that Algorithm 3 has four variations based on the SOI and the modification of SOI, namely, Hess-clip. Hess-add, QU-clip. and QU-add which refer to using Hessian and clip, Hessian and add, quadratic upper bound (See Lemma (511) and clip, and quadratic upper bound and add, respectively.
6:
7:
for t 0, O...., T do
8:
Query ff(u,, S..) and (w,, S.)
9:
H,, >x (W,,, S, SOI modification)
10:
Gr fir. S.) (00 la)
11:
W1+1
H d: + (00 llx TaTa)
Remark 5.7 (Generalization of Algorithm B} In this section our main focus is on DP logistic regression, and the privacy guarantees hold for the logistic loss. Nevertheless, in Appendix B.6, we present a generalization of Algorithm 3 whose privacy guarantee holds for every convex, doubly differentiable, Lipschitz, and smooth loss function without any constraints on the rank of Hessian. The main technical challenge for sensitivity analysis is proving the approximate Lipschitzness of V in the operator norm (See Lemma B.7). This demonstrates that our algorithm is more general than objective perturbation [CMSTT] KST12 INST+19] and the private damped Newton's method ABL21
12:
Output
CMSST;KKT12,
which both require a low-rank Hessian.
5.2 Private and Adaptive Selection of Minimum Eigenvalue
One of the hyperparameters of Algorithm 3 is the minimum eigenvalue Ag There exists tradeoff for choosing Ag- We ideally want the modification be as small as possible, so that the SOI is preserved. However, decreasing An increases 02 and we add more noise. To deal with this problem, we propose a heuristic rule for an adaptive, private, and time-varying se- lection of the minimum eigenvalue. We wish to find Ap.e that minimizes expected loss at the next iteration, for which we have the quadratic approximation (6). More formally, we com- pute Ao as arg min, E lq: (w, (W, S,),, SOI modification g. + 1g (2( E)] where ge given in (6) and E NO, Ta). We show in Appendix B.5 that an approximate minimizer Ap,t O (, tracef HH, (w..
xprvaay budget for the direction Note that Ao, depends on the data through (race(H((u)) S,))). which has sensitivity 1/4n, so it can be estimated privately. In Appendix B.5 we provide the algo- rithmic description of variant of Algorithm 3 with adaptive and private minimum eigenvalue. In particular, we divide the privacy budget at each iteration into three parts: (1) privatizing the gradient; (2) estimating the trace of SOI; and (3) privatizing the direction. We use this variant for our numerical experiments in Section 6
5.3 Convergence Results for Algorithm
In this section, we provide data-dependent convergence guarantees for Algorithm 3 We express these guarantees in terms of the conditional expectation E. [-] E [w: and they can be easily extended to obtain high probability bounds. Before presenting the results, we introduce )v)) E (IR x {-1,-++ +11"" let V E Rdxd denote the orthogonal projection matrix on the linear subspace spanned by { ).
notation. For a dataset S, = ((z1, V1),... ..., (In,
For every vector u E gd, define |!ully 2 Vu Vu. This norm naturally arises since for every w E IRd we have fL.1 (w, S..) frI(w", S..) ||l wt where w² arg min (w,, Sn.) (See Appendix B.7
5.3.1 Local Convergence Guarantee of Hess-clip and Hess-add
Theorem 5.8. Let Sn denote the dataset and rank denote the dimension of the linar subspace spanned by {T1.... Ln.) }. Let Amin, be the smallest non-zero eigenvalue of (l Sn) and p be
7

---

3P-G3
AD? RSSTWII
Kowin (50
Out
Figure 2: Privacy-Utility tradeoff on different datasets.
the privacy budget (in zCDP) per iteration. Then,
Eg [1ue411 w² w'|l2] 1 vÝ, 1uwe w w01l + 2,1, I|l - w"
w0 11 + v2,, w1we w w² +
where the coefficients are given by
Aminae Ao
(1n
Vrank Ao)
2p0
1/.
0.05 Amin,
A A=
rank
0)n² ()min.))
(7)
min Amin, do} for Hess-clip. depends on the modification procedure. Amin, + Ao for add,
Here, Amn,t
This type of convergence known as composite convergence, as is a combination of linear and quadratic rates, and has been observed in the convergence analysis of several quasi-Newton's methods (EM15] Erd15) [RM16; XYRRM16).
Remark 5.9. A is the smallest non-zero eigenvalue of EL (w,, S.). Therefore, for sufficiently large we have 0 < V1,t < shows Algorithm 3 with Hessian SOI is, in in-execctation, descent algorithm locally given |w,, w*| is sufficiently larger than A. Roughly speaking, Theorem 5.8 guarantees a linear convergence to ball around the optimum whose radius is given by A. We also observe the linear rate in Figure Moreover, the error due to the privacy, i.e., A in Equation proportional to the rank of the feature vectors which is always smaller than These interesting properties is due to the convergence analysis with respect to I1-Ily.
Remark 5.10. The coefficients of the convergence in Equation (7) depend the iteration step which is an undesirable aspect of the results. In Lemma B.11 we prove that Amii,t - A < 0.1 ||w, w" lly where A is the smallest non-zero eigenvalue of (' S.). Therefore, the coefficients can be well-approximated by their analogous values evaluated at the optimum.
5.3.2 Global Convergence Guarantee of QU-clip and QU-add
We also establish a global convergence guarantee for QU-clip and QU-add. Due to the space the formal statement and proof are deferred Appendix B.9 Roughly speaking, under the assumption of local strong convexity at the optimum [4). QU-clip and QU-add converge globally: this is intuitive since QU-clip and QU-add are based minimizing global upper bound the function.
6 Numerical Results
In this section, we evaluate the performance of our algorithm (Algorithm 3 with the adaptive minimum eigenvalue selection from Section 5.2p for the problem binary clussification using logistic regression. For brevity, many of the details behind our implementation and more experimental results are deferred to Appendix
6.1 Setup
The setup of the experiments is as follows: Baselinel- DP-(S)GD: The update rule is Wr+1 wt - // 7/ S,.) where ş is Gaussian noise (SCS13 BST14 ACGM+16). Since the logistic loss is 1-Lipschitz, we do not need gradient clipping. The Lipschitzness parameter controls the variance of the Gaussian random vector. To draw fair comparison and show the advantage of using second-order information, chose the stepsize be equal to the inverse smoothness. Baseline2.

---

gytieto 1-11.00
yyfieto DP
cwntyge c-
EP-G3
HESS-AED
QUADO
HEES-CLIP
Tantor
Iansion
fardonn
Figure 3: Comparison with DP-GD Oracle where at each iteration the stepsize tuned non-privately.
- Tours
Town (sec)
E = 0.01
6 = 0.1
==1
6 = 10
min (sec.)
max max(Tous) (sec.)
ala
4.87
2.95
5.09x
30.59x
2.45
synthetic
2.90
2.90
5.19x
11.61 x
0.18
0.21
adult
12.08x
11.84x
22.17x
38.16x
6.81
8.07
covertype
24.19x
19.85x
35.70x
36.20x
2.93
3.58
Table 1: Comparison between the run time of our algorithm and DP-GD in terms of the ratio
DP.GD/ /T..D//T.rr. our The last two columns show the minimum and maximum run time of our algorithm.
Approximate Objective Perturbation (AOP): AOP built on objective perturbation (CMSTT KST12). Objective perturbation consists of two-stage process: (1) perturbing the objective function by adding random linear term and (2) outputting the minimum of the perturbed objective. Releasing such minimum is sufficient for achieving DP guarantees [CMSII KST12), but only if we can find the exact minimum of the perturbed objective. AOP extends objective perturbation to permit using an approximate minimum of the perturbed objective 199T+19:INSTT Notice AOP is not an iterative optimization algorithm. Baseline Damped Newton Method [ABL2I]: The algorithm in [ABL21] is variant of damped Newton's method with the assumption that the Hessian of loss function is rank-1, I, which holds for the logistic loss. Their algorithm is based on adding two i..dd noises the Hessian and the gradient: W1+1 Wt T) Hnoisy, (we, Sa)) - Mr. where 7) the stepsize, e S.)) = PELLLWW,. S,) + E, and ÿt = VlL (w,, Sn) + &.. Here 3, and & are carefully chosen Gaussian noise. With 7/p = 1, our experiments show that their algorithm is not converging. We the strategy suggested in [ABL21, Page 22] and set :/ log(1 B1)/3t where B, 1I - VeL. (w,, S.) This stepsize selection makes the algorithm non- private, however, serves as a good baseline. Datasets: We conducted experiments on six publicly available datasets: ala, Adult, covertype, synthetic, fashion-MNIST and protein (Appendix [ includes fashion-MNIST and protein results). The synthetic dataset is generated as follows: Fix d N and w' d Then, (I) the feature vectors {I, E Rd E [n]} are independent and sampled uniformly at random from the unit sphere in R. (2) for the i-th datapoint the label is +1 with probability (1 + exp( - (I, w m=)))= and 1 otherwise. Privacy Notion: The privacy notion for our experiments is (e, 0 (num. of samples)-2)-D Next, we present the results.
6.2 Privacy-Utility-Rne Time Tradeoff
We study the tradeoff for our algorithm and compare with other baselines for a broad range of e E {0.01..... 10]. We non-privately tune the total number of iterations of the iterative algorithms and report the best achievable excess eгтor in Figure 2 As can be seen our algorithm almost always achieves the best excess loss for a broad range of Also, 2howss that damped private Newton method of (ABL2T) achieves a low excess loss only for large c. Figure Lindicates that DP-GD and our algorithm are the best in terms of excess loss. In Table we compare the run time of DP-GD and our algorithm, i.e., the computational time in seconds for achieving the excess loss in Figure 2 As can be seen, for many challenging datasets, our algorithm 10-40x faster than DP-GD. Our experiments are run on CPU. We also remark that each step of Algorithm 3 i.e., computing gradient and SOI, is heavily parallelizable implying that the run time of Algorithm can be made much smaller by an efficient implementation. Also, the reported numbers in Figure 2 and Table correspond to Hess-clip.

---

oytta 3GP
els, en
CONEUAL CCP
Toue
Time [rc
Figure 4: Minibatch Variant of Our Algorithm and Comparison with DP-SGD
6.3 Second Order Information vs Optimal Stepsize
In non-private convex optimization, the key to the success of second-order optimization algorithms is that the second-order information acts as a preconditioner, and the same performance cannot be attained by optimally tuning the stepsize for GD algorithm. To investigate whether the same holds for our algorithms, we consider the following variant of DP-GD. Let ÿt denote the perturbed gradient obtained by adding a Gaussian random vector V. (Wi, S.). Instead of constant stepsize, the stepsize at iteration / is chosen based on 7)- = arg min 220 (LL T)):). Notice this variant is obviously not DP. We refer to this variant as JP-GD-Oracle The comparison with DP-GD-Oracla lets us answer the following question: Could we have just computed a single number. i.e., stepsize, to achieve the same performance as our second-order optimization algorithms which require computing a d x d matrix? In Figure 3 we compare the convergence speed of our algorithms with DP-GD-Oraa -racle in low- and high-privacy regimes. Figure shows our algorithms converge faster than DP-GD-Orach which is not even a DP algorithm. Figure 3 confirms the expectation that as the privacy budget increases the difference between our algorithms and DP-GD-Oracle increases since we can use more curvature information.
6.4 Minibatch Variant of Our Algorithm and Comparison with DP-SGD
So far we have considered full-batch algorithms that compute first- and second-order information on the entire dataset. We extend Algorithm 3 to the minibatch setting, where, at each iteration, the gradient and SOI matrix are computed using a subsample of the data points. In Appendix [ we provide a formal algorithmic description of the minibatch version of Algorithm 3 along with its privacy proof. Then, we compare the convergence speed and excess loss with DP-SGD.
DP-SGD is faster than DP-GD, but to achieve good privacy and utility, we need large batches [PHKX+23] Fig. 2]. This is in stark contrast with non-private SGD, where larger batch sizes yield diminishing returns [ZLNM+19] In particular, to achieve the best excess loss we need to select the batch size as large as possible. We select the batch size of DP-SGD so that the achievable excess loss will be close to the full batch versions, Specifically, we select batch size DP-SGD R 0.02 and number samples
tune the number of iterations of DP-SGD to obtain the best result. Figure Ishows the progress of different algorithm versus run time. Obviously, for fixed run time DP-SGD performs more iterations compared to our algorithms. Nevertheless, our algorithms achieve the same excess error as DP-GI with 8- 10x faster run time over all the datasets while the batch sizes of our algorithms are larger than that of DP-SGD. We observe that the variations of our algorithms based on the adding operator performs better in the minibatch setting. This can be attributed to the smaller 02 for the adding operator in Algorithm 3 In summary, the comparison between privacy-utility- wall time tradeoff of the subsampled variant of our algorithm and DP-SGD is similar to their full-batch counterparts.
Conclusion and Limitations
We showed that second-order methods can be used in the DP setting both for improving worst-case convergence guarantees and designing faster practical algorithms. We believe our results open up many directions: A limitation of our algorithms is that the cost of forming and inverting the Hessian can be prohibitive when d is large. In the non non-private setting, a line of research tries to address this limitation by constructing an approximation
SOI such that the update efficient, yet still provides sufficient SOI (EM15) Erd15) X XYRRM16; ABH17]. It would be interesting to investigate how the ideas developed in our paper could be incorporated into these methods.
10

---

Acknowledgments
The authors would like thank Murat Erdogdu, Jalaj Upadhyay, and Mohammad Yaghini for helpful discussions. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute
www. www.vectorinstitute..lt aitttee.ii/rrteeeeee tners
References
[ABHI7]
N. Agarwal, B. Bullins, and E. Hazan. "Second-order stochastic optimization for machine learning linear time". The Journal of Machine Learning Research 18.1 (2017), pp. 4148 4488-
[ABL21]
M. -vella-Medina, C. Bradshaw, and P.-L. Loh. "Differentially private inference via (2021).
noisy optimization" arXiv preprint
[ACGM+16]
M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, et al. "Deep learning with differential privacy". In: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security. 2016, pp. 308-318.
[AMN20]
J. Arbel, O. Marchal, and H. D. Nguyen. "On strict sub- Seob-Guussiattty optimal proxy variance and symmetry for bounded random variables". ESAIM: Probability and Statistics 24 (2020), pp. 39-55.
[Bac10]
F. Bach. "Self-concordant analysis for logistic regression". Electronic Journal of Statistics 4 (2010), pp. 384-414.
[Bac14]
F. Bach. "Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression". The Journal of Machine Learning Research 15.1 (2014), pp. 595-627.
[BD99]
J. A. Blackard and D. J. Dean. "Comparative accuracies of artificial neural networks and discriminant analysis predicting forest cover types from cartographic variables". Computers and electronics in agriculture 24.3 (1999), pp. 131-151.
[BFTG19]
R. Bassily, V. Feldman, K. Talwar, and A. Guha Thakurta. "Private stochastic convex optimization with optimal rates". Advances in neural information processing systems 32 (2019).
[BS16]
M. Bun and T. Steinke. "Concentrated differential privacy: Simplifications, extensions, and lower bounds". In: Theoor of Cryptography Conference. Springer. 2016, pp. 635- 658.
[BST14]
R. Bassily, Smith, and A. Thakurta. "Private empirical risk minimization: Effi cient algorithms and tight error bounds". In: 2014 IEEE 55th annual symposium foundations of computer science. IEEE. 2014, pp. 464-473.
[BV04]
S. P. Boyd and L. Vandenberghe. Convex optimization. Cambridge university press. 2004.
[CJB04]
R. Caruana, T. Joachims, and L.. Backstrom. "KDD-Cup 2004: results and analysis". ACM SIGKDD Explorations Newsletter 6.2 (2004), pp. 95-108.
[CMS11]
K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. "Differentially Private Empirical Risk Minimization". Journal of Machine Learning Research 12.29 (2011), pp. 1069- 1109.
[DG17]
D. Dua and C. Graff. UCI Machine Learning Repository. 2017.
[DMNS06]
C. Dwork, McSherry, K. Nissim, and A. Smith. "Calibrating noise to sensitivity in private data analysis". In: Theory of cryptography conference. Springer. 2006, pp. 265-284.
[DR16]
C. Dwork and G. N. Rothblum. "Concentrated diffcrential privacy". arXiv preprint 1603.066003188 (2016).
[EM15]
M. A. Erdogdu and A. Montanari. "Convergence rates of sub-sampled Newton methods". Advances in Neural Information Processing Systems 28 (2015).

---

[Erd15]
M. A. Erdogdu. "Newton-Stein method: A second order method for GLMs via Stein's
lemma". Advances in Neural Information Processing Systems 28 (2015).
[GKLR19]
R. Gower, D. Kovalev, F. Lieder, and P. Richtárik. "RSN: randomized subspace Newton".Adannee Advances in Neural Information Processing Systems 32 (2019).
[GL12]
S. Ghadimi and G. Lan. "Optimal Stochastic Approximation Algorithms for Strongly
Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework" SIAM Journal on Optimizution 22.4 (2012), pp. 1499. eprint: https://doi org/16 1137/11084888
[GLL22]
S. Gopi, Y. T. Lee, and D. Liu. "Private Convex Optimization via Exponential Mechanism". In: Proceedings of Thirty Fifth Conference on Learning Theory. Ed. by P.-.. Loh and M. Raginsky. Vol. 178. Proceedings of Machine Learning Research. PMLR, Feb. 2022. pp. 1948-1989.
[GTU22]
A. Ganesh, A. Thakurta, and J. Upadhyay. "Langevin diffusion: An almost uni- versal algorithm for private Fuclidean (convex) optimization". arXiv preprint
arXiv:2204.01585 (2022).
[GV13]
G. H. Golub and C. F. Van Loan. Matrix computations. JHU press, 2013.
[HLR19]
Harvey, C. Liaw, and S. Randhawa. "Simple and optimal high- probability bounds for strongly-convex stochastic gradient descent". arXiv preprint arXiv:1909.000 00044300433000 (2019).
[INST+]
R. Iyengar, J. P. Near, D. Song, O. Thakkar, et al. Differentially Private Convex Optimization Benchmark. URL: https: / /t////tthbbbbb com / sunblaze ucb/ dpml benchmark
[INST+19]
R. Iyengar, J. P. Near, D. Song, O. Thakkar, et al. "Towards practical differentially private convex optimization". In: 2019 IEEE Symposium on Security and Privacy 2019.
[JM23]
Q. Jin and A. Mokhtari. "Nomttsy superlinear convergence of standard quasi- Newton methods". Mathematical PecteaaatcaaaaPPPPPreee Programming 200.1 (2023), pp. 425-473.
[JNGJ]19]
C. Jin, P. Netrapalli, R. Ge. S. M. Kakade, and M. I. Jordan. "A short note on concentration incqualities for random vectors with subgaussian norm". arXiv preprins arXiv:1902.03733. (2019).
[JT66]
F. Jarre and P. L. Toint. "Simple examples for the failure of Newton's method with line search for strictly convex minimization". Mathematical Programming 158.1 (2016), pp. 23-34.
[Kat73]
T. Kato. "Continuity of the map S + [S]] for linear operators". Proceedings of the Japan Academy 49.3 (1973). pp. 157-160.
[KSJ18]
S. P. Karimireddy, S. U. Stich, and M. Jaggi. "Global linear convergence of New- ton's method without strong-convexity Lipschitz gradients". arXiv preprint arXiv: XXi6.00000004/3 (2018).
[KST12)
D. Kifer, A. Smith, and A. Thakurta. "Private Convex Empirical Risk Minimization and High-dimensional Regression". In: Proceedings of the 25th Annual Conference on Learning Theory. Ed. by S. Mannor, N. Srebro, and R. C. Williamson. Vol. 23. Proceedings of Machine Learning Research. Edinburgh, Scotland: PMLR, 25-27 Jun 2012, pp. 25.1-25.40
[Lyu22]
X. Lyu. "Composition Theorems for Interactive Differential Privacy". arXiv preprint arXi::2207.09397 (2022).
[Mir75]
L. Mirsky. "A trace inequality of John von Neumann". "eumann".Monntsheeee für mathematik
79.4 4 (1975), pp. 303-306.
[MRTZ17]
H. B. McMahan, D. Ramage, K. Talwar, and L. Zhang. "Learning differentially private recurrent language models". arXiv preprint arXiv:1710.0660 (2017).
[MTZ19]
I. Mironov, K. Talwar, and I.. Zhang. "Renyi differential privacy of the sampled Gaussian mechanism" arXiv preprint arXiv:1908. 10530 (2019).
[Nes98]
Y. Nesterov. "Introductory lectures on convex programming volume i: Basic course".
Lecture notes 3.4 (1998), p. 5.
12

---

[NJLS09]
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. "Robust Stochastic Approxi- mation Approach Stochastic Programming" SIAM Journal on Optimization 19.4 (2009), pp. 1574-1609, eprint: https: //dpii org/10..///.. 1137/078774477
[NP06]
Y. Nesterov and B. T. Polyak. "Cubic regularization of Newton method and its global performance". Mathematical Programming 108.1 (2006), pp. 177-205.
[NW99]
J. Nocedal and S. J. Wright. Numerical optimization. Springer, 1999.
[PHKX+23]
N. Ponomareva, H. Hazimeh, A. Kurakin, Z. Xu, et al. "How to dp-fy ml: A practical guide to machine learning with differential privacy". arXiv preprint arXiv:2303.0063 (2023).
[PS22]
N. Papernot and T. Steinke. "Hyperparameter Tuning with Renyi Differential Privacy".
In: International Conference on Learning Representations, 2022.
[RM16]
F. Roosta- Khorasani and M. W. Mahoney. "Sub-sampled" newton methods ii: Local convergence rates".. arXiv preprint drXiv:101.044336 (2016).
[RM19]
F. Roosta- Khorasan and M. W. Mahoney. "Sub-sampled Newton methods". Mathe- matical Programming 174 (2019), pp. 293-326.
[SCS13]
S. Song, K. Chaudhuri, and A. D. Sarwate. "Stochastic gradient descent with differ- entially private updates". In: 2013 IEEE global conference on signal and information processing. IEEE. 2013, pp. 245-248.
[SSTT21]
S. Song. T. Steinke, O. Thakkar, and A. Thakurta. "Evading the curse of dimen- sionality in unconstrained private glms". In: International Conference Artificial Intelligence and Statistics. PMLR. 2021, pp. 2638-2646.
[Ste98]
G. Stewart. Matrix algorithms: volume basic decompositions. SIAM, 1998.
[STT20]
S. Song, O. Thakkar, and A. Thakurta. "Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems". arXiv preprint 00X:v:2006.06783 (2020).
[STU17)
A. Smith, A. Thakurta, and J. Upadhyay. "Is interaction necessary for distributed private learning?" In: 20/7 IEEE Symposium on Security and Privacy (SP). IEEE. 2017, pp. 58-77.
[V722]
S. Vadhan and W. Zhang. "Concurrent Composition Theorems for Differential Pri- vacy". arXiv preprint arXiv:2207.08335 (2022).
[WLKC+17]
X. Wu, F. Li, A. Kumar, K. Chaudhuri, et al. "Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent- Analytics". . In: Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD. Ed. by S. Salihoglu,
W. Zhou, R. Chirkova, J. Yang, and D. Suciu. 2017.
[XRV17]
H. Xiao, K. Rasul, and R. Vollgraf. "Fashion-mnist: a novel image dataset for bench- marking machine learning algorithms". arXiv preprint VrXiv:1708.077 (2017).
[XYRMI6]]
P. Xu, J. Yang. F. Roosta, C. Ré, and M. W. Mahoney. "Sub-sampled Newton methods with non-uniform sampling". Advances Neural Information Processing Systems 29 (2016).
[ZLNM+19]
G. Zhang, L. Li, Z. Nado, J. Martens, et al. "Which algorithmic choices matter at which batch sizes? insights from a noisy quadratic model". Advances neural information processing systems 32 (2019).
[ZZMW17]
J. Zhang, K. Zheng, W. Mou, and L. Wang. "Efficient private ERM for smooth objectives". In: Proceedings of the 26th International Joint Conference Artificial Intelligence. 2017, pp.
13


Reviews:
[{"review_id": "IexELtqA8M", "reviewer": "Reviewer_8XFJ", "summary": "This paper focuses on the problem of private convex optimisation using second order information where the main motivation is the acceleration of private convex optimisation problem as DP-SGD shows slow convergence. This is done in two parts. Firstly, they introduce the privatised version of the cubic method of Nesterov and Polyak when the loss function is strongly convex. In this step, the privatisation is done by solving the optimisation problem given by the global cubic upper-bound privately (DP-Solver). They analyse the algorithm and provide convergence guarantees. \n\nSince the cubic method is computationally expensive, for the rest of the paper the authors focus on a method inspired by Newton's method with its specific application to logistic regression. Specifically, they provide a global upper bound for the logistic loss and for which the optimisation the upper bound has a closed form. They then privatise this method by privatising the steps of the optimisation algorithm. They do this in two steps. First by adding the proper amount of noise to the information from gradient and then adding noise at the update step.\n\nFinally, they empirically compare the performance of their proposed method for logistic regression to DP-(S)GD and objective perturbation.", "questions": "1. The upper-bound for the convergence analysis for  ($(lw) - l(w^*)$) in both Theorem 1 and Theorem 2 is done w.r.t $w^*$ which is the optimal w not attainable in the case where $\\rho>0$ as given by the lower-bound given in [BST14].  Does it not make more sense to provide the upper bound w.r.t the set of parameters $w$ which are achievable under privacy constraints?\n\n2. Throughout the paper you mention that your proposed method is 10-40 times faster but looking at Table 1 this is the case for $\\epsilon = 10$, otherwise the range is something like 3-40. Is there a reason for mentioning 10-40?\n\n3. [KSJ18] show that the Newton's method globally converges under some conditions which hold for logistic regression. Given this result, why do we need to build the global upper bound of lemma  5.1?\n\n4. Is the idea for building global upper  bounds for newton's something done for the first time in your paper? If not, it might be a good idea to add some references.\n\n\n\n\n\n\nMinor comments:\n\n1. You can add other examples where convex optimisation appears in ML. Some examples are kernel regression and extreme learning machines.\n\n2. I think adding some explanation and details to Theorem 4.2 might help the reader to digest the theorem a bit better i.e. What is the value of $w$ for which the transition between the convergence rates happen? My intuition is that the privacy constraint makes a set of parameters centred around $w^*$)admissible and while $w$ is outside of this range the convergence rate is slower and once we are within those parameters the convergence is much much faster. \n\n3. For theorem 5.6, it might help to mention that the relationship between the semi-norm and the $\\ell^2$ norm for ease of understanding.\n\n\n", "limitations": "It is similar to the comment I make in the weaknesses. The authors have not clearly mentioned that while the method is faster than DP-SGD, it requires an expert to get the algorithm up and running for other convex optimisation problems.\n\nAdditionally, it is known that the computational complexity of Newton's method scales badly with dimension d which I think should be mentioned in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Convex optimisation appears in many settings in Machine Learning and given the increasing attention to privacy, this is a timely problem to study.\n\n2. The combination of ideas to use a method similar to newton's method while making sure the upper bound is global like in the cubic method is nice.\n\n3.  The convergence analysis for the proposed algorithms.\n\n4. The details of the experiments are explained thoroughly and for the most part, they seem fair.", "weaknesses": "1. While private convex optimisation is an important problem and the techniques are interesting, I feel the scope of the paper is a bit limited as it only allows us to use the results for logistic regression in a private setting. For any other method that uses convex optimisation, like kernel methods, the user would need to calculate the sensitivity of the queries in algorithm 3 at which point the method being faster than DP-SGD might not be justification enough for this method.\n\n\n2. One of the main motivations for this paper is the slow convergence of DP-SGD. While the authors provide references to other bottlenecks for DP-SGD like the batch size and hyper-parameter tuning, there are no references for the slow-convergence of DP-SGD and the main thing supporting this claim in the paper is Figure 1. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. We respond to the main points below.\n\n> **W1:** The scope of the paper is limited to logistic regression. \n\nFor simplicity and clarity, many of our results focus on logistic regression, but our techniques are more widely applicable. Logistic regression is a widely-used method and there are many DP baselines for this task, so it is an ideal case study for our methods. Indeed, our algorithm based on double noise can be applied more broadly. In Appendix C.6 (Algorithm 6), we have provided an extension of Algorithm 3 whose privacy proof holds for **every** convex, Lipschitz, and smooth loss functions. Please refer to Remark 5.5 in the main body for further discussion. Also, Algorithm 3 and its convergence analysis in Theorem 5.6 holds for every convex, Lipschitz, smooth, and doubly-differentiable GLM loss function.\nBased on your comment, we will highlight the extensions beyond logistic loss in the paper.\n\n> **W2:** Supporting claim for the slow-convergence of DP-(S)GD.\n\nMost of the theoretical literature on DP convex optimization either ignores the problem of slow convergence or makes strong assumptions (e.g., strong convexity, small diameter constrained set) to ensure rapid convergence. But it is a major issue. See [our common rebuttal](https://openreview.net/forum?id=h2lkx9SQCD&noteId=ZhStwLJeHt) for further discussion. We will emphasize these points in the next revision.\n\n> **Q1:** On the definition of excess loss with privacy constraints.\n\nOur results follow the standard formulation in terms of excess loss used in the literature. It would be interesting to compare our upper bound with the optimal excess loss attainable under DP, but this would be difficult as the latter quantity is not known exactly. E.g., the lower bounds of BST14 are asymptotic and do not give tight leading constants. However, the excess error of our cubic Newton’s method is (near) optimal: the lower bound for the class of strongly convex functions [BST14,Thm.5.5] implies that the achievable excess error has the optimal dependence on the dimension, privacy budget, and number of samples up to a log factor.  \n\n> **Q2:**  10-40 times faster / 3-40 times faster\n\nThanks for noticing this oversight. We neglected to update this number after adding further experiments. We have updated the abstract and mentioned that our method is 3-40 times faster in general. \nOur method shows the greatest improvement for datasets such as Adult or Covertype where the logistic loss has an ill-conditioned Hessian.  For well-conditioned synthetic data, there is less room for improvement.\n\n> **Q3:** On the comparison with the results of [KSJ18].\n\nThe results of [KSJ18] show a global convergence for the “damped” Newton method, i.e., Newton's method with **non-unit** step size. However, it is not clear how the algorithm of [KSJ18] can be used for logistic regression in an unconstrained setting. By the results in Section 2.3 Part (a) in [KSJ18], the step size is proportional to $\\exp(-\\|\\|\\text{optimal solution}\\|\\|)$. For unconstrained logistic regression, there is no a priori knowledge on the norm of the optimal solution, therefore it is not clear how this result can be used. We have included a detailed comparison with [KSJ18] in the revised version of the paper.\n\n> **Q4:** Novelty of the quadratic upper bound.\n\nTo the best of our knowledge our quadratic upper bound for the logistic loss is a novel optimization technique. We will emphasize this point.\n\n\n> **minor comments** \n\nThanks! We have included more examples in the introduction. \n\nThe transition point in Theorem 4.2 happens when  $\\|\\|w_t - w^\\star\\|\\|$ is less than $ \\frac{3 \\mu }{4 L_2} $ where $\\mu$ and $L_2$ are the strong convexity parameter and Hessian Lipschitzness constant, respectively. Your intuition is correct and we will provide more discussion on this point after the statement of Theorem 4.2.  \n\nRelationship between semi-norm and $\\ell_2$ norm:\nV is the projection matrix on the subspace spanned by the training set. Therefore, for every point $x \\in \\mathbb{R}^d$, its semi-norm, i.e., $\\|\\|x\\|\\|_V \\leq \\|\\|x\\|\\|_2$. The main reason behind proving the convergence results in $\\|\\|x\\|\\|_V$ is that the components of the output vector, i.e., $w_T$, outside the subspace spanned by the data do not affect the excess error. \n\n"}, {"review_id": "tpPs9XjmYn", "reviewer": "Reviewer_rkzh", "summary": "The paper introduces an algorithm that utilizes second-order information to enhance the speed of private convex optimization, concurrently ensuring optimization excess error is minimal.\n\nThe outcomes of the experiments indicate that employing second-order information can expedite Differential Privacy (DP) optimization. In addition, it achieves an excess loss that either equals or surpasses that of first-order methods like DP Gradient Descent (DP-GD).", "questions": "On page 1, \"One of the major drawbacks of DP-(S)GD is slow convergence. We argue that the main reason for this is the difficulty of choosing the hyperparameters (/eta; T).\" Please explain why it is that. How about gradients?\n \nFor minibatch version, how to make sure the second-order information is still relevant/meaningful from one batch to another batch? \n", "limitations": "Yes, I think so. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The strength of this paper are\n\n1) The application of second-order methods to convex optimization is challenging research area. While some progress has been made, it's still uncertain whether second-order methods can be as practical as first-order methods. This paper unveils a novel second-order approach for Differential Privacy (DP) optimization, which demonstrates optimal efficiency for strongly convex functions.\n\n2) The authors offer an analysis of both the local convergence assurance associated with Hess-clip and Hess-add, as well as the global convergence guarantee for QU-clip and QU-add.\n\n3) The numerical findings indicate that the proposed method outperforms DP Gradient Descent (DP-GD) substantially, demonstrating a speed that is 10 to 40 times quicker for the datasets tested.", "weaknesses": "The weakness the paper include\n1) The potential impact of this work remains uncertain to me. While it presents strong results in the field of Differential Privacy (DP) private machine learning, it raises the question: can these results or concepts be applied more broadly?\n\n2) The mini-batch version offers interesting numerical results, however, the loss it produces is notably higher compared to the full-batch version.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. We respond to the weaknesses and questions below.\n\n> **W1** potential impact\n\nDP optimization is an important area with numerous practical applications. Our results are a substantial deviation from the existing DP optimization literature, which is almost exclusively restricted to first-order (and zero-order) methods. We believe our work can open up many directions for future investigation within the area of DP optimization. Beyond DP, we speculate that our results may be helpful for designing second-order convex optimization algorithms under **data corruptions**, i.e., robust second-order optimization. Recently, it has been a flurry of interest in understanding the connection between robust algorithms and private algorithms. (see [Asi+23].)\n\n[Asi+23] Asi, Hilal, Jonathan Ullman, and Lydia Zakynthinou. [\"From robustness to privacy and back.\"](https://arxiv.org/abs/2302.01855) (2023).\n\n> **W2** weaker minibatch results: \n\nThis is an important observation and one that has been observed repeatedly in the differential privacy literature. In general, it has been observed that for DP optimization the best results are attained by larger  batch sizes. E.g., see Figure 1 of [P+23] which shows that for training a neural network with DP, the required batch size needs to be large in order to reduce the amount of noise. It is an interesting phenomena that we have also observed in our experiments. It is an open question to show that such a limitation is inherent.\n\n[P+23] Ponomareva, Natalia, et al. [\"How to dp-fy ml: A practical guide to machine learning with differential privacy.\"](https://arxiv.org/abs/2303.00654) Journal of Artificial Intelligence Research 77 (2023).\n\n> **Q1a**: Why is it difficult to set hyperparameters for DP-(S)GD?\n\nPlease see [our common rebuttal](https://openreview.net/forum?id=h2lkx9SQCD&noteId=ZhStwLJeHt) elaborating on this point. We will try to clarify this important point in the revision.\n\n> **Q1b**: How to make sure second-order information is still relevant/meaningful from one batch to another batch?\n\nOur subsampling procedure for second-order information (SOI)  based on Poisson sampling implies that the expected value of the subsampled SOI is equal to the full-batch SOI at each iteration. Also, using the classical matrix concentration results, we can show that the subsampled SOI is close to the full-batch SOI with high probability as well. These two observations show that second-order information is still relevant in the minibatch version.\n"}, {"review_id": "EMIraYu2WO", "reviewer": "Reviewer_QyKz", "summary": "This paper considers the problem of differentially-private convex optimization and discusses how second-order information can be utilized to accelerate the optimization process while also achieving the optimal excess error, with DP involved. The main contributions of this paper are the two proposed algorithms, and the corresponding analyses; 1) A second-order DP algorithm that is based on the cubic-regularized Newton's method - for a specific class of convex functions, 2) A second-order DP algorithm for the logistic regression problem.", "questions": "1) For a given set of inputs in algorithm 3, how can one determine whether the SOI modification is \"add\" or \"clip\"? The reader could benefit from a clear description of this part (lines 3-6) in algorithm 3.\n2) Do the authors assume any characteristics (i.e., any specific distribution or any statistical characteristics) on the dataset $S_n$ in either of the algorithms?", "limitations": "The authors have clearly stated the limited types of functions which the proposed algorithms can be applied on, and have also commented on possible extensions to other classes of functions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper considers an important problem which studies how the performance of a differentially-private convex optimization process can be enhanced with the use of second-order information. The paper is well organized and rigorous proofs have been provided for the claims made. The first algorithm presented in this paper (DP variant of the cubic-regularized Newton's Method) achieves the optimal excess loss and quadratic convergence. The proposed second-order DP algorithm for logistic regression achieves equal or better excess losses and lower computational times compared to the existing DP algorithms, based on the experimental results.", "weaknesses": "The authors could clearly state their contributions and remark on the significance of the contributions, as in some cases (for example algorithms 1 and 2), it seems like the authors have simply incorporated DP into existing non-private results. The main paper lacks justification on the privacy guarantees. The authors could comment on how the stated DP guarantees are achieved by the selected noise parameters.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. We respond to the weaknesses and questions below.\n\n> **W1**: The authors could clearly state their contributions and remark on the significance:\n\nThe existing DP optimization literature is almost exclusively restricted to first-order (and zero-order) methods. Our goal in this paper is to answer the following question: “Can second-order information yield faster convergence in the differentially private setting?” Combining second-order methods with differential privacy requires a great deal of care, as they are fairly sensitive to noise.  We believe that our results provide a convincing affirmative answer to this question both in terms of worst-case convergence guarantee and practical algorithm design.\n\n> **W2**: it seems like the authors have simply incorporated DP into existing non-private results:\n\nWe respectfully disagree. The most natural way to privatize the non-private Newton’s method is to add noise *directly* to the gradient and Hessian, as was proposed by [ABL21]. However, to achieve optimal excess error with this method we need an additional assumption that the Hessian of the loss function is a low rank matrix; our algorithm does not suffer from such a limitation. Please refer to Remark 4.5 for further discussion. \nOn the practical side we tried many noise adding schemes before settling on the double noise method (Algorithm 3) and we found that this significantly outperformed the simpler approach of adding noise directly to the Hessian matrix.\n\n> **W3**: Proof of Privacy:\n\nThe detailed privacy guarantee of Algorithm 3 is stated and proved in Appendix C.3 and C.4. Based on your comment, we will move the formal statement of privacy guarantee to the main body. \n\n> **Q1**: On “add” or “clip” for second order modification:\n\nWe apologize if the presentation of Algorithm 3 caused confusion. The type of second-order information modification is an *hyperparameter* of our proposed algorithm. Also, notice that the modification based on “add” and “clip” have a different privacy proof as can be seen by the scale of noise. Empirically, we observe that for the full-batch setting “clip” is better than “add” and for minibatch version “add” performs better. Based on your suggestion, we have included a more precise discussion of it in the revised version.\n\n> **Q2**: Dataset assumptions.\n\nNo. We assume **worst-case** dataset for both our privacy proof and for our convergence guarantees. It is an interesting direction to analyze the generalization performance of our algorithms with distributional assumptions. We will add your suggestion to the list of future work. \n\n"}, {"review_id": "wxrJCST3Bc", "reviewer": "Reviewer_FNjC", "summary": "The paper introduces the use of second-order methods in differentially private optimization. In particular, two algorithms are proposed. One is based on cubic regularized Newton and works for strongly-convex functions. The other one is designed specifically for the logistic regression problem. Numerical experiments on the logistic regression are provided.", "questions": "See weakness.", "limitations": "See weakness.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The topic of using second-order methods in differentially private (DP) optimization is under-explored. In this sense, the paper can be a good starting point and introduce the idea to the DP community. The paper is well-written and easy to follow, with theoretical results that do not exist before and are supported by numerical experiments.", "weaknesses": "1. The theoretical justification of the benefit of using second-order methods is not strong enough. For the considered smooth strongly-convex setting, first-order methods can already achieve the same rate in linear time $O(n)$ [arXiv:1703.09947, arXiv:1802.05251, arXiv:2005.04763, arXiv:2102.05855, arXiv:2206.00363]. As a comparison, since the subproblem of the cubic regularized Newton cannot be efficiently solved due to nonsmoothness, the total gradient complexity of the proposed method is $NT\\sim n^2$. The main improvement is mostly on the oracle complexity but with more assumptions on the second-order information. Even for the oracle complexity, the proposed algorithm achieves $\\sqrt{L_2}/\\mu^{3/4}+\\log\\log(n)$, which is hard to compare with the one achieved by first-order methods (e.g., $(\\sqrt{L_1}/\\sqrt{\\mu})\\log(n)$ for private versions of the Nesterov's accelerated gradient descent [arXiv:2102.04704, arXiv:2206.00363]). I am also wondering if an improved lower-bound is possible with second-order information.\n\n2. The convergence analysis of the logistic regression case seems to be not complete. I don't find (also in the appendix) any specific rate, complexity, and comparison with first-order methods. The proposed method requires the local strong convexity assumption at the optimum. Does it hold for the logistic regression loss?\n\n3. The proposed method requires computing the inverse of the second-order information, which could be hard for large-scale experiments. Also, all the numerical experiments in this paper use small models and datasets, where computing this inverse does not cost too much. Given that DP-GD already completes the task within 1 minute, such a 10-40$\\times$ improvement is not considered to be so surprising.\n\n4. What does $T^*$ mean in Table 1, or what is the stopping criterion to define $T^*$? Why do Figure 3 & 4 only show the first 10 steps or 0.6s? I guess the noise added for the proposed method is computed according to the theory. Are there any numerical privacy accounting methods used in the experiments to justify the effectiveness of the added noises? In case the privacy analysis is wrong and less noise is added than what is required, this might not be a fair comparison.\n\n5. Minors: It might be good to also summarize related works for non-DP second-order optimization algorithms. What does privacy budget for direction mean in $\\lambda_{0,t}$ in line 249.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. We respond to the weaknesses raised below.\n\n>**W1**: Justification of using second-order methods and comparison with first order methods \n \nOur goal in this paper is to understand whether second-order methods are compatible with DP. For the theory, we use oracle complexity, which is the standard measure of convergence rate in the non-private literature. \n\nThe subproblem we solve is a cubic function, which is indeed smooth *over the constraint set.* This observation lets us use more efficient algorithms as the subproblem solver. Please refer to [our common response](https://openreview.net/forum?id=h2lkx9SQCD&noteId=ZhStwLJeHt) where we discuss it further. In particular, we can show that the number of gradient and Hessian-vector evaluations is $\\log\\log(n)* n * \\log(n)$.\n\nAs mentioned, the oracle complexity of first order methods is $\\log n$ while ours is $\\log\\log(n)$. I.e. our is an exponential improvement in oracle complexity. This result tight, including the other terms, as shown by [non-private oracle complexity lower bounds](https://arxiv.org/abs/1705.07260). \n\n> **W2**: local strong convexity at the optimum for logistic loss and its convergence analysis\n\nUnless the data is linearly separable, the logistic loss has a minimum eigenvalue at the optimum which is ** bounded away from zero**. Let $f(x) = \\log(1+\\exp(-x))$, then we have $f’’(x)\\geq 1/4  \\exp(-|x|)$. Therefore, by Eq.(5) in the paper, eigenvalues at the optimum are strictly larger than zero for all eigenvectors that are not orthogonal to the subspace spanned by the data. This assumption has been used before as well. See arxiv:1303.6149.\n\nIn the submitted paper, we only present the recursion of the error. It can be easily used to obtain the following for our local convergence result: Assume that the initial point is sufficiently close to the optimum. Assume that $\\lambda_0 > \\lambda^\\star_{min}$, then after $T=\\tilde{O}\\left( \\frac{\\lambda_0}{\\lambda^\\star_{min}} \\log(n) \\right)$ iterations, Algorithm 3 achieves the excess loss of $\\tilde{O}\\left( \\kappa^\\star \\frac{\\text{rank}}{\\rho n^2 \\lambda^\\star_{min}} \\right)$ where $\\kappa^\\star$ is the condition number at the optimum.\nWe will include this result in the paper. Note that the dependence on the condition number and the assumption of the local strong convexity at optimum appear in many prior work on second-order optimization (See arxiv:1508.02810,arxiv:1607.00559)\n\n> **W3**: On significance of speed-up of our algorithm and the choice of datasets\n\nFor larger datasets (i.e. larger $n$), the gap between our algorithm and DP-(S)GD increases. For instance, for Adult the completion time for DPGD is 5 minutes while for ours is 8 seconds.  We conducted an additional larger scale experiment for the synthetic dataset with a five times more samples. In the attached PDF Item 2 in our common response, we plot the excess loss versus runtime, and as can be seen again there is a significant gap between the completion time of our algorithm and DPGD.\n\nIt is a well-known limitation of second-order methods that they require matrix computations, rather than just vector computations like first-order methods, which is a problem when the dimension $d$ is large. There is an extensive line of work on addressing this challenge by working with low-rank approximations to the second-order information. It would be interesting to combine our methods with these approaches to scale to high-dimensional settings. However, this is beyond the scope of our work. Our goal is simply to demonstrate the feasibility of using second-order information to accelerate DP convex optimization. \n\nWe use standard datasets for classification for which the linear classifier learned via logistic regression is successful. The dimension of the datasets are in the range of 55 to 784. We would appreciate the reviewer’s suggestions for further datasets to consider. \n\n\n> **W4**: What does T^\\star mean? And what is the stopping criterion?\n\n$T^*$ is the runtime of the algorithm in seconds. The star refers to the fact that we perform hyperparameter tuning to optimize the accuracy and report the runtime for this setting of hyperparameters. Note that we perform tuning of $T^*$ for **all** iterative algorithms.  \nNote that the number of steps $T$ is specified a priori as a hyperparameter; it is not a dynamic stopping criterion. This is necessary, as we must know $T$ in order to divide the privacy budget between iterations.  \n\n\n> **W4**: Why do Figure 3&4 only show the first 10 steps or 0.6s?\n\nIn Figure 3, our goal is not to plot the excess error vs runtime. Our goal was to compare the impact optimal step size for DPGD and second-order information on the excess error. The choice of 15 steps is arbitrary.\n\nFigure 4 provides a comparison between the minibatch variations of our algorithm and DP-SGD. The x-axis capped at our algorithms' maximum $T^\\star$ value. Notice that for synthetic data  $T^\\star$ of our algorithm is around 0.05. Please see Item (3) in the attached pdf in [our common response](https://openreview.net/forum?id=h2lkx9SQCD&noteId=ZhStwLJeHt) for a plot without truncating x-axis.\n\n> **W4**: Privacy accounting for the experiments\n\nWe use the same privacy accountant for all studied algorithms. The full-batch variant of our algorithms and DP-GD satisfies zCDP. zCDP provides a simple composition theorem–the privacy parameter adds up when we compose and it is tight. For translation from DP to zCDP, and for the mini batch variants, we use Opacus package.\n\n\n> **Minor Comments**:\n\nThanks! We will include a comprehensive literature review of the non-private second-order methods. \n\nFor the adaptive scheme we divide the privacy budget into three parts. We refer to the privacy budget for estimation of $\\Phi(H)^{-1} (\\tilde{g})$ as the privacy budget for the direction.\n"}, {"review_id": "zgEFLco3A8", "reviewer": "Reviewer_Pzhc", "summary": "This work investigates the use of second-order methods in differentially private convex optimization for machine learning. The authors propose a private variant of the regularized cubic Newton method and demonstrate its quadratic convergence and optimal excess loss for strongly convex loss functions. They also design a practical second-order differentially private algorithm for unconstrained logistic regression, which outperforms other baselines in terms of excess loss and is significantly faster than DP-GD/DP-SGD, achieving a speedup of 10-40 times.", "questions": "See Weakness.", "limitations": "See Weakness.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "This paper is good as it has been a really hard to use second-order information while preserving DP property. The contribution is novel and the proof seems to be correct. ", "weaknesses": "1. Maybe extend to use laplace noise? \n2. The presentation of the paper is a little bit awkward. For example, the formal DP theorems and proof of Alg. 3 only presents in Appendix. It is really hard to find the corresponding reference. This paper might need to be rewritten.\n3. Experiments:\n    1. Compare the true running time. It takes a lot of time to compute the CLIP and ADD operations as it needs to compute SVD. So instead of seeing how many steps it needs, please present the true computational time to show the true running time improvement compared with DP-SGD and DP-GD.\n    2. Compare memory usage. SVD needs tons of memory.\n    3. DP-SGD brings randomness and sometimes accelerates the training procedure. Please add a comparison with DP-SGD.\n    4. Compare with different learning rates (I know there does not exist a learning rate in Alg. 3 but a learning rate exists in DP-(S)GD). It would be interesting to see the impact of different learning rates (10, 0.1, or 0.01).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough review. We respond to the weaknesses and questions below.\n\n> **W1**: Laplace noise and pure DP:\n\nWe can potentially use laplace noise to design algorithms with stronger pure-DP guarantee. However, it has been observed empirically and theoretically that the excess loss of convex optimization under pure-DP is much higher than the relaxed notions such as zero-concentrated DP (zCDP). For instance, for DP convex optimization, by Theorem 3.2 and Theorem 2.4 in [BST14] we can see that pure-DP algorithms exhibit an excess loss dependence of O(dimension), while zCDP algorithms demonstrate a dependency of sqrt(dimension).\n\n[BST14] Bassily, Raef, Adam Smith, and Abhradeep Thakurta. \"Private empirical risk minimization: Efficient algorithms and tight error bounds.\" 2014 IEEE 55th annual symposium on foundations of computer science. IEEE, 2014.\n\n> **W2**: Presentation of the paper:\n\nThanks for the suggestion! We will state the privacy proof more formally as a theorem in the main body of the paper. We would greatly appreciate any other suggestions for improving the presentation.\n\n> **W3-Part1**: Comparison of the true runtime:\n\nIn Section 6, we have already compared the runtime (in sec) of our algorithm with DP-(S)GD. Please refer to Table 1 and Fig.2 in the main body and Table 4 in the appendix. For instance, for Covertype dataset our algorithm is 30 times faster compared to DPGD for achieving $\\varepsilon=1$. This is remarkable since the per-iteration cost of the second-order methods is higher than DP-(S)GD. \n\n> **W3-Part2**: Comparison of memory usage:\n\nIt is correct that SVD may need large memory space. The memory usage varies with the chosen SVD implementation; we utilized numpy's linalg.eigh in our experiments. To address this concern, we'll provide memory usage specifics for SVD on each dataset in the revised paper.  For instance, for Adult dataset  with dimension 100, the memory usage is 52 MiB, and for Fashion-MNIST with dimension 784, the memory usage is 67 MiB.\n\n> **W3-Part3**: Comparison with DP-SGD:\n\nIn Section 6.1, we have already compared the minibatch variant of our algorithm with DP-SGD and show that it has faster convergence. Fig. 4 summarizes the results. The subsampled variant of our algorithm achieves the same excess error as DP-SGD with $8$-$10 \\times $ faster run time over all the datasets while the batch sizes of our algorithms are larger than that of DP-SGD (Please see Section 6.1).  \n\n> **W3-Part4**: Different Learning Rate for DPGD:\n\nThanks for the suggestion. The **attached PDF (Item 1)** in [our common rebuttal](https://openreview.net/forum?id=h2lkx9SQCD&noteId=ZhStwLJeHt) shows the results for different learning rates for Adult dataset. We will include the results for all the datasets in the next revision of the paper.\nThe main observation is that a larger learning rate helps DPGD in the initial phase of optimization. However, after getting close to the optimal point, large learning rate leads to a higher excess error.  Also, in the submitted paper Line 331, we have provided numerical results comparing our algorithm with DP-GD where at each iteration, we perform linesearch to select learning rate. We call this variant DP-GD-Oracle and obviously this variant does not satisfy DP. Nevertheless, Figure 3 shows our algorithms converge faster than DP-GD-Oracle which is not even a DP algorithm. \n\n\n"}, {"review_id": "h0UfrJdDwr", "reviewer": "Reviewer_Xt6K", "summary": "This paper studies DP convex optimization by using second-order methods. The authors present a private version of the cubic regularized Newton method and prove it faster than the first-order methods under strongly convex case. They also provide efficient second-order method for solving the DP logistic regression problems.", "questions": "See weakness part.", "limitations": "N/A", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This is the very first paper to study the second-order methods for DP convex optimization. The author present algorithms for both general strongly convex functions and logistic regressions which are very novel. The Algorithm 3 for DP logistic regression consider the special structure of the object function which is very interesting.", "weaknesses": "The algorithm for solving the general strongly convex functions seems straight forward. It is a combination of cubic-regularized Newton and DPGD. The requirement of solving subproblem by DPGD at each iteration is not satisfying and may cause the total computation cost even worse than the first-order method.  Can the author present the total number of the iterations (including the inner loop) and compare it with the first-order DP method?\n\nAlthough the author present efficient method for solving the DP logistic regression, Algorithm 3 seems quite different from the meta algorithm for the general strongly convex optimization problems. Can the authors show the connection between the Algorithm 3 and Algorithm1,2?\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments on our submission. We respond to the weaknesses raised.\n\n> **W1**:  The algorithm for solving the general strongly convex functions seems straight forward:\n\nWe respectfully disagree. The most natural way to privatize the non-private Newton’s method is to add noise directly to the gradient and Hessian, as was proposed by [ABL21]. However, to achieve optimal excess error with this method we need an additional assumption that the Hessian of the loss function is a low rank matrix; our algorithm does not suffer from such a limitation. Please refer to Remark 4.5 for further discussion. On the practical side we tried many noise adding schemes before settling on the double noise method (Algorithm 3) and we found that this significantly outperformed the simpler approach of adding noise directly to the Hessian matrix.\n\n> **W2** Algorithm for strongly convex functions and its total iteration cost:\n\nWe discuss this in [our common response](https://openreview.net/forum?id=h2lkx9SQCD&noteId=ZhStwLJeHt). The total iteration cost depends on the subproblem solver. In particular, as discussed in our common response, the total iteration complexity is $\\log\\log(n) * \\log(n)$. Therefore, the iteration cost is competitive with first-order methods. The win is in the oracle complexity.\n\n> **W3**: Connection between Algorithm 1 and Algorithm 3 in the paper:\n\nLogistic loss is *not strongly convex* in the unconstrained setting. Also, the main limitation of the proposed cubic Newton's method is that each iteration requires solving a nontrivial subproblem. These are the main reasons why we develop a new algorithm for private logistic regression with significantly improved *wall clock time* (in seconds) compared to other baselines, as shown in Table 1. Note that our proposed algorithm is not limited to the logistic loss; we provide a generalization of Algorithm 3 in Appendix C.6. Please see Remark 5.5.\n\n"}]

Author rebuttal:
We are extremely grateful to the reviewers & AC for their time & comments. Their comments have been very constructive. We respond to each review individually, but we respond to some common points here:

**On the slow convergence of DP-SGD:** Several reviewers questioned the claim that DP-(S)GD converges slowly, which we made in the last paragraph on the first page of the submission and supported with Figure 1. We wish to elaborate on this point, since it is integral to the motivation for our work. Informally, this is because the addition of noise can push us in directions of increasing loss, so we need more conservative step sizes to avoid moving too far in the wrong direction. This fact is reflected both theoretically and empirically in the literature:

 - Theoretically, optimal instantiations of DP-SGD use a smaller step size than in the non-private case, e.g. [Bassily et al. (2019)](https://arxiv.org/pdf/1908.09970.pdf) use $\eta$ that decays as $\max\\{1/\sqrt{n}, \sqrt{d}/\varepsilon n\\}$, much smaller than the non-private setting of $\eta = 1 / \beta$ when the loss is $\beta$-smooth. Smaller step size requires more steps (i.e. more iterations) to converge. Also, refer to the attached PDF (Item 4) for an example of noiseless and noisy gradient steps on a 1-smooth quadratic loss. This example intuitively explains why we need small $\eta$ for DP-(S)GD.

 - Empirically, e.g., Figure 1 of [Kurakin et al. (2022)](https://arxiv.org/abs/2201.12328) shows that the accuracy of DP training significantly improves if we run DP-SGD for more iterations while keeping the overall privacy budget fixed.

**On computing second-order information and iteration/runtime complexity:** Several reviewers had concerns relating to the complexity of Algorithm 1. We focused on oracle complexity, which is common in the literature. We can also show that in terms of computational complexity, Algorithm 1 is competitive with the best first-order methods. We will add a discussion of this to the paper.

First, we do not need to compute a full Hessian to run DPSolver, but only to compute Hessian-vector products (HVPs). HVPs in practice can often be computed in the same order of time as it takes to do a gradient computation (see e.g. https://jax.readthedocs.io/en/latest/notebooks/autodiff_cookbook.html). So for any first-order method we use as DPSolver, each iteration of Algorithm 1 can be made to take time comparable to the runtime of DPSolver on an arbitrary loss. 

While we use DP-GD as DPSolver for simplicity of presentation, any first-order method with the same privacy and utility guarantee as DP-GD gives the same privacy and utility guarantee for Algorithm 1, so we can choose e.g. a more efficient method for strongly convex losses as Algorithm 1. As a concrete example, we can use Alg.1 in [Wang et al. (2017)](https://proceedings.neurips.cc/paper/2017/file/f337d999d9ad116a7b4f3d409fcc6480-Paper.pdf) using which the subproblem solver has HVP and gradient complexities of order $n\log(n)$ and iteration complexity of order $\log(n)$.


Putting it all together, the runtime of Algorithm 1 in practice will be no worse than $O(\log\log n)$ times the runtime of the first-order method we choose as DPSolver. Furthermore, we hypothesize that since we are using DPSolver to optimize a well-behaved cubic function, the runtime of DPSolver can be made even faster, making our Algorithm 1 even faster as well. 


Meta-review: After a fairly intense discussion, all reviewers recommended some degree of acceptance of the paper. However, I **strongly** encourage the authors to update their manuscript to reflect the issues raised by the reviewers and the updates presented in their rebuttal.

Specifically, during the AC-reviewer discussion phase, the reviewers appreciated the contributions the paper makes to the field of differential privacy but still highlighted some areas for improvement. One concern is the lack of a clear explanation about the limitations of the methods used, e.g., the scalability of Newton's method. Reviewers also suggested that a **brief** review of related optimization literature would be welcome, particularly to further motivate the paper (as opposed to only Fig. 1). Finally, reviewers suggested streamlining and improving the statement of the theorems.
Decision: Accept (poster)