Privacy-Preserving Logistic Regression Training with A Faster Gradient Variant

Summary

This paper proposes a second-order version of Nesterov's accelerated gradient (NAG) descent and Adagrad for logistic regression by incorporating an approximation to the Hessian. The authors call this the "quadratic gradient". Specifically, a diagonal approximation to the Hessian for logistic regression is proposed. Some empirical results are shown to illustrate the benefit of the proposed method over vanilla NAG and Adagrad.

Strengths

The proposed approximation of the diagonal Hessian may be interesting for NAG.

Weaknesses

Unfortunately, this paper has several weaknesses. **1.** **Limited novelty**: The proposed approximation to the Hessian in Section 3.2 seems like a trivial and incremental extension of the idea of reference [4] discussed in Section 3.1. **2.** **Lack of clarity**: The proposed methods are unclear to me and the presentation needs to be heavily improved. * The enhanced NAG method described in line 150 is unclear to me -- what is $G$ here and is $\alpha_t$ the step-size here? Moreover, Algorithm 1 seems different from the discussions in Section 3.3. What are $\alpha_0$ and $\alpha_1$? They don't look like the quantity $\alpha_t$ introduced in Section 3.3. Why is $\alpha_1$ chosen to be $0.5(1 + \sqrt{1 + 4 \alpha_0^2})$? I don’t understand lines 31 and 37 in Algorithm 1 and what are $\gamma$ and $\eta$ here? What is the role of $W$ in lines 34 and 35 – it is not being used at all. In summary, the enhanced NAG method/Algorithm 1 has been presented poorly and I don't understand the method at all. * What is the enhanced Adagrad algorithm? The two equations after line 154 which are supposed to explain the enhancement are not very clear. What is the difference between $G^{(t)}$ and $g^{(t)}$ in these equations? Is $G = \tilde{B}^{-1} g$ here? There is no algorithm summarizing it like Algorithm 1 for enhanced NAG. Also, suddenly for Adagrad, the authors have a negative sign in front of the gradient which corresponds to minimizing the function whereas for NAG and the previous discussions in the paper, maximizing the function has been considered. Please stick to either minimization or maximization for consistency. **3.** **Premise of enhanced Adagrad:** One way to interpret Adagrad is that it tries to maintain a diagonal approximation of the Hessian inverse and applies it to the gradients (a.k.a. preconditioning). So I'm not sure why applying a second approximation of the Hessian inverse on the *already preconditioned* gradients makes sense intuitively. Additionally, the authors themselves point out that enhanced Adagrad cannot be applied to general optimization problems (line 182) due to "learning-rate explosion". Then why introduce this method at all? **4.** **Setup and experiments**: The datasets on which experiments are performed are not standard benchmarking datasets in the ML community and appear to have very few features (looking at Table 2). There are no test set statistics provided. I'd be more convinced if the authors showed empirical results in a *standard logistic regression setup without any kind of encryption* (which frankly seems irrelevant to me in this paper) on benchmarking ML datasets. ---- *Some general comments*: The introduction on logistic regression can be compressed. It is standard to consider the *negative* log-likelihood objective and apply gradient *descent* to minimize it. A couple of small typos -- in line 96, I guess it should be "$\bar{h}_{k i}$ is the $k^\text{th}$ element in the $i^\text{th}$ row of the Hessian" and in line 216, it should be "public".

Questions

Please see the Weaknesses.

Rating

2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

1 poor

Presentation

1 poor

Contribution

1 poor

Limitations

Not in too much detail but as I mentioned in Weaknesses, the authors point out that enhanced Adagrad cannot be applied to general optimization problems. No foreseeable negative societal impact.

Summary

This paper proposed a new approach to improve the gradient used by first-order optimization methods in logistic regression by utilizing a constant bound to the Hessian matrix. The authors demonstrate how to use their method under a fully Homomorphic-Encryption scenario. They test their method on many real-world datasets under non-private settings and Homomorphic-Encryption settings.

Strengths

1. The paper is written clearly. 2. The experiments are all using real-world datasets which have strong practical implications.

Weaknesses

1. The `quadratic gradient` method is not very new. As the authors have mentioned in Section 3.1 (Line 95), most parts of the method were proposed by Bonte and Vercauteren. I understand that the missing non-negative restriction is important for using the convergence results by Böhning and Lindsay (Line 92). However, using the absolute value is rather an straightforward solution. * A more interesting and critical question remaining to be answered is why this proposed `quadratic gradient` method is faster as the authors claimed in the conclusion (Line 238). * Another problem with this method is its usage being restricted in logistic regression: The authors provided a choice of $\bar{H}$ for logistic regression, while it may be very hard to generalize it to other problems, especially neural network training. 2. The experiments have not shown much advantage of using the `quadratic gradient` method. In Table 1 and Table 2, the accuracy and AUC of the proposed method are almost always lower than the compared baseline method [12]. I understand that the learning time is reduced, but it was not a main problem in [12] as shown in the tables, and we are not sure if there is a tradeoff between the learning time and the accuracy. * The description of the experiment details in Section 5 is very short. The authors suggest the readers refer to [12]. I think it would be better to have the details in supplementary and a discussion of the weaknesses of [12] in these experiment settings, along with why the proposed method solves those weaknesses. Minor weaknesses: 1. The maximum likelihood estimation (MLE) is commonly referring to the estimate for $\beta$. The value of the loss function is the negative log-likelihood. That said, the y-axis of the figures could be corrected. Also, the objective function is usually the mean of the loss for each data point, not the sum. 2. Typo: Line 216, pulbic -> public. --- I have read the rebuttal which answered my questions but did not fully address my concerns on the weakness.

Questions

1. The cited paper [7] also used `quadratic gradient`. Is it a following up paper to this paper? If yes, it is better to have a dedicated discussion of the relationship between this paper and [7], e.g. about the difference and the novelty.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

1 poor

Limitations

N.A.

Summary

This paper proposes the quadratic gradient for privacy-preserving logistic regression. Such gradient is used together with Nesterov’s accelerated gradient (NAG) and Adagrad on Homomorphic Encryption techniques.

Strengths

This paper tackles the privacy-preserving (in the sense of encryption) logistic regression. The paper is clear with introduction and motivation. The algorithm is easy-to-follow and well-supported by experiments.

Weaknesses

Overall, it is hard to understand the privacy concerns in this work as there are many privacy-preserving techniques available. Without an example or experiment of privacy attack, the motivation of using HE in the first place is not backed up. In addition, only [12] is compared in the empirical results. While the new method seems promising, the lack of other baselines makes it hard to understand the limitations and benefits of the new algorithm.

Questions

See weakness.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

NA.

Summary

The paper proposes a new gradient method that can be efficiently used under homomorphic encryption. The proposed method replaces the gradient $g$ by an approximation of $H^{-1}g$, where $H$ is the Hessian. This approximation is done using a specific diagonal matrix, that speeds up convergence while being possible to use under homomorphic encryption.

Strengths

1. The paper proposes a new method for privacy-preserving logistic regression under FHE, that achieves reasonable results with less computation than existing methods. 2. The proposed method is quite versatile as it can be applied to a variety of optimization algorithms.

Weaknesses

1. Experimental results are not convincing. Contrary to the paper's claims, the proposed method often performs way worse than existing ones (especially on iDASH, Edunburgh and pcs). Datasets are also very small, and therefore do not account for how the method scales with the dimension. Given this is an empirical paper, it seems a bit insufficient. 2. The fixed-Hessian method seems to be closer to preconditioning (see e.g. [1]), where gradients are linearly transformed before being used, than to a proper second order method. 3. The proposed method does not seem to be too novel. In particular, the paper refers to [2] (which itself refers to a paper with the same title as this manuscript), which proposes a very similar method. [1] Preconditioned Stochastic Gradient Descent, Xi-Lin Li 2015. [2] Quadratic Gradient: Uniting gradient algorithm and newton method as one, by Chiang, 2022.

Questions

1. Are there settings where the difference in runtime between the proposed method and existing ones is more significant? What would cause this difference to get larger? 2. When normalizing the data, this has an impact on the Hessian matrix (and therefore on $\bar B$). In particular, one could imagine that after normalization, $X^T X$ is close to the identity. Could you comment on the effect of normalization on $\bar B$? 3. Line 108, it is claimed that with proper learning rate, the fixed Hessian Netwon method converges: can you give evidence/proof to support this claim?

Rating

2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

1 poor

Limitations

Limitations are not discussed in the paper. In particular, experiments only consider a specific setting, with a choice of parameters that seems arbitrary (e.g., 3 vs. 7 iterations), and some claims are not supported with evidence.

Thank you for the response!

A1: Got it. A2: If I understand your statement correctly, this 'faster' claim is from the intuition that NAG, Adagrad, or Adam should be faster than the vanilla SGD. I think some theoretical analysis would help support this claim. A3: Yes. Therefore, I wanted to say that this paper as an extension of the simplified fixed Hessian is restricted to the logistic regression setting. A4: Yes. Usually, the baseline is for the comparison between the best possible performance of the previous method, and the best of your method. You are free to choose the hyperparameter to demonstrate various aspects of advantage in your method. Based on my comments above, I will keep my score at 3.

Reply

Thanks for the rebuttal. I have read it and would like to keep my score. My question about limited novelty has not been addressed though.