Differential Privacy in Scalable General Kernel Learning via $K$-means Nystr{\"o}m Random Features
Authors: Bonwoo Lee
Jeongyoun Ahn
Cheolwoo Park
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
kernel learning
kernel mean embedding
kernel empirical risk minimization
Primary area: privacy

Abstract: As the volume of data invested in statistical learning increases and concerns regarding privacy grow, the privacy leakage issue has drawn significant attention. Differential privacy has emerged as a widely accepted concept capable of mitigating privacy concerns, and numerous differentially private (DP) versions of machine learning algorithms have been developed. However, existing works on DP kernel learning algorithms have exhibited practical limitations, including scalability, restricted choice of kernels, or dependence on test data availability. We propose DP scalable kernel empirical risk minimization (ERM) algorithms and a DP kernel mean embedding (KME) release algorithm suitable for general kernels. Our approaches address the shortcomings of previous algorithms by employing Nyström methods, classical techniques in non-private scalable kernel learning. These methods provide data-dependent low-rank approximations of the kernel matrix for general kernels in a DP manner. We present excess empirical risk bounds and computational complexities for the scalable kernel DP ERM, KME algorithms, contrasting them with established methodologies. Furthermore, we develop a private data-generating algorithm capable of learning diverse kernel models. We conduct experiments to demonstrate the performance of our algorithms, comparing them with existing methods to highlight their superiority.

Differential Privacy in Scalable General Kernel Learning via K-means Nyström Random Features
Bonwoo Lee
Jeongyoun Ahn" KAIST Daejeon, 34141 South Korea
Cheolwoo Park
righthim@kaist.ac.k.
jyahnOkaist.ack ac. kr, parkc:2021@kaist. ac. kr.
Abstract
As the volume of data invested in statistical learning increases and concerns re- garding privacy grow, the privacy leakage issue has drawn significant attention. Differential privacy has emerged as a widely accepted concept capable of mitigat- ing privacy concerns, and numerous differentially private (DP) versions of machine learning algorithms have been developed. However, existing works on DP ker- nel learning algorithms have exhibited practical limitations, including scalability, restricted choice of kernels, or dependence on test data availability. We propose DP scalable kernel empirical risk minimization (ERM) algorithms and DP ker- nel mean embedding (KME) release algorithm suitable for general kernels. Our approaches address the shortcomings of previous algorithms by employing Nys- tröm methods, classical techniques in non-private scalable kernel learning. These methods provide data-dependent low-rank approximations of the kernel matrix for general kernels in a DP manner. We present excess empirical risk bounds and computational complexities for the scalable kernel DP ERM. KME algorithms, con- trasting them with established methodologies. Furthermore, we develop private data-generating algorithm capable of learning diverse kernel models. We conduct experiments to demonstrate the performance of our algorithms, comparing them with existing methods highlight their superiority.
1 Introduction
As data collection and access continue expand, protecting privacy has emerged crucial concern. Differential privacy (DP), introduced by Dwork et al. (2006b), stands as the current gold standard in data privacy. It provides rigorous framework for privacy in statistical procedures, wherein noise is added proportional to the maximum deviation induced by the change of a single individual in the dataset. The field has seen significant advances differentially private (DP) algorithms for machine learning. Notably, DP empirical risk minimization (ERM) has become key area of research, attracting extensive attention (Chaudhuri al., 2011; Kifer al., 2012; Bassily et al., 2019; Wang et al., 2019; Feldman et al., 2020). These efforts focus on developing models with high generalization capabilities across various ERM problems, including regularized regression, logistic regression, support vector machines, and some other ERM problems equipped with non-convex or non-smooth loss functions. However, vast majority of the current DP ERM algorithms primarily address linear ERM, suitable for datasets with linear structures.
preeeccvress statistical
Kernel methods hold significant importance in machine learning due to their ability to capture intricate, non-linear structures. Kernel-based learning is ubiquitous in both supervised and unsupervised settings as well as in hypothesis testing problems. For an extensive review on the subject, see Muandet et al. (2017). This work focuses the supervised kernel learning problem via ERM well as kernll mean embedding (KME) for probability distributions. Developing a DP framework for general kernels
"Corresponding authors
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

poses significant hurdle due to their reliance on the local attributes of the data. For instance, not every kernel amenable a well-behaved DP solution. As rather extreme case, the Kronecker delta kernel, ((x,,) y) = (z = y), yields meaningful solution only when the test data exactly matches one of the training instances. Consequently, the solution becomes highly sensitive to the data changes, exhibiting substantial deviations with even a single data alteration.
As a result, there has been relatively little DP research regarding kernel ERM, especially compared to linear counterparts. Chaudhuri et al. (2011) suggested transforming kernel ERM into linear form via random features, which facilitates scaling- down operations. However, their method is limited to invariant kernels, excluding wide variety of other kernels, such as polynomial kernels or the pyramid match kernel from the computer vision domain (Grauman and Darrell, 2007), the chi- chi-squared kernel in hand gesture recognition (Abadi al., 2015), Histogram intersection kernel in image classification (Maji et al., 2013), Bayesian kernel in protein prediction (Alashwal et al., 2009), and the diffusion kernel in manifold learning (Lafferty and Lebanon, 2005). Hall et al. (2013) proposed perturbing the output function of kernel ERM. Although their work can be applied to general kernels, lacks scalability in practice (e.g.. (n²) in kernel ridge regression). Additionally, it requires access to the training data for every prediction, posing a potential threat of privacy leakage. The DP kernel ERM proposed by Jain and Thakurta (2013) can work with general kernels; however, its utility is guaranteed only when test data are accessible.
translation iinaariion-nvvariant
KME is a pivotal tool in diverse applications such as two-sample testing and synthetic data generation (Harder et al., 2021). It enables the comparison of probability distributions via metric in Reproducing Kernel Hilbert Space (RKHS). by embedding these distributions into elements of the RKHS. Ad- ditionally, Balog et al. (2018) found utility of KME for the private release of data. The embedding itself acts as a concise representation of the distributional information of the data. However, their methods appear to suffer in high-dimensional settings. Moreover, it is important to note that the DP functional release algorithm suggested by Hall et al. (2013) cannot be directly applied to DP KME. This limitation arises because the output is not a member of the RKHS, which is a crucial distinction since statistical methods related to KME heavily depend on operations within the RKHS.
Our study is motivated by the frequent oversight in prior research of the practical challenges in real-world implementations, such as scalability, private implementation without access to test data, accurate DP KME release, and the lack of information algorithms designed for practical DP kernel ERM by integrating the Nyström method. Although the Nyström method has been a state-of-the-art technique with random Fourier features in scalable kernel learning, this work is the first to apply it to DP kernel learning. The proposed algorithms are designed to be scalable and are suitable even for unregularized learning or non-convex loss functions. Morcover, we demonstrate that our Nyström- based techniques can be used to construct DP estimate of KME, which can be utilized for private two-sample tests via maximal mean discrepancy, for example. We also address the cases where the model is unknown, such as in public releases of private data, by employing an algorithm that releases versatile private data suitable for kernel ERM with diverse objectives.
future private data use. We propose
1.1 Related Works
DP ERM. ERM serves fundamental tool in machine learning, with substantial literature on DP ERM dating back to Dwork et al. (2006b). Among the current works, most of which regard linear ERM, main approaches include output and objective perturbation methods (Chaudhuri et al., 201 1; Kifer et al., 2012; Jain and Thakurta, 2014; McSherry and Talwar, 2007; Gopi et al., 2022, 2023; Mangoubi and Vishnoi, 2022), and gradient perturbation methods (Bassily al., 2014; Wang et al., 2017: Song et al., 2013). However, Iyengar et al. (2019) pointed out that most output or objective perturbation-basse algorithms suffer from scalability issues in their implementation. For example, they need to directly access optimal solutions in order to release private models, thereby reducing scal- ability, particularly in kernel learning, Additionally, they often require strong assumptions on learning problems to guarantee privacy, such as double differentiable loss or strongly convex regularizer, which limits the range of applicable learning scenarios (lyengar et al., 2019). In contrast, gradient or SGD- based output perturbation methods (Wu et al., 2017; Feldman et al., 2020) are relatively unconstrained by learning restrictions or scalability concerns. While a vast amount of literature exists on linear ERM, not all DP kernel ERM algorithms can capitalize on these findings.
DP kernel ERM and KME. To adapt techniques from DP linear ERM to kernel ERM, one needs random features of the kernel suitable for DP learning. Random Fourier features were suggested as
2

---

candidate for translation-invann kernels (Chaudhuri et al., 2011), but none have been proposed for general kernels. Hall al. (2013) and Jain and Thakurta (2013) addressed DP kernel ERM algorithms for general kernels without using random features. However, Jain and Thakurta (2013) assumes accessible test data, which may be inappropriate in certain cases. On the other hand, Hall al. (2013) suggests sophisticated method for releasing a private model but requires strong regularization. Moreover, both algorithms need the true solution before releasing the private model, resulting in scalability issues. The discussion on DP KME has been somewhat distant from DP kernel ERM, initially introduced by Balog et al. (2018) as a technique for private database release. Balog et al. (2018) developed private algorithms for releasing KME for both general and craslltion-invariint kernels. However, their methods suffer from the curse of dimensionality in both cases. Additionally, note that the techniques in Hall et al. (2013) and Jain and Thakurta (2013) cannot be directly adapted to DP KME release.
1.2 Main Contributions
Scalable DP kernel ERM for general kernels. We develop scalable algorithms for DP kernel ERM that accommodate general kernels, particularly non-translation-invaiiar ones. The Nyström method serves principal tool that enables much-desired scalability in practical applications. Our work is the first to propose a DP K mmeans Nyström method and incorporate it in DP kernel ERM. Also, to the best of our knowledge, this the first attempt to compare the theoretical and experimental efficacy of scalable private kernel learning algorithms. The proposed algorithms reduce time complexity and memory costs, akin the Nyström method non-private settings. Furthermore, experiments in Section 4 demonstrate the superior performance of our algorithms for different learning problems. We present a brief comparison of our approach and three existing methods in Table
Table I: Comparison of DP kernel ERM algorithms in terms of restrictions for privacy guarantee.
Algorithms
General kernels
Scalable
Test data free
General objective
Chaudhuri et al. (2011)
Jain and Thakurta (2013)
X
X
Hall et al. (2013)
X
Proposed
DP KME. We propose a data-dependent DP KME releasing algorithm based on the DP K K-means Nyström method. The error of the DP KME is shown to be primarily related to how accurately the kernel matrix is estimated by the Nyström method. Our empirical study suggests its superiority compared to alternative DP KME releasing algorithms.
Private data release for versatile kernel learning. We consider the offline setting for database release, where the database owner releases data without knowledge of the models or statistics desired by users. We provide DP algorithm that generates dataset yielding excess empirical risk bounds of O(n ") for the logistic and the Linex (Ma et al., 2019) losses it is used for kernel ERM.
2
Preliminaries
2.1 Differential Privacy
Among the numerous variants of DP, this work primarily employs (c, 8DDP, as it is widely applicable to various statistical procedures. Let X' be the data space. We consider randomized algorithm M X + P (Z), where P(Z) is family of distributions over an output space Z. Let D D indicate that datasets D and D' are neighbors, meaning they differ only by a single individual.
Definition 2.1 ((c, DD,, Dwork et al. (2006a)). An algorithm M is (c, 6)-DP if the following holds:
sup sup (M e A) c'P (M(D') E A) S 8. D D.D'CX= D'D'' AC2
Definition 2.1 states that algorithm is DP if its randomness is proportional to the deviation in the output due to a single data change, as demonstrated in Proposition 1.
Proposition 1 (Gaussian mechanism, Nikolov et al. (2013)). If a deterministic algorithm A x R satisfies D' (AA()))))))))))))))))) - A(D))l2 & Â, an algorithm defined by M(D)
A(D) + A A(1+/2log ! (e, 8D- where E follows the standard normal distribution on Rd
3

---

Statistical procedures, including the algorithms we propose, typically involve multiple steps, such as data-dependent evaluations and multiple references the data. Proposition 2 provides privacy guarantee for such procedures.
Proposition 2 (Composition theorem, Dwork et al. (2006a)). For algorithms M1 x + P()) and M2 : Xn 2 P(W), the algorithm M : x - 2 defined by M(D) = MM MD) for D C Rm is (el + E2, 61 + DDP if Mi is (e1, DDP and M2(-;²) 2)) is (22,02)-DD) for every 2 E 2.
2.2 Kernel, RKHS, and Random Features
Kernl methods learn non-linear structure by using non-linear map, called a feature map 6. to transform the data (x; )i=1 and analyze the linear structure of {<(x;) j==1- An appropriate choice of captures the underlying complex structure of the data. The feature maps are inherently determined by the kernel function k, a positive definite function with corresponding RKHS (He, ll-l/ satisfying (6(x)), (, = k(x,, y). Within the RKHS, the outputs of the feature map behave akin to vectors in Euclidean space, allowing
to learn the non-linear structure through linear model.
A random feature is map 9 X + R" that approximates the kernel function in a way that ((x,g) y) = ((((z), (Q))). providing linearized version of kernel learning, as will be discussed in Sections 3.2 and 3.3. Traditionally, k(z, y) = [[((((), p(y)) is required for random feature map, but we adopt a more broad terminology.
2.2.1 Nyström Methods
Nyström methods are low-rank kernel matrix approximation methods that facilitate scalable kernel learning. For given dataset {=:]]=1 C X, and kernel matrix K, the approximation K is calculated as K = Kzx Ky Kzx where Kz == [k(2; 23) mxx. and Kzx := [k(2,, Zy m Here, Z = (z....., 2m C X' are some pre-chosen landmark points, and i represents the Moore-Penroe inverse. Then, K can be interpreted as projections of data points onto the plane in the RKHS:
K = [(rojs projs
where S = span((())]1 < m} C H4. Thus, the accuracy of K, or the accuracy of scalable kernel learning via K, depends how closely the subspace S resembles the data {Ø(x;) J the corresponding elements the RKHS of the original data. Consequently, Nyström methods operate by selecting landmark points that effectively represent the original data, as demonstrated in the past studies using data-dependent landmark points such as K K-means centroids or subsamples (Kumar et al., 2012; Zhang et al., 2008; He and Zhang, 2018).
2.3 Problem Formulation
DP kernel ERM. For a given dataset D = (();, Wi) C (A' x y)", a loss function I: R² - Rgo. and regularization parameter 0, we consider the following regularized kernel ERM:
1 Σ T
> 11.
arg min (f: &
(((f. (.::) u.)+
JEHL
The minimization finds a function ff that best explains the data under the given loss, and the reg- ularization parameter prevents over-fitting We measure the quality of the model by the excess empirical risk of f. defined by (f: mingem, (>: D).
DP KME. For given data (x:) C X our objective is to design DP KME release mechanism: an (c, DD mechanism M 2 > P (Ha) that sufficiently close to the KME #x = E [o(X) in the RKHS norm with high probability. Since it is known that the empirical KME Ax := +(m)))---66e.. converges to µx with Op à) (Muandet et al., 2017), our DP KME
algorithm will focus on releasing fxx.
Versatile DP kernel ERM. We explore DP public dataset release tailored for kernel ERM. Unlike mechanisms developed in DP kernel ERM, which train models for specific loss functions and regularization parameters X, we develop a private dataset release (e, 8)-DP mechanism M x - 2", This mechanism enables learning kernel ERM for post-given, possibly infinitely many I functions and À values.

---

3
Proposed Methods
Proofs for the theorems presented in this section are deferred to Appendix 6.3.
3.1 DP K- K-means Nyström Approximation
This section presents pivotal tool for achieving scalability for general DP kernel learning: DP K- means Nyström method. It instrumental for our DP algorithms to make predictions using released private functions without needing access to the original data, and to be easily incorporated into the current linear DP ERM framework, unlike Hall et al. (2013).
As demonstrated by Chaudhuri et al. (2011) and Balog al. (2018), DP kernel learning can effectively utilize the established methods DP linear learning through random features. However, the use of random Fourier features depends specific kernel characteristics, particularly which complicates the development of random features for more general kernels. To overcome this challenge, adopt the Nyström approximation scheme, which is suitable for constructing random features for a wider range of kernels. As discussed in Section 2.2.1, 1, selecting landmark points that accurately capture the data structure is crucial for the Nyström method. Following the landmark selection guidelines outlined in Zhang et al. (2008), namely the K-means approach, we provide detailed rationale behind this criterion to demonstrate how effectively these points represent the underlying data structure.
iotisslationnivviianne
(Nys) ((projs((2)) bu. (pro)s bm) where (Nys) X + RD f2z Define fz {b ) is orthonormal basis of S. Here, (A ye) is our random feature map. Our goal is to select suitable landmarks that minimize the approximation error of p(Nus) for the kernel & { Jz)]nxn which can be expressed as follows:
Σ fJ=1
[((2,,))) - (42 (Nvs) (xx), 42
K R. (Nus) (z,)))² = n
(I)
2
Note that the error described in Eq. (1) is also known the Nyström approximation error in the literature on low-rank kernel approximation. The accuracy of Nyström-based kernel learning depends on the accuracy of the kernel matrix approximation: |KK K||2. |K-K|a which is upper bounded by ||KK]]]r-
However, optimizing the landmark selection by minimizing LHS in Eq. (1) under DP is challenging because the problem is neither convex nor Lipschitz, making DP optimization difficult. Theorem offers a comprehensive approach to identifying appropriate landmark points by solving the K-means problem, rather than directly addressing the complex challenge.
Theorem 1.
If a kernel k is c' c'-Lipschitz for both of its arguments, the Nyström approximation error is bounded by the quantization error of the landmark points for the original dataset:
K
K -K-KIp
2dd,
2d'
min 22 2
23 11
(2)
Theorem sheds light on the connection between low-rank kernel approximation and data clustering. Since the Nyström method is essentially an orthogonal projection of data onto S in RKHS and the LHS of Eq. (2) resembles the common clustering objective, the theorem essentially suggests that a proper clustering can identify a subspace S that is closely aligned with the data. We emphasize that the bound stated in Theorem 1 is O(yne), where Σ min,, [ 2z 1/ The bound is tighter than the One Kz -1 [])) bound provided Zhang al. (2008), the sample size n and the number of landmark points m are sufficiently large such that Kz has small eigenvalues, even though the assumption on kernel equivalent to the one made in Zhang et al. (2008).
In Algorithm I, we present DP algorithm for K K-means-based Nyström approximation. The obtained orthonormal basis {b; j 1 of S and their corresponding random feature map (Nyys) can be used in the subsequent DP kernel learning. For the DP K-means step in line 2, the algorithm from the di seffprivvil package implemented by IBM can be used.
2A function f is e' Lipschitzz [f(x) - f(y)ls d| - y) holds for every x. y. httpss//gihubb.cmm/////tfftteet wwwpaeyyiwiiiyoooooaaaaaaaaiiiie means.py
5

---

Algorithm DP K-means Nyström approximation.
Input: given data (-i,....a -, random features of dimension 17, cluster threshold parameter mo and privacy parameters 6, 6.
Output: a random feature mapping glNue) : X + Rm, and (bl....,bay bmp C Hk-
1. K Imoe].
2. {z1... 2x t centroids of e e/2-DP K means for (.1...., Inf.
3. If K m, draw (2R+11.... 2m from some distribution Q.
4. UEU + the unitary diagonalization of matrix [k(2 2g) Im xm
5. ((Nve)= < ((Nve) (x) R E ()),, k(2m; +))²
where R = Vmaazee k(r,)))
6. D5
for 1,2,...,.
7. return go (Ne)), (b1, (bi..... .bm
Theorem 2. Algorithm is C-D,,, and (N)(NN (profs((2),
bir H. for all and æ E X.
Although the privacy remains unaffected by the threshold parameter Mp, it does influence the quality of the landmark points: the DP K-means centroids. Setting K = m and omitting the thresholding step will result in small cluster sizes for large m, making the centroid estimates more susceptible to the noise added in the DP K K-means step. This issue is exacerbated by small privacy budget e, which further amplifies the noise. To mitigate this effect, thresholding performed using [moe]. After applying cluster size thresholding. additional m K landmark points are generated in line from distribution Q. While Q can be chosen arbitrarily. we choose it as a mixture of K truncated normal distributions centered at 2,s, incorporating data information extracted from the DP K K-means.
3.2 Scalable DP Kernel ERM
Using the output of Algorithm 1, we can construct a DP kernel ERM for general kernels, as presented in Algorithm 2. Since the generation of random features is performed differentially privately, any existing DP linear ERM algorithms can be subsequently applied to achieve DP, in accordance with the composition theorem in Proposition 2. As illustration, the method in Kifer et al. (2012), detailed in Algorithm 5 in Appendix 6.2, is adapted for general kernels in line 2 of Algorithm 2.
Algorithm 2 DP kernel ERM for general kernels
Input: given data {#1...., ), integer and kernel k.
Output: J He.
1. ((N))), (by,..., bm } + e/2-DP feature map and basis, output of Algorithm 1.
2. u + by solving 8)-D linear ERM for data ((o(N)) 9,)
3. f E uzbi
4. return
Theorem 3. Algorithm 2 is (e, 6)-DP.
Line I of Algorithm 2 transforms the data points to random features, and line 2 solves the DP linear ERM with respect the newly produced data (xx)) This step reduces the computational complexity, for example, from ( ) to O(nm² + nmd) in kernel ridge regression.
The linearization through random features introduces extra learning errors beyond the DP linear ERM error, specifically the approximation error for the given kernel, which is related to the |KK K 2, as shown in Theorem 4. The experiment results in Appendix 6. suggest that our DP random feature algorithm approximates the Gaussian kernel better than random Fourier features for small m.
Also, we note that although the privacy budgets were allocated equally for step and 2, it may not be the optimal choice. The Fig. demonstrates the utility can be improved in other privacy allocations. However, we fix the allocation as half since tuning the optimal allocation may involve privacy leakage. We included the detail in Appendix 6.1.

---

Theorem 4. the loss function is c-Lipschitz with respect to its first argument, the excess empirical risk of Algorithm 2 equipped with (5, 6)-D linear ERM algorithm is m
(3) + =llK-Kll with 2An
probability at least 1 - 3 where n,,m (3) is an empirical risk bound of the DP linear ERM algorithm
satisfied with probability at least 1 3 for inputs in a unit ball.
3.3
DP Kernel Mean Embedding
This section introduces a DP KME method using K-means Nyström approximation in Algorithm 3. An important consideration in DP KME is that the released private embedding should be an element of the RKHS. Note that the noise level in the release of the coefficient vector w line of the algorithm determined by Proposition 1, ensuring accuracy proportional to the sample size n.
Algorithm 3 DP kernel mean embedding (DP KME)
Input: given data {æ1, ......... } integer
Output: a DP kernel mean embedding f E H*
1. ((Ne)) (b), bm} + e/2-DP feature map and basis, output of Algorithm 1.
2. w t R E (Nv))))))
where ~ N (0, Imxm
3. ix f Ei wiby
4. return P.x
Theorem 5. Algorithm 3 is (e, 6)-DP.
The following theorem regards the difference between our DP KME and the conventional empirical KME estimate ux.
Theorem 6. The DP KME error the RKHS norm is given as follows:
|K
K|12
2Rv 2m
(1+ / log
(vm y 22
1
1 -xxl I
Vn
nc
with probability at least 1 - B.
According to Theorem 6, the accuracy of DP KME depends on the accuracy of the low-rank ap- proximation of K. By adaptively selecting landmark points according the data, we can effectively reduce the approximation error. The following thcorem confirms the advantage using the data distribution in DP KME.
Theorem 7. If the landmarks are selected independently of the data, the KME error of Algorithm would become:
(22 2 2 log
(in))
3'
B
(vm+ v/s)))))))))) + -loxx-prossxx
Ax
2R
14
71
n
nE
(ind) with probability at least 1 3 where 8 2 log G. and px denotes the DP KME obtained by eetaiindependently selected landmark points.
Theorem 7 addresses the scenario where landmark points are selected independently of the data, as suggested by Balog al. (2018). The error depends on how closely the distribution of the landmark points S resembles that of the data. Consequently, disregarding the data distribution μu can lead to suboptimal results in kernel learning.
3.4 Data Release for Versatile DP Kernel ERM
Here, we consider scenarios where sensitive data must be released without knowing which ERM model(s) will be trained on it. We propose a framework for releasing sevaacyprrservingg datasets suitable for kernel ERMs that ensures robust accuracy with diverse loss functions. The non-interactive local DP ERM framework utilizing a polynomial approximation of the gradient of the objective is employed for the purpose. The proposed Algorithm Zheng et al. (2017), tailored for kernel learning. Denote || = max
modified version of Algorithm from

---

Algorithm 4 DP data release for versatile DP kernel ERM
Input: given data ((I), (In, Vo)): integers m. and privacy budget (c, 6).
Output: DP data
dm} +- e/2-DP feature map and basis, output of Algorithm 1. 1. vo(Nve), (b1y...,
2.
2
(xp(N)))(x;))) + 1 c ye ye (Nus) (x;) )) + 1 Ee, ................................ yip (Nu) (x;) + 1 ((nt)) where eg ((, 4||3"]] (m) and Ej ~ N(0, 4p(p 1)112)) for j -.... p(++
3. πt -
4. return {7:)=11
Theorem 8. Algorithm 4 is (c, 8).P).
In this versatile learning problem, we add new constraint that the parameter space has radius r > O, which is a common restriction in private ERM contexts (Kifer et al., 2012). Then the ERM problem can be written as:
I E (((f.
A + 2 -
min fe Sr
We assume the following to ensure an efficient polynomial approximation of the loss by constraining its form. Note that the assumption accommodates broader range of existing losses; for instance, logis- tic loss and smooth variants of hinge loss, compared to the assumption in Zheng et al. (2017).
Assumption 1. The loss function satisfies I(0. 3) = lo(v)) for convex, c-Lipschitz 4o RR R20- which is I-smooth i.e., is differentiable and satisfies to (41) - 1o(2) S (12) 12) + [4 1 -2
Theorem 9 states that the optimization in Eq. (3) can be solved using the output of Algorithm 4 with a theoretical utility guarantee.
Theorem 9. Under Assumptions 1, for regularization parameter À > O and a pth degree polynomial h, there exists an algorithm AI,x that takes the output of Algorithm 4 and returns classifier with excess empirical risk:
+ 0(02+0 2
2p+1
mR
log" 3 + +aRlD111
TP
ndpu
with probability 3, where a = (1)( b( on loyl r| R, as the maximum absolute value of the coefficients h, and O is a big O notation ignoring log factors.
Remarks. The bound in Theorem 9 relies heavily on the quality of the polynomial approximation of the gradient. For example, the Huber loss used for support vector machines (SMM, gives a poor guarantee: O (loo n²) -) with Chebyshev polynomial approximation h due to the lack of smoothness of the gradient. In contrast, smooth losses, such as the logistic loss ((), v) - log(1 + e Bv), and the Linex loss ((j, y) cal--v)) a(1 - -yy 1, offer faster convergence of guaranteed excess empirical loss bounds: O(n for some > 0. The algorithm Ar, in Theorem 9, detailed in Algorithm 7 in Appendix 6.2, utilizes an inexact oracle gradient method as outlined Algorithm of Dvurechensky and Gasnikov (2016).
4 Experiments
In this section, we demonstrate our proposed DP methods for DP kernel learning with simulated and real data. Specifics on the data generation can found Appendix 6.
The first example is designed to demonstrate the benefit of scalable DP kernel ERM for general kernels. The data comes from two classes with polynomial boundary between them, making the mon-translationiinaarii
polynomial kernel the most preferable choice for kernel function. We
'[ww; y) = (1.5 yw==>) (, z) + (1 ywu 2) 0.0--x...ssyyee (yw x)) differentiable version of the hinge loss (Chapelle, 2007)
8

---

polymoiaa
0.82
0.20
Gaussion
0
0.18
0.16
0.78
0.14
Balog al.
k-menns
subsamplex
10a1
10P
10
10
161
Figure I: (a) Comparison of classification accuracy of scalable DP kernel ERMs with different kernels over a range of the privacy budget (b) Comparison of embedding errors of the proposed DP KME with alternative approaches.
consider three kernlls: 3rd-order polynomial, Gaussian RBF, and linear kernels. Learning with the former two kernels is conducted as a DP linear ERM (SVM with Huber loss using the algorithm in Kifer al. (2012)) with m 200 random features obtained by Algorithm and random Fourier features, respectively. The test data classification accuracy shown in Figure ((a) clearly demonstrates superior performance of the polynomial kernel across a wide range of the privacy budget.
We assess the estimation error of DP KME algorithms using the adult dataset (see Appendix 6.1 for details) with Gaussian kernel for fixed number of landmark points m. Although Algorithm uses the K K-means-based Nyström method, we also explore a subsampling-based version (outlined in Algorithm 6 in Appendix 6.2) with privacy budget that is 100 times larger, it demonstrates meaningful results in low privacy regions. We compare DP KME algorithms employing both methods, well as Algorithm 1 in Balog et al. (2018). Figure 1(b) shows the superior performance of K- means-based method among the three methods. The higher errors for Balog et al. can be attributed to the misalignment of distributions between random samples and the data, causing a larger error than the error added by the noise for privacy guarantee. In contrast, Nyström methods are data-dependent, incorporating data information into their kernel approximation. However, in highly private scenarios with small values, this capability is compromised, leading to accuracy loss. Furthermore, the K X--menns-asse Nyström method outperforms subsampling. This is partly due the characteristic of the DP K-means algorithm, which adds noise inversely proportional to the cluster size, whereas the subsampling-bon -baeed method adds noise indiscriminately. Consequently, DP K-means ensures that larger, more significant clusters are less perturbed, and selects important landmark points with greater accuracy, leading to improved performance in DP kernel learning. Also, appears that the quality of the subsampling-bees based landmark points deteriorates easily with the addition of noise. Kernel approximation through DP subsamples more susceptible to degradation under privacy constraints compared to DP K-means.
5 Discussion, Limitations, and Future Work
In this work, we propose K-means Nyström-based private scalable kernel learning framework that is applicable for general kernels. We have developed DP kernel ERM, KME, and public data release mechanisms for versatile kernel learning within this framework. Theoretical and empirical investigations verify that our new framework is superior existing ones, offering better performance with fewer constraints.
The Nyström method employed for the kernel matrix approximation has few discussion points. First, we point out that utilizing DP K K-means for scalability does not necessarily imply that the data must contain discernible clusters; instead, it helps ensure that the landmark points more effectively retain prominent features of the data. Second, supervised Nyström method, if feasible, could yield better results in certain cases. Specifically, in kernel ridge regression, focusing on few eigenvectors aligned with the response, rather than the entire kernel matrix, might require less DP noise and enable more efficient learning.

---

Even though our proposed framework is designed to work with general kernels, the current implemen- tation limited to handling Euclidean data due its dependence on K K-means. potential remedy for this limitation would be to consider a K-medoids type clustering method, which ensures that the centroids are selected among actual observations. Further investigation into DP K- K-medoids Nyström approximation and the development of subsequent private kernel learning methods are recommended as areas for future research.
Acknowledgement
This work was supported by the Institute Information & Communications Technology Planning Evaluation (ITTP) grant funded by the Korean government (MSIT) (No.2022-0-0093) Solving the problem of increasing the usability and usefulness of synthetic data algorithms for statistical data.) The work of Jeongyoun Ahn was partially supported by the National Research Foundation of Korea (NRF- 2021R A22RIAAC1093526 NRF-2022M3JA 10663000 ASS20033-00118231) The work of Cheolwoo Park was partially supported by the National Research Foundation of Korea ANRF-222R1AA2C1999 IRF-2022MM3JAA1033222),
References
Abadi, W., Fezari, M., and Hamdi, R. (2015). Bag of visualwords and chi-squared kernel support vector machine: A way to improve hand gesture recognition. In Proceedings of the International Conference Intelligent Information Processing, Security and Advanced Communication, pages 1-5.
Alashwal, H., Deris, S. B., and Othman, R. M. (2009). A bayesian kernel for the prediction of protein- protein interactions. World Academy of Science, Engineering and Technology, International Journal of Computer, Electrical, Automation, Control and Information Engineering, 3(3):705-710.
Balog, M., Tolstikhin, I., and Schölkopf, B. (2018). Differentially private database release via kernel mean embeddings. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 414-422.
Bassily, R., Feldman, V., Talwar, K., and Guha Thakurta, A. (2019). Private stochastic convex optimization with optimal rates. In Advances in Neural Information Processing Systems, volume 32.
Bassily, R., Smith, A., and Thakurta, A. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473.
Becker, B. and Kohavi, R. (1996). Adult. https://doi.org110.22 10.2442//CCXX
UCI Machine
Learning Repository. DOL:
Chapelle, O. (2007). Training a Support Vector Machine in the Primal. In Large-Scale Kernel Machines. The MIT Press.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. (2011). Differentially private empirical risk minimization. J. Mach. Learn. Res., 1069):1069 1109.
Dong, J., Roth, A., and Su, W. J. (2022). Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3-37.
Dvurechensky, P. and Gasnikov, A. (2016). Stochastic intermediate gradient method for convex problems with stochastic inexact oracle. J Optim Theory Appl, 171:121-145.
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. (2006a). Our data, ourselves:
Privacy via distributed noise generation. In Advances in Cryptology EUROCRYPT 2006, pages 486-503.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. (2006b). Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, pages 265-284.
Feldman, V., Koren, T., and Talwar, K. (2020). Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, page 439-449.
10

---

Gopi, S., Lee, Y. T.. and Liu, D. (2022). Private convex optimization via exponential mechanism. In Proceedings of Thirty Fifth Conference on Learning Theory. volume 178, pages 1948-1989.
Gopi, S., Lee, Y. T., Liu, D., Shen, R., and Tian, K. (2023). Private convex optimization in general norms. In Proceedings of the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pages 5068-5089.
Grauman, K. and Darrell, T. (2007). The pyramid match kernel: Efficient learning with sets of features. J. Mach. Learn. Res., 8:725-760.
Hall, R., Rinaldo, A., and Wasserman, L. (2013). Differential privacy for functions and functional data. J. Mach. Learn. Res., 14(1):703-727.
Harder, F., Adamczewski, K., and Park, M. (2021). Dp-merf: Differentially private mean embeddings with randomfeatures for practical privacy-preservinn data generation. In Proceedings of The 24th International Conference Artificial Intelligence and Stutistics, volume 130, pages 1819-1827.
He, L. and Zhang, H. (2018). Kernel k-means sampling for nyström approximation. IEEE Transac- tions on Image Processing, 27(5):2108 (1(5):210-21122 -1200.
Iyengar, R., Near, P., Song, D., Thakkar, O., Thakurta, A., and Wang, L. (2019). Towards practical differentially private convex optimization. In 2019 IEEE Symposium on Security and Privacy (SP), pages 299-316.
Jain, P. and Thakurta, A. (2013). Differentially private learning with kernels. In Proceedings of the 30th International Conference Machine Learning, volume 28, pages 118-126.
Jain, P. and Thakurta, A. G. (2014). (near) dimension independent risk bounds for differentially private learning. In Proceedings of the 31st International Conference Machine Learning, volume 32, pages 476.
Kifer, D., Smith, A., and Thakurta, A. (2012). Private convex empirical risk minimization and high-dimensional regression. In Proceedings of the 25th Annual Conference on Learning Theory, volume 23, pages 25.1-25.40.
Kumar, S., Mohri, M., and Talwalkar, A. (2012). Sampling methods for the nyström method. J. Mach. Learn. Res., 13:981-1006.
Lafferty, J. and Lebanon, G. (2005). Diffusion kernels on statistical manifolds. J. Mach. Learn. Res.. 6: 6:129-163.
Laurent, B. and Massart, P. (2000). Adaptive estimation of quadratic functional by model selection. The Annals of Statistics, 2865):1302-1338.
Ma. Y., Zhang, Q. Li. D., and Tian, Y. (2019). Linex support vector machine for large-scale classification. IEEE Access, 7:70319-7033..
Maji, S., Berg, A. C., and Malik, J. (2013). Efficient classification for additive kernel svms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):66-77.
Mangoubi, O. and Vishnoi, N. (2022). Sampling from log-concave distributions with infinity-distanee guarantees. In Advances Neural Information Processing Systems, volume 35, pages 12633- 12646.
McSherry, F. and Talwar, K. (2007). Mechanism design via differential privacy. In 48th Annual IEFE Symposium on Foundations of Computer Science (FOCS pages 94-103.
Moro, S., Rita, P.. and Cortez, P. (2014). Bank Marketing. UCI Machine Learning Repository. DOL: http:://oi..gg//0.44222533333
Muandet, K., Fukumizu, K., Sriperumbudur, B., Schölkopf, B., et al. (2017). Kernel mean embedding of distributions: review and beyond. Foundations and Trendso Machine Learning, 10(1-2):1- 141.

---

Nikolov, A., Talwar, K., and Zhang, L. (2013). The geometry of differential privacy: the sparse and approximate cases. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC "13, page 351-360.
Pinelis, (1994). Optimum bounds for the distributions of martingales in banach spaces. The Annals of Probability, 22(4):167--176.
Song, S., Chaudhuri, K., and Sarwate, A. D. (2013). Stochastic gradient descent with differentially private updates. In 2013 IEEE Global Conference on Signal and Information Processing, pages 245-248.
Wang, D., Chen, C., and Xu, J. (2019). Differentially private empirical risk minimization with non-convex loss functions. In Proceedings of the 36th International Conference Machine Learning, volume 97, pages 6526-6535. PMLR.
Wang, D., Ye, M., and Xu, J. (2017). Differentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems, volume 30, pages 2722-27311
Wu, x., Li, F., Kumar, A., Chaudhuri, K., Jha, S., and Naughton, J. (2017). Bolt-on differential privacy for scalable stochastic gradient descent- based analytics. In Proceedings of the 2017 ACM International Conference on Management of Data, SIGMOD '17, pages 1307-1322.
Yang. T., Li, Y-f., Mahdavi, M., Jin, R., and Zhou, Z.-H. (2012). Nyström method vs random fourier features: A theoretical and empirical comparison. In Advances in Neural Information Processing Systems, volume 25, pages 476-484.
Zhang, K., Tsang, I. W., and Kwok, T. (2008). Improved nyström low-rank approximation and error analysis. In Proceedings of the 25th International Conference on Machine Learning, ICML '08, pages 1232-1239.
Zheng, K., Mou, W., and Wang, L. (2017). Collect at once, use effectively: Making non-interactive locally private learning possible. Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 4139. PMLR.
Appendix
6.1 Experiment details and additional results
We provide specifics the two experiments: DP kernel ERM conducted simulated dataset and DP KME performed on the adult dataset. We use five Intel@ Xcon@ Gold 6248 processors for the computing resources in the simulation and one in the other experiments.
Privacy parameter. Throughout the experiments, we use privacy parameters (e, {(10-) )), (10-0.5, n -)), (10", -)), (10..5 .n -n), size used in the algorithm.
"), (10', n -))] where represents the dataset
Algorithm hyperparameters. Throughout the experiments, the hyperparameters for Algorithm I are set as follows: the distribution Q is defined as a mixture of m truncated normal distributions, each supported on [0, 1]d and centered at {2, i=,,, with standard deviation o; max 2; 2:ll2- Additionally, the thresholding parameter mg is set to [0.0In].
6.1.1 Scalable DP Kernel ERM
Simulation dataset generation. The feature vector of the simulated dataset is drawn independently from a mixture of truncated normal distributions supported on [0, 1,200 The following the density formula:
f(x) Σ dN 0.04T2m0x200))
where dNNe(u, x2000x000 is the density of the coordinate-wise truncated normal distribution, that is:
, dNelu, 22 1200x200) + X, Ze/2, e [0, 1] where Z; N(4, o3).
12

---

The mean values of the truncated normal distribution are as follows:
(0.7....,0.7 0.7)
200
A2
(0, ...,,
(0.5,
0.5, 0,
100
100
0. 0.5, 0.5)
100
100
The response variable y is obtained as follows:
sign ((1
1 ) 837
(1
noise
where & denotes the coordinate-wise power operation, Z is a 20 x 200 random matrix with entries drawn from the standard normal distribution, w a random vector following (O, 20)) and and 0 are vectors with all components equal to 0 or 1, respectively. The noise is assigned according to the standard normal distribution. Additionally, in the DP polynomial kernel ERM, we preprocess the data ensure their norm remains below 1, wwwaaccc-reeeiingggggg procedure. The experiment was repeated 10 times, 1,000,000 training samples and 200,000 test samples were generated for each run to solve and evaluate the accuracy of the DP kernel ERM.
DP Kernel ERM hyperprameter. (10-5, 10 10-3, 10-10-... 10-2) is used in tuning. Figure 1a shows the highest accuracy achieved for each privacy parameter across these values of X.
The regularization parameter
E
Preprocessing of the data in simulation Additionally, constrain the l norm of the data when employing both linear ERM and polynomial kernel ERM. This step is essential for DP kernel ERM. particularly when the kernel is unbounded, as it requires the boundedness of the data.
1=-v1ă 512 and the 3rd-order kernel (2.9) 2
Kernel used in DP Kernel ERM. The Gaussian kernel e
are used. The hyperparameter of the Gaussian kernel selected by grid search in a non-private kernel SVM setting: we generate 1000 training data and 200 test data, then compare the test error
of the non-private kernel SVM for the Gaussian kernel Im=all w
over O 2- 2- ..... 27. The with the lowest test error is selected. Each non-private kernel SVM for the kernel is repeated 10 times, and the averaged errors are compared. The 3rd-order kernel is scaled to ensure its maximum value is at least for data within unit ball.
6.1.2 DP KME release experiment
Data description. The real dataset, the adult dataset(Becker and Kohavi, 1996). can be downloaded from the UCI Machine Learning Repository. It consists of 48,842 observations for binary classification whether the income above 50K less than 50K.
Adult dataset processing. In the data processing, we follow the conventional practice of existing works on DP ERM, for example, Chaudhuri et al. (2011), Iyengar et al. (2019). Continuous features (all positive) underwent scaling by their maximum values, while categorical features were expanded via one-hot encoding. To eliminate collinearity, we omit the last column in each of the one-hot encoded features, resulting in dimensionality of 103.
Kernel choice, For the empirical KME release, we use the entire dataset to produce a DP KME
based on the Gaussian kernel k(æ, y) e 1=-viğ and m = | n2 dimension of random features for comparison.
Approximation evaluation. The approximation error is evaluated by the RKHS distance between the empirical KME and the DP KME. The experiment is repeated 10 times, and the average error along with the standard deviation for each privacy parameter displayed in Figure 1b.
13

---

DP KME algorithms. We compare Algorithm I from Balog et al. (2018) with our DP KME algorithms, which use DP K K-means and subsampling- -based Nyström methods. The DP K-means- based algorithm corresponds to Algorithm 3, while the subsampling-basee algorithm is described in Algorithm 6. Algorithm from Balog et al. (2018) is implemented using their code, with a single modification: the random sample distribution is changed from the normal distribution to the uniform distribution on the unit cube, as our data is preprocessed to fit within this unit cube.
6.1.3 Additional experiments
Landmark quality: kernel approximation experiments. We evaluate the performance of three DP landmark-based methods and random Fourier features-based low-rank kernel approximation, across various settings of rank m. The rank of the approximation corresponds to the number of the landmark points in the Nyström methods and the dimension of the random features in the random Fourier features method. Notably, even when the number of landmark points is small, random Fourier features tend to perform less effectively than Nyström- Nyström-based methods.
The kernel matrices are calculated from the Gaussian kernels k(æ,, y) =
for 2 with i = 0, 1, 2, across the entire adult datasets. The approximation error is assessed by the relative error with respect to the Frobenius norm²: K K-Klle, The experiments are repeated 10 times, and the ||]]
averages of the relative errors along with their standard deviations are presented in Figure 2.
Privacy allocation. In Algorithm we allocate the privacy budgets equally between the construction of DP random features and DP ERM. Figure 3 compares the accuracies of DP kernel ERM using Algorithm 2 with various privacy allocations. The blue line shows allocating 20% of the privacy budget to the DP kernel random features construction and 80% to the DP ERM achieves better accuracy than allocating them equally. A possible heuristic rule for determining the optimal privacy allocation ratio is to allocate the budget depending on the strength of the clustered structures in the data. For instance, when the number of landmarks m small relative to the sample size n, is advisable to allocate larger portion of the privacy budget to the linear ERM rather than the DP K-means. This is because DP K-means algorithms are more accurate when m is small. A smaller m typically results in larger cluster sizes. Since DP K-mean algorithms acquire private centroids by averaging the members of each cluster privately, larger clusters tend to lead to more accurate centroids given fixed privacy budgets. Therefore, we can afford to allocate more privacy resources to linear ERM.
DP KME experiments.
In what follows, we present a comparison between Algorithm 3 and other algorithms (Algorithm 6 and Algorithm 1 in Balog et al. (2018)) using datasets other than adult datasets in Figure 4. The datasets used include bank, CDC, credit, and MNIST, which are described below. Due to the large size of these datasets, only 30,000 examples are utilized in the experiments.
Bank. The Bank dataset pertains to telemarketing phone calls made by a Portuguese banking institution from 2008 to 2013 (Moro et al., 2014). It includes information on clients' financial and social backgrounds, as well contact details from the bank, with a binary label indicating whether deposit subscription was made. This dataset is available in the UCI database (https: //wrchivaeceeeeee ics. uci. edu/ http//aattte22/////ae http//222aaaaa/a/ marketingg. It contains 45,211 I examples, comprising 5,289 positive cases and 39,922 negative cases. The dataset features 6 numerical variables and 8 categorical variables, which are one-hot encoded.
CDC. The CDC dataset is part of the CDC's BRESS 2015, which consists of responses collected from Americans in the CDC's annual health-related telephone survey. This dataset includes relevant information for diabetes prediction and is available in the UCI database (https: // //www ar chive. cators). It contains demographic in- formation, health history, personal details, and diabetes diagnoses of the respondents. The dataset comprises 253,680 examples, with 218,334 negative cases and 35,346 positive cases. It includes 21 numerical features along with a binary label.
ics. uci. edu htt//daaasee/BBB
Credt. The Credit dataset is related the transactions made by European credit cardholders and is available on Kaggle (https: //www/wwwwwco kaggle. com/ hete//aaasess//// /mlp///mmggmmm/ healb//eedtcaarffrauuu This
'The Frobenius norm of the matrix A = [ai]]xx n is defined by ||] y == v Eigisshdh di.
14

---

67
(a)
0.3
(b)
1, 1,70
0.4
(c)
m/
0.0
0.0
04
12
10a4
20'
10a
20"
(d)
2,
0.3
[n 0.4
(1) 2,
1.0
0.4
02-
00
50
12
10
20'
10
20
4, m
0.3
(h)
4, m
nm
4,
0.5
1.0
1.0
1.0
Gausstan Salog meae suble
(j) 0 = 8, m [n
(k) = 8, m
[n
()) a = 8, m In 0.5
Figure 2: Comparison of four methods for various settings. In each figure, the x axis represents the privacy budget, and the y axis
K K-
[
0.32
0.70
0.78
piancy Albeet 830.
6.7
di 8.8022
Figure 3: Classification accuracy under varying privacy budget allocations
15

---

63h
640
(30
c0
551
(a)
0.30
(
(h)
krom
3
(i)
(k)
(I)
Figure 4: DP KME estimation results for Bank data (1tt column), CDC data (2nd column), Credit data (3th column), and MNIST data 44th column), using a Gaussian kernel with 2 (1st row), and polynomial kernels of degree 2 (2nd row) and 4 (3nd row)
dataset contains 30 numerical features, two of which are 'Time' and 'Amount," indicating the time and amount of each transaction. The remaining 28 features are principal components derived from principal components analysis due to confidentiality concerns. The dataset includes a total of 284,807 examples, with 492 labeled as fraudulent and 284,315 as non-fraudulent.
MNIST.
The MNIST dataset contains 60,000 images of handwritten digits and can be downloaded using the PoTorch package. Each image is represented by 784 numerical features, corresponding to the pixels in a 28 x28 image, along with categorical label indicating the digits from 0 to 9.
6.2 Additional algorithms
Denote
l/- the operator norm of square matrix.
Algorithm 5 DP linear ERM, Kifer et al. (2012)
Input: given data {a1,..., hn in a unit ball, V < S, [|V V)pp S o.
Output: E Rd
1. Set A < 20
2. Sample random vector b from N (0. <2(1+/21og 3)2
I mmx
3. arg min
E U( 21.9:) 9:) + ($
A)
||ull + bTu
4. return u
Algorithm 6 outputs the DP Nyström- based random feature map using a subsampling Nyström method. The algorithm is e-DP. The proof is in the Appendix. Unlike Algorithm 1, no thresholding parameter is included since subsampling treats m subsampled data equally whereas K-means centroids receive noise inversely to the cluster size they belong.
Algorithm uses the output of Algorithm 4 to solve the kernel ERM for a given polynomial h that approximates the gradient of the given loss function, and regularization parameter À >> 0. No measure for privacy guarantee included in Algorithm 7 since the algorithm uses only the privatized data, the output of Algorithm 4, and does not reference the original data.
16

---

Algorithm 6 DP subsampling Nyström approximation.
Input: given data {21....,Za? C [0, 1]". random features of dimension m, and privacy parameter
6,
Output: a random feature mapping (N R + IR",, and {bi...., bm) C Ha.
1. K [mge].
2. {2] ................................ 001 < m uniform subsamples of (ri,..., InJ without replacement.
3. + lox 1+ E₁ where E; is random vector with i.i.d. components following
Laplace distribution with density v(x) _ !
4. UEU + the unitary diagonalization a matrix [k(2,, 2m)mmmm
5. ((NN))) t p(Nve) (z) = (M(2,))) k(2m, x)]"
6. b Ex= U" (1502))))z))) for 1,2,....
7. return g( (bi,...,by bmp
Algorithm 7 Versatile DP kernel ERM
Input: given output { of Algorithm 4, integer m, h Output: DP solution f
1. for .,..., do
2. G(w,; 2,) + Ex= aA == W 20
Ezo + Awa
3. Apply Algorithm Dvurechensky and Gasnikov (2016) using & as the inexact gradient.
4. end for
5. return
-=Em ===1 [Wn]ebe
6.3 Proofs of theorems
6.3.1 Pinelis's inequality
According to Theorem 3.1 Pinelis (1994).
P Suuplfflla 2r) s 2e -xr+ 3 B,-1 a -1- [n
(4)
for any A > 0, where Wز}ر= is martingale He and dj SJ -Si-1 with do 0. Let f, = D (Ø(x)) px - ((()_( px)) if j I n and f, = fn for j > n. Then, f, is martingale Hd according Eq. (4), we have
$
P Σ
(o(x)) px -rojo(((ss)) - (xx))
2r
S P
Supplssll 2r)
HH
2e Ar+n ( 28 11 28
since [(((2)) px ux I 2R and function ex 1 increases (0, oc). Setting A
log (1 + 28 we have
P Σ wi(o(r;)) - px pro)) - xx))
< e -n -n( +1) (or))ooR((11)) (1))
-x
rr
Setting r 2RI, we have
P
w,(o(x;) - px - -prois(ó(z.) - ux))
2 2Rt
< -o-ntn
< -
Hx
17

---

since log T+z T+7
2
Putting
log 1
T+x
147
T+x
2 V n log n log² #1 we have
(r(((x;)) px projs(((xi)) - xx))
2 2R
log
+
log
+
1
log²
B
3
n22
Hh
with probability at most 3. Therefore.
2
P
w. (6(x,) pх (rojs(((x,)) xx))) -xxx)
2 22
log
+
log
S B
He
Lemma 1 (Lemma in Laurent and Massart (2000)). PP (IEll2 S vn + v 2 1
for
(0, 1] where is diemnsional standard normal distribution.
6.3.2 Proof of Theorem 1
The Cauchy-Swarte inequality gives
1 K
22
(k)); - (F2 (NN (x))) (Naa) (NN0) (1z)) )²
K
1
(xx),
n
n
4,==1
((ó(x;) projs(((,). - (roj))
n
1,==1
1
[ς((x;) - 10(zz) projgo(I,) (x,(((1)))))))) 11..
n
1
[((x)) projs
[0(x)) - projst(as;)11
Also, the Lipschitzness gives
k(ri,2;)
||ő(x;) - pr;)s S ((z,,2z))
k(zz,zz) zz)
k( 22)
k(z,, 2z) + c'|122 - 2z 112 k( 2g) c/ -
(k(1,, 23) + c(Ilar 22112)2 - k( 22)
k(01, 2z) + c' 1144-21 1
< d||x; zi|12 2k( 23) + c( 23 ||2
ki 23) + e d||=; Zj
< 2c 2d|1 by llz
for every 2j Z. Thus
K K < 2c
o 1,
1=
Choosing 2,5 to be the K-means centroids, we obtain the desired.
6.3.3 Proof of Theorem 2
The post-processing property of the differential privacy guarantees privacy since the landmark points 21, Z1s.r 2m were obtained differentially privately.
18

---

Additionally, (projs((x)) bm
we show {br is
an
orthonormal basis of S, and R[j(Naa))
(b,, by D (a(()))))))))))))))))
D Ul
Σ K2 K2]a (
A
EE by
1(i=j$4)
where to is the rank E or equivalently the rank Kz. Thus the members [6 are orthonor- mal to each other or are zero. Ignoring the zero terms we get the orthonormal subset of S. Also, dimension the spanned subspace coincides to rank of Kz. Thus the subset also basis. Finally, R[ys(Nwe)]= (projs(((1)), bi) follows from the direct calculation:
(projs((x), bi) (d(x)), bi)
= (b(xr), Σ E U (z)())
(0(x), 66 u
Σ
xz),
j=1
(R(NN=)(z))
6.3.4 Proof of Theorem 3
The algorithm is a composition of two DP algorithms so the (c, 8)-DP is guaranteed by Proposi- tion 2.
Proof of Theorem 4
Proof. Denote the DP linear algorithm as then the excess empirical risk is:
7.a Σ (IM()(NNe)))))
(Nv+) (x (xn)))
min î²(s)
SEH,
= i. (M(((())),....... ... ((xn)))
min i.*()) fES
min EES
i.*()
min i²(
fEHz
privacy error
where b;s are the output of Algorithm 1, the basis of S, and (N)) (Mo)) denotes the ith component of the output of the DP linear algorithm from input (v((ive)) (x:)) The random feature error is bounded by
(N)e(()))))
L K
min i^(f) min i^()) 5
feS
JeHt
2An
by Lemma I in the proof of Theorem 2 in Yang al. (2012). Then,
A EIM(O (Nvo) (xn)))
L K
(xn)))
min i²()) < (B) JEH2
2An
with probability 1- B.
19

---

6.3.5 Proof of Theorem 5
Proof. We show releasing in line 2 is (e/2,6)-DP. Then Proposition 2 gaurantees the overall algorithm satisfies (c, 6)-P).
The lg norm of the difference between outputs of deterministic algorithm releasing ; 1,' Rip(Nss)) (x:) for neighboring datasets is 2 Applying Proposition guarantees that releasing w is (f/2, 6)-DP. 17
6.3.6 Proof of Theorem 6
Proof. Denote xx (Nye)
2i-1 Eラ=1
R (x:)){b) Since R Ry
(x:))
12
pr,))
[Ax Ax (Nv+)
Σ ==1
((z;) ((o))
H4.
V 1" (K R)1
K K||2
/n
Also,
2R 1 + v 2 log
[ xx (Nv0)
~ ((No (xi) w
||1122
1=1
and from Lemma I, we have P
(Ieell S /m + /2 log
2 1 - B. Therefore,
2R 1 + v 1 1
πix xx (Nys)
(Vm++ + 2200g 3)
Ha
ne
with probability - 3.
6.3.7 Proof of Theorem 7
Proof. Denote (ind) 1 Σラ Eラ (x))), where (0() is random feature map from Algorithm 1 replacing { to data independent landmark. Since R RE (x,)),,, = pro)
| (m)d)) - ix (xx1
n Σ ((xx) - (ro))
He
n
16
The Pinelis inequality gives:
2
(p(x)) - px (rojs(((x;)) - xx))
2 2R
log
+
log 3
$ SB.
n
B
He
Thus,
p
| ((iid00)
jix 11111,
5 2R
2
log
+
log 3
+ 1| - projs/ 11
2 3.
7dn
n
3
Also,
2R ( + 2 log 1
(ind))
(ind)
||=||2.
H+
nE
and from Lemma I, we have P
(1E/12 5 /m /
/
> 1 B. Therefore,
|
((an))
pxx
< 2R
log
+
log
+ eIIpriv
+ +1lux projs 1|H
3
n
/2422/o0f)
(Vm + /210g
with probability 2,3 where eriprio
ne
20

---

6.3.8 Proof of Theorem 8
We show line 3 is (c/2,6)-DP. Then the Proposition 2 guarantees the overall algorithm satisfies (c, DD.
Proposition 3 (Composition theorem for Gaussian noise addition, Dong al. (2022)). For p1. > 0, and deterministic ulgorithms A, : + Z and A2 : X x Z - 2, define algorithms M1 : P2)) and M2 x x Z + P(2)
AI
Mi(D) = A1(D) + E1
P1
2
M2(D,2) 22(D,2)
E2
12
where A = (upD=- and A2 = sup=ez Du (D,, (DD',,
Then M3 X P(2) defined by Ma(D) (i (e,8)-DP if V ng
+t/2log
The l norm of the difference between outputs of deterministic algorithm releasing (y1 (N (x1), .......... ,,))).....))"""""" (N (I,)) for neighboring datasets is most 2/ since (N |||]| Thus if we apply Proposition repeatedly to algorithms
+ v2 . .u... (In)
(Fn)) + V2
Mo(D) = V1 (1
1
M((D) = (n (x1) + p(p + 1) El
e......, Uuep (Ns)) (Ir) + p(p + 1)
where of are normal random vector with mean 0 and covariance 4|2 I mx releasing the outputs of Mo. MI...., M at once is O)-2 since 2+2 2 /
Therefore the overall algorithm
satisfies (e, O)-D)
6.3.9 Proof of Theorem 9
Denote h(gy)) Eh_ en (vi)* We show that Algorithm 7 satisfies the theorem.
Definition 6.1 (Dvurechensky and Gasnikov (2016), modified), A convex function f Q C Rd R is endowed with a (6, b, or) stochastic oracle if an inexact gradient function ğ Q + IR and inexact function Q were given such that
0 H f(v) - fu(x) - [(]))
(y x)
ly
z
1
+
2
E [l
E
Lemma (Dvurechensky and Gasnikov (2016)). For a A-strongly convex function f endowed with a (6, b)) stochastic oracle, the sequecne {w:}i= generated by the algorithm 3 in Dvurechensky and Gasnikov (2016):
(o2 (1+ log log
13,3 2
3rr
f(w)) arg min f(w) 20 ||w||25
82
2nd
with probability at least 1 3.
Proof. Set Q fo 1m sاls r). Then, the projection mapping sp (Nys) : X R maps E X' to 1 ((projsó(x)) b.) (projo((z), bm Ha bm) where [b. is orthonormal basis of S transform the kernel ERM linear ERM. Denote w ((projsf. b............................... (projsJ. bm.) n. then constraint ||, < r is equivalent to |!ll2 I since f E S. Then, the transformed linear ERM is
min S
1w oo (NV))
(a:).
+1 1202
T1
i=1
21

---

For given x, y, denote j(w; v, v) == l(w7 ((wTTo(Ne)))))))))) (o(N
v) + 2/1001 12 Then, Vul(w" (( (x). - (w yup (N us) (x)))rp ( (Nv (x).
Denote
((wx,,)) v) = h(yw" h (NNN))
T(W,K,y) 3)
ag w² 2
k=0
j=1
where 8 yz + x 22 ya + vplp+1)
vplo+1) k
yx
following the notation in
Algorithm 4. Then
j(W1z,y) j[W2:j] v) (2 x, (N xx2)) U22)
A + b
s (6(wz (Nv)) (I)) g) (Nee) (x)² (wi w2) +
||w1 w222
I 22I + A 12
|| w2112
2
and similarly
jw11; x. v) - (w2; x, v) - (g(ws (22, x. y) (N (x)) + Awz) (ee))(ww))))) - ww)) 2 -2R
Next, we evaluate the variance of the gradient estimator:
E [lo(w, wis ws Mu (Nu)) (z:)) + Aw F(w, Ti, 1:) xwl12
2E
(Na)) (I:) (N
g20 1 + 2E (0 (Nua) (x.) - 1
where 9.9 7 stands for g (w T4, v1), 5 (w,, F4, Bt). The former can be bounded as
E (lovrs((Nv)) (x,) Tu.0o N5) (z:)
(x;) Var(()
S 1D
Var
Mck
12
k=0
j=1
27
s |D R22
E
w
T
k=0
j=1
12
0
E
T w
2
nckk 13 +3)
k=0
3=1
1 p(p + 1) 112
s R2
12
k=0
1 + p(p+1) (1+ 1+1
2 2n+2
| R22
13113/22
1+ (( -1
and the latter can be bounded as
E l (N (Nus) (x.) - 32
[ E ( (xx)) - 2
(Var(ī) + (c+ + )E
- 2/133]
4m
(Var(ā) + ac+
422
22

---

since
E [ 1 1h(w" mip (Nys) (xx)) 161 lol5 c a. Finally
I1av (xx) (au)) Vul(w" o(N (x.):
<
2 [1unn (2x) V vol(w" (NNN ve)):
+E |1 V/V (xs) BGNN Vul(w" (aN)))
(D (g - ly(w" (p (x:e)) + 402)
(a² + 122 |2'|
and combining the bound Var(g) we obtain
mR² 12011
[[G x.)= E(z.u>>p
V Vul(w= walllw=FoWWee (( (x)): 11 S
a² + 0²
12p+4
112
and the algorithm has
| A+ 1212?
a. r2ppptt
+ a² +c2) a2pl4
oracle. By
Lemma 2, the excess empirical risk is bounded by TP
δ o
{((
3p+1
mR log"
a²
0²
2
3
+ [RRD)/1
ndpu
with probability 1 B.
6.3.10 Proof of privacy of the DP subsampling- Nyström method
Proof. For a sequence :.y....,, :ia. denoted by without duplication, let M(S) Uy + ne where Ug == [ 2i,l" is a flattened vector obtained from the sequence with increasing index order, i.., in < ig. and be the random vector in Red with i.i.d. components following the Laplace distribution given in the algorithm. Note that our algorithm first release the output of M (SS) ) for log (1+ where S. a random subset of size m uniformly drawn from D, in line 2 and 3. The operations in line 4-7 does not refer to the data thus no privacy leakage. Therefore we show the algorithm ((Sm) is c-DP if y) log # (es-1) However, we will assign the value of y at the
d
very last of our proof, and leave v) to be undetermined until then.
Denote S,, S", the length m uniform random sequences of D and D', respectively, and Sm-1 the length m 1 random sequence of D n D'. Denote Lap(v, 7)) be the distribution of the e + mE for v E Ad If we denote the distributions of the outputs of the algorithm for D and D' as j&D and po then
(n m)!
PD
Lap (USm: 11)
n!
Sm DD
(n m)!
Lap (USt,,))
n!
8 CD'
Denote
(n
1)!
141
Lap (USm. 1)
(n 1)!
In 1.Sm
(n - mi)
42
m((n 1)!)
Lap (Us 7)
ZnES
(n 1)!
Lap (Usr. 17
(n 1)!
(n - m))
#/ =
Lap (US,,
m((n 1)!)
x SY
23

---

Then.
m
m
PDD
P1
+
112
m
m
pD
11
+
11
71
Note that pan = 141. Thus
D14 (e5- ((-))(((llll)))) =
/
m
11
+
m
- 142
(1 + 7h
{e
- 11)
m
M1 + 1 162)
n
n2.
n2
((1
+ = (c' -1]
1 + = [c=² - 1)
é'
14 +
e²
e"
1 1 + m (e' -1)
+ m (e' - 1)
m
D.:
Wzll
Há +
n
71
e²
e
x
max Des (pallиí) Des (1elll6)
n
since μ1 = p//. Also
(m 1)!
De (121l14)
Σ
EDer Der (USm-1-(zu) + n -u4z) nE")
(n m - 1)!)
Sm-1
(m - 1)!
Σ
de
In
(n (n 1
1]
where z are selected uniformly in D' - Sm-1 f E and s' are independent random vectors with i.i.d. components following Laplace distribution given in the algorithm, and (c( denotes De- + Elle). Although we refer to Sm-1. {I, }. {z} as sets for convenience, they are actually sequences. {2n) or {z} can be added any position in Sm-1, and each such case should be treated differently. However, by comparing the case where n, is added to the ith position of Smn-1 with the case where = is added the ith position of Sm 1, we can reach the desired conclusion.
is known that if the & norm difference of the output of an deterministic algorithm A D + Rd is most e then A(D) + is e-DP (Dwork al., 2006b) or equivalently De (c++ellk') 0f ||c|| = for vector c. Thus if we set 7) E then the inequality gives D. (μ2llи4) 0.
Thus, the algorithm is log (1 + " (e - DDP if r L. Replacing to log (1 [e 1))
arrive at the conclusion that the algorithm is ş -DP if log ++ (1)
so we are done.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract outlines the motivation for the scalable DP kernel learning using the Nyström method, and theoretical and experimental analyses. Also, the introduction details the limitations of existing works and our contributions to the field.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
24

---

It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the Section 5, the limitations of our algorithms were discussed, and possible breakthroughs were suggested.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proofs for every theorems are given in the Appendix(Section 6.3), and every assumptions required for the theorems are described in the theorem statement.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
25

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
We gave detail explanation for our experiment setting including simulation data distribution, accessible real data, data preprocessing procedures, and hyper-paramedt used in the experiments required for the reproduction the Appendix(Section 6.1). Also, instruction for the reproduction is given in the supplementary material.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in cases, in which authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
26

---

Justification: We gave publicly accessible link or the distribution description of the data in the Appendix(Section 6.1). which also implemented the attached code. Also, the code attached in the supplementary is written by python, and does not use any non-open-sourced or non-free libraries.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips. cttppss.ccpbbbicc//cccc gtwpiiiccguis////eeeeeeeeee http:///guiieee/eeeuubbiiiiiiii wwtsssubmisssooooo ittpe/uuiiisiioooooooooooo
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question:
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In the Appendix(Section 6.1), the experimental details and additional ex- periments are elaborated, including the size of the training and test data, preprocessing procedures, and the hyperparameters used in the experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report the number of the repetitions made in our experiments, with the standard deviations which are displayed in the plots. The Appendix(Section 6.1) details the caleulation methods.
Guidelines:
The answer NA means that the paper does not include experiments.
27

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory. time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: The computing resources used in the experiments given in the Ap- pendix(Section 6.1).
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: //teer/nnee.s//ee wwtppblicctteciccococccccccceeee www.eetthiiiiieeeeeeeeeee inees?
Answer: [Yes]
Our work conforms to the NeurIPS Code of Ethics since it does not involve human subjects participants, and the datasets used are either simulated existing public datasets with proper respect for copyright. The research is intended for beneficial applications, and any potential harm would only arise from misuse, which is not primary goal.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
28

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Although, our work lies in the area of the privacy, our main focus is reducing computational complexity and memory cost of the kernel learning under differential privacy which irrelevant to significant societal impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Answer: [NA]
Justification: Our algorithms and data do not contain information or data that have high risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
29

---

We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We used the adult,bank, CDc, and MNIST data sets, giving proper credit by citation in the Appendix(Section 6.1).
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New Assets
Question:
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The algorithms are explained and elaborated in the paper. Also, code imple- mentations are attached the supplementary material with instructions and annotations.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
30

---

Justification:
No human subject experiments or research are included in our work.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work does not include crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "t4Ue3780yy", "reviewer": "Reviewer_XDHr", "summary": "This paper considers the problem of differentially private kernel learning. The main idea of proposed\nalgorithm is to approximate the kernel matrix using the Nystrom kernel embeddings. The landmark\npoints on which the approximation is built are chosen as the centroids given by k-means algorithm\non data based-on the relationship between the kernel approximation error and k-means problem.\nGiven the Nystrom kernel embeddings, the authors propose algorithms for three tasks: DP-ERM,\nkernel mean embeddings, and data release.", "questions": "- While Eq. (2) shows the approximation error of kernel matrix is similar to that of k-means,\nit seems that the set Z in here can be viewed as an optimization variable. Is it possible to\nformulated the problem as a bi-level optimization?\n- Algorithm 1 embeds the landmark points into functions in a reproducing kernel Hilbert space\n(RKHS) and releases the random feature map along with the bases. Line 5 in Algorithm 5\ncomputes the scale factor R. Is R computed independent of data?\n- In line 3 of Algorithm 1, the algorithm samples the landmark points from distribution Q when\n$K < m$. Although the authors mentioned that this distribution Q can be arbitrarily chosen, it\nis not intuitive and they should be landmark points representative of the underlying dataset.\nHow does the choice of distribution Q affect the results?", "limitations": "Due to the use of $K$-means as a sub-routine, the proposed approach inherits the limitations of $K$-means, for example, difficulty of handling datasets with mixed data types and curse of dimensionality.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The authors make an important observation about the relationship between the kernel matrix\napproximation error and k-means problem. Based on the observation, they designs an algorithm\nthat releases approximate feature map under differential privacy.\n- The released DP Nystrom approximation is useful as it can be used for other tasks. The\nauthors demonstrate how the released feature map can be used for other tasks including ERM,\nhypothesis testing, and data release.\n- The paper addresses practical issues in applying DP kernel learning methods: scalability, ability\nto use general kernels and objective functions, and test data-free approach.", "weaknesses": "- While the proposed Nyström kernel embedding approach is versatile, its utility for a single\ntask might be lower that that for the algorithms entirely dedicated for the task. Unfortunately,\nempirical evaluations provided in Section 4 do not provide systematic comparison of utility\nwith existing approaches for each task.\n- The equal privacy budget split between Nystrom approximation and the linear ERM task seems\narbitrary. Since Theorem 1 and 4 allows to express the excess risk of kernel ERM algorithm\n(Algorithm 2) as the sum of two errors, each of which can be expressed as a function of ϵ. It\nmight be possible to find a more advanced approach for the privacy budget allocation.\n- When it comes to privatization method, the proposed algorithm seems incremental as its privacy\nrelies on the privacy of subroutines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1.** The utility of the versatile method\n\nWe acknowledge that the utility of learning from privatized data for versatile DP kernel ERM may be inferior compared to a DP kernel ERM algorithm dedicated to a specific task. For instance, when the RKHS of a given kernel has a finite dimension $d$, kernel regression via privately released data (from our method) has an excess empirical risk of $O(\\sqrt{d}n^{-\\frac{1}{2}})$. In contrast, the DP algorithm specifically designed for kernel regression can achieve an excess empirical risk of $O(d^2n^{-2})$ (Chaudhuri et al., 2011), which is faster when $d<n$. However, we point out that, in practice, it is common not to have a specific learning method in mind beforehand, and multiple methods are often experimented with. In such scenarios, our proposed approach can guarantee privacy for various learning problems, unlike DP algorithms tailored for a specific task. \n\n**W2.** Privacy budget allocation\n\nWe agree that optimizing privacy budget allocations can enhance the effectiveness of private learning. Figure 1 in the attached PDF implies that the 50-50 allocation may not always be the best. A possible heuristic rule is to allocate the budget depending on the strength of the clustered structures in the data. For instance, when the number of landmarks $m$ is small relative to the sample size $n$, it is advisable to allocate a larger portion of the privacy budget to the linear ERM rather than the DP $K$-means. This is because a smaller $m$ typically results in larger cluster sizes. Since DP $K$-means algorithms acquire private centroids by averaging the members of each cluster privately, larger clusters tend to lead to more accurate centroids given fixed privacy budgets. Therefore, we can afford to allocate more privacy resources to linear ERM. A deeper exploration of the connection between the cluster structure and the quality of the private landmarks is suggested as future work.\n\n**W3.**  Contributions\n\nWhile it is true that our algorithms utilize existing private learning schemes, we emphasize two novel contributions and one practically critical point:\n\nFirst, while the Nyström-based method is a known approach, applying it under privacy constraints is a novel and significant contribution. Existing scalable private kernel learning algorithms typically combine random Fourier features with private linear ERM algorithms, which was inadequate for private general kernel learning. We found that integrating the Nyström-based scheme with private linear ERM is effective, marking the first application of the Nyström-based scheme in the context of differential privacy.\n\nSecond, implementing an effective Nyström-based scheme under privacy constraints is another key contribution. Various Nyström-based schemes have differing quality under privacy constraints. As shown in Figure 1(b) in the paper, the solid lines show the accuracy of private KME estimation using Nyström-based schemes implemented by various landmark selection methods. The standard subsampling-based Nyström method (gray line) performs poorly under privacy constraints. Our discovery that the DP $K$-means landmark selection is effective underlines the importance of investigating clustering-based Nyström methods under privacy constraints.\n\nFinally, our composition framework is a practical strength, enabling adaptive design of private learning algorithms in various settings. Existing private linear ERM algorithms are tailored to specific scenarios, such as convex or non-convex loss, smooth or non-smooth loss, differentiable or non-differentiable regularizer, etc. Since the composition framework only requires the subroutines to be differentially private, it allows one to privately learn various models by substituting private linear ERM algorithms for the corresponding setting.\n\n**Q1.** Bi-level optimization.\n\nIt is possible to tune $Z$ through optimization, and similar approaches have been explored in non-private settings. However, there are important issues to deal with. The optimization objective is neither convex nor Lipschitz, and involves many variables (i.e., landmarks). Note that most literature on private optimization assumes a convex or at least Lipschitz objective. Nevertheless, we believe that exploring private landmark selection through the suggested optimization approach could be an interesting direction for future research.\n\n**Q2.** The scale factor R\n\nThe scale factor $R$ is defined in line 5 of Algorithm 1, and this definition is consistent throughout all subsequent discussions. It is a parameter that depends on the kernel function $k$ and the data space $\\mathcal{X}$, and is independent of the individual data. \n\n**Q3.** The effect of $Q$\n\nIn what follows we explain why the landmark points are sampled from $Q$ rather than using centroids or other possible representatives of the underlying dataset. Naturally, it would be preferable to choose landmark points that represent the underlying dataset accurately rather than using random samples. However, when $m$ is too large, the accuracy of the private centroid estimates degrades since the size of each cluster shrinks, which makes centroid estimates (i.e., sample averages) vulnerable to noise for privacy guarantees. Such inaccurate estimates would result in ineffective landmark points. Therefore, we selected $K(<m)$ representatives of the underlying dataset by using $K$ private centroids $z_1,\\ldots,z_K$, and chose the remaining $m-K$ landmark points from some distribution $Q$. Thus, $Q$ is intended to enhance the quality of the landmark points by adopting information from the DP $K$-means. \n\n`$Q$ can be arbitrarily chosen' means that the choice of $Q$ does not affect the privacy of the algorithm as long as $Q$ does not directly reference the data. Although we used a truncated normal centered at the private cluster centroids, we observed that the results from a different choice of $Q$ (e.g., uniform) are insignificant.", "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": "", "extra_scores": {}}, {"review_id": "s7vNe4ywQD", "reviewer": "Reviewer_PMbb", "summary": "The paper studies scalable kernel learning algorithms under differential privacy. First, the authors propose an algorithm for DP K-means Nyström approximation to obtain an orthonormal basis and their corresponding random feature map. Then, the authors use the basis and feature map for kernel ERM algorithm and kernel mean embedding algorithm. The paper presents both theoretical and empirical evaluations of the proposed methods, demonstrating their performance and superiority over existing approaches.", "questions": "1. How does the allocation of the privacy budget between different components of the algorithm (e.g., K-means, DP ERM) affect the overall performance? Could we improve the performance by choosing privacy budget more carefully?\n\n2. The proposed methods claim to offer improved scalability compared to existing DP kernel learning algorithms. Can you provide a detailed comparison of the complexities of your algorithms versus existing methods? Specifically, how does the time/sample complexity scale with the size of the dataset and the dimensionality of the data?", "limitations": "The limitations are addressed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed method is novel and practical. Both theoretical results and experiments are provided.", "weaknesses": "1. The quality of the Nyström approximation depends on the DP-K-means method. However, the proposed method is based on an existing library. \n\n2. This paper claims to provide a scalable solution. However, the experiments are somewhat limited in scope. (adult dataset)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1** Contributions\n\nWhile it is true that our algorithms utilize existing private learning schemes, we emphasize two novel contributions and one practically critical point:\n\nFirst, while the Nyström-based method is a known approach, applying it under privacy constraints is a novel and significant contribution. Existing scalable private kernel learning algorithms typically combine random Fourier features with private linear ERM algorithms, which was inadequate for private general kernel learning. We found that integrating the Nyström-based scheme with private linear ERM is effective, marking the first application of the Nyström-based scheme in the context of differential privacy.\n\nSecond, implementing an effective Nyström-based scheme under privacy constraints is another key contribution. Various Nyström-based schemes have differing quality under privacy constraints. As shown in Figure 1(b) in the paper, the solid lines show the accuracy of private KME estimation using Nyström-based schemes implemented by various landmark selection methods. The standard subsampling-based Nyström method (gray line) performs poorly under privacy constraints. Our discovery that the DP $K$-means landmark selection is effective underlines the importance of investigating clustering-based Nyström methods under privacy constraints.\n\nFinally, our composition framework is a practical strength, enabling adaptive design of private learning algorithms in various settings. Existing private linear ERM algorithms are tailored to specific scenarios, such as convex or non-convex loss, smooth or non-smooth loss, differentiable or non-differentiable regularizer, etc. Since the composition framework only requires the subroutines to be differentially private, it allows one to privately learn various models by substituting private linear ERM algorithms for the corresponding setting.\n\n**W2.** Scalability\n\nWhile the scalability of our algorithm is discussed in terms of computational complexity in line 240, we will provide additional experimental results to address the reviewer's concern in the revised manuscript, if the paper is accepted. For instance, Figure 2 in the attached PDF demonstrates the utility of our algorithm for KME estimation across multiple datasets, with the Gaussian and polynomial kernels. We have conducted similar experiments on additional datasets and obtained consistent results. This additional experiment confirms that the superiority of the proposed algorithm is not confined to the adult dataset alone.\n\n**Q1.** Privacy budget allocation\n\nWe agree that optimizing privacy budget allocations can enhance the effectiveness of private learning. Figure 1 in the attached PDF illustrates that there is a budget combination that outperforms others. One possible explanation is that the optimal allocation may depend on the strength of the clustered structures in the data. For instance, when the number of landmarks $m$ is small relative to the sample size $n$, it is advisable to allocate a larger portion of the privacy budget to the linear ERM rather than the DP $K$-means. This is because a smaller $m$ typically results in larger cluster sizes. Since DP $K$-means algorithms acquire private centroids by averaging the members of each cluster privately, larger clusters tend to lead to more accurate centroids given fixed privacy budgets. Therefore, we can afford to allocate more privacy resources to linear ERM. Further exploration to connect the cluster structure to the quality of the private landmarks is suggested as future work.\n\n**Q2.** Comparison of complexities\n\nWe can provide a comparison of the time complexity of our algorithms versus existing methods for kernel ridge regression. Note that the time complexity of kernel ridge regression in the non-private setting is $O(n^3)$, arising from the inversion of the $n\\times n$ kernel matrix.\n\nThe time complexity of our DP kernel ERM algorithm (Algorithm 1) for kernel ridge regression is $O(nm^2+nmd)$ as given in line 240. The $nmd$ term is the time complexity of the DP $K$-means algorithm, and the $nm^2$ term is the time complexity of the linear regression for $n$ observations of $m$ dimensions with $m<n$. Other candidates, such as the functional noise adding algorithm in Hall et al. (2013) and Algorithm 3 in Jain et al. (2013), have different complexities. The former has a time complexity of $O(n^3)$ since it adds noise for the privacy guarantee after evaluating the non-private model, equating it to the time complexity of non-private kernel ridge regression. The latter has a time complexity of  $O(n^d)$.\n\nAlthough we have only compared the time complexity of DP kernel ERM algorithms for kernel ridge regression, we note that the superiority of our algorithm extends to other kernel ERMs as well. Our algorithm reduces the time complexity by transforming an optimization problem of $n$ observations of $n$ dimensions to $n$ data of $m$ dimensions. However, the algorithm in Hall et al. (2013) requires solving the original optimization problem. Thus our algorithm will be more scalable than Hall et al. (2013) for general ERM. Also, the algorithm in Jain and Thakurta (2013) has a time complexity of $O(n^d)$ for general ERM.\n\nFinally, for the KME estimation (Algorithm 3), the time complexity of our algorithm is $O(nm^2+nmd)$, whereas the existing DP KME estimation algorithm suggested in Balog et al. (2018) has a time complexity of $O(nm^2)$. In this case, our algorithm can be slower than Algorithm 1 in Balog et al. (2018). However, our algorithm demonstrates superior performance compared to Algorithm 1 in Balog et al. (2018), as shown in Figure 1(b) and discussed in lines 318-322.", "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": "", "extra_scores": {}}, {"review_id": "vAKaeBEfeL", "reviewer": "Reviewer_7ffV", "summary": "The paper proposes differentially private scalable kernel ERM and KME algorithms that are more general than the prior works. The authors provide privacy and convergence proofs for their proposed approaches, and experimentally compare their approach with prior works.", "questions": "None", "limitations": "I do not feel there are any negative societal impacts of this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Thorough discussion on background and comparison with prior works\n- Detailed theoretical proofs for the proposed approach\n- Experimental evaluation of the proposed approach", "weaknesses": "None that I could find, although I'm not very familiar with the topic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's positive feedback.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all reviewers for their constructive feedback. We have addressed all comments to the best of our ability. Detailed point-by-point responses to the reviewers' comments are provided below. Additionally, please see the attached one-page PDF for further experimental results.

Meta-review: All reviewers felt this paper sits above the threshold for acceptance, agreeing that it presents novel and practical algorithms for private kernel methods, backed up by both theoretical and empirical evidence, and that the authors have clearly situated it with respect to prior work. The authors are encouraged to incorporate suggestions from the reviewers in their final version, particularly by adding experiments demonstrating scalability and answers to reviewer questions from the rebuttals, which were helpful.
Decision: Accept (poster)