Single SMPC Invocation DPHelmet: Differentially Private Distributed Learning on a Large Scale
Authors: Moritz Kirschte
Sebastian Meiser
Saman Ardalan
Esfandiar Mohammadi
Venue: Submitted to ICLR 2023 (2023)
Keywords: differential privacy
distributed learning
privacy-preserving machine learning
privacy
federated learning

Abstract: Distributing machine learning predictors enables the collection of large-scale datasets while leaving sensitive raw data at trustworthy sites. We introduce a learning technique that is scalable to a large number of users, satisfies Differential Privacy, and is applicable to non-trivial tasks, such as CIFAR-10. For a large number of participants, communication cost is one of the main challenges. We achieve a low communication cost by requiring only a single invocation of an efficient secure multiparty summation protocol. By relying on state-of-the-art feature extractors, we are able to utilize differentially private convex learners for non-trivial tasks such as CIFAR-10. Convex learners have proven to have a strong utility-private tradeoff. Our experimental results show that for $1{,}000$ users with $50$ data points each, our scheme outperforms state-of-the-art scalable distributed learning methods (differentially private federated learning, short DP-FL) while requiring around $500$ times fewer communication costs: For CIFAR-10, we achieve a classification accuracy of $67.3\,\%$ for an $\varepsilon = 0.59$ while DP-FL achieves $57.6\,\%$. We also show the learnability properties convergence and uniform stability.

SINGLE SMPC INVOCATION DPHELMET: DIFFERENTIALLY PRIVATE DISTRIBUTED LEARNING ON A LARGE SCALE
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce a distributing differentially private machine learning training protocol that locally trains support vector machines (SVMs) and computes their averages using a single invocation of secure summation protocol. With state-of-the-ane secure summation protocols and using a strong foundation model such as SimCLR, this approach scales to a large number of users and is applicable to non-trivial tasks, such as CIFAR-10. 10. Our experimental results illustrate that for 1,000 users with 50 data points each, our scheme outperforms offteoofthh--ee art scalable distributed learning methods (differentially private federated learning, short DP-FL) while requiring around 500 times fewer communication costs: For CIFAR-10, a classification accuracy 79.7 % for an E 0.59 while DP-FL achieves 57.6 %. More generally, we prove learnability properties for the average of such locally trained models: convergence and uniform stability. By only requiring strongly convex, smooth, and Lipschitz-conntinour objective functions, locally trained via stochastic gradient descent (SGD), we achieve strong utility- trade-off.
achieve
INTRODUCTION
Scalable distributed ranging from medical institutions that want to learn from distributed patient data, over edge Al health applications, to decentralized recommendation systems. Preserving each person's 'ssoossssss privacy during distributed learning raises two challenges: (1) during the distributed learning process the inputs of all parties have to be protected and (2) the resulting model itself should not leak information about the contribution of any person to the training data. To tackle (1), secure multi-party computation protocols (SMPC) can protect data during distributed computation. To tackle (2), differentially private (DP) mechanisms provide guarantees for using or releasing the model in a mrivacy-preserve
machine learning methods have plethora of applications,
manner.
The literature contains rich body of work on this kind of privacy preseeriigeeiinggg distributed machine learning (PPDML) which is frequently evaluated with respect to scalability with the number of users who participate in the distributed learning, expressivity of the learning method with the goal of encompassing complex learning tasks, and good utility-privacy trade-off without a significant loss in accuracy for protecting each person's data, optimally the same utility-privacy trade-off' the centralized training scheme while only adding little communication overhead.
Jayaraman al. (208)) introduced theoretic result where the model optimum is noised (output perturbation). Here, each of the n users locally trains a convex empirical risk minimization (ERM) model on m data points and contributes the parameters of this model, carefully noised to a single invoked SMPC step, resulting in averaged differentially private model. This approach achieves DP (Chaudhuri et al., (201T), requires as little noise as the centralized setting (1/m/)) )), and incurs little communication overhead, with one SMPC invocation. However, they untight utility bounds Pathak ct al. (2010) that scale with the number of local data points (O(1/m) and not with the combined number of data points across all users (O(+/mm)).
Jayaraman et al. 2018) prove strong utility bounds with another scheme, the gradient perturbation: each user contributed the gradients of each local training iteration carefully noised to single invoked SMPC step which results in an averaged differentially private gradient step. This construction adds little noise centralized training (O(1/mm) and achieves strong utility bounds which scale with

---

the number of data points across all users (O(+/mm)) However, it has considerable communication overhead since it requires one SMPC invocation per training iteration.
Federated learning (McMahan et al. 2017) with DP-SGD approximation (Abadi et al. 2016) (DP- FL) constitutes another line of research with moderate utility bounds and moderate communication overhead. In DP-FL., untrusted aggregator combines the gradient updates from each user, while each user satisfies DP. DP-FL. does not require SMPC for similar security guarantees but needs #triiiiigggtteee communication rounds. The utility bounds comparatively high since the noise scales with (m))a.) Appx. C discusses related work in more detail.
Concerning expressivity, Abadi et al. (2066;; Tramer & Boneh (021): )) De et al. (2022) have shown that pre-trained models can improve the performance of a differentially private machine learning method (DP-SGD) for non-trivial tasks (e.g.. CIFAR-10). While such models require sufficient public data, they exist and provide simplifying representations for various domains: SimCLR for pictures, Facenet for portrait pictures, UNet for medical segmentation imagery, or GPT-3 for natural language.
Yet, this prior work does not excel at all three metrics simultaneously: scalability, expressivity, and utility-privacy trade-off. This places an inherent disadvantage when comparing current distributed training processes to centralized training process.
Contributions. Our Secure Distributed DP-Helmer work extends on prior work (Jayaraman et al., 2018) such that it is scalable, expressive, and has a good utility-privacyy trade-off. (Table compares our approach with Jayaraman et al. (2018)'s approaches and DP-FL. In summary, we make two tangible contributions:
For SGD-based strongly convex ERM, we prove a tighter utility bound which essentially states that we only need the average of locally trained models, e.g. support vector machines (SVMs) or logistic regression (LR), to converge to the optimal centrally trained model with rate Ol1M) M)) for .M iterations (cf. Thm. 21). We also show train-test generalization by proving uniform stability which states that averaging our models linearly improves the stability bound (cf. TThm. 19).
Cor. 10 we show how with enough data, guarantees as in local DP can be achieved, even without assumptions on the training algorithm beyond norm-bounde parameter space: protect the entire input of a user while achieving strong utility bounds (> 80% test accuracy for CIFAR-10).
OVERVIEW
inforens via pre trained feonure extractuc (SimCL.))
with leaming algorithm (egt., SVM)
simplified representation D2
noisy model(s) T(D,, & (
User
local data
with leorning algoritm (e.g. SVM)
pre tmined feature extmanor (SimULIt)
simplified representation D2
noisy model(s) Mr T(D & +
User 2
socune
modelts)
summation
M
pre-trained fraturo extrattor (SimCLX)
learning algoritm (eg. SVM)
simplified reprosenttion D,
nuisy model(s) T(D & +)+ (C
User
local data
Figure 1: Schematic overview of Secure Distributed De-Helmet. Each user locally extracts simplified data representation via a pre-training feature extractor (SimCLR), then trains a model, e.g. an SVM, via learning algorithm T, and finally contributes model which carefully noised with spherical Σ- P-raameterized Gaussian to single invoked secure summation step which results in an averaged and (e, DD model. & denotes some hyperparameters and K a set of classes.
Systems overview. preserving training on sensitive data with strong classification performance. A schematic overview
Secure Distributed DP-Helmet achieves scalable, distributed privacy-
2

---

of our work is illustrated in Fig. Here each user the protocol party holds and protects small dataset while all users jointly learn a model without leaking information about the local dataset. More precisely, the jointly computed model protects information about individual persons in two scenarios: first, each user is a local aggregator (e.g.. a hospital) and each person contributes one data point (differential privacy, see see Fig. 3); second, each user is person and contributes a small dataset (local DP, see Fig. 2 for Y- = 50).
Essentially, we base our method on the following simple yet effective scheme introduced by Jayaraman et al. (2018): Each user locally trains a model, e.g. an SVM, via a learning algorithm T, and contributes the parameters of this model carefully noised to a single invoked secure summation or SMPC step which results in an averaged and (s, 6)-DP model. This construction allows using only (1/mmm much noise for n users with m data points each the same as in a centralized setting.
Thus we seek and subsequently achieve three criteria: (1) scalability with the number of users which is measured by the number of communication rounds and the number of secure summation invocations if required with the above privacy definition. the classification accuracy as well as the utility degradation when compared to a centralized scheme (3) good utility-privacy trade-off which is measured by how much more noise we need to add due to the distributed training scheme.
(2) high expressivity which is measured by
where all data is stored at the aggregator.
Related Work. In Table I we detail our utolity-bound improvement in comparison to prior work. Observe that our work matches the utility bound and privacy bound of centralized training while having constant secure summation overhead: We only require one invocation of secure summation which is even realistic for Smartphone- haaeeehooe--eedd applications since we do not have to deal with issues of multiple consecutive communication rounds like dropouts unstable connectivity. When using Bell et al. 2020)* i construction for secure summation, the number of communication rounds is fixed to 4 rounds and the size of each communication round increased by only log(n (n users), which is diminishingly small when compared to the constant overhead amounting to the model size. In comparison to DP-FL, we have 500-fold decrease communication cost: DP-FL has 1,920 rounds of size f, where & is the model size (roughly 60,000 floats for CIFAR-10) while we have 4 rounds of size (s__ers) + for roughly the same model size.
Evaluation. Our evaluation on CIFAR-10 with SimCLR -basd pre-training shows that for 1,000 users with 50 data points per user, our scheme achieves with SVMs a classification accuracy of 79.7% for an g = 0.59. Extrapolated to hundreds of thousands and millions of protocol parties (see Fig. 2] for a thorough evaluation), we can protect the entire local dataset (say. 50-group DP) of a protocol party and achieve high accuracy: For local datasets of size 50, Secure Distributed De-Helmet achieves 2 84 % accuracy and (s. 5) = (0.01, 10-10) for 200, 000 users and 2 87 % accuracy and 0c (2- 10-4 10-12) for 20,000,00 ,000 users while guaranteeing local DP-like properties (or 50-group DP). In our experiments, Secure Distributed DP-Helmet significantly improves upon DP-FL for more than 400 < n users (for CIF,R-10), as it avoids the factor /n noise overhead.
Table 1: Comparison to related work for users with m data points each: utility guarantee to the population optimum, DP noise scale, and number of SMPC invocations. In DP-FL an untrusted aggregator combines the updates from each user, while each user update satisfies DP (by adding noise and norm-clipping each gradient). It does need a communication round per training iteration M.
Algorithm
Utility
Noise scale
SMPC Invocations
DP federated learning (DP-FL)
0(1/mm)
(O(M) rounds)
Jayaraman et al. 2018
gradient perturbation
f//m)
/nm)
O
((M)
Jayaraman et al.
2018
output perturbation
/nm)
1
Secure Distributed Delmee (ours)
/mm)
/nm)
Centralized training
0 /nm)
(11/nm)
0
2.1 KEY IDEAS
Trustworthy distributed noise generation. One core requirement of SMPC-based distributed learning is honestly generated and unleakable noise as otherwise, our privacy guarantees would not hold anymore. There is rich body of work on distributed noise generation (Moran et al. 2009
3

---

Dwork et al., 2006a Kairouz et al. 2015b 2021
Goryczka & Xiong 2015). distributed noise generation protocol scales to millions of users. To jointly create noise of a given magnitude, can alternatively use simple, yet effective technique: utilizing the large number of users in our system, we can reasonably assume that at least a fraction of them (say t = 50%) are not colluding to violate privacy by sharing the noise they generate with each other. As long as combine the noise of each user in an oblivious fashion, every user can create noise separately and independently and we are still guaranteed noise of a magnitude depending on t.
So far, however, no
Strong utility-privacy tradeoff via tight composition and convexity. Secure Distributed DP-Helmet utilizes differentially private SGD-based SVMs for which strong utility-privacy tradeoffs have been shown (Wu et al.) 2017). We use SVMs for multi-class classification via the one-vs-rest (OVR) scheme. Each class waged against the combination of all other classes during training. We rely on output perturbation to estimate a sensitivity bound on the resulting models and add calibrated noise to the model. |Miiser& & Mohammadi (2018); ; [Sommer et al. (2019) [Bllee et al. (2020a) show tight composition bounds for such sensitivity censttivity-buuneed additive mechanism.
Expressivity of our approach. A known limitation of convex SVMs their limited expressivity. As remedy, we utilize transfer learning and operate in two phases: a pre-training phase in which a powerful representation model is trained on a public dataset, and a training phase in which we train a set of SVMs on sensitive dataset. The datasets can have different, disjoint distributions; it suffices that the two datasets are comparable in structure. In our evaluation, we use the SimCLR representation model (Chen et al. 2020b) trained on ImageNet and then fine-tune it on CIFAR-10.
Threat model & security goals. We separate the security assumptions of our protocol and those of the underlying secure summation. For our work, we assume security against malicious, global attackers that do not follow our protocol as long as we have a ratio of at least honest users (say t t= 50 %). In particular, we consider dishonest noise generation. The attacker in both variants tries to extract sensitive information about other parties from the interaction and the result. As in other strong security definitions, the attacker has strong background knowledge and knows everything about and can influence each user's 's dataset, except for one data point of one user. Our privacy goals are (e, 5) -differenntaal privacy (protecting single samples) and (c, -grouu differential privacy (protecting all samples of user at once).
2.2 WHAT DOES THAT MEAN FOR PRACTICAL APPLICATIONS?
From a bird's eye view, our experiments show that the mean of several SVMs significantly improves the classification accuracy, even if the individual SVMs have a poor performance on their own. We pushed this approach to its limit and trained each SVMs on only 50 data points. Our experiments show that the SVM obtained by computing the mean of 1,000 such SVMs has very high accuracy.
Local DP. For applications with around 200,000 or more users, we can protect the entire local dataset user, i.e., the entire locally trained SVM This result can be generalized: We can protect each local SVM independently of how many data points were used to train it. With this generalized view, our scheme does not only protect data points but users, which makes our DP guarantees akin to group-DP setting (comparable to local DP). Applications can leverage this method and let users train SVMs on their own devices instead of requiring local aggregators for sets of users.
For which other learning algorithms is this framework applicable? Our utility- Sellitt--rivcy results apply, beyond SGD-based SVMs, to other learning methods; those methods improve significantly upon averaging locally trained models (cf. Cor. 10 and Appxs. Mandd N). We show that the following five requirements suffice for showing both differential privacy and learnability properties: (1) bounded output sensitivity. (2) strongly convex training objective, (3) smooth training objective, (4) Lipschitz continuous training objective, and (5) SGD-based update routine. Notably, we formally only require that the norm of each model is bounded; we do not make any assumptions about the training procedure of each base learner, which learns a single model in the ensemble. In particular, base learners do not need to satisfy differential privacy. Concerning learnability properties, we show that generalizability property and convergence property improve the average of locally trained models when compared to the locally trained models, for a certain class of learning methods. Whenever SGD is used with a strongly convex, smooth, and Lipschitz ERM objective (empirical risk minimization), averaging local models improves on uniform stability, which is a form of generalizability property, and convergence, which measures the loss-distance to the optimal model for given dataset.
4

---

Algorithm 1: SGD SGGDSSV(DDD,, K) with hyperparameters & == (h, c, A, R,M
Data:
dataset D = { ( )1));= where 2; is structured as 21,1 .......................... Ti.pl: set of classes K; Huber loss smoothness parameter h R4; input clipping bound: E R4; #iterations M; regularization parameter: A E R4;
model clipping bound: R E R4;
Result: models (1d intercepts with p- p-dimensional hyperplanes);
{1
E R(++1)x|K]
kEK
clipped (x) = c // max (c, [|x])):
J(s, D) = A fT f+ ++ N EleviED Ltubber (f" (z) y (1(y = k]] 1 + k)));
2
for k in K:
for m in L..... M:
(()) + SGD ( [[[m: k),,, amm) with learning rate Om == min() 3. Xmm) and
3 1/2h + A;
((h) = R. (k)
/ /1 (K)
// projected SGD
3 PRELIMINARIES
3.1 DIFTERENTIAL PRIVACY AND DP DP_SGD_SVM
Preliminaries of the Secure Summation protocol (Bell et al. 2020) as well as pre-training as a tactic to boost DP performance available in Appx. B.2 and Appx. B.3 respectively.
As a privacy notion, we consider differential privacy (DP) (Dwork et al. 2006b). Intuitively, differen- tial privacy quantifies the protection of any individual's 's data within a dataset against an arbitrarily strong attacker observing the output of a computation on said dataset. Strong protection is achieved by bounding the influence of each individual's 's data the resulting SVMs. For the (standard) definition of differential privacy we utilize in our proofs, we refer to Appx. B.T
We consider Support Vector Machines (SVMs), which can be made strongly convex, thus display unique local minimum, and have a lower bound on the growth of the optimization function. Having a unique local minimum makes those methods ideal for computing tight differential privacy bounds and thus highly relevant machine learning predictors for our work. In fact, this differentially private SVM definition (DP_SGD _GD_SVM) can be derived directly from the work of Wu et al. (2017) on empirical risk minimization using SGD-based optimization. They rely on a smoothed version of the hinge-loss: the Huber loss haaeer (cf. Appx. B.4 for details). We additionally apply norm-clipping to all inputs. We use the one-vs-rest (OVR) method to achieve multiclass classifier. Alg. provides pseudocode for the sensitivity-bounded algorithm (before adding noise).
In contrast to Wu et al. (2017), which assumes for each data point ||>||| < 1, we use generalization that holds for larger norm bounds e > 1: we assume ||=||| S c, where is a hyperparameter of the learning algorithm SGD S_SM. As result, the optimization function J is c RA Lipschitz (instead smooth (instead of 1/2h- + A
of 1 + RA Lipschitz as in Wu et al. (2017)) and ((e"/2h + A) + pA2) +p?) smooth). Wu et al. (0017) showed a sensitivity bound for SGD SVM from which we can conclude DP guarantees. The sensitivity proof follows from Wu et al. (2017) Lemma 8) with the Lipschitz
constant L = + RA, a smoothness 3 = ((.2/2h + A)² + pA²) 2 and a A-strong convexity.
Similarly, our work applies to Ly-regularized logistic regression where we adapt Alg. with the optimization function [', D) = f f N E (( In(1 + exp(-ft pT clipped (z) v)) which is
A-strongly convex, L = + RA Lipschitz, and = ((2/1 + A)2 + pA²) smooth. We would also need to adapt the learning rate to accommodate the change in the smoothness parameter but continue to have the same sensitivity as for the classification case.
Definition (Sensitivity). Let ff be function that maps datasets the p-dimensional vector space RP. The sensitivity of f is defined as maxp-, f - f((D'll, where D ~ D' denotes that the datasets D and D' differ in at most one element. We say that is an s-sensätivity-bounded function.
The following lemma directly follows from Wu et al. 2017 Lemma 8).
5

---

Lemma 2. With the input clipping bound the model clipping bound R. the strong convexity factor A. and the number of data points N. the learning algorithm SGD_ BDDDSVMM@ of Alg. has a sensitiviry bound of 2(c+RA) for each of the [K] output models. NA
For sensitivity- boundde functions, there is generic additive mechanism that adds Gaussian noise to the results of the function and achieves differential privacy, if the noise is calibrated to the sensitivity.
Lemma 3 (Gaussian mechanism is DP (Theorem A.I & Theorem B.1 in Dwork & Roth (2014)). Let Qs. be functions with sensitivity s on the set of datasets D. For (0, I). c > 2n 1.25 ()) the
Gaussian Mechanism D + {4x(D) + +N(0, (a [(x+1)x(x)) with o 2 -. is (s, 0)DP, where La is the d-dimensional identity matrix.
The mechanism that first learns |K] SVM models via SGD L_SV of Alg. I and then adds multivariate Gaussian Noise. (0, (a- [(p+1xx]]]]]] [K] )²) is DP. Note that there are tighter composition results (Meiser
& Mohammadi] 2018 Sommer et al. 2019 Balle et al. 2020a) where = E ((v(K) which we do not lormalize for brevity reasons but follow our experıments.
Corollary 4 (Gaussian mechanism on SGD SVM DP). With the s-sensitivity -esusiiivitybouudeed -bounedd learning algorithm (GD_SVM (cf. Lem. 2). the dimension of each data point p, the set of classes K, and 8 E (0, 1), DP_ MP_SGD_SS SGD_SVM(D,,, K, == SGD__VM (D,5, E, K) + (0, (a 8 [(p+1)x(K)))) is (E, DDD,, where = 2 222nn 1/25/1 | and Ia is the d-dimensional identity matrix.
Notation. A learning algorithm is function from datasets to learned models. Subsequently, consider the notion of a configuration in many theorems.
Definition 5 (Configuration S). A configuration I,,,,,T,, 8. U, N, K, consists of a set of users of which t U are honest, an s- cunsitivity-boundde learning algorithm T on inputs (D, K), hyperparameters E. a local datasets D(6) of user U(i) E U with N = minge D and U U. D a set of classes K, and noise multiplier a. avg(T") is the aggregation of [ut] local 14 models of algorithm T: avg(T((3)) = TV EM ((DD(),,,)) If unique, we simply write Ç.
4 SECURE DISTRIBUTED DP-HELMET
This section presents Secure Distributed DP-Helmet in detail (cf. Alg. 2 and its utility-privace proper- ties. Here, each user separately trains a before their parameters are combined with the parameters trained by other users via a single round of secure summation. The single round of secure multiparty computation allows us to have the full benefit securely aggregating data: we can show centralized-DD guarantees within a threat model akin to that of federated learning with differential privacy.
learning algorithm, e.g. DP_ PP_SGD_ST SVMS.
Active attacks and untrustworthy noise. Our threat model allows each user to place very little trust in other users. However, we focus on passive adversaries. Active attacks that, c.g., aim to poison the resulting model, are left for future work. Note that even passive adversaries can collude and exchange information about the randomness they used in their local computation. As combine the noise added by different users, we need to take into account that not all of that noise is necessarily secret to the adversary. To compensate for untrustworthy users, we double the noise added by each user; as long as half of all users are honest, our guarantees thus are valid.
Next, we derive tight output sensitivity bound. A naïve approach would be to release each individual predictor, determine the noise scale proportionally to ā == a (cf. Cor. 4h, showing (s, 6DP for every user. We can save a factor of /24'//a by leveraging that [2/] is known to the adversary and we have at least f 50%, yielding == a 1-///-
Corollary 6. Given a configuration Ç. Secure Distributed DP DP-Helmer(C) (cf. Alg. 2) without adding noise, i.e. av)(T has sensitivity of s 1/j41 for each class k E K.
The proof is placed in Appx. G Having bounded the sensitivity of the aggregate to s 1/14,, we show that locally adding noise per user proportional to σ s s- 1/14// and taking the mean is equivalentt to only centrally adding noise proportional to a s. 11/14 (as the central aggregator was honest).
Lemma 7. Given a configuration Ç and any noise scale ō, then 1 14 No (ā 1/vRa)3) =
(O (ā 2/

---

Algorithm 2: Secure Distributed De-Heleet. For T = SGD_SVM (cf. Alg. 1) we have 2(+ 2(++RA) with hyperparameters' & (h, C, A, R. M). Age is described in Bell al.
NA
2220
Algorithm 2) and can be extended to floating points using fixed-point arithmetic.
def Client Secure Distributed DP-He 1met (D, [u], K. 1, &, o):
Data: local dataset D with N = D]; #users U4] set of classes K; training algorithm T; ratio of honest users; hyperparameters &; noise multiplier o
Result: DP-models (intercepts with p-dimensional hyperplanes): Mpric == ( }
KEK
M T(D,); Mpriv < M (O, 1)+1X|11)
// T is s-sensstiiityy with Ø == a 1/VT- M
Run the client code of the secure summation protocol ASecAgg on input M/rn//e1:
def Server Secure Distributed DP-Helmet (U):
Data: users 4
Result: empty string
Run the server protocol of AgeeAggi
The proof is placed in Appx. H We can now prove differential privacy for Secure Distributed DP-Helmer of Alg. 2 where we have noise scale ō == a 1////- |u] and thus O1///t-
Theorem 8 (Main Theorem, simplified). Given a configuration Ç. Secure Distributed DP-Helmer(() (cf. Alg. 2) satisfies computational (s, 5 + DD with e 2 / 1/25/66/ 1. K))- (b)))) 2/0 and a function
negligible in the security parameter of the secure aggregation.
The full statement and proof are in Appx. I Simplified, the proof follows by the application of the sensitivity (cf. Cor. 6) to the Gauss Mechanism (cf. [em. 3) where the noise is applied per user (cf. Lem. 7). If each user contributes 50 data points and we have 1000 users, N [24| 50,000.
Next, we show that we can protect the entire dataset of single user (e-g.. for distributed training via smartphones). The censitivity-basee bound on the Gaussian mechanism (Apx K) directly implies that we can achieve strong T- T-group privacy results, which is equivalent to local DP.
Corollary 9 Stroup-private variant). Given configuration Ç. Secure Distributed DP DP-Helmer(() (cf. Alg. 2) satisfies computational (s, + +v). T-group DP with 2 T 22 (,25/6// for v as above: for any pair of datasets V5, 3' that differ at most Y many data points,
|K| -10
Secure Distributed DP-Helmer(((.....
R5,5 Secure Distributed DP- OO-Helmme((((.... ,.,....)
Cor. and DP-FL. While the averaging will slightly offset this massive amount of noise, such result does not hold for DP-FL because in the local training the sensitivity does not decrease. Hence, in contrast to Secure Distributed DP-Helmet, the standard deviation of the noise that is locally added will continuously increase, no matter how many users join the distributed training.
Cor. Iggneraaizess to a more comprehensive Cor. 10 that is data oblivious. If we can show that the training algorithm of every user has the same bounded sensitivity, i.e., that the norm of each model is bounded, then Secure Distributed DP-Helmet can apply to the granularity of users instead of that of data points. We explicitly don't 't need to make any further assumptions about the training procedure of each base leamer, it is sufficient that the local models are combined via noisy arithmetic mean. This method renders tighter sensitivity bound than SGD_SV SVM for certain settings of Y or data points per user N. Moreover, it enables the use of other SVM optimizers or Logistic Regression.
In particular, the training procedure of each base learner does not need to satisfy differential privacy. Corollary 10. Given a learning algorithm T. we say that T is R-norm bounded if for any input dataset D with N = [D), any hyperparameter and all classes k E K, [[, E. k)]l < R. Any R-norm bounded learning algorithm T has a sensitivity $ = 2R. In particular, TO,( (a 8- satisfies (e, 5), T -ggroup differential privacy with Y = N and & 2 v 22nn (/25/(/1KK)) | 1/o, where (0 (a 8 Ta)?) is spherical multivariate Gaussian noise and a a noise multiplier.
The proof is in Appx. Here the number of local data points N can vary among the users.

---

STABILITY & CONVERGENCE. The of our approach is to locally train models and compute the average without further synchronizing or fine- tuning of the models: avg(T). ). For T = SGD SVM, we prove that the learnability properties Shalev-Shwardd et al., 2010) uniform stability and convergence are comparable to a centrally trained SGD_SVM.
Uniform stability. We show in Appx. M that the training generalizes well by prov- ing uniform stability the sense of Bousquet & Elisseeff (2002) for T = SGD_SVM, where J is the objective func- tion (cf. Alg. I and 2 an unknown data distribution where U E Z. In particular, we show that averaging the locally trained SGD SVMs linearly improves the stability bound.
[E[ (3),
(avz([(avg( 2ill E 0(3
Convergence. In line with Zhang et al. (2013) on averaged ERM models, we show in Appx. N that avg(SGD SVM) gracefully converges the best model for the combined local datasets Ü: (SDGa inf, J(. O(3/a)) for M many training iterations.
EXPERIMENTAL RESULTS
0.21
0.38
0.72
0.84
0.87
0.89
0.21
0.38
0.61
0.79
0.87
0.89
0.21
0.38
0.72
0.84
0.87
0.89
(ggpp
0.21
0.38
0.61
0.79
0.87
0.89
1
0.57
0.87
0.34
0.76
0.87
5c-05
0.0002
2 (priaayy bedget)
C (pptiaacy bedget0
Figure 2: (s, T)-Heatmap for classification accuracy of Secure Distributed De-Helmet on CIFAR-10 dataset (left: 8 = 10 10, right: 5 10- 10-12) with 200,000 (left) and 20, 0,,0000000 (right) users. We train 1,000 models on 50 data points each; to emulate having more users we rescale the e-values (e' = 1000 e //..... and report the respective (interpolated) accuracy values. We extrapolate the privacy guarantees, due to the limited dataset size. Our accuracy values are pessimistic as we keep the accuracy numbers that we got from averaging 1,000 models. Actually taking the mean or even 20,000,000 users should provide better results. In our evaluation, T = 50 group privacy is comparable to local DP. lower value of T 50 places trust users as local aggregators. For Y 2 2, we can use tighter group-privacy bound (cf. CCrr. 10); hence, the accuracy values are the same as for T
200,000
N, where the entire local data set a user is protected.
We analyze four experimental questions: (RQ1) First, how does Secure Distributed DP-Helmet as well as the strongest alternative, DP-SGD-based federated learning, perform in terms of privacy-utility trade-off? Moreover, how does the performance change if we allow
users (cf. [Fig. 3] right, and
Fig. 4h? (RQ2) Second, what is the utility loss of applying both methods in a distributed fashion instead of centrally (ef. Fig. left)? (RQ3) Third, how does Secure Distributed DP-Helmet perform when we have truly many users (2 200,000 users) and when we are in a local-DP setting Fig. 2) (RQ4) Fourth, how do learning algorithms different than DP DP_SSDD SVM perform (cf. Appx. F)?
Pretraining.
We used a SimCLR pre-trained mode - on ImageNet ILSVRC-2012 Russakovsky al., 2013) for all experiments (cf. Fig. 6) in the appendix for an embedding view). it built with
a Net152 with selective kernels (Li et al. 2019) architecture including width multiplier of 3 and it has been trained in the fine-tuned variation of SimCLR where 100 % of ImageNet's label information has been integrated during training. Overall, it totals 795 M parameters and achieves 83.1 1 % classification accuracy (1000 classes) when applied linear prediction head. In comparison, supervised-onjy model of the same size would only achieve 80.5 % classification accuracy.
Sensitive Dataset. CIFAR- (Krizhevsky 2009) acts as our sensitive dataset, as is frequently used as a benchmark dataset, especially in the context of the differential privacy literature. CIFAR-10 an MIT-licensed dataset consisting of 60,000 thumbnail-sizee colored images of 10 classes.
Evaluation. The model performance is delineated threefold: First, evaluated a benchmark
scenario in Fig. 3 (left) to compare our Secure Distributed De-Heelet (cf. [Section 4) to a DP-SGD-
thub accessible httppp////gtthhb..cc//////g/////
Apache-2.0 license
8

---

0.6
1001 8-C0000
0.7
SVM
0.6
DESSLID SNM
Ausess
0.4
400
1000
0.
1000
03
0.1
0.3
1.0
30
01 03
1.0
300
(proouy hadggst
Figure 3: Classification accuracy compared to the privacy budget (in logae-) of Secure Distributed DP-Helmet (ef. [Section 4) and DP-SGD-based federated learning (FI.) on CIFAR-10 10 dataset (6 10 10- (left) We use all available data points of CIFAR- 10 for each line, spreading them among a differing number of users. (right) Different numbers users with 50 data points per user.
based federated learning approach (DP-FL) on single layer perceptron with softmax loss. There the approximately same number of data points is split across various number of users ranging from 1 to 1000. Second, we also evaluated a realistic scenario in Fig. 3 (right) where we fixed the number of data points per user and report the performance increase obtained with more partaking users. Fig. 4 depicts the setting of Fig. 3 (right) for fixed privacy budget. Third, we evaluated scenario with truly many users as well as local-DP setting in Fig. budget to accommodate the changed parameters.
where we rescale the privacy
The experiments lead to three conclusions: (RQ1) First, performance improves with an increasing number of users (ef. Fig. 3 (right)). Al- though the Secure Distributed De-Helmet training performs subpar to DL-FL for few users, it takes off after about 400 users due to its vigorous performance gain with the number of users (cf. Fig. 4).
0.8
0.7
Iest accunccy
0.6
(RQ2) Second, in a scenario of globally fixed number of data points (cf. Fig. 3] (left)) that are distributed over the users, Secure Distributed DP-Helmet's performance degrades more gracefully than that of DP-FL.
0.5
0.4
Thm. 21] supports the more graceful decline; it states that averaging multiple of the here used SVM predictors eventually converges to the optimal SVM on all training data. The difference between I and 100 users largely due to our assumption of 50 % dishonest users, which means noise scaled by a factor of /2. In comparison, DP-FL performs worse the more users U/ partake as the noise scales with (/14
DP-SGD-SVM
0.2
FL
250
500
750
1000
#users
Figure Classification accuracy versus #users with 50 data points per user for fixed 0.5885, = 10-5, Values for FL are interpolated.
(RQ3) Third, the advantage of our method over DP-FL becomes espe- cially evident when considering significantly more users (cf. Fig. 2). such as is common in distributed training via smartphones. Here, DP- guarantees of 2- 2-10-4 become plausible with at least 87 % prediction performance for a task like CIFAR-10. 10. Alternatively, leveraging Cor. 9 we can consider local DP scenario (with T 50) without trusted aggregator, yielding an accuracy of 84 % for E 5 10-4 Starting from Y 2 2, a user-level sensitivity (cf. Cor. 1Op is in the evaluated setting tighter than a data point dependent one; hence, the accuracy values are the same as for the local DP scenario.
(RQ4) We refer to Appx. For an ablation study in the centrally trained setting for different learning algorithms than DP_SGD SGD_SVM. SVM. In this setting, the here used DP SGD_SGDDDDD SVM has worse privacy- utility trade-off than other DP learners like DP-SGD: for E = 0.59, DP SGD SVM has an accuracy of 87.4 % while SPD has 93.6 %. The reasons include leakage via sequential composition (through DP-SGD-SVM' one-versus-rest multi-class approach) compared to DP- joint learning of all classes well its noise-correcting property from its iterative noise application.
Computation costs. For Secure Distributed De-Helmet with 1,000 users and a model size I z 100,000 for CIFAR-10, need less than 0.2 for the client and 40 s for the server, determined by extrapolating the experiments of (Bell et al. 2020 Table 2).
Experimental setup.
Appx. D) describes our experimental setup.

---

REFERENCES
Martin Abadi, Andy Chu, lan Goodfellow, Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. epSGD: Communication--fficcee and differentially-priinn distributed SGD. In Advances in Neural Information Processing Systems (NeurIPS), pp- 7564 -7575, 2018.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy profiles and amplification by subsampling. Journal of Privacy and Confidentiality, 10(1), 2020a.
Borja Balle, Peter Kairouz, H. Brendan McMahan, Om Thakkar, and Abhradeep Thakurta. Privacy Amplification via Random Check-Ins. In Advances in Neural Information Processing Systems (NeurIPS), 2020b.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science, pp. 464-473 IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference Computer and Communications Security, pp. 1253- 2020.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1191- 2017.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi- cemi-supervised learners. In Advances in Neural Information Processing Systems, volume 33. pp. 12243-22255 Curran Associates, Inc., 2020b.
Soham De, Leonard Berrada, Jamie Hayes, Samuel Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint arXiv:2204.13650, 2022.
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Disferential Privacy, volume 9 of Foundations and Trends in Theoretical Computer Science. Now Publishers, 2014.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual international conference on the theory and applications of cryptographic techniques, pp. 486-503, Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006b.
Rong- En Fan, Kai-Wei Chang, Cho-Jui Hsich, Xiang-Ru Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. the Journal of machine Learning research, 9:1871-1874, 2008.
10

---

Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. 2018 IEEE 59th Anmual Symposium on Foundations of Computer Science (FOCS), pp- 521-532. IEEE, 2018.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020.
Antonious M. Girgis, Deepesh Data, Suhas Diggavi, Peter Kairouz, and Ananda Theertha Suresh. Shuffled Model of Federated Learning: Privacy, Communication, and Accuracy Trade-offs. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
Slawomir Goryczka and Li Xiong. A comprehensive comparison of multiparty secure additions with differential privacy. IEEE transactions on dependable and secure computing, 14(5):463-477 4777
2015.
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv: 2015.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234. PMLR, 2016.
Roger Iyengar, Joseph Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. Towards practical differentially private convex optimization. In 2019 IEEE Symposium Security and Privacy (SP), pp. 299-316. IEEE, 2019.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning with- out distress: Privacy-presse privacy-rrseervng empirical risk minimization. Advances Neural Information Processing Systems, 31, 2018.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pp. 1376-1385. PMLR, 2015a.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Secure multi-party differential privacy. Advances in neural information processing systems, 28, 2015b.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning, pp. 5201-5212. PMLR, 2021.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pp. 25-1. JMLR Workshop and Conference Proceedings. 2012.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Xiang Li, Wenhai Wang, Xiaolin Hu, and Jian Yang. Selective kernel networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 510-519, 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-effiiee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282. PMLR, 2017.
Sebastian Meiser and Esfandiar Mohammadi. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 247-264, 2018
Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil Vadhan. Computational differential privacy. In Annual International Cryptology Conference, pp. 126-142. Springer, 2009.
Tal Moran, Moni Naor, and Gil Segev. An optimally fair coin toss. In Theory of Cryptography Conference, pp. 1-18. Springer, 2009.

---

Jack Murtagh and Salil Vadhan. The complexity of computing the optimal composition of differential privacy. In Theory of Cryptography Conference, pp. 157-175. Springer, 2016.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal on optimization, 19(4):1574- 1609, 2009.
Manas Pathak, Shantanu Rane, and Bhiksha Raj. Multiparty differential privacy via aggregation of locally trained classifiers. Advances in neural information processing systems, 23, 2010.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma. Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115 2015.
Shai Shalev-Shwart Ohad Shamir, Nathan Srebro, and Karthik Sridharan, Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010.
David M Sommer, Sehastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem differential privacy. Proceedings on privacy enhancing technologies, 2019(2): 245-269 2019.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference on Learning Representations (ICLR), 2021.
Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. Hybrid Approach Preeccc-rrseeving Federated Learning. Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security (AlSec), pp. 1-11. 11.1.AA ACM, 2019.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008
Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent-baan -ased analytics. In Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1307-1322, 2017.
A. Yousefpour; Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, Nguyen, Ghosh, A. Bharadwaj. J. Zhao, G. Cormode, and I. Mironov. Opacus: User-friendly differential privacy library in pytorch. arXiv preprint arXiv:2109.12299 2021.
Yuchen Zhang, John C Duchi, and Martin J Wainwright. Communication-efficienn algorithms for statistical optimization. Journal of Machine Learning Research, 14:3321-3366 2013.
12

---

A LIMITATIONS & DISCUSSION
Distributional shifts between the public and sensitive datasets For pre-training our models, we leverage contrastive learning. While very effective generally, contrastive learning is susceptible to performance loss if the shape of the sensitive data used to train the SVMs is significantly different from the shape of the initial public training data.
As we train separate SVMs for the different classes, this approach works best if the number of classes is limited. Distributed DPHelmet deal with multiple classes; CIFAR-10 10 has 10 classes. However, if a classification task has significantly more different classes, non-SVM-based approaches might perform better.
Multi-class classification
Input Clipping DP_ SP_SGD_ST CVD_ requires a norm bound on the input data as it directly influences the SVM training. In many pre-training methods like SimCLR no natural bound exists thus we have to artificially norm clip the input data. To provide non-data- dape-dddedeeeentttt clipping bound in CIFAR-10 1- data, we determined the clipping bound on the CIFAR-101 dataset (here: 34.854); its similar data distribution encompasses the output distribution of the pretraining reasonably well.
Hyperparameter Search In SGD_SVM, we deploy two performance-crucial hyperparameters: the regularization weight A as well as the predictor radius R. both of which influence noise scaling. In the noise scaling subterm c/A + R, the maximal predictor radius is naturally significantly smaller than </a due to the regularization penalty. Thus, an imperfect I resulting from non-hyperparameter tuned SVM does not have a large impact on the performance. Estimating the regularization weight for fixed from public data is called hyperparameter freeness in prior work (lyengar et al. (019). For other & values we can fit a (linear) curve on a smaller but related public dataset (proposed by Chaudhuri et al.] (20TT) synthetic data (proposed by AMP-NT ([yengar al., 2019)) smaller prefer higher regularization weights and vice versa.
B EXTENDED PRELIMINARIES
B.1 DIFFERENTIAL PRIVACY
To ease our analysis, consider randomized mechanism M to be function translating a database to random variable over possible outputs. Running the mechanism then is reduced to sampling from the random variable. With that in mind, the standard definition of differential privacy looks as follows.
Definition (5% relation). Let Obs be a set of observations, and RV RV(Obs) be the set of random variables over Obs, and D be the set of all databases. A randomized algorithm M D > RV (Obs) for a pair of datasets D, D', we write M (D) Re.8 M(D') if for all tests S C Obs we have PD( E S) S exp(E) Pr(M E S]
(1)
Definition 12 (Differential Privacy). Let Obs be
of observations, and RV Obs) be the set of random variables over Obs, and 'D be the set of all databases. A randomized algorithm M : D - RV Obs) for all pairs of databases D, D'' that differ in at most I element (0,6)-DP mechanism if we have
M(D) 25,5 M(D).
In the context of machine learning, the randomized algorithm represents the training procedure of a predictor. Our distinguishing element one data record of the database.
Computational Differential Privacy Note that because of the secure summation, we technically require the computational version of differential privacy (Mironov et al. 2009), where the differential privacy guarantees are defined against computationally bounded attackers; the resulting increase in 8 is negligible and arguments about computationally bounded attackers are omitted simplify readability.
Definition 13 (Computational 2E,8 Differential Privacy). Let D be the set of all databases and 1 a security parameter. A randomized algorithu M D -> RV Obs) for a pair of datasets 'D2 D'' we write (D) 25,5 M(D)) for any polynomial-tin probabilistic attacker
Pr(A(M(D)) = 0) & exp(e) Pr(A(M(D')) 1] +1++0 5(n).
13

---

For all pairs of databases D, D' that differ in most 1 element M is computational (e, -D mechanism if we have
DD) 26 M(D).
(4)
B.2 SECURE SUMMATION
Hiding intermediary local training results as well as ensuring their integrity is provided by an instance of secure multi-party computation (SMPC) called secure summation (Bonawitz et al. 2017 Bell et al.. 2020). It targeted to comply with distributed summations across a huge number of parties. In fact, Bell et al. 2 has a computational complexity for n users on an l-sized input of (log* n- log n) for the client and (nn(lo" n + log r1)) for the server as well as a communication complexity of (log n + 2) for the client and (n n + 1)) for the server thus enabling efficient run-through of roughly 10 users without biasing towards computationally equipped users. Additionally, it offers resilience against client dropouts and colluding adversaries, both of which are substantial features for our distributed setting:
Theorem 14 (Secure Aggregation Sec in the semi soni-honest setting exists (Bell et al. 2020 ) Let
$1...., Sn be the d-dimensional inputs of the clients UO), U U(m). Let F be the ideal secure summaation function: F(s1...., Sn)) == 1/n Ei=1 S4. If secure authentication encryption schemes and authenticated key agreement protocol exist, the fraction of dropouts (i.e., clients that abort the protocol) is at most p E 1). at most a 7 E [0, 1] fraction of clients is corrupted (C S {U'))..., U. |C|=mn) and the aggregator is honest- but-curious, there a secure summation protocol Agg for central aggregator and n clients that securely emulates F in the following sense: there is probabilistic polynomial-time simulator Simy such that Reulag (81,.... ......... 8.) is
statistically indistinguishable from Simx(C, F(s)....,,n)) i.e. for an unbounded attacker A there a negligible function v such that
Advantage(A)
(ReaARRel ($1,..., sn)) 1] (C
1]1 v(n).
B.3 PRE-TRAINING TO BOOST DP PERFORMANCE
trained on public data-
trained on sensitive data
Pretrained
DP Trained
simplified representation
input data
predictions
Figure 5: Pre-training: Schematic overview. Dashed lines denote data flow in the training phase and solid lines in the inference phase.
Recent work Tramer & Boneh 2021 De et al. 2022) has shown that strong feature extractors (such as SimCLR (Chen al. 2020a b trained an unsupervised manner, can be combined with simple learners to achieve strong utility-privacy tradeoff's for high-dimensional data sources like images. As variation to transfer learning, it delineates two-step process (cf. Fig. 5). where simplified representation of the high nigh-dimensional data is learned first before a tight privacy algorithm like DP SGD SVM conducts the prediction process on these simplified representations. For that, two data sources are compulsory: public data source which is used to undertake the learning of a framework aimed to obtain pertinent simplified representations in addition to our sensitive data source that conducts the prediction process in differentially private manner. Thereby the sensitive dataset is protected while strong expressiveness is assured through the use of the feature reduction network. Also note that homogeneous data distribution of the public and the sensitive data is not necessarily required.
Recent work has shown that for several applications such representation reduction frameworks can be found, such as SimCLR for pictures, FaceNet for face images, UNet for segmentation, or GPT-3 for language data. Without loss of generality, focus in this work on the unsupervised SimCLR feature
14

---

reduction network (Chen et al. 2020a b SimCLR uses contrastive loss and image transformations to align the embeddings of similar images while keeping those of dissimilar images separate (Chen et al.. 2020a It is based upon self-supervised training scheme called contrastive loss where no labeled data is required. Labelless data is especially useful as it exhibits possibilities to include large-scale datasets which would otherwise be unattainable due the labeling efforts needed.
B.4 PPGSGGDS -GD_VVM
Definition 15. The Huber loss according to Chaudhurri et al. (011 Equation 7) is with smoothness parameter ht defined as
if h if - 2 - h.
Exaaber (2)
(1 h 2)²
4h
1
if h
C RELATED WORK
C.I PRIVACY-PRESERVING DISTRIBUTED MACHINE LEARNING
There is a rich body of literature about different differentially private distributed learning techniques that protect any individual data point (sometimes called distributed learning with global DP guaran- tees). One direction uses an untrusted central aggregator; users locally add noise to avoid leakage toward the aggregator. This method computationally scales well with the number of users. Another direction utilizes cryptographic protocols to jointly train model without a central aggregator. This direction requires less noise for privacy, but the cryptographic protocols face scalability challenges.
For local noising. the most prominent and flexible approach is federated learning (McMahan et al. 2017) with DP-SGD approximation (Abadi et al. (016) (DP-FL). DP-FL proposes each of the n users locally train with the DP-SGD algorithm and share their local gradient updates with a central aggregator. This aggregator updates a global model with the average of the noisy local updates, leading to noise overhead in the order of vn.
This noise overhead can be completely avoided by PPDML protocols that rely on cryptographic methods to hide intermediary training updates from central aggregator. There are several secure distributed learning methods that protect the contributions during training but do not come with privacy guarantees for the model such as DP: an attacker (e.g., curious training party) can potentially extract information about the training data from the model. As we focus on differentially private distributed learning methods (PPDML. in this paper), we will neglect those methods.
epSGD (Agarwal et al. 2018 is a PPDML protocol that utilizes SMPC methods to honestly generate noise and compute DPDSGD. While epSGD provides the full flexibility of SGD, does not scale to millions of users as it relies on expensive SMPC methods. Another recent PPDML work (Truex et al., 2019) relies on a combination of SMPC and DP methods. This work, however, also does not scale to millions of users.
Another line of research aims for the stronger privacy goal of protecting user's entire input (called local DP) during distributed learning (Balle et al. [220bb] Girgis et al., 202T). Due to the strong privacy goal, federated learning with local DP tends achieve weaker accuracy. With Cor. 9 evaluated in Fig. in Seccion 5] we show how Secure Distributed De-Helmet achieves a comparable guarantee via group privacy: given enough users, any user can protect their entire dataset at once while we still reach good accuracy.
For DP training of SVMs, there exist other methods, such as objective perturbation and gradient perturbation. When performed under SMPC-based distributed training, both methods would require significantly higher number of SMPC invocations; hence, they are unsuited for the goals of this work. Appx. C.2 discusses those approaches in detail.
C.2 DIFFERENTIALLY PRIVATE EMPIRICAL RISK MINIMIZATION
On differentially private empirical risk minimization for convex loss functions (Chaudhuri et al.. 2011), which is utilized in this work, the literature discusses three directions: output perturbation,
15

---

objective perturbation, and gradient perturbation. Output perturbation (Chaudhuri et al. 2011 Wu al. 2017) estimates a sensitivity on the final model without adding noise, and only in the end adds noise that calibrated to this sensitivity. We rely output perturbation because it enables to only have a single invocation of an SMPC protocol at the end to merge the models while still achieving the same low sensitivity if the model was trained at trustworthy central party that collects all data points, trains model and adds noise in the end.
Objective perturbation (Chaudhuri al. 2011 Kifer et al. 2012 Iyengar et al. 2019 Bassily et al. 2019) adds noise to the objective function instead of adding noise to the final model. In principle, SMPC could also be used emulate the situation that a central party as above trains a model via objective perturbation. Yet, in that case, each party would have to synchronize with every other party far more often, as no party would be allowed to learn how exactly the objective function would be perturbed. That would result in far higher communication requirements.
Concerning gradient perturbation (Bassily et al.] 2014) Wang et al., 2017 Feldman et al., 2018 Bassily et al., 2019 Feldman et al., 2020), recent work has shown tight privacy bounds. In order to achieve the same low degree of required noise as in a central setting, SMPC could be utilized. Yet, for SGD also multiple rounds of communication would be needed as the privacy proof (for convex optimization) does not take into account that intermediary gradients are leaked. Hence, the entire differentially private SGD algorithm for convex optimization would have to be computed in SMPC, similar to epSGD (see above).
D EXPERIMENTAL SETUP
We leveraged 5-repeated 6-fold stratified cross-validation for all experiments unless stated differently. Privacy Accounting has been undertaken either by using the privacy bucket (Meiser & Mohammadi 2018 Sommer al. 2019) toolbox or, for Gaussians without subsampling, with Sommer al. (2019 Theorem 5) where both can be extended to multivariate Gaussians (see Ssee|Appx. L). We note that with either of these tactics, e E (( The ō parameter of differential privacy has been set to 8 10- 5 if not stated otherwise, which for the CIFAR-10 dataset always below 1/x, where is the sum of the size of all local datasets.
Concerning computation resources, for our experiments, we trained 1000 DP DP_SGD_ CGD_SVM with 50 data points each, which took 10 minutes on a machine with 2x Intel Xeon Platinum 8168, 24 Cores @2.7 GHz with an Nvidia A100 and allocated 16GB RAM.
For DP_SPDDDDDD_ PPP_SGDDSVMMbbS saseb experiments. we utilize the strongly convex projected stochastic gradient descent algorithm (PSGD) as used by (Wu et al. (2017). More specifically, we chose batch size of 20, the Huber loss with a smoothness parameter h 0.1, a hypothesis space radius R E {0.04, 0.05, 0.06, 0.07, 0.08), regularization parameter A E f10, 100, 200), and trained for 500 epochs; for the variant where we protect the whole local dataset, we have chosen a different A E (0.5, 1, and E {0.06, 0.07].
In every experiment, we chose for each parameter combination the best performing regularization parameter A as well as R, i.c. those values that lead to the best mean accuracy. This is highly important, the regularization parameter not only steers the utility but also the amount of noise needed to the effect where there is a sweet spot for each noise level where the amount of added noise is on the edge of still being bearable.
For the federated learning experiments, we utilized the opacus Py Torch library Yousefpourr et al. 202T), which implements DP-SGD (Abadi al. 2016). We loosely adapted our hyperparameters to the ones reported by Tramer & Boneh (2021) who already evaluated DP-SGD on SimCLR's embeddings for the CIFAR- 10 dataset. In detail, the neural network is a single-layer perceptron with 61 450 trainable parameters on a 6 144-d input and 10d output. The loss function is the categorical cross-entropy on softmax activation function and training has been performed with stochastic gradient descent. Furthermore, we set the learning rate to 4, the Poisson sample rate 4 == 1024 /500000000 which in expectation samples batch size of 1024, trained for 40 epochs, and norm-clipped the gradients with clipping bound e == 0.1.
Fi
at h http:///tttaaaaaaooo/o/oo/////aa "accessible at
MIT license
Apache-2.0 license
16

---

In the distributed training scenario, instead of running end-to-end experiment with full SMPC clients, we evaluate a functionally equivalent abstraction without cryptographic overhead. In our experiments, we randomly split the available data points among the users and emulated scenarios where not all data points were needed by taking the first training data points. However, the validation size remained constant. Moreover, for Do-dGeD-based federated learning, size whenever enough data is available i.c. increased the sampling rate as follows: g' := 1024 /22000 for 20000, q" 1024/5000 for 5000, and q" == 1028/102/ for 500 available data points (2)) N). For DP-SGD-based FL, we emulated a higher number of users by dividing the noise multiplier o by |4/1//2 to the benefit of DP-FL. The justification for dividing by [2/ is that in FL the model performance is not expected to differ as the mean of the gradients of user is the same as the mean of gradients from different users: SGD computes, just as FL, the mean of the gradients. Yet. the noise will increase by factor of |2////2 Hence, we optimistically assume that everything stays the same, just the noise increases by a factor of [/)//
kept constant batch
E PRE-TRAINING VISUALISATION
Figure 6: 2-d projection of the CIFAR-10 10 dataset via I-SNE (Van der Maaten & Hinton 2008) with colored labels. Note that t-SNE is detined on the local neighborhood thus global patterns or structures may be arbitrary.
F EXTENDED ABLATION STUDY (CENTRALIZED SETTING)
0.90
0.90
0.35
0.65
0.50
0.50
Ref. CC mc)
Ref. (C)
TOP SUKO SVM
TIP SUOD SSM
0.25
DP-SCDD-SN 5VM
0.75
DP-SOD--VN
DP-52D
SP-3KDD
AMP
0.70
1.0
6.8
#griinacy brdgett
Cprinacyy Isalget
Figure 7: Classification accuracy compared to the privacy budget E of DP_ DP_S L____DDDVMM (cf. Sec- tion 3. DP_ SLSSSMOSSS _SM where only the optima are perturbed, DGD (1-layer perceptron) (Abadi ct al. (2166), and AMP (SVM with objective perturbation) (Iyengar et al. 2019) on CIFAR-10 benchmark dataset (left: 5 = 10-5, right: 5 = 2 10-8 < 1/datoset size). For comparison, we report a non-private SVM baseline.
17

---

F.1 SETUP OF THE ABLATION STUDY
PP_SMO__ SVM-based experiments, we used the liblinear (Fan et al. 2008) library via the Scikit-Learn method LinearSV for classification. Liblinear a fast C++ implementation that uses the SVM-agnostic sequential minimal optimization (SMO) procedure. However, it does not offer guaranteed and private convergence bound.
For DP
More specifically, used the Le-regularized hinge loss, an SMO convergence tolerance of tol == 2 1-10-12 with maximum 10,000 iterations which were seldom reached, and a logarithmically spaced inverse regularization parameter C E { [3, 6] 10 (1, 63 10-7 {1, 2, 3,3,3 6] 10 (1,2,3, 6) 10-5, (1, 10-1). To better fit with the LinearSVC implementation, the original loss the number of data points. Furthermore, appropriate - up SMO __SV training we extended the range of the hyperparameter C whenever 10-3 which becomes relevant in scenario with many users and few data experiment, the best performing regularization
function is rescaled by 1/4 and C' is set to 1/A n with
for distributed DP_SMC
points per user. Similar to DP SLDDSGGD-MMaa parameter C' was selected for each parameter combination.
The non-private reference baseline uses a linear SVM optimized via SMO with the hinge loss and an inverse regularization parameter C' 2 (best performing of C' E { 5 10 0.5, 1,2)).
For the ablation study, we also included the Approximate Minima Perturbation (AMP) algorithm [yengar et al. 2019) which resembles an instance of objective perturbation. There, we used (80-20)- train-test split with 10 repeats and the following hyperparameters: I, E {0.1, 1.0, 34.854), eps__e_______eeeeeee frac E (.9.-95, 98, .99). eps_ _outut_ffu frac E {.001, 11, .5). We selected (L. = 1, wes.eees_tt... mosss_tt_faeeee 0.001, eps_frac= = 0.99) as a good performing parameter combination for AMP. For better performance, we resembled the GPU-capable jigssmiiimiee from the Tensorflow Probability package. To provide better privacy guarantees, we leveraged the results of Kairouz et al. (2015a); Murtagh & Vadhan (2016) for tighter composition bounds on arbitrary DP mechanisms.
F.2 RESULTS OF THE ABLATION STUDY
For the extended ablation study, we considered the centralized setting (only user) and compare different algorithms well as different values for the privacy parameter 6. The results are depicted in 7 and display four algorithms: firstly, the diffcrentially private Support Vector Machine with SVM (cf. [Section 3.1), secondly, similar differentially private SVM
SGD-based training but with SMO-based training which does not offer a guaranteed and private convergence bound, thirdly, differentially private Stochastic Gradient descent (DP-SGD) (Abadi et al.) 2016) applied l-layer perceptron with the cross-entropy loss, and fourthly, approximate minima perturbation (AMP) [yengar al.) 2019) which based upon an SVM with objective perturbation. Note that, only DP SMO SVM and DP SGD SVM have an output sensitivity and are thus suited for this efficient Secure Distributed De-Hel scheme.
While all algorithms come close to the non-private baseline with rising privacy budgets s, we observe that although DP-SGD performs best, DP SMO_SVM comes considerably close, DP DP_SGD_ SVM has a disadvantage above DP SMO SVM of about a factor of 2, and AMP a disadvantage of about factor of 4. We suspect that DP-SGD able to outperform the other variants as is the only contestant which directly optimizes for the multi-class objective via the cross-entropy loss while others are only able to simulate it via the one-vs-res. (ovr) SVM training scheme. Although DP SMO_SVM renders best of the variants with an output sensitivity, it does not offer privacy guarantee when convergence is not reached. In the case of AMP, we have an inherent vistdvantage of about a factor of 3 due to an unknown output distribution, and thus bad composition results in the multi-class SVM. Here, the privacy budget of AMP roughly scales linearly with the number of classes.
SWW_SSSOOSSSSSSSSS For DP-SGD. DP JGD SVM, and DP SPPSMM_SST SVM, Fig. 7 shows that smaller and considerably
more secure privacy parameter & 1/dataset_s size is supported although reflecting on the reported privacy budget e.
httpss:/scciktt-1111 httpa////akt......or.rr///llliis http://////memeee//eereee///////
leneersvc. html BSD-33-lluse license
reference implementation by the authors:
https:://githhb..cmmm/// uub/
dpm1 bbenchmark MIT license
18

---

G PROOF OF COR. 6
We recall Cor,
Corollary 6 (Sensitivity of Secure Distributed DP-Helmet). Given a configuration Ç, Secure Dis- tributed DP- (P- (cf. Alg. 2 without adding noise, i.e. (V)(T has sensitivity of s 1/u for each class k E K.
Proof. Without loss of generality, consider arbitrary class lo E K. We know that T is an s-sensitivity bounded algorithm thus
T(D( (5,k) "
max D (()
(5)
with ( and ( as l-neighboring datasets. For instance, for T = SGD_SGDDD BVM we have 2(0+ RA) NA
(cf.
Lem.
ByAlg Alg. 2 we take the average of multiple local models, i.e. avg(T(U)) = प Σ ((D(,,,K))
The challenge element- i.e. the element that differs between D and D( is only contained in one of the [24] SGD SVM's. By the application of the parallel composition theorem, we know that the sensitivity reduces to
M
max D6 ~D Vi=0....Ilu
Σ
T(D (
,C,
1
Σ
T(D1
= 88 [4
[2
Hence, the constant 1/L4 factor reduces the sensitivity by factor of 1/ul).
H
PROOF OF LEM. 7
We recall Lem. 7
Lemma 7 Given a configuration Ç and any noise scale o, then 77 MM NoO, (ō 11///133))
(O, (ō //n)22)
Proof.
We have to show that
10 D NO0
= / - NN (ā -2))))
It can be shown that the sum of normally distributed random variables behaves follows: Let X ~ M(ux,o of and Y ~ NNuy, .o?) two independent normally-disributeed random variables, then their sum Z X + Y equals Z NNxx + ,y, o + og) in the expectation.
Thus, in this case, we have
/ ))) (0., (ō 1/VRx)33 (00,
As the normal distribution belongs to the location-scale family, we get ((, (ā 1/21)22.
I PROOF OF THM.
We state the full version Thm.
Theorem 8 (Main Theorem, full). Given a configuration Ç, maximum fraction of dropouts p E [0. 1).
and a maximum fraction of corrupted clients E [0, 1), if secure authentication encryption schemes
and authenticated key agreement protocol exist, then Secure Distributed DP-Helmet(() (cfl Alg. 2)
satisfies computational (e, 8 DDP with s 2 /2 1.25 /2//0///KI [K] Va, for v = (1 + exp(=)) un)) and function negligible in the security parameter 1) used in secure aggregation.
19

---

Proof. We first show (e.8)-DP for variant M1 of Secure Distributed DP-Helmet that uses the ideal summation protocol F instead of TeccAgg- Then, we conclude from Thm. t4at for Secure Distributed DP-Helmet (abbreviated as M2) which uses the real secure summation protocol SeeAgg for some negligible function Vi (e, + v1 --DP holds.
Recall that assume at least [2]] many honest users. As solely rely the honest t | to contribute correctly distributed noise to the learning algorithm T, we have for each class similar to
Lem.
N(O. (o. 1 )3) Σ
1 )2)
NO
U
VIu
RlV
Vt. [4
19)
Vt
= (0 (ō-
)2) = NO
[4]
kIv u
Hence, we scale the noise parameter ā with 1/v2 and get
1 3)) = (O, (o
1
NO (ā-
)2).
V
V
By Cor. Lem. 7 and Lem. 3 we know that M1 satisfies (c, dD- (with the parameters as described above).
Hence, considering an unbounded attacker A and Thm. 14 we know that for any pair of neighboring data sets D, D' the following holds
Pr Pr(A(M((D) = 1] S exp(s) Pr(A)) = +]
By Thm. 14, know that TTScAgg (.. 8n)
securely emulates F (w.r.t. an unbounded attacker).
Hence, there is negligible function v such that for any neighboring data sets D, D' (differing in at most one element) the following holds w.l.o.g.:
Pr [A(22 = 1] - unn) - Pr [A (Sim)(M =].
For the attacker A' that first applies Sim and then A, we get:
Pr (r(A(M((D) 1] - - (())())))
(8)
< exp (M
(9)
thus we have
(D)) 1| S (
exp(()) v(n). (10)
From a similar argumentation follows that
Pr Pr(A(M2(D')) 1] s (xp(()
1] + (1 exp(e)) v(n)
(11)
holds.
Hence, with vs = (1 exp(e)) v(n) the mechanism Secure Distributed DP-Helmet mechanism M2 which uses TSacAge is (e, + un -DP. As u negligible and & is constant, v1 is negligible as well.
PROOF OF COR. 10
We recall Cor. 10
(User-level sensitivity). Given learning algorithm T, we say that T is R-norm bounded if for any input dataset D with N = [D], any hyperparameter S, and all classes k E K. [T(D.E, ke)] < R. Any R-norm bounded learning algorithm T has a sensitivity = 2R. In particular, T (O, (a . 3- 1..ss-a) 1a)²) satisfies (e, 8), T-group differential privacy with = N and
Corollary 10
E 2 2 1.25/16/ KI) K] 1/o, where N0, (a s- Ia)2) is spherical multivariate Gaussian noise and noise multiplier.
20

---

Proof. We know that the sensitivity of the learning algorithm T is defined as D { - kb)ll for T-neighboring datasets D, Thus, in our case we have 2R since any k) E I-R, R]. As this holds independent on the dataset and by and by Lem. 16 we can protect any arbitrary number of data points per user, i.e. we have T-group DP.
K GROUP PRIVACY REDUCTION OF MULTIVARIATE GAUSSIAN
Lemma 16. Let N(A BB) [z]] denote the probability density function of the multivariate Gaussian distribution with location and scale parameters A, B which is evaluated on an atomic event x. For any atomic event x, any covariance matrix E, any group size N. and any mean pa we get
pdf [2]]
pdf [7/4]
(12)
pdf Ndf [x]
w [/A]
Proof.
pdc p [x]
(2 exp( 1:p(-2x7'2> xx)
(13)
pdl ((w, [x]]
( exp(
(x - 11) 12 (x
= la 1n 12- 10
1
=exp(
11
1 x - x p 1 -1125-111)) k))
(14)
2
1
=exp(-
22
1- 1 nn
(15)
2
for μl = k/4
1 kk( 11(-1/
=exp(- 1
-ー
x
M1 + + シー #1/k)
(16)
2
for x = 2/k
exp((
(-Mi 1'
- - / Σー 11))
Σ
(17)
2
1
= =exp(
(-yi Σ
+ 7 Σ エー 11))
(18)
2
[e expl | デーーーーーンン
(19)
2) exp(
(x) - ( 1 (1))
pdf
[+/A]
(20)
pdf pdf
As the Gaussian distribution belongs the location-scale family, Lem. 16 implies that the (c, DDP guarantees of using (0, 22 Σ) noise for sensitivity A: and using N (0,0 Σ) for sensitivity 1 are the same.
L REPRESENTING MULTIVARIATE GAUSSIANS AS UNIVARIATE GAUSSIANS
For the sake of completeness, we rephrase a proof that we first saw in Abadi et al. (016)) that argues that sometimes the multivariate Gaussian mechanism can be reduced to the univariate Gaussian mechanism.
Lemma 17. Let pdf ((g.ding(o?)) denote the probability density function of multivariate (p 2 1) spherical Gaussian distribution with location and scale parameters μ E IR o E Rp. Let Mpause.p.q be the p dimensional Gaussian mechanism D + (D) + NO 0² Ip) for 0² >0 of a function q D - R", where D is the set of datasets. Then, any 2 1, if q is s-sensitivity bounded, then for any p 2 1, there is another s-sensitiviyy bounded function of D > R such that the following holds: for all ε > 0, 5 [0, 1] if M Mgauss, 1.4 satisfies (e, -ADP, then M gonsss.pg satisfies (c, 8)ADP.
21

---

Proof. First observe that for any seseniitvviyybooudee function q", two adjacent inputs D, D' (differing in one element) with ( - DD' = are worst-case inputs. As a spherical Gaussian distribution (covariance matrix Σ = 0² Ipxx) is rotation invariant, there is rotation such that the difference only occurs in one dimension and has length 8. Hence, it suffices to analyze Hence, the privacy loss distribution of both mechanisms (for the worst-case inputs) is the same. As result, for all e 2 0,8 E [0, 1] (i.e. the privacy profile is the same) if (e, AD holds for the univariate Gaussian mechanism it also holds for the multivariate Gaussian mechanism.
univariate Gaussian distribution with sensitivity
M STABILITY OF AVERAGING MODELS
Definition 18 (Uniform Stability, Definition 2.1 in Hardt et al. (0166). Let f(h, z) denote loss function on hypothesis h and instance z. A randomized algoritim A is c-uniformly stable for all datasets S, S' E z" of size n such that S and S' differ in at most one example, we have
f(A(S"); 2)) S Sstub
Theorem 19 (Averaging models is uniformly stable). Given set of users U E u each with local data set D(s) E Z originating from an unknown data distribution 2, learning algorithm with a Atstonggyy convex, L-Lipschitz. and 3-smooth training objective [f.. D K) on model parameters f (like SGD_SVM of Alg. 1 an averaging routine (vg(T((()) |ল T(D ,, K)
with V U,:41 ( (like in Alg. 2). and the projected SGD update routine for c-norm clipped data point (i) D and class is K, ie.. s1it III I fm 04 as
((
(3) [[ 2m k)) G, then
for a constant learning rate I 1/8, M steps, and N = [6] total data points, T is Cuab unifforlly stable in the sense of Bousquet & Elisseeff (2002) with
2L
[_DSGD__svi [J
LLez (avgg(((()) 2, S EsTab I
E ((
AN
Proof. By definition of uniform stability (Hardt al. 2016 Definition 2.1), it suffices prove (cf.
Hardt et al. (2016, Theorem 2.2))
sup Eq z.k
J 2
Σ
2,
J(
Σ
( M
2, kc)
S
Cytab
[4
with T( and f = T(D((), k, respectively after M steps where
D LDDOUUDD D'O are 1-neighboring datasets.
We know due to the Lipschitz condition that for given 2, k
44
E
J
M
( J
k,
(3) M
2, k))
< L [6
U
with 8m
44
(()
प 14
[2
Next, we need to bound [[δM] by defining a modified growth recursion (Hardt et al. 2016 Lemma 2.5) for two arbitrary sequences of gradient updates GI...., GM and G....., G the starting point
(5) ((1) any i [4[], and some j [1, [1] as
fo
8n =0
m/pm
if ( =000) is exxaanssvve if Gli) and G(()) a-bounded, G(0) is n-expansive"
8mt1 <
nmmm
+
Ed
Note that we consider the differing element occurring only in one local gradient update and not in each one. We recall the definition of gradient update fm+1 Gm (fm) and f G (.%a)-
22

---

Proof. growth recursion (case 1).
8m+1
Gm((
Gm (fm)
[
-
p(0)
(Expansiveness, cf. Hardt et al. 2016
Definition 2.3))
U
2
n/mm
Proof, growth recursion (case II).
[4]
dm+1=
GmL(tn)) - (((())))))
Gm (F Go, ((H)))
U
[2]
i=
R
U
== Li
- -
G. (ftt)) Gm (f+1))
[
R
(m(( - (m)
21
==
(m((lh))) - (L(())
G (m(()) - Gm (1
[2
12
(G))) Gm (m)())))
24
1
MG)
G'm G'm (fat)))
[
20 [
S 170m +
(Expansiveness and o-boundedness, cf. Hardt et al. (2016) Definition 2.3)).
Having established the growth recursion, occurrence as well as calculate the corresponding n-expansiveness and o-boundedness terms. Hardt al. (2016) Lemma 3.3) have shown that have aL-boundedeess for L-Lipschitz objective function as well as (1 (1-aA) -expansiveness for learning rate < 1/3 and a 8-smooth and A-strongly convex objective function (cf. Hardt al. (2015) Proof of Theorem 3.9)). Since each user samples during each training iteration one data point, we have for given iteration probability of /N that an individual data point of Ü has been chosen resulting in differing gradient updates G(i) # G Thus, we have
combine the bounds with their probability of
U N
[24] N
20m
E(ōm+1] S (1
n [[6m]
(n E[6m]
[21
[ N a. aAA)((mm)
U 2aL
< (1
(1 aA)) E(ōm)
[(5m]
N
N
M
20L N
= - aA E[8m]
+
The remaining part goes by the proof of Hardt et al. (0055 Theorem 3.9) with the Lipschitzness of the training objective as well as the growth recursion [[m+1].
In short, we unfold the recursion:
2La N
2L
ElgM]
Σ (1
aA)m
AN
m=1
23

---

and insert it into initial bound which gets for all lt and any
4
1
2L
F
J
M
2
J
Σ
(E)) M
k)
AN
Note that this proof permits the learning rate scheduling in Secure Distributed DP-Helmet which has been set to Otm = min(1 (2/2, 1/Am) for iteration m and the 3-smooth and A-strongly convex objective.
N CONVERGENCE OF AVERAGING MODELS
Definition 20 (Convergence). Let f(,, 2) denote a loss function on hypothesis and instance a and (h) = [ST EEes f(h,,) E
the empirical risk on some dataset S. An algorithm A converges with rate Conn under a data distribution if
Esez (Be2(Fs(A(S)) inf Fs S Conee-
Theorem 21 (Averaging models converges). Given a set of users U E U each with a lo- cal data ser D learning algorithm T with a A-strongly convex, L-Lipschitz, and 3-smooth training objective J(f K) model parameters f (like SGD_SVM of Alg. 11, an averag- [o| Σ.4 T(D()), ,, with U = U D (like in Alg. 2), and the projected SGD update routine for a c-norm clipped data point (0) E D(9) and class k E K, i.e. 1 [ (112 an 85 J( 2m k) G. then for diminishing learning rate O'm =min ).)) M steps, a given 7 = { gences to = argmin, I (f) with
ing routine (v)(T())) 1
li )(0) salp. and a bias term T conver-
31.2
E[J ((Tg (TU)), [(f.; Ceom
(M - 11 + 6(M - 1) 2 O(M-1).
2A2
The bias term depends on 7,3,A A, 1 I.
Proof. The proof is based on Nemirovski et al.'s proof of convergence for strongly convex LVD_SVM
training. (Nemirovski et al.] 2009 Section 2.1). Subsequently, we abbreviate the output of the learning algorithm iteration m for the i-th user with f(i) T(D()) (..((()..))) k). First, we define the convergence criterion Am at the iterate m and then its recursive growth Am+1-
M
Am
fo
2
ビ=0
Our convergence criterion describes that we measure and subsequently seek to bound the difference in the weights between the averaged I's
1
Ei ) and the optimal weights fa for the loss J on
[
24

---

the combined data of all users. Subsequently, abbreviate G(f) 8. J(
R4
1
Am+1
E
Unssn(f - am G(f f f.
2
U
27
14
1 E
UInss( - am G(f(() - Hns sn(f))
2
U
R4
1 $ E
f(0
am ama G(f(() - f.
2
U
(binomial expansion (Ir
y, y) (z, x) + 2 8) + (y. y) and linearity of expectation)
Am
1 E
a
G
am E
1
f(i))
f.)
1
Σ )(
U
U
Recall that because of the T-Lipsehitz continuity of J.
||GDI
S L.
Hence,
D. G( 119 -E
G
M Σ
i
(
L2 We now have for the recursion
1 L2
Am+1 S Am am E
f(()
GL)
(
U
U
Recall, strong convexity states that (J' (V)() -1 -11 .V'
Hence, we
also know for the optimal f. that (f f-) 2 - f.ll Vf' With f [. we conclude
14 .(i)
Jm
M
E
M
G
G
2 E
M
1
fx
= 2p.m.
7
2=
1=0
The strong convexity constant μ A can be determined by H (JUJU, D(.) () Z AT, where H is the hessian matrix, I the identity matrix and B > il means that B - rl is positive semi- definite. As the argumentation above about J's strong convexity holds for any also holds for
In summary, we now have
Amt1 S (1 2 a I.2
(21)
The smoothness assumption can be equivalently formulated as ( vS 3 ||ʃ f'll VS. e I()) < ( + f - 1 + [[{[(()) S s, Similarly to the argumentation above, since beta smoothness holds for any f. also holds for f [7 Σ |4 Thus we conclude that
<
(0)
4
J
-
B
fa
BAM
2
im0
By unraveling the recursive formula of Aus (cf. Eqqution (21)
we get with the base case Ag
M
M
M
< 3
Σ
I
- 2Aan
2 o
1
1
+ 8
II 1 2Aan
Ao.
m=1
#=
==1
25

---

Recall the learning rate am min( B. Xm/) At mu
switching the learning rate from
/ to
First, we consider the case m S Mg where we rewrite for a constant learning rate Cm 8 and
Am
L2_
25
21
mo
Mig
2)
A
mo II n=1
A 3
E
( mig
U.
J(v.
5
Σ
II \==++1
+
Ao
1=0
m==
mn
S 4
ma
+ mo
A) D¹
Next, we consider the case m > mg where we rewrite for diminishing learning rate O'm
1 Amn
as
well as <
H
E
J
J
-
U
1m0
2
1 2 b'
Σ
m
(nmm+11 m=
V=m++1
M
M
71
(mo 1)mo, R'
55
m
(M 1)M
m=
n=m++
1- 1/m
-1
(mo 1)mgb'
(M
1)M
(M 1)M
M
+
((mp 1)mpb' - -mo)
(M 1)M
(M 1)M
< <(M - 1) b(M 1
If we approach M to co, i.e. assume a sufficient number of iterations, we further simplify
2
lim
E
J
H -
=0
M 100
U
1=
which proves the convergence.
Note that the bias term depends on how many iterations are conducted with the constant learning rate 1/9.
26


Reviews:
[{"review_id": "qKziuDcaCK", "reviewer": "Reviewer_a5Qe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper works on the efficiency of distributed differentially private learning without a trusted server. The main idea is that each user first trains the local model. Then the sever aggregates the local minimizers with only a single call of Secure Multi-Party Computation (SMPC).", "summary_of_the_review": "My recommendation is mainly based on 1) one important baseline is missing; 2) there is neither strong empirical performance nor a reasonable theoretical utility bound. Please see Strength And Weaknesses for possible improvements.", "strength_and_weaknesses": "To better understand the position of this paper, here are two alternative options in the literature. \n\n**Option A**. Each user perturbs the local gradient and then sends the noisy gradient to the server. The serve then broadcasts the aggregated gradient. Such communication is repeated for many times. This approach has a high communication cost because there are many rounds. The variance of noise is also large because it depends on the local data size $n_i$ instead of overall data size $N$ (bad utility, bad communication cost, the baseline in this paper). \n\n**Option B**. All users use SMPC to send noisy gradients to server, the noise variance in aggregated gradient is small because it scales with $1/N$ instead of $1/n_{i}$. The noise variance depends on overall data size, but the communication cost is even higher because 1) one still need to run multiple communication rounds; 2) each call of SMPC is more expensive than standard communication and the cost of SMPC scales with the number of users (good utility, bad communication cost, not evaluated in this paper).\n\nThe authors try to design an algorithm that is good in terms of both utility and communication cost. The main design choices are 1) they use an advanced SMPC protocol (Bell et al. 2020), which could scale to millions of users while the protocol used by previous works cannot; 2) they only call the SMPC once; 3) in order to maintain reasonable accuracy, they use a pre-trained feature extractor and only train local linear classifiers. The authors show the proposed algorithm is significantly faster and, in some cases, achieves higher accuracy than Option A.\n\nIn general, I think this work is a good attempt towards solving an important problem, i.e., making the algorithm good in both criterions. However, there is still room for improvement. Please see my comments/suggestions below.\n\n1. An important baseline is missing. This paper does not evaluate the algorithms take Option B, e.g., [1]. Note that those algorithms could also scale to millions of users with the advanced protocol. A fair comparison would be all algorithms use the same protocol. In terms of efficiency, such a comparison would demonstrate the efficiency advantage of calling only a single SMPC. In terms of utility, it is important to show the drop in accuracy. The drop in accuracy seems non-negligible. With a pretrained feature extractor+linear classifier and eps=0.5, [2,3] both achieve ~90% accuracy on CIFAR-10 (see Figure 5 in [2] and Table 3 in [3]) while the accuracy in this work is $<$70%. \n\n2. Although the noise scales with $1/N$, the utility guarantee of the aggregated model would not scale with $1/N$ because each local minimizer only sees $n_i$ datapoints. This may be inevitable if you only allow a single SMPC. However, if you run SMPC $log(N)$ times, it is possible to have a global utility guarantee scales with $1/N$. A simple example is Option 2 with DP-GD, which is studied in [1]. I think a good distributed private learning algorithm should have a utility bound scales with $1/N$. If the authors are interested in this direction, I would recommend papers about variance reduced methods in the non-private distributed learning setting, e.g., [4]. The basic idea is to let each user minimize its local objective (inner loop) and only occasionally run synchronization (outer loop), which would result in fewer calls of SMPC than DP-GD.\n\n3. The utility of the local minimizer may be improved with gradient perturbation (DP-SGD or DP-GD). The current version uses output perturbation on the minimizer of a regularized Huber loss. Note that DP-SGD and DP-GD usually achieve better empirical performance (see [5]) despite they add noise at every step. The reason may be the noises added in earlier iterations get corrected by later gradient updates.\n\n[1]: Distributed Learning without Distress: Privacy-Preserving Empirical Risk Minimization, https://proceedings.neurips.cc/paper/2018/hash/7221e5c8ec6b08ef6d3f9ff3ce6eb1d1-Abstract.html.\n\n[2]: Differentially Private Learning Needs Better Features (or Much More Data), \nhttps://arxiv.org/abs/2011.11660.\n\n[3]: Do Not Let Privacy Overbill Utility: Gradient Embedding Perturbation for Private Learning, https://arxiv.org/abs/2102.12677.\n\n[4]: Convergence of Distributed Stochastic Variance Reduced Methods without Sampling Extra Data, https://arxiv.org/abs/1905.12648.\n\n[5]: A Practitioners Guide to Differentially Private Convex Optimization, https://icml.cc/Conferences/2021/ScheduleMultitrack?event=12667. You can find the presentation at https://slideslive.com/38964861/contributed-talks-session-2?ref=folder-87822 (starts ~32:20).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "omtYDoD7i23", "reviewer": "Reviewer_p4WT", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a scalable differentially private distributed learning framework for protecting privacy over distributed dataset. The scalability of the framework is based on a scalable secure summation protocol.  The privacy of the framework is achieved by aggregating the noise of non colluded users in an oblivious way instead of distributed noise generation over millions of users. They also consider a combination of SimCLR pre-training with linear convex private learning (DP-SVM) to achieve better performance. \n", "summary_of_the_review": "The paper proposed a scalable differentially private distributed learning framework. However, the idea of integrating pre-trained model extractor with private convex model is not new. Also, the combination of DP with SMPC is also not new. ", "strength_and_weaknesses": "Strengths:\n1. The problem of achieving privacy protection in distributed learning is timely and important, especially over large number of users.\n2. Considered the combination of pre-trained model and private linear models to improve the model performance and communication efficiency. \n3. Provided the uniform stability and convergence of proposed methods. \n\nWeaknesses\n1. The presentation of the proposed framework is not clear. The paper is quite hard to understand what kind of framework it proposed. It is better to give some figures for the framework and how the SimCLR-based pretraining is integrated in the whole pipeline. \n2. Many related works on SMPC + DP are ignores and do not provide comparisons in the experiments, e.g., [1] Jayaraman, Bargav, Lingxiao Wang, David Evans, and Quanquan Gu. \"Distributed learning without distress: Privacy-preserving empirical risk minimization.\" Advances in Neural Information Processing Systems 31 (2018).\n3. The reason for introducing the computational DP is not clear.  \n4. How the pretrained model affects the model performance is not clear. \n5. Why is the dimension of Gaussian variance $(p+1)\\times K$ instead $p \\times K$?\n6. Please provide the utility and privacy tradeoff for the private version of Algorithm 1 and the comparison with common private erm methods, e.g., Wang, Di, Minwei Ye, and Jinhui Xu. \"Differentially private empirical risk minimization revisited: Faster and more general.\" Advances in Neural Information Processing Systems 30 (2017).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3IdLVSM3qtO", "reviewer": "Reviewer_7DLA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies how to reduce the number of MPC rounds in privacy preserving learning.", "summary_of_the_review": "While the authors seem to know good techniques, i dont see how the current paper uses them for a coherent contribution.", "strength_and_weaknesses": "\nThe exact claimed contribution isn’t very clear.  Even though compared to the earlier NeurIPS submission the authors added a “contributions” paragraph in the introduction, (a) several items in the bullet list are not contributions themselves but more properties of a contribution described earlier, and (b) the description of the contribution doesnt specify clearly to what extent this contribution improves over the state of the art.\n\nIt is unclear to me why the presented algorithm could run with a single SMPC invocation.\n\nAs already stated in my neurips 2022 review, it is unfortunate that the whole paper focuses on a single dataset (Cifar-10).\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "1PFQeMV0Jj-", "reviewer": "Reviewer_qk3x", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "the paper proposes a method that combines transfer learning (based on fitting linear model on pretrained features), secure aggregation, and differentially private mechanisms, to achieve secure and private machine learning. authors empirically compare against DP-FL and claim performance improvements in the large user regime. ", "summary_of_the_review": "the paper proposes a method that combines transfer learning (based on fitting linear model on pretrained features), secure aggregation, and differentially private mechanisms, to achieve secure and private machine learning. while interesting, the works have several technical and writing issues that can be improved on. ", "strength_and_weaknesses": "strength: the idea of introducing secure aggregation into private machine learning is interesting. this idea likely helps bypass certain limitations of federated learning under local DP in terms of utility (albeit introducing new, but perhaps mild, assumptions, e.g., at least half the users are honest). \n\nweakness: while the main idea makes sense, there are several technical as well as presentational issues which lead to the paper being hard to read. in addition, some of the results / claims are hard to verify (and i personally doubt some claims are true). i list the main points below. \n\n- it's unclear what model of a \"dishonest user\" this work assumes. for instance, in distributed computing, there's this notion of byzantine nodes, which essentially means that they can do whatever they'd like. in milder models, a dishonest user might just be assumed to fail without tampering with aggregation (but also not provide their data). i'm assuming the claim that \">50% users being honest implies secure aggregation works\" is dependent on a precise notion of a \"dishonest user\" whose definition which i was not able to pinpoint in the main text. in the extreme case, what if i assumed the dishonest user is omnipotent and was able to \"steal\" the key of all honest users? wouldn't that give the dishonest user the ability to revert the noise? \n\n- algorithm 1 seems problematic in several ways. \n  - the loss defined on 2 is independent of datapoints whose y is not k. this would mean that the models trained here are only increasing the margin for the positive class -- the margins for the negative class is not penalized, and can grow however they like. there's a chance i might be missing something, but i'd be very surprised if this loss gives high-performing models. can authors clarify how they train these models and perform inference? \n    - personally, i'd perhaps use the loss J = L2 reg + average of l_huber ( f clipped(x) [ 1[y = k] - 1[y \\ne k] ] ), which takes the negative classes' margin into account. \n  - for privacy purposes, i can somewhat see why the loss on line 2 is desirable -- it ensures that each data point only affects the loss of a single model. one could probably argue that this gives a smaller sensitivity (than naive joint release, which produces a \\sqrt{K} factor), though this nuance is not explicitly mentioned in the main text. more generally, if one uses the loss i defined above (the one that penalizes small margins for both pos and neg classes), one cannot assume the joint release still has sensitivity s, but would rather need the conservative bound of \\sqrt{K} s (s is sensitivity of single model release for a particular k). section 3.1 in the main text does not make these points explicit. \n  - have the authors tried the simpler logistic regression? the loss for multi-class logistic regression is strongly convex, and lipschitz (for bounded iterates), and does not possess this awkward one-vs-rest problem with SVMs. \n\n- the authors frame their method with training linear models as an integral component. note while the framework is generally applicable to strongly convex and lipschitz losses (where coefficients are known), the overall method is limited to convex problems, and cannot be applied to when linear model adaptions cannot work well. \n\n- given the strong resemblance to early works such as PATE, i'm surprised the similarities and differences are not discussed. i personally can figure out these, but this job should not be left to the reader solely. some references below. \n\nPapernot, Nicolas, et al. \"Scalable private learning with pate.\" arXiv preprint arXiv:1802.08908 (2018).\nPapernot, Nicolas, et al. \"Semi-supervised knowledge transfer for deep learning from private training data.\" arXiv preprint arXiv:1610.05755 (2016).\nChoquette-Choo, Christopher A., et al. \"Capc learning: Confidential and private collaborative learning.\" arXiv preprint arXiv:2102.05188 (2021).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject