1 Introduction↩︎

In recent years, Machine Learning (ML) models have become ubiquitous in our daily lives. It is now common for these models to be trained on vast amounts of sensitive private data provided by users to offer better services tailored to their needs. However, this has given rise to concerns regarding users’ privacy, and recent works [1]–[3] have demonstrated that attackers can maliciously query ML models to reveal private information. To address this problem, the de-facto standard remedy is to enforce \((\epsilon,\delta)-\)Differential Privacy (DP) guarantees on the ML algorithms [4]. However, satisfying these guarantees often comes at the cost of the model’s utility, unless the amount of available private training data is significantly increased [5]–[9]. A way to alleviate the utility degradation is to leverage feature extractors pre-trained on a large-scale dataset (assumed to be public) and whose data generating distribution can differ from the one from which the private data is sampled [10]–[13]. Training a linear classifier on top of these pre-trained features has been shown to be among the most cost-efficient and effective techniques [10], [11]. Gains in utility can also be obtained if part of the private data is deemed public: a setting known as Semi-Private (SP) learning [14]–[18].

In this work, we propose a SP algorithm to efficiently learn a linear classifier on top of features output by pre-trained neural networks. The idea is to leverage the public data to estimate the Principal Components, and then to project the private dataset on the top-\(k\) Principal Components. For the task of learning linear halfspaces, this renders the algorithm’s sample complexity independent of the dimensionality of the data, provided that the data generating distribution satisfies a low rank separability condition, specified in [defn:low-dim-large-margin]. We call this class of distributions large margin low rank distributions. For the practically relevant task of image classification, we show that pre-trained representations satisfy this condition for a wide variety of datasets. In line with concerns raised by the concurrent work of [19], we demonstrate the effectiveness of our algorithm not only on standard image classification benchmarks used in the DP literature (i.e. CIFAR-10 and CIFAR-100) but also on a range of datasets (1) that we argue better represents the actual challenges of private training.

Indeed, in our evaluations we particularly focus on private data distributions that deviate significantly from the pre-training ones and on low-data regimes. We believe that testing on such relevant benchmarks is essential to demonstrate the practical applicability of our algorithm. Strikingly, we observe that the benefits of our approach increase as the privacy guarantees become tighter, i.e., when \(\epsilon\) is lower. In contrast, we find that reducing the dimensionality of the input without imposing privacy guarantees, i.e., when \(\epsilon=\infty\), leads to a decline in the model’s performance.

To summarise, our contributions are the following:

• We propose an SP algorithm, PILLAR, that improves classification accuracy over existing baselines. Our algorithm, as well as baselines, use representations generated by pre-trained feature extractors. We demonstrate that our improvements are independent of the chosen pre-training strategy.

• We prove that, for learning half-spaces, our algorithm achieves dimension-independent private labelled sample complexity for large margin low rank distributions.

• We improve DP and SP evaluation benchmarks for image classification by focusing on private datasets that differ significantly from pre-training datasets (e.g. ImageNet-1K [23]) and with small amounts training data available. We enforce strict privacy constraints to better represent real-world challenges, and show our algorithm is extremely effective in these challenging settings.

2 Semi-Private Learning↩︎

We begin by defining Differential Privacy (DP). DP ensures that the output distribution of a randomized algorithm remains stable when a single data point is modified. In this paper, a differentially private learning algorithm produces comparable distributions over classifiers when trained on neighbouring datasets. Neighbouring datasets refer to datasets that differ by a single entry. Formally,

For \(\epsilon < 1\) and \(\delta = o\br{1/n}\), \((\epsilon, \delta)\)-differential privacy provides valid protection against potential privacy attacks [3].

2.0.0.1 Differential Privacy and Curse of Dimensionality

Similar to non-private learning, the most common approach to DP learning is through Differentially Private Empirical Risk Minimization (DP-ERM), with the most popular optimization procedure being DP-SGD [20] or analogous DP-variants of typical optimization algorithms. However, unlike non-private ERM, the sample complexity of DP-ERM suffers from a linear dependence on the dimensionality of the problem [24], [25]. Hence, we explore slight relaxations to this definition of privacy to alleviate this problem. We show theoretically (3) and through extensive experiments ([sec:exp-main,sec:exp-shift]) that this is indeed possible with some realistic assumptions on the data and a slightly relaxed definition of privacy known as semi-private learning that we describe below. For a discussion of broader impacts and limitations, please refer to 10.

2.1 Semi-Private Learning↩︎

The concept of semi-private learner was introduced in [14]. In this setting, the learning algorithm is assumed to have access to both a private labelled and a public (labelled or unlabelled) dataset. In this work, we assume the case of only having an unlabelled public dataset. This specific setting has been referred to as Semi-Supervised Semi-Private learning in [14]. However, for the sake of brevity, we will refer to it as Semi-Private learning (SPL).

A key distinction between our work and the previous study by [14] is that they examine the distribution-independent agnostic learning setting, whereas we investigate the distribution-specific realisable setting. On the other hand, while their algorithm is computationally inefficient, ours can be run in time polynomial in the relevant parameters and implemented in practice on various datasets with state-of-the-art results. We discuss our algorithm in 2.2.

2.1.0.1 Relevance of Semi-Private Learning

In various privacy-sensitive domains such as healthcare, legal, social security, and census data, there is often some amounts of publicly available data in addition to the private data. For instance, the U.S. Census Bureau office has partially released historical data before 2020 without enforcing any differential privacy guarantees ¹. It has also been observed that different data providers may have varying levels of concerns about privacy [26]. In medical data, some patients may consent to render some of their data public to foster research. In other cases, data may become public due to the expiration of the right to privacy after specific time limits ².

It is also very likely that this public data may be unlabelled for the task at hand. For example, if data is collected to train a model to predict a certain disease, the true diagnosis may have been intentionally removed from the available public data to protect sensitive information of the patients. Further, the data may had been collected for a different purpose like a vaccine trial. Finally, the cost of labelling may be prohibitive in some cases. Hence, when public (unlabelled) data is already available, we focus on harnessing this additional data effectively, while safeguarding the privacy of the remaining private data. We hope this can lead to the development of highly performant algorithms which in turn can foster wider adoption of privacy-preserving techniques.

2.2 PILLAR: An Efficient Semi-Private Learner↩︎

In this work, we propose a (semi-supervised) semi-private learning algorithm called PILLAR (PrIvate Learning with Low rAnk Representations), described in 2. Before providing formal guarantees in 3, we first describe how PILLAR is applied in practice. Our algorithm works in two stages.

Leveraging recent practices [10], [11] in DP training with deep neural networks, we first use pre-trained feature extractors to transform the private labelled and public unlabelled datasets to the representation space to obtain the private and public representations. We use the representations in the penultimate layer of the pre-trained neural network for this purpose. As shown in 2, the feature extractor is trained on large amounts of labelled or unlabelled public data, following whatever training procedure is deemed most suitable. For this paper, we pre-train a ResNet-50 using supervised training (SL), self-supervised training (BYOL [22] and MocoV2+ [27]), and semi-supervised training (SemiSL and Semi-WeakSL [28]) on ImageNet. In the main body, we only focus on SL and BYOL pre-training. As we discuss extensively in 9.6, our algorithm is effective independent of the choice of the pre-training algorithm. In addition, while the private and public datasets are required to be from the same (or similar) distribution, we show that the pre-training dataset can come from a significantly different distribution. In fact, we use ImageNet as the pre-training dataset for all our experiments even when the distributions of the public and private datasets range from CIFAR-10/100 to histological and x-ray images as shown in 1. Recently, [29] have explored the complementary question of how to choose the right pre-training dataset.

In the second stage, PILLAR takes as input the feature representations of the private labelled and public unlabelled datasets, and feeds them to [alg:no95shift]. We denote these datasets of representations as \(\Slab\) and \(\Sunl\) respectively. Briefly,  [alg:no95shift] projects the private dataset \(\Slab\) onto a low-dimensional space spanned by the top principal components estimated with \(\Sunl\), and then applies gradient-based private algorithms (e.g. Noisy-SGD [25]) to learn a linear classifier on top of the projected features. [alg:no95shift] provides an implementation of PILLAR with Noisy-SGD, whereas in our experiments we show that commonly used DP-SGD [20] is also effective.

3 Theoretical Results↩︎

In this section, we first describe the assumptions under which we provide our theoretical results and show they can be motivated both empirically and theoretically. Then, we show a dimension-independent sample complexity bound for PILLAR under the mentioned assumptions.

3.1 Problem setting↩︎

Our theoretical analysis focuses on learning linear halfspaces \(\linear{d}\) in \(d\) dimensions. Consider the instance space \(\instspace_d = B_2^{d} = \bc{x\in \bR^{d}: \norm{x}_2 =1}\) as the \(d\)-dimensional unit sphere and the binary label space \(\cY=\bc{-1,1 }\). In practice, the instance space is the (normalized) representation space obtained from the pre-trained network. The hypothesis class of linear halfspaces is \[\linear{d} = \bc{f_w(x) = \text{sign}\br{\ba{w, x}}\vert w \in B_2^d }.\]

We consider the setting of distribution-specific learning, where our family of distributions admits a large margin linear classifier that contains a significant projection on the top principal components of the population covariance matrix. We formalise this as \(\br{\gamma,\xi_k}\)-Large margin low rank distributions.

It is worth noting that for every distribution that admits a positive margin \(\gamma\), the low-rank separability condition is automatically satisfied for all \(k\leq d\) with some \(\xi_k\geq 0\). However, the low rank separability is helpful for learning, only if it holds for a small \(k\) and small \(\xi_k\) simultaneously. These assumptions are both theoretically and empirically realisable. Theoretically, we show in 1 that a class of commonly studied Gaussian mixture distributions satisfies these properties. Empirically, we show in 3 that pre-trained features satisfy these properties with small \(\xi\) and \(k\).

For any \(\theta, \sigma^2 = O(\frac{1}{\sqrt{d}})\), it is easy to see that this family of distributions satisfies the large margin low rank properties in [defn:low-dim-large-margin] for \(k = 2\) and \(\xi=0\). Next, we show empirically that these assumptions approximately hold on the features of pre-trained feature extractors we use in this work.

3.1.0.1 Pre-trained features are almost Large-Margin and Low-Rank

 3 shows that feature representations of CIFAR-10 and CIFAR-100 obtained by various pre-training strategies approximately satisfy the conditions of [defn:low-dim-large-margin]. To verify the low-rank separability assumption, we first train a binary linear SVM \(\tw\) for a pair of classes on the representation space and estimate \(\xi_k=1-\norm{A_kA_k^{\top}\tw}_2\) as defined in [defn:low-dim-large-margin]. We also compute \(\xi_k\) when \(\tw\) is trained on the pixel space ³. As shown in 3, images in the representation space are better at satisfying the low-rank separability assumption compared to images in the pixel space.

3.2 Private labelled sample complexity analysis↩︎

In this section, we bound the sample complexity of PILLAR for learning linear halfspaces. Our theoretical analysis relies on a scaled hinge loss function that depends on the privacy parameters \(\epsilon, \delta\), as well as an additional parameter \(\zeta\), characterized by \(\gamma\) and \(\xi_k\). We also denote the gap between the \(k^\mathrm{th}\) and the \({k+1}^{\mathrm {th}}\) eigenvalue of the population covariance matrix as \(\deltak\).

[thm:no-shift] shows that if the private and public datasets come from the same large-margin low rank distribution, then PILLAR defined in [alg:no95shift] is both \(\br{\epsilon,\delta}\)-DP with respect to the private dataset as well as accurate, with relatively small number of private labelled data. As motivated in 3.1, the feature representations of images are usually from large-margin low rank distributions. Thus, in practical implementation, the private and public datasets refer to private and public representations, as shown in 2.

Note that while [thm:no-shift] only guarantees \((\epsilon, \delta)\)-DP on the set of private representations in 2, this guarantee can also extend to \((\epsilon, \delta)\)-DP on the private labelled image dataset. See 8.2 for more details. For large margin Gaussian mixture distributions, [thm:no-shift] implies that PILLAR leads to a drop in the private sample complexity from \(O(\sqrt{d})\) to \(O(1)\). The formal statement with the proof is provided in 8.5.

3.2.0.1 Tolerance to distribution shift

In real-world scenarios, there is often a distribution shift between the labeled and unlabeled data. For instance, when parts of a dataset become public due to voluntary sharing by the user, there is a possibility of a distribution shift between the public and private datasets. To handle this situation, we use the notion of Total Variation (TV) distance. Let \(D^L\) be the labelled data distribution, \(D^L_X\) be its marginal distribution on \(\cX\), and \(D^U\) be the unlabelled data distribution. We say \(D^L_X\) and \(D^U\) have \(\eta\)-bounded TV distance if \[TV(D^U, D^L_X) = \sup_{A\subset \cX} \vert D^U(A) - D^L_X(A)\vert \leq \eta.\]

We extend the definition of semi-private learner to this setting. An algorithm \(\cA\) is an \(\eta\)-TV tolerant \((\alpha, \beta, \epsilon, \delta)\)-semi-private learner if it is a \((\alpha, \beta, \epsilon, \delta)\)-semi-private learner when the labelled and unlabelled distributions have \(\eta\)-bounded TV.

[thm:with-shift] provides a stronger version of [thm:no-shift], which can tolerate a distribution shift between labeled and unlabeled data. Refer to 8.4 for a formal definition of \(\eta\)-TV tolerant \((\alpha, \beta, \epsilon,\delta)\)-learner and a detailed version of [thm:with-shift] with its proof.

3.3 Comparison with existing theoretical results and discussion↩︎

Existing works have offered a variety of techniques for achieving dimension-independent sample complexity. In this section, we review these works and compare them with our approach.

3.3.0.1 Generic private algorithms

 [30] proposed the Noisy SGD algorithm \(\Anoisy\) to privately learn linear halfspaces with margin \(\gamma\) on a private labelled dataset of size \(O(\frac{\sqrt{d}}{\alpha\epsilon\gamma})\). Recently,  [21] showed that DP-SGD, a slightly adapted version of \(\Anoisy\), can achieve a dimension independent error bound under a low-dimensionality assumption termed as Restricted Lipschitz Continuity (RLC). However, these methods cannot utilise public unlabelled data. Moreover, the low dimensional assumption with RLC is more stringent compared with our low-rank separability assumption. In contrast, generic semi-private learner in [14] leverages unlabelled data to reduce the infinite hypothesis class to a finite \(\alpha\)-net and applies exponential mechanism [31] to achieve \((\epsilon, 0)\)-DP. Nonetheless, it is not computationally efficient and still requires a dimension-dependent labelled sample complexity \(\bigO{\frac{d}{\alpha\epsilon}}\).

3.3.0.2 Dimension reduction based private algorithms

Perhaps, most relevant to our work, [32] applies Johnson-Lindenstrauss (JL) transformation to reduce the dimension of a linear halfspace with margin \(\gamma\) from \(d\) to \(\bigO{\frac{1}{\gamma}}\) while preserving the margin in the lower-dimensional space. Private learning in the transformed low-dimensional space requires \(\bigO{\frac{1}{\alpha\epsilon\gamma^2}}\) labelled samples. Our algorithm removes the quadratic dependence on the inverse of the margin but pays the price of requiring the linear separator to align with the top few principal components of the data. For example, a Gaussian mixture distribution (1) satisfies large margin low rank property with parameters \(\xi_k = 0\) and \(k = 1\). 2 shows that our algorithm requires labelled sample complexity \(O(\frac{1}{\alpha\epsilon\gamma})\) instead of \(O(\frac{1}{\alpha\epsilon\gamma^2})\) required by [32]. Low dimensionality assumptions have also successfully been exploited in differentially private data release [33], [34], however their work is unrelated to ours and we do not compare with this line of work.

Another approach to circumvent the dependency on the dimension is to apply dimension reduction techniques directly to the gradients. For smooth loss functions with \(\rho\)-Lipschitz and \(G\)-bounded gradients, [35] showed that applying PCA in the gradient space of DP-SGD [20] achieves dimension-independent labelled sample complexity \(\bigO{\frac{k\rho G^2}{\alpha\epsilon} + \frac{\rho^2 G^4\log d}{\alpha}}\). However, this algorithm is computationally costly as it applies PCA in every gradient-descent step to a matrix whose size scales with the number of parameters. [36] proposed a computationally efficient method by applying JL transformation in the gradient space. While their method can eliminate the linear dependence of DP-SGD on dimension when the parameter space is the \(\ell_1\)-ball, it leads to no improvement for parameter space being the \(\ell_2\)-ball as in our setting. Gradient Embedding Perturbation (GEP) by [15] is also computationally efficient. However, their analysis yields dimension independent guarantees only when a strict low-rank assumption of the gradient space is satisfied. We discuss these works and compare the assumptions in more detail in 8.6.

3.3.0.3 Other private algorithms

Boosting is another method for improving the utility-privacy tradeoff. [37] analyzed private boosting for learning linear halfspaces with margin \(\gamma\). They proposed a weak learner that is insensitive to the label noise and can achieve dimension independent sample complexity \(O(\frac{1}{\alpha\epsilon\gamma^2})\), matching the sample complexity achieved by applying JL transformation [32].

3.3.0.4 Non-private learning and dimensionality reduction

It is interesting to note that our algorithm may not lead to a similar improvement in the non-private case. We show a dimension-independent Rademacher-based labelled sample complexity bound for non-private learning of linear halfspaces. We use a non-private version of [alg:no95shift] by replacing Noisy-SGD with Gradient Descent using the same loss function. As before, for any \(\gamma_0\in (0, 1), \xi_0\in (0, 1)\), let \(\cD_{\gamma_0, \xi_0}\) be the family of distributions consisting of all \((\gamma, \xi_k)\)-large margin low rank distributions with \(\gamma \geq \gamma_0\) and \(\xi_k\leq \xi_0\).

The result follows directly from the uniform convergence of linear halfspaces with Rademacher complexity. For example, refer to Theorem 1 in [38]. The labelled sample complexity in the above result shows that non-private algorithms do not significantly benefit from decreasing dimensionality⁴. We find this trend to be true in all our experiments in [fig:neardist,fig:farshift]. In summary, this section has showed that our computationally efficient algorithm, under certain assumptions on the data, can yield dimension independent private sample complexity. We also show through a wide variety of experiments that the results transfer to practice in both common benchmarks as well as many newly designed challenging settings.

4 Results on Standard Image Classification Benchmarks↩︎

In this section, we report performance of PILLAR on two standard benchmarks (CIFAR-10 and CIFAR-100 [39]) for private image classification. In particular, we show how its performance changes with varying dimensions of projection \(k\) for varying privacy parameter \(\epsilon\).

4.1 Evaluation on CIFAR-10 and CIFAR-100↩︎

4.1.0.1 Experimental setting

 The resolution difference between ImageNet-1K and CIFAR images can negatively impact the performance of training a linear classifier on pre-trained features. To mitigate this issue, we pre-process the CIFAR images using the ImageNet-1K transformation pipeline, which increases their resolution and leads to significantly improved performance. This technique is consistently applied throughout the paper whenever there is a notable resolution disparity between the pre-training and private datasets. For further details and discussions on pre-training at different resolutions, please refer to 9.2.

We diverge from previous studies in the literature, such as those conducted by [10], [11], [13], by not exclusively focusing on values of \(\epsilon > 1\). While a moderately large \(\epsilon\) can be insightful for assessing the effectiveness of privately training deep neural networks with acceptable levels of accuracy, it is important to acknowledge that a large value of \(\epsilon\) can result in loose privacy guarantees. [40] emphasizes that reasonable values of \(\epsilon\) are expected to be less than 1. Moreover, [41] and [42] have already highlighted that \(\epsilon > 1\) leads to loose upper bounds on the success probability of membership inference attacks. Consequently, we focus on \(\epsilon \in {0.1, 0.7, \infty}\), where \(\epsilon=\infty\) corresponds to the public training of the linear classifier. However, we also present results for \(\epsilon=1,2\) in 9.3.

4.1.0.2 Reducing dimension of projection \(k\) helps private learning

In 4, we present the test accuracy of private and non-private trianing on CIFAR-10 and CIFAR-100 as the dimensionality of projection (PCA dimension) varies, with an initial embedding dimension of \(k=2048\). The principal components are computed on a public, unlabelled dataset that constitutes 10% of the full dataset, as allowed by Semi-Private Learning in [defn:private-learning]. Our results demonstrate that private training benefits from decreasing dimensionality, while non-private training either performs poorly or remains stagnant. For example, using the SL feature extractor at \(\epsilon=0.1\) on CIFAR-10, the test accuracy of private training reaches \(81.21\%\) when \(k=40\), compared to \(76.9\%\) without dimensionality reduction. Similarly, for CIFAR-100 with the SL feature extractor at \(\epsilon=0.7\), the accuracy drops from \(55.98\%\) at \(k=200\) to \(50.83\%\) for the full dimension.

This observed dichotomy between private and non-private learning in terms of test accuracy and projection dimension aligns with [thm:no-shift] and [thm:nondp] in 3.3. [thm:no-shift] indicates that that the private test accuracy improves as the projection dimension decreases, as depicted in 4. For non-private training with moderately large dimension, (\(k\geq 520\)), the test accuracy remains largely constant. We discuss this theoretically in [thm:nondp]  3.3. The decrease in non-private accuracy for very small values of \(k\) is attributed to the increasing approximation error (i.e. how well can the best classifier in \(k\) dimensions represent the ground truth). This difference in behaviour between private and non-private learning for decreasing \(k\) values is observed consistently in all our experiments and is one of the main contributions of this paper. While we have demonstrated the effectiveness of our algorithm on the CIFAR-10 and CIFAR-100 benchmarks, as discussed in 5, we acknowledge that this evaluation setting may not fully reflect the actual objectives of private learning.

4.2 Comparison with Existing Methods↩︎

To ensure a fair comparison, we focus on the setting where \(\epsilon=0.7\) and use the RDP accountant [43] instead of the PRV accountant [44] employed throughout the rest of the paper. For a comprehensive discussion on the rationale behind this choice, implementation details, and the cross-validation ranges for hyper-parameters across all methods, refer to 9.5

4.2.0.1 Baselines

We consider the following baselines: 

Whenever public data is utilized, we employ \(10\%\) of the training data as public and remaining data as private. The official implementations of AdaDPS and GEP are used for our comparisons. In 9.4, we discuss PATE [17], [18] and the reasons for not including it in our comparisons. For a detailed comparison with the work of [11], including the use of a different feature extractor to ensure a fair evaluation, we refer to 9.2, where we demonstrate that our method is competitive, if not superior, while being significantly computationally more efficient.

4.2.0.2 Results

In Table 1, we compare our approach with other methods in the literature. Our results suggest that reducing dimensionality by using the JL transformation is insufficient to even outperform DP-SGD. This may be attributed to the higher sample size required for their bounds to provide meaningful guarantees. Similarly, employing public data to pre-condition an adaptive optimizer does not result in improved performance for AdaDPS. Additionally, GEP also does not surpass DP-SGD, potentially due to its advantages being more pronounced in scenarios with much higher model dimensionality. Considering their lower performance on this simpler benchmark compared to DP-SGD and the extensive hyperparameter space that needs to be explored for most baselines, we focus on the strongest baseline (DP-SGD) for more challenging and realistic evaluation settings in 5.

5 Experimental Results Beyond Standard Benchmarks↩︎

In line with concurrent work [19], we raise concerns regarding the current trend of utilizing pre-trained feature extractors [10], [11] for differentially private training. It is common practice to evaluate differentially private algorithms for image classification by pre-training on ImageNet-1K and performing private fine-tuning on CIFAR datasets [10], [11]. However, we argue that this approach may not yield generalisable insights for privacy-sensitive scenarios. Both ImageNet and CIFAR datasets primarily consist of everyday objects, and the label sets of ImageNet are partially included within CIFAR. Such a scenario is unrealistic for many privacy-sensitive applications, such as medical, finance, and satellite data, where a large publicly available pre-training dataset with similar characteristics to the private data may not be accessible.

Moreover, public datasets are typically large-scale and easily scraped from the web, whereas private data is often collected on a smaller scale and subject to legal and competitive constraints, making it difficult to combine with other private datasets. Additionally, labeling private data, particularly in domains such as medical or biochemical datasets, can be costly. Therefore, evaluating the performance of privacy-preserving algorithms requires examining their robustness with respect to small dataset sizes. In order to address these considerations, we assess the performance of our algorithm on five additional datasets that exhibit varying degrees of distribution shift compared to the pre-training set, as described in 5.1. Furthermore, we also demonstrate the robustness of our algorithm to minor distribution shifts between public unlabeled and private labeled data. In 5.2, we show our algorithm is also robust to both small-sized private labeled datasets and public unlabeled datasets.

5.1 Effectiveness under Distribution Shift↩︎

5.1.0.1 Distribution Shift between Pre-Training and Private Data

We consider private datasets that exhibit varying levels of dissimilarity compared to the ImageNet pre-training dataset: Flower-16 [45], GTSRB [46], Pneumonia [47], a fraction (\(12.5\%\)) of PCAM [48], and DermNet [49]. In 1, we provide visual samples from each of these datasets. Flower-16 and GTSRB have minimal overlap with ImageNet-1K, with only one class in Flower-16 and 43 traffic signs aggregated into a single label in ImageNet-1K. The Pneumonia, PCAM, and DermNet datasets do not share any classes with ImageNet-1K. We also observe that, given a fixed pre-training distribution and model, different training procedures can have a different impact in the utility of the extracted features for each downstream classification task. Therefore, for each dataset we report the best performance produced by the most useful pre-training algorithm. Results for all the 5 pre-training strategies we consider and a discussion of how to choose them is relegated to 9.6.

In 5, we demonstrate that reducing the dimensionality of the pre-trained models enhances differentially private training, irrespective of the private dataset used. For instance, when applying the SL feature extractor to Flower-16 at at \(\epsilon=0.1\) with \(k=40\), the accuracy improves to \(69.3\%\) compared to only \(41.2\%\) when using the full dimensionality. For DermNet, PCAM, and Pneumonia at \(\epsilon=0.1\), we observe accuracy improvements from \(14\%\) to \(19\%\), from \(75\%\) to \(77.5\%\), and from \(65\%\) to \(83\%\) respectively. Dimensionality reduction has a more pronounced effect on performance when tighter privacy constraints are imposed. It is worth noting that using dimensionality reduction can significantly degrade performance for non-DP training, as observed in CIFAR-10 and CIFAR-100.

5.1.0.2 When to use labels in pre-training

We also investigate the impact of different pre-training strategies on DP test accuracy. From [fig:neardist,fig:farshift], we observe that some pre-trained models are more effective than others for specific datasets. To measure the maximum attainable accuracy with a publicly trained classifier, we compute the drop in performance, observed by training a DP classifier on BYOL pre-trained features, and the drop in performance for SL pre-trained features. We then plot the fractional reduction for both BYOL and SL across all the datasets for \(\epsilon=0.1\) in Figure 6. In 10 we compare the relative reduction in performance when using Semi-supervised pre-training and BYOL pre-training. We find that datasets with daily-life objects and semantic overlap with ImageNet-1K benefit more from leveraging SL features and thus have a smaller reduction in accuracy for SL features compared to BYOL features. In contrast, datasets with little label overlap with ImageNet-1K benefit more from BYOL features, consistent with findings by [50].

5.1.0.3 Distribution Shift between \(\Sunl\) and \(\Slab\)

We demonstrate the effectiveness of our algorithm even when the public unlabeled data (used for computing the PCA projection matrix) is sourced from a slightly different distribution than the private labeled dataset. Specifically, we utilize the CIFAR-10v1 [51] dataset and present the results in [tab:c10v1]. Notably, CIFAR-10v1 consists of only \(2000\) samples (\(4\%\) of the training data), yet the results for both CIFAR-10 and CIFAR-100 remain essentially unchanged. This finding indicates that the data used to compute the PCA projection matrix does not necessarily have to originate from the same distribution as the private data and underscores that large amounts of public data are not required for our method to be effective.

5.2 Effectiveness in Low-Data Regimes↩︎

In privacy-critical settings such as medical contexts, there is often a limited availability of training data. For instance, the DermNet and pneumonia datasets contain only 12,000 and 3,400 training data points, respectively, which is significantly smaller compared to datasets like CIFAR-10 with 50,000 samples. To examine the impact of reduced data (both private labeled and public unlabeled) on privacy, in this section we conduct ablations using different fractions of training data on the CIFAR-100 and GTSRB datasets. Please refer to 9.1 for more details. .

5.2.0.1 Less private labelled data

In 7, we present the performance of private and public training using different percentages of labeled training data for CIFAR-100 and GTSRB. Our results indicate that under stringent privacy constraints \(\br{\epsilon \in\bc{0,7,0.1}}\), the performance of DP training, without dimensionality reduction, is considerably low. Conversely, even with a small percentage of training data, non-DP training demonstrates relatively high performance. By applying our algorithm in this scenario, we achieve significant performance improvements compared to using the full-dimensional embeddings. For instance, applying PCA with with \(k=40\) dimensions enhances the accuracy of our proposed algorithm from \(7.53\%\) to \(18.3\%\) on \(10\%\) of CIFAR-100, with \(\epsilon=0.7\) using the SL feature extractor. Similar improvements are also shown for GTSRB and to a smaller extent for \(\epsilon=0.1\)

5.2.0.2 Less public unlabelled data

We demonstrate the robustness of our algorithm to reduced amounts of public unlabeled data. In [tab:low-public-data], we vary the amount of public data and observe that the performance of our algorithm remains mostly stable despite decreasing amounts of public data.

6 Conclusion↩︎

In this paper, we consider the setting of semi-private learning where the learner has access to public unlabelled data in addition to private labelled data. This is a realistic setting in many circumstances e.g. where some people choose to make their data public. Under this setting, we proposed a new algorithm to learn linear halfspaces. Our algorithm uses a mix of PCA on unlabelled data and DP training on private data. Under reasonable theoretical assumptions, we have shown the proposed algorithm is \((\epsilon,\delta)\)-DP and provably reduces the sample complexity. In practical applications, we performed an extensive set of experiments that show the proposed technique is effective when tight privacy constraints are imposed, even in low-data regimes and with a significant distribution shift between the pre-training and private distribution.

7 Acknowledgements↩︎

AS acknowledges partial support from the ETH AI Center Postdoctoral fellowship. FP acknowledges partial support from the European Space Agency. AS, FP, and YH also received funding from the Hasler Stiftung. We also thank Florian Tramer for useful feedback.

8 Proofs↩︎

8.1 Noisy SGD↩︎

In this section, we present 8, an adapted version of the Noisy SGD algorithm from [30] for \(d\)-dimensional linear halfspaces \(\linear{d}\), that is used as a sub-procedure in [alg:no95shift]. 8 first applies a base procedure \(\cA_{Base}\) on \(\linear{d}\) for \(k\) times to generate a set of \(k\) results while preserving \((\epsilon, \delta)\)-DP, and then applies the exponential mechanism \(\cM_E\) to output one final result from the set.

In [lem:noisy-sgd-guarantee-emp], we state the privacy guarantee and the high probability upper bound on the excess error of the adpated version of Noisy SGD (8). This is a corollary of Theorem 2.4 in [25], which provides an upper bound on the expected excess risk of \(\cA_{Base}\). The proof of [lem:noisy-sgd-guarantee-emp] follows directly from Markov inequality and the post-processing property of DP ([lem:dp-post-processing]), as described in Appendix D of [25].

8.2 Proof of [thm:no-shift]↩︎

8.3 Privacy guarantees for PILLAR on the original image dataset↩︎

As described in 2, in practice PILLAR is applied on the set of representations obtained by passing the private dataset of images through a pre-trained feature extractor. Therefore, a straightforward application of [thm:no-shift] yields an \(\br{\epsilon,\delta}\)-DP guarantee on the set of representations and not on the dataset in the raw pixel space themselves. Here, we show that PILLAR provides (at least) the same DP guarantees on the dataset in the pixel space as long as the pre-training dataset cannot be manipulated by the privacy adversary. One way to achieve this, as we show is possible in this paper, is by using the same pre-trained model across different tasks. Investigating the extent of privacy harm that can be caused by allowing the adversary to manipulate the pre-training data remains an important future direction.

8.4 Proof of [thm:with-shift]↩︎

In this section, we restate [thm:with-shift] with additional details and present its proof. Before that, we formally define \(\eta\)-TV tolerant semi-private learning.

Now, we are ready to prove that PILLAR is an \(\eta\)-TV tolerant \((\alpha, \beta, \epsilon, \delta)\)-semi-private learner when instantiated with the right arguments.

8.5 Large margin Gaussian mixture distributions↩︎

Here, we provide the sample complexity of PILLAR on the class of large margin mixture of Gaussian mixture distributions defined in 1. We present a corollary following [thm:no-shift], which shows that for large margin Gaussian mixture distributions, PILLAR leads to a drop in the private sample complexity from \(O(\sqrt{d})\) to \(O(1)\).

Here, in line with the notation of [defn:low-dim-large-margin], \(\gamma\) intuitively represents the margin in the \(d\)-dimensional space and \(M\) is the upper bound for the radius of the labelled dataset. For \(\theta = \sigma^2 = \frac{1}{2C\sqrt{d}}\) and ignoring the logarithmic terms, we get \(M = 1.5\) and \(\gamma = 0.5\). 2 implies the labelled sample complexity \(\tilde{O}\br{\frac{1}{\alpha\epsilon}}\).

8.6 Discussion of assumptions for existing methods↩︎

4 summarises the comparison of our theoretical results with some existing methods. We describe the notation used in the table below.

8.6.0.1 Analysis of the Restricted Lipschitz Continuity (RLC) assumption [21]

As indicated in 4, DP-SGD [21] achieves dimension independent sample complexity if the following assumption, known as Restricted Lipschitz Continuity (RLC) is satisfied. For some \(k\ll d\), \[\label{eq:RLC-assumption} \sum_{i = 1}^{\lfloor\log(d/k)+1\rfloor}G_{2^{i-1}k}^2 \leq O(\sqrt{\frac{k}{d}}),\tag{34}\] where \(G_0, G_1, ..., G_d\) represent the RLC coefficients. For any \(i\in [d]\), the loss function \(\ell\) is said to satisfy RLC with coefficient \(G_i\) if \[\label{eq:RCL-coef-definition} \quad G_i \geq \min_{\substack{\rank{P_i}=i\\P_i\in\Pi}} \norm{(I - P_i)\nabla \ell(w; (x, y))}_2,\tag{35}\] for all \(w,x,y\in\text{domain}\br{\ell}\), where \(\Pi\) is the set of orthogonal projection matrices. Equivalently, assumption 34 states that for some \(k\ll d\), \[\label{eq:RLC-assumption-simplified} \sum_{i = k+1}^{d}G_{i}^2 \leq O(\sqrt{\frac{k}{d}}).\tag{36}\]

In this section, we demonstrate that if we assume the Restricted Lipschitz Continuity (RLC) condition from [21], our low rank separability assumption on \(\norm{A_k A_k^\top \tw}\) holds for large-margin linear halfspaces. However, using the RLC assumption leads to a looser bound compared to our assumption. More specifically, given the 36 assumption and the loss function \(\ell\) defined in [eq:loss-funtion-alg], we can show \(\norm{A_k A_k^\top \tw}\geq \gamma\).

Given the parameter \(\zeta\) in [alg:no95shift], for \(x, y\in \supp{D}\) and \(w\) satisfying \(y\ba{w, x}\leq \zeta\), we can calculate the \(i^{\text{th}}\) restricted Lipschitz coefficient \[\label{eq:loss-function-rlc-bound} \begin{align} G_i &\geq \min_{\substack{\rank{P_i}=1\\P_i\in\Pi}} \norm{(I - P_i)\nabla \ell(w; (x, y))}_2 \\ &= \min_{\substack{\rank{P_i}=1\\P_i\in\Pi}}\norm{\frac{y}{\zeta}(I - P_i)x}_2\\ &= \min_{\substack{\rank{P_i}=1\\P_i\in\Pi}} \norm{\frac{1}{\zeta}\br{x - P_ix}}_2. \end{align}\tag{37}\]

Equivalently, we can rewrite 37 as there exists a rank-\(i\) orthogonal projection matrix \(\Pigood\) such that \[\label{eq:gradient-rank-i-bound} \norm{x - \Pigood x}_2 \leq \zeta G_i.\tag{38}\]

Thus, for \(x\) such that \(y\ba{w, x}\leq \zeta\), \[\label{eq:rlc-upper-bound1} \begin{align} \norm{xx^\top - (\Pigood x)(\Pigood x)^\top }_\op &\overset{(a)}{=} \norm{(x-\Pigood x)(x+\Pigood x)^\top}_2 \\ &\leq \norm{x+\Pigood x}_2\norm{x - \Pigood x}_2\\ &\overset{(b)}{\leq} 2\norm{x - \Pigood x}_2 \\ &\overset{(c)}{\leq} 2G_i \zeta \end{align}\tag{39}\] where step \((a)\) follows from the orthogonality of \(\Pigood\), step \((b)\) follows from \(\norm{\Pigood x}_2\leq \norm{x}_2 = 1\), and step \((c)\) follows from 38 .

Then, we can bound the low-rank approximation error for the covariance matrix of the data distribution. \[\begin{align} \norm{\cov_X - \Pigood \cov_X (\Pigood) ^\top}_{\op} \overset{(a)}{\leq} \bE_{x\sim D_X}\br{\norm{xx^\top - (\Pigood x)(\Pigood x)^\top }_{\op}} \overset{(b)}{\leq} 2G_i \zeta. \end{align}\] where \(\cov_X = \bE_{x\sim D_X}\bs{xx^\top}\), and step \((a)\) follows from the convexity of the Euclidean norm and step \((b)\) follows from 39 .

This further provides an upper bound on the last \(d-k\) eigenvalues of the covariance matrix \(\cov_X\) of the data distribution \(D_X\). Let \(\lambda_i\) denote the \(i^{\text{th}}\) eigenvalue of the covariance matrix \(\cov_X\). Then, we apply [lem:rank-k-approximation] that gives an upper bound on the singular values of a matrix in terms of the rank \(k\) approximation error of the matrix.

This gives an upper bound on the \(i^{\text{th}}\) eigenvalue of the covariance matrix \(\cov_X\) in terms of the \(i^{\text{th}}\) restricted Lipschitz coefficient, \[\lambda_{i+1} = \sigma_{i+1}^2 = \inf_{\rank{\cov_X'} = i} \norm{\cov_X - \cov_X'}_{\op}^2\leq \norm{\cov_X - \Pigood \cov_X (\Pigood)^\top}^2_{\op}\leq 4G_i^2\zeta^2.\]

Thus, for matrix \(A_k\) consisting of the first \(k\) eigenvectors of \(\cov_X\), we can upper bound the reconstruction error of \(A_k^\top x\) with the eigenvalues of the covariance matrix \(\cov_X\),

\[\begin{align} \bE_{x\sim D_X}\bs{\norm{x}_2 - \norm{A_k^\top x}_2} &= \bE_{x\sim D_X}\bs{\norm{xx^\top}_{\op} - \norm{(A_k x)(A_k x)^\top}_{\op}} \\ &\leq \bE_{x\sim D_X}\bs{\norm{xx^\top - (A_k x)(A_k x)^\top}}_{\op}\leq \sum_{i = k+1}^d \lambda_i \leq 4\zeta^2\sum_{i = k+1}^d G_i^2. \end{align}\] By Markov’s inequality, with probability at least \(1-\beta\), \[\label{eq:hp-low-rank-property-uppper} \begin{align} &\bP_{x\sim D_X}\bs{\norm{xx^\top}_{\op} -\norm{(A_k^\top x)(A_k^\top x)^\top}_{\op}\geq \frac{4\zeta^2}{\beta}\sum_{i = k+1}^dG_i^2} \\ &\leq \bP_{x\sim D_X}\bs{\norm{xx^\top - (A_k^\top x)(A_k^\top x)^\top}_{\op} \leq\frac{4\zeta^2}{\beta}\sum_{i = k+1}^dG_i^2} \leq \beta. \end{align}\tag{40}\]

This implies our assumption with probability at least \(1-\beta\), \[\label{eq:rlc-our-assumption} \begin{align} \norm{A_k A_k^\top \tw}_2 &\overset{(a)}{=} \norm{x}_2\norm{A_k A_k^\top \tw}_2 \geq |\ba{A_k A_k^\top x, \tw}|\\ &\overset{(b)}{\geq} |\ba{x, \tw}| - |\ba{x - A_k A_k^\top x, \tw}|\\ &\overset{(c)}{\geq} \gamma - \norm{x - A_k A_k^\top x}_2\norm{\tw}_2 \\ &\overset{(d)}{\geq} \gamma - \frac{4 \zeta^2}{\beta}\sum_{i = k+1}^dG_i^2 \end{align}\tag{41}\] where step \((a)\) follows from \(\norm{x}_2 = 1\), step \((b)\) follows by \(\ba{A_k A_k^\top x, \tw} = \ba{x, \tw}-\ba{x - A_k A_k^\top x, \tw}\) and the triangle inequality, step \((c)\) follows by the large margin assumption \(y\ba{x, \tw} = \abs{\ba{x, \tw}}\geq \gamma\), and step \((d)\) follows by 40 with probability at least \(1-\beta\).

The RLC assumption requires the last term in 41 to vanish at the rate of \(O(\frac{k}{d})\). This implies our low-rank assumption holds with \(\xi = 1-\gamma\).

8.6.0.2 Analysis on the error bound for GEP

To achieve a dimension-independent sample complexity bound in GEP [15], the gradient space must satisfy a low-rank assumption, which is even stronger than the rapid decay assumption in RLC coefficients (34 ). By following a similar argument as the analysis for the RLC assumption [21], we can demonstrate that our low-rank assumption is implied by the assumption in GEP.

9 Experimental details and additional experiments↩︎

9.1 Details and hyperparameter ranges for our method↩︎

Unless stated otherwise, we use the PRV accountant [44] in our experiments. Following [11], we use the validation data for cross-validation of the hyperparameters in all of our experiments and set the clipping constant to \(1\). We search the learning rate in \(\bc{0.01,0.1,1}\), use no weight decay nor momentum as we have seen it to have little or adverse impact. We search the number of steps in \(\bc{500, 1000,3000,5000, 6000}\) and our batch size in \(\bc{128,512,1024}\). We compute the variance of the noise as a function of the number of steps and the target \(\epsilon\) using opacus. We set \(\delta=1e-5\) in all our experiments. We use the open-source opacus [52] library to run DP-SGD with the PRV Accountant efficiently. We use sciki-learn to implement PCA. Checkpoints of ResNet-50 are taken or trained using the timm [53] and solo-learn [54] libraries. Standard ImageNet pre-processing of images is applied, without augmentations.

9.2 Discrepancy in pre-training resolution↩︎

Several works have used different resolutions of ImageNet to pre-train their models. In particular, [11] used ImageNet 32x32 to pre-train their model, which is a non-standard dimensionality of ImageNet, but it matches the dimensionality of their private dataset CIFAR-10. In contrast, we use the standard ImageNet (224x224) for pre-training in all our experiments with both CIFAR datasets as well as other datasets. In this section, we show that using the resolution of 32x32 for pre-training, we can indeed outperform [11] but also highlight why this may not be suitable for privacy applications.

9.2.0.1 Low-resolution (CIFAR specific) pre-training

Different private tasks/datasets may have images of differing resolutions. While all images in CIFAR [39] are 32x32 dimensional, in other datasets, images not only have higher resolution but their resolution varies widely. For example, GTSRB [46] has images of size 222x193 as well as 15x15 , PCAM [48] has 96x96 dimensional images, most images in Dermnet [49] have resolution larger than 720x400, and in Pneumonia [47] most x-rays have a dimension higher than 2000x2000. Therefore, it may not be possible to fine-tune the feature extractor at a single resolution for such datasets.

Identifying the optimal pre-training resolution for each private dataset is beyond the scope of our work and orthogonal to the contributions of our work (as we extensively show, our method PILLAR  operates well under several pre-training strategies in 9 and 11). Furthermore, assuming the pre-training and private dataset resolution to be perfectly aligned is a strong assumption.

9.2.0.2 Comparison with [11]

Nevertheless, we compare our approach with [11] pre-training a ResNet50 on a 32x32 rescaled ImageNet version, and obtain a non-private accuracy larger than \(94\%\) reported for \(\epsilon=8\) in Table 5 in [11] for Classifier training. Note that our approaches is computationally significantly cheaper than theirs as we do no use the tricks proposed in their work (including Augmult, EMA, and extremely large batch sizes (\(>\) 16K))

Using ImageNet32x32 for pre-training, we perform slightly better than them in private training. Our results are reported in 5. We expect that applying their techniques will result in even higher accuracies at the cost of computational efficiency. Interestingly, 5 shows that our model’s accuracy for \(\epsilon=0.7\) on CIFAR10, is as good as [11] for \(\epsilon=1.0\). This provides evidence that large batch sizes, which is one of the main hurdles in producing deployable private machine learning models, might not be required using our approach.

9.3 Experiments with large \(\epsilon~(\geq 1)\)↩︎

While in most of the paper, we focus on settings with small \(\epsilon\), in certain practical settings, the large epsilon regime may also be important. In 6, we repeat our experiments for CIFAR10 and CIFAR100 with \(\epsilon\in{1,2}\) and report the accuracy for the best projection dimension. Our results show that for \(\epsilon\in\bc{0.1,0.7,1,2}\) our method can provide significant gains on the challenging dataset of CIFAR-100; however for CIFAR-10 with \(\epsilon=1,2\) the improvements are more modest.

9.4 Comparison with PATE↩︎

We now discuss discuss the PATE family of approaches [17], [18], [55], [56]. These methods partition the training set into disjoint subsets, train an ensemble of teacher models on them, and use them to pseudo-label a public dataset using a privacy-preserving mechanism. For PATE to provide tight privacy guarantees, a large number (150-200 [18]) of subsets is needed, which reduces the test accuracy of each teacher. Large amounts of public data are also required. For CIFAR-10, [18], [55] use 29000 examples (58% of training set size), whereas we only use 5000 (10% of training set size) public unlabelled data points (and to retain its accuracy, in 5.2 we show 500 (1%) samples are sufficient). Of these 29000 examples, [55] reports only half of them is labelled due to the private labelling mechanism, further limiting the student’s performance in settings with low amounts of public training data. Despite our best attempts, we could not train PATE-based approaches in our challenging setting to satisfactory levels of accuracy on either CIFAR-10 or CIFAR-100.⁶

9.5 Experimental details for 4.2↩︎

In this section, we provide details of the other algorithms we compare our approach with in 4.2. To ensure a fair comparison for all the baseline methods, which independently implement most of the private training algorithms (including per-sample gradient computation, clipping, and noise addition), we limit our comparison to the setting where \(\epsilon=0.7\). We use the RDP accountant [43] for this specific comparison, while in the rest of the paper, we employ the more recent PRV accountant [58]. The reason behind this choice is that the code of the other methods is available with the RDP accountant, and the implementation of the RDP accountant is unstable for small \(\epsilon\) values \(\epsilon~(=0.1)\).

9.5.0.1 JL transformation [32]

 [32] uses JL transformation to reduce the dimensionality of the input. For our baseline, we simulate this method by using Random Matrix Projection using Gaussian Random Matrices (GRM) instead of PCA to reduce the dimensionality of the inputs. Our experimental results in 1 show that our method outperforms these approaches. Although this approach does not require the availability of public data, this comparison allows us to conclude that reducing the dimensionality of the input is not sufficient to achieve improved performance. Furthermore, even though the JL Lemma [59] guarantees distances between inputs are preserved up to a certain distortion in the lower-dimensionality space, the dataset size required to guarantee a small distortion is much larger than what is available in practice. We leverage scikit-learn to project the data to a target dimension identical to the ones we use for PCA. We similarly search the same hyperparameter space.

9.5.0.2 GEP [15]

We use the code-base⁷ released by the authors for implementation of GEP. We conduct hyper-parameter search for the learning rate in \(\{0.01,0.05,0.1,1\}\) and the number of steps in \(\{500,1000,2500,3000,5000,6000,20000\}\). As recommended by the authors, we set the highest clipping rate to \(\{1,0.1,0.01\}\) and the lowest clipping rate is obtained by multiplying the highest with \(0.20\). The anchor dimension ranges in \(\{40,120,200,280,512,1024,1580\}\). We try batch sizes in \(\{64,512,1024\}\). We tried using \(\{0.1\%,0.01\%\}\) of the data as public. Despite this extensive hyperparameter search, we could not manage to make GEP achieve better performance than the DP-SGD baseline (see 1).

9.5.0.3 AdaDPS [16]

We use the code-base⁸ released by the authors of AdaDPS. We estimate the noise variance as a function of the number of steps and the target \(\epsilon\) using the code of opacus under the RDP accountant (whose implementation is the same as the code released by the authors of AdaDPS). We search the learning rate in \(\{0.01,0.1,1\}\), the number of steps in \(\{500,1000,2500,3000,5000,6000, 7500,10000\}\), the batch size in \(\{32,64,128,512,1024\}\), and we tried using \(\{0.1\%,0.01\%\}\) of the data as public, and the \(\epsilon_c\) (the conditioner hyperparameter) in \(\{10,1,0.1,1e-3,1e-5,1e-7\}\). of the validation data for the public data conditioning. We applied micro-batching in \(\{2,4,32\}\). Despite this extensive hyperparameter search, we could not manage to make AdaDPS achieve better performance than the DP-SGD baseline.

9.6 Different pre-training algorithms↩︎

In [fig:neardist,fig:farshift] in the main text, we only reported accuracies for the best performing pre-training algorithm. In this, section we report the performance of our algorithm against five different pre-training algorithms that we consider in this paper. In particular, we consider two self-supervised pre-training algorithms: BYOL [22] and MoCov2+ [27] and two semi-supervised algorithms [28]. While one of them is a Semi-Supervised (SemiSL) algorithm, the other only uses weak supervision and we refer to it Semi-Weakly Supervised (SemiWeakSL) algorithm. In 9 we report the results on CIFAR-10 and CIFAR-100. In 11 we report the results for Flower-16 [45], GTSRB [46], PCAM [48], Pneumonia [47] and DermNet [49].

Similar to 6 in the main text, we show the accuracy reduction for Semi-Supervised pre-training vs BYOL (Self-Supervised) pre-trianing in 10. Our results shows similar results as [50] that labels are more useful for pre-training for tasks where there is a significant label overlap between the pre-training and the final task.

10 Computational Cost, Broader Impact and Limitations↩︎

10.0.0.1 Computational cost

Except for the supervised training on ImageNet32x32, we leverage pre-trained models. To optimize the training procedure, we checkpoint feature embeddings for each dataset and pre-trained model. Therefore, training requires loading the checkpoint and training a linear layer via SGD (or DP-SGD), accelerating the training procedure by avoiding the forward pass through the feature encoder. We use a single Tesla M40 (11GB) for each run. We perform approximately 405 runs for PILLAR. The same amount of runs is performed for the JL baseline. For GEP we perform 3528 runs. For AdaDPS we perform 4320 runs. We make the code needed to reproduce our main results available in the zip of the supplementary materials.

10.0.0.2 Broader impact and Limitations

In this work we show our method can be used in order to increase the utility of models under tight Differential Privacy constraints. Increasing the utility for low \(\epsilon\) is crucial to foster the adoption of DP methods that provide provable guarantees for the privacy of users. Further, unlike several recent works that have shown improvement in accuracy for deep neural networks, our algorithm can be run on commonly available computational resources like a Tesla M40 11GB GPU as it does not require large batch sizes. We hope this will make DP training of high-performing deep neural networks more accessible. Finally, we show our algorithm improves not only on commonly used benchmarks like CIFAR10 and CIFAR100 but also in privacy relevant tasks like medical datasets including Pneumonia, PCAM, and DermNet. We hope this will encourage future works to also consider benchmarking their algorithms on more privacy relevant tasks.

As discussed, the assumption that labelled public data is available may not hold true in several applications. Our algorithm does not require the public data to be labelled, however the distribution shift between the public unlabelled data and the private one should not be too large. We have shown that for relatively small distribution shift our method remains effective. Finally, recent works have suggested that differentially private learning may disparately impact certain subgroups more than others [60]–[62]. It remains to explore whether semi-private learning can help alleviate these disparity.

References↩︎