Non-asymptotic Analysis of Stochastic Gradient Descent under Local Differential Privacy Guarantee

Thank you for the constructive feedback, which has been very helpful in enhancing the quality of our paper. We respond below to your questions and concerns:

W1: Acknowledging the complexity of the theoretical expressions in our work, we appreciate the reviewer's observation regarding their intricacy for those less familiar with the field. The task of non-asymptotic analysis is notably challenging, particularly when it comes to deriving tractable theoretical results from complex estimation bounds. Such complexity often renders these results difficult to comprehend, especially in understanding the convergence behavior of estimators. Our work, however, provides a clear and accurate bound for the estimation process. It elucidates key aspects: the predominant rate of convergence, the diminishing influence of initial conditions, and how various factors—like dimensionality and the privacy budget—affect the theoretical bounds. This clarity in our results sheds significant light on areas previously obscured by complexity. To facilitate understanding, we have included detailed explanatory remarks. In response to the feedback, we will further simplify these expressions in the revised version to enhance accessibility for our readers. For a more comprehensive overview, we add Table 1 in our revised version to summarize our results. This table will detail the leading convergence rates for each specific situation addressed in our research, offering a more comprehensive understanding of our contributions in comparison to existing work.

W2: We appreciate the reviewer's concerns and apologize for any confusion our work may have caused. Indeed, there is a notable difference in how quickly initial conditions diminish in two scenarios: the averaged version and the last step estimation, particularly with smaller step sizes. As outlined in Remark 1 and Remark 2, the averaged version tends to 'forget' these initial values at a slower rate compared to the last step estimation. For a more comprehensive understanding of the differences in the convergence rate between these two methods, we direct readers to the detailed results and discussion in Paragraph 1 on Page 9 of our report. Please also see Table 1 for the summary of convergence rate in different situations.

W3: Thank you for your feedback. Our choice to utilize linear and logistic regression models is grounded in their widespread use and representativeness in regression and classification problems, respectively. These models also exemplify the two categories of loss functions our paper explores: strongly convex and non-strongly convex. Furthermore, we have conducted simulations with higher-dimensional data, the details of which are available in the supplementary materials.

W4: Intuitively, our procedure involves introducing a noise term with a zero mean in each iteration. This addition leads to considerable variance when considering the last step as our estimator. However, by employing an averaging technique, we significantly reduce the variance induced by this noise. As a result, this averaging approach not only stabilizes our estimator but also endows it with a smaller variance.

Q1: We thank the reviewer for reading our paper carefully. Actually, Condition 3 is not used in the proof of Theorem 3. In this revision, we have corrected it.

Q2: We feel sorry for the misleading notation here. To clarify, the initial conditions referred to are fixed numbers.

Q3: These constants are associated with the loss function, as detailed in the supplementary material on Page 4, Paragraph 2. We aim to present our results in a more simplified manner in the revised version.

Q4: In practice, according to Section 2.4 in [1], we know $f$-DP is a generalization of $(\varepsilon, \delta)$-DP. Therefore, this result can be easily extended to the regular DP. Meanwhile, within the context of an online setting, we utilize the parallel composition approach rather than relying on the composition property of the GDP. In this case, incorporating the classical definition of LDP seems more appropriate. Theoretically, it’s possible to extend noise distribution beyond Gaussian noise by imposing the assumptions on the boundedness of noise moments when considering the general LDP. In our revised version, we are committed to thoroughly integrating classical LDP notation alongside GDP.

[1] Dong, Jinshuo, Aaron Roth, and Weijie J. Su. "Gaussian differential privacy." Journal of the Royal Statistical Society Series B: Statistical Methodology 84.1 (2022): 3-37.

Thank you for the constructive feedback, which has been very helpful in enhancing the quality of our paper. We respond below to your questions and concerns:

W1 & Q1: Thank you for your insights on the use of GDP over classical DP in our work. We recognize that classical DP is indeed a more general framework. As outlined in Section 2.4 of [1], $f$-DP, which includes GDP, is an extension of $(\varepsilon, \delta)$-DP, allowing us to easily extend our results to classical DP scenarios. It is theoretically feasible to expand our analysis to include noise distributions beyond Gaussian, which forms our ongoing research.

Our choice of GDP in this work is driven by two main factors. Firstly, there is a growing interest in GDP, with numerous algorithms proposed that lack theoretical convergence guarantees. Our work aims to bridge this gap, providing a foundation for non-asymptotic analysis of these algorithms. Secondly, GDP demonstrates advantageous theoretical properties in asymptotic analysis, as detailed in [2], prompting us to offer a comprehensive non-asymptotic analysis for GDP in advance. In conclusion, while classical DP offers a broader context, our focus on GDP is intentional, aligning with the specific aims and scope of our current paper.

W2: In our technical details of online SGD algorithm, we recognize that specialists in the field might note the structural similarities in proofs across various studies. Such similarities often stem from the use of standard methods and tools within the discipline. Specifically, in our convergence analysis of DP-SGD estimator, the proof structure mirrors that of non-private versions, a similarity we only discerned after completing our analysis. This resemblance arises from the inherent recursive nature of the SGD algorithm.

Also, we wish to clarify that our work does not claim to introduce novel proof techniques. Instead, our significant contribution lies in adeptly applying established methodologies from the extensive literature to tackle the new and distinct challenges presented by online LDP problems. Our focus is on solving these novel problems using existing tools, rather than on the novelty of the proof techniques themselves. Indeed, the non-asymptotic analysis of online LDP is inherently challenging, and achieving tractable theoretical results was not feasible until we developed these theorems.

Q2: In our exploration of the theoretical outcomes when $\alpha=1$, we found that the convergence of the algorithm hinges on specific conditions. These are determined through mathematical derivation and involve factors such as the correlation between the eigenvalues of the loss function's Hessian matrix and the initial step size. Additionally, our simulation studies highlight that these conditions often go unmet in practical scenarios, leading to situations where convergence is not guaranteed.

This distinctive behavior in convergence under the condition $\alpha=1$ for private versus non-private cases further underscores an important aspect of our work. It demonstrates that even though the structures and tools of the proofs may be similar, the outcomes in private settings, as opposed to non-private ones, can differ significantly. This distinction not only highlights the uniqueness of our results but also reinforces the value of our contribution in extending non-asymptotic analysis to the private version of the online SGD algorithm.

[1] Dong, Jinshuo, Aaron Roth, and Weijie J. Su. "Gaussian differential privacy." Journal of the Royal Statistical Society Series B: Statistical Methodology 84.1 (2022): 3-37.

[2] Avella-Medina, Marco, Casey Bradshaw, and Po-Ling Loh. "Differentially private inference via noisy optimization." arXiv preprint arXiv:2103.11003 (2021).

We appreciate the reviewer's constructive suggestion.

W1: We agree with the reviewer on the importance of a lower bound in evaluating and understanding the estimator's behavior. However, the task of establishing a lower bound for parameter estimation in our specific context, and similar ones, is exceptionally challenging and remains an unresolved issue in the field. To our knowledge, there exists a substantial gap in the literature and available methodologies that directly address this challenge. Also, the existing literature [1, 2] conducting non-asymptotic analysis only provide upper bounds, which indirectly highlights the inherent challenges associated with establishing a lower bound.

Indeed, theoretical analysis in the field of LDP algorithms, particularly in terms of their convergence, is generally sparse. Our study distinguishes itself from existing studies in LDP, which primarily concentrates on the development of algorithms that achieve set privacy benchmarks, but often overlooks their convergence behaviors. In contrast, our study makes a significant contribution by not only examining but also quantifying the rate and manner in which these DP algorithms approach optimal solutions. This marks a significant leap forward in the realm of DP.

W2: We thank the reviewer for providing additional work focusing on LDP. However, the papers you referenced address different contexts within the field of local differential privacy. For instance, 'Local differential privacy for data collection and analysis' focuses on mean estimation, contrasting with the general parameter estimation issue our study addresses. Similarly, 'Fedsel: Federated SGD under local differential privacy with top-k dimension selection' considers private dimension selection mechanisms and adapts the gradient accumulation technique to stabilize the learning process with noisy updates within a distributed framework, while our work is framed in an online parameter estimation context under LDP. Considering these different scenarios, making direct comparisons within a uniform framework or situation is difficult. Nonetheless, for a more lucid comparison, we have introduced a table in our revision. This table details the leading convergence rates for each specific situation addressed in our study, offering a more comprehensive understanding of our contributions in comparison to existing work.

W3: In our technical details of online SGD algorithm, we recognize that specialists in the field might note the structural similarities in proofs across various studies. Such similarities often stem from the use of standard methods and tools within the discipline. Specifically, in our convergence analysis of DP-SGD estimator, the proof structure mirrors that of non-private versions, a similarity we only discerned after completing our analysis. This resemblance arises from the inherent recursive nature of the SGD algorithm.

Also, we wish to clarify that our work does not claim to introduce novel proof techniques. Instead, our significant contribution lies in adeptly applying established methodologies from the extensive literature to tackle the new and distinct challenges presented by online LDP problems. Our focus is on solving these novel problems using existing tools, rather than on the novelty of the proof techniques themselves. Indeed, the non-asymptotic analysis of online LDP is inherently challenging, and achieving tractable theoretical results was not feasible until we developed these theorems.

Finally, in our exploration of the theoretical outcomes when $\alpha=1$, we found that the convergence of the algorithm hinges on specific conditions, which is different from the non-private cases. It demonstrates that even though the structures and tools of the proofs may be similar, the outcomes in private settings, as opposed to non-private ones, can differ significantly. This distinction not only highlights the uniqueness of our results but also reinforces the value of our contribution in extending non-asymptotic analysis to the private version of the online SGD algorithm.

W4: We express our sincere gratitude to the reviewer for identifying the editing error in the cross-reference links. Our main emphasis has been on the thorough derivation of theoretical results to ensure their accuracy. We acknowledge the importance of clear and precise presentation and commit to improving this aspect in the final manuscript.

We thank the Reviewer for the constructive comment. First, we want to clarify that "guiding practitioners in hyperparameter selection" is not the motivation of our work, although the theorems we presented can address this issue. Actually, the aim of this paper is to study the non-asymptotic bounds of Differentially Private Stochastic Gradient Descent (DP-SGD) estimator as well as its variants under local differential privacy in finite samples. The main motivations of our paper are twofold.

1. Bound for finite sample: Unlike traditional asymptotic analysis, in which bound is only valid for a sample size exceeding a certain rank. In contrast, our non-asymptotic bound is valid for each finite sample size, which makes it more relevant for practitioners seeking to understand parameter convergence. Meanwhile, examining the behavior of finite samples is an important task [1, 2, 3], as sample sizes in practical problems are always finite. Usually, obtaining such results requires more mathematical effort than merely obtaining asymptotic results and typically, this involves more restrictive assumptions.
2. In-depth exploration of convergence rate: Also, our study focuses on providing precise bounds and convergence rates of DP-SGD estimators to the optimum in finite samples. Unlike existing studies in local differential privacy, which primarily focus on developing algorithms that satisfy expected privacy guarantees but often overlook their convergence properties and rates, our study addresses this shortfall and fills this gap. We delve into how these algorithms converge to the optimum and, importantly, the speed at which this convergence occurs, providing a more comprehensive understanding of their performance.

Acknowledging the complexity of the theoretical expressions in our work, we appreciate the reviewer's observation regarding their intricacy for those less familiar with the field. The task of non-asymptotic analysis is notably challenging, particularly when it comes to deriving tractable theoretical results from complex estimation bounds. Such complexity often renders these results difficult to comprehend, especially in understanding the convergence behavior of estimators. Our work, however, provides a clear and accurate bound for the estimation process. It elucidates key aspects: the predominant rate of convergence, the diminishing influence of initial conditions, and how various factors—like dimensionality and the privacy budget—affect the theoretical bounds. This clarity in our results sheds significant light on areas previously obscured by complexity. To facilitate understanding, we have included detailed explanatory remarks. In response to the feedback, we will further simplify these expressions in the revised version to enhance accessibility for our readers. For a more comprehensive overview, we add Table 1 in our revised version to summarize our results. This table will detail the leading convergence rates for each specific situation addressed in our research, offering a more comprehensive understanding of our contributions in comparison to existing work.

We sincerely accept the reviewer's criticism of the Hessian matrix Condition. Actually, the requirements on the Hessian matrix are commonly used in analyzing the convergence of SGD’s algorithm; see [4]. We note that it is easy to verify this Condition holds for the two classical examples: quadratic loss and logistic loss. Indeed, this condition can be relaxed by imposing some assumptions regarding on the martingale difference $\xi_n = \nabla F({\theta}_{i-1}) - \nabla f({\theta}_{i-1},x_i)$, as outlined in Assumption 3.2 by [4], which we are working on it. Moreover, this condition underscores the difficulty in obtaining non-asymptotic results, thereby reinforcing the significance of our contribution.

Finally, we are grateful to the reviewer for pointing out the editing error of the cross-reference links. While we regret any confusion caused, we believe this does not reflect a lack of diligence on our work. Our primary focus has been on the meticulous derivation of theoretical results, ensuring their correctness. Consequently, we think the compiling error should not undermine the significant contribution of our work.

[1] Korba, Anna, et al. "A non-asymptotic analysis for Stein variational gradient descent." Advances in Neural Information Processing Systems 33 (2020): 4672-4682.

[2] Zhou, Lijia, et al. "A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models." Advances in Neural Information Processing Systems 35 (2022): 21286-21299.

[3] Chen, Sitan, Giannis Daras, and Alex Dimakis. "Restoration-degradation beyond linear diffusions: A non-asymptotic analysis for ddim-type samplers." International Conference on Machine Learning. PMLR, 2023.

[4] Chen, Xi, et al. "Statistical inference for model parameters in stochastic gradient descent." Annals of Statistics 48.1 (2020): 251-273.