Differential Privacy in Scalable General Kernel Learning via $K$-means Nystr{\"o}m Random Features

We greatly appreciate the reviewer's positive feedback.

W1 Contributions

While it is true that our algorithms utilize existing private learning schemes, we emphasize two novel contributions and one practically critical point:

First, 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.

Second, 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.

Finally, 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.

W2. Scalability

While 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.

Q1. Privacy budget allocation

We 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.

Q2. Comparison of complexities

We 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.

The 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)$.

Although 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.

Finally, 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.

W1. The utility of the versatile method

We 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.

W2. Privacy budget allocation

We 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.

W3. Contributions

While it is true that our algorithms utilize existing private learning schemes, we emphasize two novel contributions and one practically critical point:

First, 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.

Second, 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.

Finally, 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.

Q1. Bi-level optimization.

It 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.

Q2. The scale factor R

The 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.

Q3. The effect of $Q$

In 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.

`$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.