Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant
Authors: Li-Yue Sun
Venue: NeurIPS 2022 Submitted (2022)
Keywords: Homomorphic Encryption
Logistic Regression
Quadratic Gradient
Simplified Fixed Hessian
Privacy Preserving
Nesterov's accelerated gradient

Abstract: Logistic regression training over encrypted data has been an attractive idea to security concerns for years. In this paper, we propose a faster gradient variant called quadratic gradient to implement logistic regression training in a  homomorphic encryption domain, the core of which can be seen as an extension of the simplified fixed Hessian. We enhance  Nesterov's accelerated gradient (NAG) and Adaptive Gradient Algorithm (Adagrad) respectively with this gradient variant and evaluate the enhanced algorithms on several datasets. 
Experimental results show that the enhanced methods have a state-of-the-art performance in convergence speed compared to the naive first-order gradient methods. We then adopt the enhanced NAG method to implement homomorphic logistic regression training and obtain a comparable result by only 3 iterations.

Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant
Anonymous Author(s) Affiliation Address
email
Abstract
Logistic regression training over encrypted data has been attractive idea security concerns for years. In this paper, we propose a faster gradient variant called quadratic gradient implement logistic regression training in ho- momorphic encryption domain, the core of which can be seen as an extension of the simplified fixed Hessian (5). We enhance Nesterov's accelerated gradient (NAG) and Adaptive Gradient Algorithm (Adagrad) respectively with this gradient variant and evaluate the enhanced algorithms several datasets. Experimental results show that the enhanced methods have state-of-the performance in convergence speed compared the naive first-order gradient methods. We then adopt the enhanced NAG method to implement homomorphic logistic regression training and obtain a comparable result by only iterations.
2
4
10
11
Introduction
13
Logistic regression (LR) is widely used classification technology especially in medical risk assess- ment due to its simplicity but powerful performance, Given a person's 's healtheare data related to certain disease, we can train LR model capable of telling whether or not this person likely to develop this disease. However, such personal health information is highly private to individuals. The privacy concern, therefore, becomes major obstacle for individuals to share their biomedical data. The most secure solution is to encrypt the data into ciphertexts first by Homomorphic Encryption (HE) and then securely outsource the ciphertexts the cloud, without allowing the cloud to access the data directly. iDASH is an annual competition that aims to call for implementing interesting cryp- tographic schemes a biological context. Since 2014, iDASH has included the theme of genomics and biomedical privacy. The third track of the 2017 iDASH competition and the second track of the 2018 iDASH competition were both to develop samomorphic-encryppin -ased- solutions for building LR model over encrypted data.
14
15
16
17
18
19
20
21
23
25 Several studies on logistic regression models are based on homomorphic encryption. Aono et al. only used an additive HE scheme and left some of the challenging HE computations to trusted client. Kim et al. 14 discussed the problem of performing LR training in an encrypted environment. They used the full batch gradient descent in the training process and the least square method to get the approximation of the sigmoid function. In the iDASH 2017 competition, Bonte and Vercauteren (5). Kim et al. [12. Chen et al. (6), and Crawford et al. 8 all investigated the same problem that Kim et
26
27
29
31 al. 44 studied. the iDASH competition of 2018, Kim et al. [I3] and Blatt et al. [3] further worked on it for efficient packing and semi-paralle algorithm. The papers most relevant to this work 33 are [5] and [12]. Bonte and Vercauteren [5] developed a practical algorithm called the simplified fixed Hessian (SFH) method. Our study complements their work and adopts the ciphertext packing technique proposed by Kim et al. 12 for efficient homomorphic computation.
35
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

38
Our specific contributions in this paper are as follows:
37
We propose a new gradient variant, quadratic gradient, which can unite the first-order gradient method and the second-order Newton's method
38
39
2. We develop two enhanced gradient methods by equipping the original methods with quadratic gradient. The resulting methods show better performance in the con- vergence speed.
40
41
42
3. We adopt the enhanced Nesterov's accelerated gradient to implement privacy-preserving logistical regression training, our best knowledge, which seems be the best candidate without compromising much on computation and storage.
44
Preliminaries
45
We adopt the square brackets "[]" to denote the index of vector or matrix element in what follows. For example, for vector [2(x) and matrix M E æmxx, v[i] or Vig means the i-th element of vector and [+][]] M[[ the j-th element in the i-th row of M.
47
2.1 Fully Homomorphie Encryption
Fully Homomorphic Encryption (FHE) a type of cryptographic scheme that can used compute 51 an arbitrary number of additions and multiplications directly on the encrypted data. It was not until
50
52 2009 that Gentry constructed the first FHE scheme via a bootstrapping operation [9]. FHE schemes themselves are computationally time-consuming: the choice of dataset encoding matters likewise 54 to the efficiency. In addition to these two limits, how to manage the magnitude of plaintext [I]] also contributes the slowdown. Cheon al. 77 proposed method to construct an HE scheme
56 with a rescaling procedure which could eliminate this technical bottleneck effectively. We adopt their open-source implementation HEAAN while implementing
homomorphic LR algorithms. It 58 is inevitable to pack a vector of multiple plaintexts into a single ciphertext for yielding a better amortized time of homomorphic computation. HEAAN supports parallel technique (aka SIMD) to pack multiple numbers in a single polynomial by virtue of the Chinese Remainder Theorem and provides rotation operation on plaintext slots. The underlying HE scheme in HEAAN is well described in
60
82
63
2.2
Database Encoding Method
Kim et al. 12 devised an efficient and promising database-encodie method by using SIMD technique, which could make full use the computation and storage resources. Suppose that a database has a training dataset consisting of samples with (1 + d) covariates, they packed the training dataset Z into a single ciphertext in a row-by-row manner:
65
67
Training Dataset: Matrix Z
2[1[[]]
2(10(1)
2[[][o]
2[][4] 2p][
Database Encoding Method
12
2|2][0]
R[2[[1]
68
2[][0]
-[2[[1]
Enc
2[n][11]
[[x][0)
[[n][]]
[[m][d]]
89
70
Encoding
71
[[][0]]
2DJ1
[[2][0]
2|2][4]
2[n][0]
2[n][4]
Encrypt
74
Encl 2[1(0)
2[14
2[2)0
2(x][0)
2[1][4]
Using this encoding scheme, we can manipulate the data matrix Z by performing HE operations on the ciphertext Enc[Z], with the help of only three HE operations rotation, addition and multiplication. For example, if we want the first column of Z] alone and filter out the other columns, we can
76

---

78
design constant matrix F consisting of ones in the first column and zeros in the rest columns and
79 then multiply Ene[2] by Enc[F], obtaining the resulting eiphertext Enc[Zp]:
Enc(F F)
3 Encl 2| = Enc 7pp
(where "Ø" means the component-wist HE multiplication)
0
0
[[]]0]]
[[][[]]
2[1][o] 0
[[2][]]
P[2[[1]
2|2][4
[[2][0]
Enc
s Enc
Enc
:
:
0
[/]][[]]
2[m][1]
2(m][o]
80
Han al. 10] introduced several operations to manipulate the ciphertexts, such a procedure named "SumCol Vec" to compute the summation of the columns of a matrix. By dint of these basic operations, more complex calculations such as computing the gradients in logistic regression models are feasible.
81
82
83
2.3
Logistic Regression
84
Logistic regression is widely used in binary classification tasks to infer whether binary-valued variable belongs certain class or not. LR can be generalized from linear regression (15) by mapping the whole real line (3' x) (0, 1) via the sigmoid function ((2) the vector 3 E (L++d) is the main parameter of L.R and the vector (1,41,---) x.2) R (1+d) the
85
86
where
88
input covariate. Thus logistic regression can be formulated with the class label y E {=1} as follows:
Pr(y +1|x, 3) o(3Tx)
1 1+e-8'x
1
Pr(y - =1 -
e+8"x
89 LR sets a threshold (usually 0.5) and compares its output with it to decide the resulting class label.
80 The logistic regression problem can be transformed into an optimization problem that seeks param- 91 eter ( to maximize L(3) -II Pr(y:|x,, (3 or its log-likelihood function ((3) for convenience in
92 the calculation:
a
in - Σ
In(1 -B0Tx:)
93 where is the number of examples in the training dataset. LR does not have a closed form of 94 maximizing ((3) and two main methods are adopted estimate the parameters of an LR model:
(a) gradient descent method via the gradient; and (b) Newton's 's method by the Hessian matrix. The 96 gradient and Hessian the log-likelihood function ((3) are given by, respectively:
V (1-001183 x:))xxxi,
V3((3) = Σ (ouxx)oou,,,'' x,) 30,
X
37 where is a diagonal matrix with entries S. = - x.) and X the dataset.
- (,,
98 The log-likelihood function l(3) of LR has at most a unique global maximum M. where its gradient
99 zero. Newton's method a second-order technique to numerically find the roots of real-valued differentiable function, and thus can be used to solve the /3 in Val(3) = 0 for LR.
100
3 Technical Details
quite time-consuming to compute the Hessian matrix and inverse Newton's method for each iteration. One way to limit this downside is to replace the varying Hessian with fixed matrix Н. This novel technique called the fixed Hessian Newton's method. Böhning and Lindsay 4 have shown that the convergence of Newton's 's method is guaranteed long H Vz((3), where H is

---

symmetric begative-definity matrix independent of B and "I" denotes the Loewner ordering in the sense that the difference (3( H is non-negative definite. With such fixed Hessian matrix H, the iteration for Newton's method can be simplified to:
B 3, H ---VVVVlll (3)(
Böhning and Lindsay also suggest the fixed matrix H = - x=xxX X is good lower bound for the Hessian of the log-like ligeeellioood function ((3) in LR.
102
103
104
3.1 the Simplified Fixed Hessian method
Bonte and Vercauteren [S] simplify this lower bound H further due the need for inverting the fixed Hessian in the encrypted domain. They replace the matrix H with a diagonal matrix B whose diagonal elements simply the sums of each in H. They also suggest specific order of calculation to get B more efficiently. Their new approximation B of the fixed Hessian is:
Σ hos
E his
0
Σ 2i=0
has
where hus is the element of H. This diagonal matrix B is in very simple form and be obtained from H without much difficulty. The inverse of B can be approximated in the encrypted form by
105
106
107
means of computing the inverse of every diagonal element of B via the iterative of Newton's method
108
with an appropriate start value. Their simplified fixed Hessian method can be formulated as follows:
B B₂
B
V (B)
00o
Vo V1
buo
V
0
b1
d1
V
Br
bad
V
bad
V
109 where by; is the reciprocal of Σi= bos and V, is the element of Vg((3).
110 Consider special situation: if boo.... ... bas are all the same value -1 with 17 > 0, the iterative formula
of the SFH method can be given as:
Vo
V
Bo1 (-n)-
B, + V)l(B),
V
112 which is the same the formula of the naive gradient ascent method. Such coincident is just what the idea behind this work comes from: there is some relation between the Hessian matrix and the learning rate of the gradient (descent) method. We consider by V, as a new enhanced gradient variant's s element and assign a new learning rate to it. As long as we ensure that this new learning rate decreases from a positive floating-poin number greater than 1 (such as 2) to bounded number of iteration steps, the fixed Hessian Newton's 's method guarantees the algorithm will converge eventually.
113
114
116
118
119
The SFH method proposed by Bonte and Vercauteren [5] has two limitations: (a) in the construction of the simplified fixed Hessian matrix, all entries the symmetric matrix / need be non-positive For machine learning applications the datasets will be in advance normalized into the range [0, 1]. meeting the convergence condition of the SFH method. However, for other cases such as numerical optimization, it doesn't It always hold; and (b) the simplified fixed Hessian matrix B that Bonte and
120
122
123
124
Vercauteren constructed can still be singular, especially when the dataset a high-dimensional
sparse matrix, such as the datasets from the MNIST database. We complement their work by removing these limitations so as to generalize this simplified fixed Hessian be invertible in any case and propose faster gradient variant, which we term quadratic gradient.
126

---

128
3.2
Quadratic Gradient
129
scalar-valued valued function F(x) has its gradient g and Hessian matrix H, with any matrix H I H in the Loewner ordering as follows:
Suppose that a differentiable scalar-
130
9u
V
90
V
hoo hai
hoa hia
hio hn
91
ld
g =
H
9d
do
V
dd
hao has had
131 where V2
V jz
8² Sw:
We construct new Hessian matrix B as follows:
Σ ==
hoo
EL Paa
0
B =
Ei [
where is a small positive constant to avoid division by zero (usually set to 1e 8).
As long as B satisfies the convergence condition of the above fixed Hessian method, B < H, we can use this approximation B of the Hessian matrix as lower bound. Since we already assume that H < H, it will suffice to show that B S H1 We prove < Hl in a similar way that [5] did.
133
134
135
136
Lemma 1, Let A E R be a symmetric matrix, and let be the diagonal matrix whose diagonal entries B&k- - E; Akal for k R, then B S A.
138
Proof. By definition of the Loewner ordering, we have to prove the difference matrix C = A - B non-negative definite, which means that all the eigenvalues of C need to be non-negative. By construction of C' we have that Cyy = Ay + E + Σ |Asal for i = j and Ciy = Ai for & By means of Gerschgorin's 's circle theorem, we can bound every eigenvalue À of C in the sense that
140
141
142
A Cial < Eips [Ciyl for some index i E {1, ...,,.., n}. We conclude that À 2 Ai + Au 2
143
8 > 0 for all eigenvalues À and thus that B < A.
O
Definition 3.1 (Quadratic Gradient). Given such B above, we define the quadratic gradient g with a new learning rate T, where B a diagonal matrix with diagonal entries BE = Bss), and n should be always no less than 1 and decrease to I in a limited number of iteration steps. Note that G is still a column vector of the same size the gradient g. To maximize or minimize the function F(x), we can use the iterative formulas: xx+1 Xx + or X X 1) G. just like the naive gradient.
145
as G
146
148
We point out here that H could be the Hessian matrix H itself and B further optimized to: BEg FaR
hhaa + E [gg. In our experiments, we use H 1 construct our B.
151
152
3.3
Two Enhanced Methods
153
Quadratic Gradient can be used to enhance NAG and Adagrad.
NAG is different variant of the momentum method to give the momentum term much more prescience. The iterative formulas the gradient ascent method for NAG are as follows:
155
V4+1 3, + 04 (GG)) B (1 -1)) V(+1 + V4,
(3)
(4)
156
where Vi+1 is the intermediate variable used for updating the final weight B.+1 and f E (0. 1) is a smoothing parameter of moving average to evaluate the gradient at approximate future position
[2]. The enhanced NAG to replace B with V441 = 3, + (1 + a.) G. Our enhanced NAG
158
159
method is described in Algorithm
180
Adagrad a gradient-based algorithm suitable for dealing with sparse data. The updated operations of Adagrad and its guadratic-gradiin version, for every parameter Big each iteration step t, are as
5

---

Algorithm 1 The enhanced Nesterov's accelerated gradient method
Input: training dataset X E [Rxx training label Y E [R=x11 and the number x. of iterations;
Output: the parameter vector V E R(++d)
1: Set H 6- - X
E (R++)x((+d)
2: Set V f- 0, W + 0, 0. 0
D DVE R(+d, W E R(++ B E (1+))(((+))
3: for := 0 do
4:
B +
D e is a small positive constant such as le - 8
5: for j := to do
6:
B|i][ - B Нب
7: end for
8: end for
9: Set og +- 0.01, 01 0.5 (1 + v1+4x a
10: for countt == to do
11: Set 2 + 0
E 18t the inputs for sigmoid function
12:
for : 1 to do
13:
for j :- 0 do
14:
2 < Z|i] + Y
15:
end for
16:
end for
17:
Set σ +
> o E R" is to store the outputs of the sigmoid function
18:
for
1 do o <- 1/(1 +
19:
20:
end for
21:
Set < 0
22:
for to d do
23:
for i- = to n do
g < g/و (1
Y X|
25:
end for
end for
27:
Set G t 0
for = 0 to d do
29:
Gbi + B[j][]] ز|و
end for
31:
Set +- (1 a0)/a1, +- 1/(n x count)
is the size of training data
32:
for j = to d do
33:
Wtemp f- Vb + (1 11+ 7) Giji]
34:
V[j < (1 17) x Wtemp + 17 x Wh1
35:
W [i] f- Wtemp
36:
end for
37:
Oip ai, an 0.5 x (1 1 11+4x0
38:
end for
39: return V

---

182
follows, respectively:
3 ( (++1)
7
9 [
+
Σ k=
(1)
9
B ((+1)) (
+ n
E G G
+
163
Performance Evaluation We evaluate the performance various algorithms in the clear using the Python programming language on the same desktop computer with an Intel Core CPU G640 at 1.60 GHz and 7.3 GB RAM. Since our focus on how fast the algorithms converge the training phase, the loss function, maximum likelihood estimation (MLE), is selected as the only indicator. We evaluate four algorithms, NAG, Adagrad, and their quadratic-gradee
164
165
167
versions (denoted as Enhanced NAG and Enhanced Adagrad, respectively) the datasets that Kim et al. [12] adopted: the iDASH genomic dataset (iDASH), the Myocardial Infarction dataset from Edinburgh (Edinburgh), Low Birth weight Study (lbw), Nhanes III (nhanes3), Prostate Cancer study (pcs), and Umaru Impact Study datasets (uis). The genomic dataset is provided by the third task the iDASH competition 2017, which consists of 1579 records. Each record has 103 binary genotypes and binary phenotype indicating if the patient has cancer. The other five datasets all have a single binary dependent variable. Figures and show that except for the enhanced Adagrad method on the iDASH genomic dataset our enhanced methods all converge faster than their original ones in other cases.
189
171
173
Maximum Likelihood Estimation
100
400
-20
6000
Adaccal
Ealaccel Adagnd
Ashigrad
800
140
Adaarad
Eszaased Adgera
Enlunsed Askanal
0
10
20
30
10
20
30
10
20
30
lteration Number
lteration Number
Iteration Number
(a) The iDASH dataset
(b) The Edinburgh dataset
(c) The Ibw dataset
Maximum Likelilond Estimation
-104
0.5
200
300
300
400
-1.5
-300
-40
Arbegnal
Adagral
Adagrd
Instancd Adagra
Inbaanedd Adagmd
Enhunced Asiigaal
20
20
Tteration Number
Iteration Number
Iteration Number
(d) The nhanes3 dataset
The pes datasct
The uis datasct
Figure 1: Training results in the clear for Adagrad and Enhanced Adagrad
175
176
In all the Python experiments, the time to calculate the B quadratic gradient G before running the iterations and the time to run each iteration for various algorithms are negligible (few seconds).
177
4
Logistic Regression Training
179 Adagrad method is not practical solution for homomorphic LR due to frequent inversion operations. It seems plausible that the enhanced NAG is probably the best choice for privacy- preserving IRR training. We adopt the enhanced NAG method implement privacy-preserving logistic regression training. The difficulty in applying the quadratic gradient is to invert the diagonal
181
7

---

Maximum Likelibood Extimation
9000
100
950
400
110
1,000
120
-1,050
800
1,100
Erbaased NAG
Inttanced NAG
130
Entanced NAU
0
10
20
30
10
20
30
10
20
30
Iteration Number
Iteration Number
Iteration Number
(a) The iDASH dataset
(h) The Edinburgh dataset
(c) The lbw dataset
Maximum Likelihond Estimation
10
200
00.6
320
220
3-10
0.8
240
360
380
NAG
YAG
YAG Dakannod NAG:
Entoneed NAG
260
Unttoned NAG
400
20
Tteration Number
Tteration Number
Treration Number
(d) The nhanes3 dataset
The pes dataset
The uis dataset
Figure 2: Training results in the clear for NAG and Enhanced NAG
matrix B in order obtain B. We leave the computation of matrix B data owner and let the data owner upload the ciphertext encrypting the B to the cloud. Since data owner has to prepare the dataset and normalize
184
185
would also be practicable for the data owner calculate the B owing to no leaking of sensitive data information.
186
logistic regression training via homomorphic encryption technique faces difficult dilemma that no homomorphic schemes are capable of directly calculating the sigmoid function the LR model. A common solution is to replace the sigmoid function with polynomial approximation
188
190
by using the widely adopted least square method. We can call a function named " "polyfit (.) in the Python package Numpy to fit the polynomial in least-square sense. We adopt the degree [12] used the least square approach to approximate the sigmoid function over the domain [-8, 8): g(x) 0.5 0.19131 I 0.0045963
192
5 polynomial approximation g(x) by which Kim et al.
194
x + 0.0000412332. x
Given the training dataset X E [1*((+d)) and training label Y 1x adopt the same method that Kim et al. [12 used to encrypt the data matrix consisting of the training data combined with
196
training- information into single ciphertext ctz. The weight vector ((0) consisting of zeros and the diagnoal elements of B are copied times to form two matrices. The data owner then encrypt the
197
two matrices into two ciphertexts (t and ctg, respectively. The ciphertexts ctz, et and ct are follows:
199
Fi1
21
F1
1
321
32d
1/2
1/2
y2
y2or2
X
Y
,tz
Enc
Fnl
Fnd
Un
Yn
Und
((0)
(()
Bioloo
Buroo
50
Biolol
Bujm
Bidl
ct
Enn
.tg
Fnc
8
(()
Biolol
Bug
where BBI( is the diagonal element of B that is built from
x x.

---

The pulbic cloud takes the three ciphertexts et ety ) and ct and evaluates the enhanced NAG
algorithm to find decent weight vector by updating the vector ct (0) Refer to [2] for detailed description about how to calculate the gradient by HE programming.
205
We implement the enhanced NAG based on HE with the library HEAAN. The C++ source code publicly available at
Implementation
206
4open. science/r Dttaan/e///DSHH017--202 All the experiments on the ciphertexts were conducted on public cloud with 32 vCPUs and 64 GB RAM.
208
209
For fair comparison with 12]. we utilized the same 10-fold cross-validation (CV) technique on the same iDASH dataset consisting of 1579 samples with 18 features and the same 5-fold CV technique on the other five datasets, Like [2], We consider the average accuracy and the Area Under the Curve (AUC) as the main indicators. Tables and 2 show the two experiment results, respectively. The two tables also provide the average evaluation running time for each iteration. We adopt the same packing method that Kim al. [22 proposed and hence our solution has similar storage of ciphertexts to [2] with some extra ciphertexts to encrypt the B.
210
211
212
214
The parameters of HEAAN set same [2 log 16, logQ 1200, logp 30, slots
217
32768, which ensure the security level À = 80. Refer [12 for the details of these parameters. Since our enhanced NAG method need to consume more modulus to preserve the precision of B, use logp = 60 to encrypt the matrix B and thus only can perform iterations of the enhanced NAG method. Yet despite only 3 iterations, our enhanced NAG method still produces comparable result.
218
219
220
Table 1: Implementation Results for iDASH datasets with 10-fold CV
Learn Time
Sample Num
Feature Num
Iter Num
Accuracy (%)
Dataset
Method
deg
AUC
(min)
Ours
3
5.53
53.69
0.678
iDASH
1579
18
12
5
7
6.07
62.87
0.689
Table 2: Implementation Results for other datasets with S-fold CV
Learn
Sample Num
Feature Num
Iter Num
Accuracy (%)
Dataset
Method
deg g
Time (min)
AUC
Ours
84.4
0.853
Edinburgh
1253
9
112
7
3.6
91.04
0.958
Ours
0.5
69.19
0.619
lbw
189
12
3.3
69.19
0.689
Ours
3
5.5
79.23
0.490
nhanes3
15649
15
12
79.22
0.717
Ours
3
0.6
65.33
0.721
379
9
12
3.5
68.27
0.740
Ours
0.6
74.43
0.598
uis
575
8
12]
7
3.5
74.44
0.603
5
Conclusion
222
In this paper, we proposed faster gradient variant called quadratic gradient, and implemented the sundratic-gradienn version of NAG in the encrypted domain to train the logistic regression model.
224
The quadratic gradient presented this work can constructed from the Hessian matrix directly, and thus somehow integrates the second-order Newton's method and the first-order gradient (descent) method together. There is a good chance that quadratic gradient could accelerate other gradient methods such as RMSprop and Adam, which open future work.
226

---

References
228
229
[1] Allison, P. D. (2008). Convergence failures in logistic regression.
230
[2] Aono, Y., Hayashi, T., Trieu Phong, L., and Wang. L. (2016). Scalable and secure logistic regression via homomorphic encryption. In Proceedings of the Sixth ACM Conference Data and Application Security and Privacy, pages 142-144.
232
233
[3] Blatt, M., Gusev, A., Polyakov, Y., Rohloff, K., and Vaikuntanathan, V. (2019), Optimized homomorphic encryption solution for secure genome-wide association studies. IACR Cryptology ePrint Archive, 2019:223.
234
235
236
[4] Böhning, D. and Lindsay, B. G. (1988). Monotonicity of aupooxaicaap algorithms. Annals of the Institute of Statistical Mathematics, 40(4):641-663
237
238
[5] Bonte, C. and Vercauteren, F. (2018). Privacy-preserving logistic regression training. BMC medical genomics, 11(4):86.
[6] Chen, H., Gilad-Bachrace Bachrach, R., Han, K.,, Huang, Z., Jalali, A., Laine, K., and Lauter, K. (2018). Logistic regression over encrypted data from fully homomorphic encryption. BMC medical genomics, 11
241
[7] Cheon, J. H., Kim, A., Kim, M., and Song, Y. (2017). Homomorphie encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security, pages 409-437. Springer.
244
248
[8] Crawford, L.. Gentry, C., Halevi, S., Platt, D., and Shoup. V. (2018). Doing real work with fhe: the case of logistic regression. In Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 1-12.
247
248
249
[9] Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 169-178.
[10] Han, K., Hong, S., Cheon, J. H., and Park, D. (2019). Logistic regression homomorphic en- crypted data at scale. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 9466-99 6471.
252
[1I] Jäschke, A. and Armknecht, F. (2016). Accelerating homomorphic computations on rational numbers. In International Conference on Applied Cryptography and Network Security, pages 405-423. Springer.
255
256
257
[12] Kim, A.. Song, Y., Kim, M., Lee, K., and Cheon, J. H. (2018a). Logistic regression model training based on the approximate homomorphic encryption. BMC medical genomics, 1 1(4):83.
258
259
[13] Kim, M., Song, Y., Li, B., and Micciancio, D. (2019). Semi cemilllrallll logistic regression for gwas on enerypted data. IACR Cryptology ePrint Archive, 2019:294.
260
261
[14] Kim, M., Song, Y., Wang. S., Xia, Y., and Jiang, X. (2018b). Secure logistic regression based on homomorphic encryption: Design and evaluation. JMIR medical informatics, 6(2):e19.
[15] Murphy, K. P. (2012). Machine learning: a probabilistic perspective. The MIT Press, Cam- bridge, MA.
264
Checklist
285
286
1. For all authors...
287
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
270
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
271
(d) Have you read the ethics review guidelines and ensured that your paper conforms to
them? [Yes]
10

---

273
2. If you are including theoretical results...
274
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
275
(b) Did you include complete proofs of all theoretical results? [Yes]
278
3. If you ran experiments..
277
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL.?? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
280
281
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
282
283
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
285
4. If you are using existing assets (e.g., code, data, models) or curating/releasngg new assets...
286
(a) If your work uses existing assets, did you cite the creators? [Yes]
287
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent obtained from people whose data you'n using/curating? [Yes]
290
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
292
293
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [Yes]
295
296
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [Yes]
297
296
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [Yes]
A Appendix
301
Optionally include extra information (complete proofs, additional experiments and plots) in the appendix. This section will often be part of the supplemental material.


Reviews:
[{"review_id": "xYCAg_QDrO", "reviewer": "Reviewer_o6pq", "summary": "This study suggests an enhanced gradient method on logistic regression with homomorphic encryption (HE)\nThe contents of the paper generally follows (Kim et al., 2018), so for who read the paper the contents are familiar.\nThe others modified existing algorithm by replacing learning rate with quadratic gradient, which is a variant of simplified fixed Hessian.\nExperimental results show that the proposed method converges better than existing method in (Kim et al., 2018).", "questions": "1. Parameter setting is an important issue when using HE, because parameter search is extremely unfriendly with HE. In algorithm 1, the authors set $\\alpha_{t+1}=(1+\\sqrt{1+4\\alpha_{t}^2})/2$, which is different to the setting in (Kim et al., 2018), which is $\\alpha_t=10/(t+1)$. Can the parameter choice be justified?\n\n2. In the experiments, iDash dataset showed different results than other datasets. Can it be explained?\n\n3. Can the results with $\\lambda=128$ be given?\n\n4. In table 2, the auc score of Ours on nhanes3 is too low. Is it a typo?", "limitations": "The authors have not address the limitations of their work. Because the study is about privacy-preserving logistic regression, it seems to have a positive societal impact.\n\nAs mentioned above, the biggest limitation of their work is that there is no significant improvement compared to the existing methods.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- In table 2, It is empirically shown that the proposed method can achieve similar accuracy compared to (Kim et al., 2018) with much less computation time. (the ratio of the computation time is bigger than 7/3 for most datasets, which seems because bigger $logq=60$ was used for the proposed method)\n- By transferring the role of computing $\\tilde{B}$ to the data owner, the proposed method does not require more multiplicative depth compared to (Kim et al., 2018).\n- The paper seems clear and easy to follow.\n\nWeaknesses\n- The novelty seems rather shallow; (Kim et al., 2020) has already proposed an approximate Hessian which is very similar to quadratic gradient method. The authors should check the paper.\n- Algorithm 1 seems rather meaningless. The algorithm should incorporate operations on ciphertexts, which deal with ciphertext packing.\n\n(Kim et al., 2020)  Kim, M., Lee, J., Ohno-Machado, L., & Jiang, X. (2019). Secure and differentially private logistic regression for horizontally distributed data. IEEE Transactions on Information Forensics and Security, 15, 695-710.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nhmDJPyvy6S", "reviewer": "Reviewer_mJWs", "summary": "This paper studied the problem of privacy-preserving logistic training on encrypted data. The quadratic gradient is proposed to implement logistic regression training in the homomorphic encryption domain. The proposed method can be seen as an extension of the simplified fixed Hessian and an enhancement of the Adaptive Gradient Algorithm (Adagrad). The implemented homomorphic logistic regression training obtains a comparable result by only 3 iterations.", "questions": "-", "limitations": "-", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThis paper studies an important problem. Privacy-preserving logistic regression training is one popular method to protect the training data privacy, especially when logistic regression is ubiquitous in the real world.\nThe paper provides extensive experimental details and implemented codes that are helpful for reproducibility. \n\nWeakness:\n\nThe writing is not clear to distinguish between the proposed methods and previous methods. Most of section 3 are previous works, instead of proposed methods. For example, section 3.1 about the Simplified Fixed Hessian method is actually from previous works. It is better to write it in a background section. Section 3.2 seems to be the proposed method. Thus, it should be highlighted and clarified using diagrams, and clear descriptions. More importantly, it is not clear to know the motivation why the authors propose a quadratic gradient. What are the observations and insights that we have to using quadratic gradient? \n\nTypos: for example: lines 183-184. Ower-->owner\n\nMore comparisons are needed. Although the authors mentioned [1], it is required to have a result comparison with [1] since the techniques are applicable to logistic regression training. It is also better to compare with [2]. \n\nThe results are not robust or generalized. For example, the enhanced method in the iDash dataset of figure 1 is not robust and may be worse than the baseline method. It would be better to explain more about the reason. Otherwise, it may show that the proposed method is not generalized to other datasets. Also, in table 2, the proposed method has worse accuracy than the baseline method on the Edinburgh dataset.  \n\n[1] Han, K., Hong, S., Cheon, J., & Park, D. (2019). Logistic regression on homomorphic encrypted data at scale. In Proceedings of the AAAI conference on artificial intelligence (pp. 9466–9471).\n\n[2] Bergamaschi, F., Halevi, S., Halevi, T., & Hunt, H. (2019). Homomorphic training of 30,000 logistic regression models. In International Conference on Applied Cryptography and Network Security (pp. 592–611).\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RaHZt0fJwxF", "reviewer": "Reviewer_2fQY", "summary": "This paper presents a faster gradient variant to implement logistic regression training in a homomorphic encryption domain. The results show the new optimization method could speed up the convergence of training on small datasets.", "questions": "1. In Figure 1(a), why the convergence speed of Enhanced Adagrad is worse than the raw Adagrad?\n2. I am curious about the consumption of memory in the HE domain, it will be better if the authors include a comparison between the proposed method and the baseline method.\n3. I like the idea of the second-order optimization and wonder whether the SFH method could be applied to more general NNs like CNN, LSTM or Transformer?\n", "limitations": "Yes, the authors have included the limitations in line 119, which includes (a) the numerical condition of the SFH method and (b) the singular problem for some high-dimensional sparse matrix datasets.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. This paper is well-written and clearly organized, including sufficient theoretic analysis of the proposed Simplified Fixed Hessian method. I like such a solid line of work.\n2. The targeted topic – privacy-preserving domain of logistic regression is very promising and deserves insightful hard work to resolve the application of homomorphic encryption.\n3. The results of convergence speed are clear and convincing.\n\nWeakness:\n1. The experiments are somewhat not enough, considering the lack of experimental support for the claim in line 44 “without compromising much on computation and storage.” It will be better if a detailed comparison of computation and storage is presented.\n2. The algorithm may lack of generalization to some large-scale datasets, considering the calculation of $\\bar{\\math{B}}$ needs to walk through the whole dataset, which is quite resource-hungry\n3. Lack of further analysis of the results of the experiment, such as in Figure 1(a), why the convergence speed of Enhanced Adagrad is worse than the raw Adagrad.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject