Mixed Differential Privacy in Computer Vision

We introduce AdaMix, an adaptive differentially private algorithm for training deep neural network classifiers using both private and public image data. While pre-training language models on large public datasets has enabled strong differential privacy (DP) guarantees with minor loss of accuracy, a similar practice yields punishing trade-offs in vision tasks. A few-shot or even zero-shot learning baseline that ignores private data can outperform fine-tuning on a large private dataset. AdaMix incorporates few-shot training, or cross-modal zero-shot learning, on public data prior to private fine-tuning, to improve the trade-off. AdaMix reduces the error increase from the non-private upper bound from the 167-311\% of the baseline, on average across 6 datasets, to 68-92\% depending on the desired privacy level selected by the user. AdaMix tackles the trade-off arising in visual classification, whereby the most privacy sensitive data, corresponding to isolated points in representation space, are also critical for high classification accuracy. In addition, AdaMix comes with strong theoretical privacy guarantees and convergence analysis.

Introduction
When training a deep neural network for visual classification, it is critical to protect privacy by limiting the amount of information that could be gleaned about any individual training sample. Differential Privacy (DP) [15] is a theoretical framework to provide strong guarantees on the maximum amount of information that any attacker can extract about an individual training sample. In particular, DP allows users to select the desired trade-off between privacy and accuracy, mediated by a privacy parameter , which typically depends on the application scenario.
Training large machine learning models while guaranteeing strong privacy for each sample is challenging. In * work done during an Amazon internship practice, however, one often has a pool of data available for which there are no privacy concerns. This could be a synthetic datasets or datasets designed to be available for public use. Such public data are distinct from the private ones, for which we seek strong privacy guarantees. 1 In particular, using large amounts of generic public data for pre-training has recently enabled the creation of language models that achieve DP on the target task while remaining close to state-of-the-art performance [34,57]. The same strategy in vision [49], however, still yields punishing error increases (Tab. 1) ranging from 311% to 167% on average across datasets, depending on the desired level of privacy.
Can we, then, make use of public data that is better suited for vision, so we can retain close-to-paragon performance while ensuring privacy?
One sure way of preserving privacy is not to use private data altogether, and recent literature has given us multiple ways to do so. For example, using zero-shot learning [19,29,30,33,46] one can leverage public data from a different modality (e.g., text) to train a visual model without ever seeing the private data. More generally, one can source or synthesize a few samples of labeled public data from the task distribution, and train using few-shot learning [54], still without using private data. Surprisingly, simple fewshot techniques outperform private training on much larger dataset (Fig. 2, left).
Of course, there may be subtle domain shifts between the public and private data, so ignoring the latter is not a desirable strategy to maintain privacy. The question, then, is how to use even small amounts of public data, in addition to the private data, to break the trade-off between privacy and accuracy. To do so, we change the setting from most work on DP to include labeled public data sourced with the same labels as the target task. We call this setting mixed differential privacy, or MixDP.
To address MixDP, we propose to use the public data not just for pre-training the backbone, but for few-shot or zero-shot learning of a classifier on the target tasks, prior to private fine-tuning (Sec. 3.2). In Tab. 1, we show that indeed in the MixDP setting it is possible to achieve significant gains compared to training with only the private or only the public data, even using a small amount of the latter. To do so, we have to modify existing DP training algorithms to the mixed setting, which leads us to the development of AdaMix, a method for MixDP that uses public data to tune and adapt all major steps of private training, in particular model initialization, clipping of the gradients, and projection onto a lower-dimensional sub space. Some of these ideas to use auxiliary public data were applied in different contexts in isolation, but have suboptimal privacy/performance tradeoffs for visual tasks.
In visual classification tasks, the long-tails of the data play an important role in achieving high classification performance [17,18]. However, DP is a worst-case framework which is highly-influenced by outliers or long-tails. MixDP eases the problem, since it allows to collect public data to ensure that each sub-population is sufficiently covered. This reduced the cost of privacy for the long tails, as we show using a per-instance DP (pDP) analysis of [55].
Unlike most related work, we use NoisyGD rather than DP-SGD as we find that it is faster and more private for our use case. We give a tight analysis of its ( , δ)-DP properties using the Analytical Gaussian mechanism [5,14] (Sec. 3.1). In addition, we present a convergence proof for our algorithm together with new stronger bound for the strongly convex case. This also allows us to describe the utility of the algorithm relative to its non-private counterpart.
To summarize, our contributions are: (1) we introduce AdaMix, a state-of-the-art adaptive method for mixed privacy learning; (2) we show significant improvement w.r.t. baselines on a novel benchmark for MixDP vision tasks; (3) we show that the zero-shot text information can improve the performance of private models (Sec. 4); (4) we analyze the goodness of our method both theoretically (new theorems) and empirically (pDP analysis).

Related Work
Most work on Differential Privacy [6,10,22,24,32,44,47,53,53,57] uses public data either for: generic pre-training unrelated to the task [49], or to tune parameters [25,58,60], or as additional unlabeled data [37,38]. Instead, we use a small amount of labeled public data related to the task to improve the accuracy of a private model under a given privacy parameter .
Unlabeled public data. PATE [37, 38, 50] trains teacher models on different partitions of the data to predict labels, and privately vote on how to label public (unlabelled) data. Then, a student model is trained in semi-supervised fashion on public data, now partially labelled using the private data. This strategy does not directly allow to train a model on a mix of labeled public and private data. [62] noted that the number of partitions required for meaningful privacy guarantees may be prohibitive for vision datasets. As an alternative, they suggest labeling with a differentially private KNN. In MixDP, where we assume that the public data is already labeled, these algorithms would perform at best similarly to our Only-Public baseline. Instead, what we are interested in effectively using labeled private data to improve performance relative to already labeled public data.
DP for Language models. [34,57] show that a large language model pre-trained on generic public data can be finetuned on task-specific private data with only modest loss in accuracy. In contrast, our focus is on using small amounts of public data for fine-tuning. We note that in language models strong transfer of information from the pre-training is facilitated by the fact that the output space (a sequence of tokens) is the same for all tasks. Conversely, vision models need to relearn different output spaces based on the task (i.e., the last layer is always trained from scratch) reducing the transfer of information. We show that we can partly recover this advantage by either using an initialization based on public data of the same task, or a multi-modal visionlanguage model. We use CLIP [41] for zero-shot learning.
Adaptive clipping. Similarly to us, [52] studies DP training with access to a small amount of public data, and use adaptive gradient clipping [3,4,51,59] based on the public gradients. Contrary to us, they first train a private model separately and then a mixed public-private model using the private one as a regularizer with compelling results on tabular data. We found this approach ineffective for computer vision, where usually models are pre-trained on public data. In Sec. 4 we show that AdaMix works better on vision tasks, and is further improved with multi-modal data.
Adaptive projection. [25,58,60] suggest improving DP-SGD by projecting the gradients into a lower-dimensional space estimated from public data. However, these methods do not leverage the performance improvements derived from training on public data, which are needed to make vision models viable. Using public data both to train and to estimate the subspace introduces more challenges, since the gradients of the public data and private data will then behave differently. Moreover, while they perform an SVD on the individual public sample gradients, we do the SVD of the total gradient matrix. Unlike the SVD of the matrix of individual sample gradients, this is cheaper to compute at each step.
Analysis. [2] studies the theoretical limits of mixed privacy learning, but does not provide practical algorithms. We provide both a method for MixDP and a proof of convergence. Our analysis leverages the results of [28] which shows that a particular non-uniform averaging scheme of SGD converges at an O(1/t) rate, rather than the classical O(log t/t) rate. In the context of differentially private learning, [6] showed that NoisySGD achieves the optimal rates for (convex) empirical risk minimization (ERM) [11]. [48] provided the first analysis of NoisyGD in the general convex case. To the best of our knowledge, we are the first to formally establish that the use of an arbitrarily small public data gives provably smaller sample complexity in learning compared to the standard private learning setting.

Method
Notation. Let z ∈ Z be a datum, with z = (x, y) being the feature/label pair; Z * = ∪ ∞ n=0 Z n is the universe of datasets with arbitrary size. For learning, we have access to a private dataset D pri := {z 1 , ..., z Npri } and a public one D pub := {z 1 , ...,z Npub }. The loss function : Z ×W → R takes data z ∈ Z and "weights" w ∈ W ⊂ R d to yield the total loss on the private and public dataset L pri (w) := Npri i=1 i (w) and L pub (w) := Npub j=1˜ j (w), with i and˜ j short-hands for (w, z i ) and (w,z j ) respectively. Notice that L pri and L pub are sums, not averages, of the loss functions. Their gradients are indicated by g pri In addition, we say N = N pri +N pub and L(w) = L pri (w)+ L pub (w).
The average empirical risk is written asR(w) := L(w)/N . When the data are drawn from some distribution D, the risk, i.e., generalization error, R(w) := E z∼D [ (z, w)]. Our goal is to design a differentially private algorithm that returnsŵ which minimizes L(ŵ). Its performance is measured by the excess empirical risk, i.e., R(ŵ) − min w∈WR (w); and by the excess risk R(ŵ) − min w∈W R(w). In the experiments, the latter is measured by the error on a test set.

Differential privacy
Two datasets D, D ∈ Z * are said to be neighboring, written as D D , if we can obtain D from D by adding or removing a single data point.
Definition 1 (Differential privacy [15,16]). For > 0 and δ ≥ 0, a randomized algorithm M is ( , δ)-differentially private if for any neighboring datasets D D and any measurable S ⊆ range(M), In our context, M is the randomized learning algorithm, and Y is the space of model weights. This condition bounds the maximum amount of information that an attacker, having access to the weights of the model, can extract about Algorithm 1: (Projected) Noisy Gradient Descent Data: Constraint set W, initialization w 1 , noise level σ, clipping threshold τ , number of iteration T , weight decay parameters λ and w ref , learning rates η t .
one of the training samples. The parameter is referred to as the privacy parameter: lower values of carry better privacy guarantees, but also make it harder to train an accurate model, as it reduces the amount of information about the training samples that can be represented via the parameters of the model. The goal of a good DP training algorithm A is to train an accurate model while satisfying the ( , δ)privacy constraint selected by the user where, ideally, ≈ 1 and δ = o(1/n).
NoisyGD. NoisyGD is defined in Algorithm 1. We now show that NoisyGD is differentially private and that, in the convex case, it converges to the optimal solution.
Mixed private learning. We define the problem of differentially private learning when we have access to an additional public dataset mixed private learning. We say the algorithm M (now taking two arguments D pri and D pub ) satisfies ( , δ)-DP if M(·, D pub ) satisfies ( , δ)-DP (Def. 1) for every fixed D pub . [2] shows that a small public dataset from the same distribution allows one to privately PAC-learn any classes with bounded VC-dimension, but with an inefficient algorithm. We focus on designing practical DP algorithm that can effectively use both public and private data under the setting of convex empirical risk minimization [11] and convex fine-tuning of deep models [1].

AdaMix
Model. Following [49], we use a linear logistic regression model trained on top of the last layer features of an Ima-geNet pre-trained network. This reduces the expressivity of the model compared to training a full network. However, the significant reduction in number of parameters makes it a better choice DP algorithms and recent deep networks allow for competitive performance on most tasks even when training only the last layer. We normalize the features before feeding them to the logistic model, which both improves the accuracy and bound the gradients at each step.
Initialization and regularization. The choice of initialization is normally of minor concern for logistic regression: since the problem is convex we will converge to a global optimum regardless of the initialization. L2 regularization (weight decay), when employed, is usually centering at 0 by default. However, centering the regularizer is critical in differential privacy, as we prove in the following result: Theorem 3 (Convergence of NoisyGD on strongly convex problems). Assume W is a convex set satisfying sup w∈W w ≤ B. Let w 1 , ..., w T +1 be the parameter vectors returned by running Algorithm 1 on the following regularized loss J(w) = L(w) Then, the ensemble solution: for any w * ∈ W, where ρ is the privacy parameter of the algorithm.
Note that as T → +∞ the first term vanishes and the second term matches the information-theoretic limit for privately solving general convex ERM problems when w ref = 0 [6]. However, this can improve if we choose w ref according to the public data such that w ref is closer to w * than 0. This motivated us to propose choosing w ref by training on the public data. Then, we proceed to fine-tune the model on the concatenation of private and public data, using Noisy-GD while preserving ( , δ)-DP.
Provable benefits of public data access. Next we provide a theoretical guarantee for the above approach under standard statistical learning assumptions.
Theorem 4 (Generalization with access to public data, informal). Assume that private and public data are drawn i.i.d. from the same distribution D and that R(w) = E (x,y)∼D [ (w, (x, y))] is c-strongly convex in W. Let w ref be obtained by training for one epoch on the public dataset and letw be as in Thm. 3, then at the limit when T is suffi-ciently large, the excess risk obeys where w * = argmin w∈W R(w) and Gen(w, N ) := is the expected generalization gap of (a potentially data-dependent) w.
To the best of our knowledge, Theorem 4 is the first demonstrated claim that access to even a very small public dataset can improve private learning in the convex ERM setting. We note that the generalization bound decomposes in a first term, which describes the generalization cost incurred by using DP, and a second part which is common to non-private learners. Interestingly, in the Appendix we show that in MixDP the cost of privacy asymptotically vanishes even if the percentage of public data becomes neglegible (i.e., when N pub → ∞, N pub /N → 0).
Besides providing a good initialization, access to a small public dataset also enables ways to further improve Noisy-GD in practice, as we will now see.

Adaptive threshold.
Since the norm of the gradients changes significantly during training, a fixed clipping threshold τ is suboptimal throughout training.
[52] suggests to tune this threshold adaptively using public data. However, the norm of the average gradient of the public sample, may not yield good clipping thresholds for the per-sample gradients. Instead, we find the following adaptive threshold to be more robust: that is, we take the 90-th quantile of the norm of the public gradients, where g pub i (w) = ∇ w˜ i (w) is the gradient of the i-th public sample. Then the clipped gradient we use is This quantile rule is also used by [3], but we differ in the use of public data to determine τ , rather than allocating part of the privacy-budget for releasing the quantile. It was established in [12] that gradient clipping has the effect of Huberization of the loss function in the GLM cases. The convergence to the optimal solution of a modified objective function is guaranteed if we fix the clipping parameter. Our approach on the adaptive clipping has the effect of selecting the hyperparameter adaptively in a homotopy style algorithm, which shows further empirical benefits.
Adaptive subspace projection. From Thm. 4, the utility of a DP algorithm decreases with the number of parameters d of the model. In view of this, we do not train the whole network but rather use it as a feature extractor and only train a linear model on top. However, for modern vision architectures, even the number of parameters of the final layer is in the order of tens of thousands. Therefore, we use an adaptive mechanism to project private gradients onto a lowdimensional subspace before adding noise. More precisely, be the total gradient of the public dataset D pub . Since we are using a linear logistic model, where D is the number of features and C is the number of classes. Consider the SVD decomposition: We now project each (clipped) private gradient matrixg pri i on the top P components, and obtain a matrixĝ pri i = U tg pri i of size P × C. Other methods projecting the gradient using public data [25,58,60] do not compute the SVD of the total gradient matrix, as noted in Sec. 2. Rather, use the vectorized per-sample gradients of the public examples to compute the principal components to project. Since, in vision, the size of matrix of all per-sample gradients has a much larger size N × F C (rather than our F × C), several approximations would be required to carry out this strategy.
Final algorithm. The final gradient update step at time t is: U Tg pri i + n t . and n t ∼ N (0, σ 2 τ 2 I C ). We then train for T steps. The pseudo-code of algorithm is given in Algorithm 2.
Note that the privacy guarantee is the same as long as the ratio σ/ √ T remains constant, which gives a degree of freedom in choosing σ (hence T ). Higher values of σ requires more training steps T , but, by Thm. 3, it also ensures better convergence (which we validate this empirically in Sec. 4). Hence, the user should generally pick the largest σ allowed by their computational budget.

Textual side information
CLIP [41] is an embedding trained so that the representation of an image is close to the representation of its textual description. This enables zero-shot learning, i.e., initializing an high-performance image classification model using Algorithm 2: AdaMix training algorithm.
Data: Public dataset D pub , private dataset D pri , privacy parameter ( , δ), noise variance σ, learning rate η, L 2 reg. coefficient λ ; // Adaptive projection U, S, V ← SVD(G public (w)); // Clip, project and add noise to private gradients only the name of the labels or a textual description of the classes, which is generally public. AdaMix can be easily adapted to work in this multi-modal MixDP setting, where the public data comes from a different modality. First, we initialize a linear logistic model using the names of the classes: Let c i be the text associated to the i-th class, the weight matrix is [41]: that is, each row is the normalized encoding of a label scaled by a parameter β (we use β = 100). Starting from this public initialization, we train with AdaMix on image data.

Results
Setting. Unless otherwise specified, we train a linear logistic model on top of the last layer features of a ResNet-50 [21] pre-trained on ImageNet [13]. For NoisyGD, we initalize the logistic weights to zero, fix σ = 20 and δ = 10 −5 . We train with λ = 1e − 2, weight decay centered at zero, learning rate η ∈ {0.0005, 0.001, 0.0025, 0.005}, and select the best learning rate for each value of . For AdaMix, we initialize the weights by training on the public data until convergence. We use the Gaussian mechanism implementation of autodp 2 to calibrate the parameters of the training algorithm, in particular T max , in order to achieve the desired ( , δ)-DP requirement.  Table 1. Mixed privacy, full privacy and AdaMix. We report the result (test errors) of different methods on a diverse set of vision tasks (see text for description). Surprisingly Only-Public, which throws away private data and only trains a model on the small amount of public data outperforms Fully-Private, which trains on all data as if it was private. AdaMix is instead able to effectively use both the private and public data at the same time, and achieves a significant improvement even at relatively small value of (e.g., 10% improvement on MIT-67 w.r.t. Only-Public). Instead, the closest method to us, PPGD does not significantly improve over the Only-Public baseline.
Datasets. We test our algorithm on the following vision classification datasets commonly used in transfer learning (see Tab. 1). We split each training dataset into a "public" dataset consisting of N -samples per class (see Tab. 1), and consider the remaining training data as private. In all cases, the public data is less than 10% of the private data.
Baselines considered. We compare AdaMix with the following baselines: (Fully-Private) Ignore the MixDP setting and simply train on all data as if it was private, starting form a zero initialization and using NoisyGD; (Only-Public) Train a standard non-private model using only the few public samples and discarding the private ones; (PPGD) A version of PPSGD [52], but trained with NoisyGD rather than DP-SGD for easier comparison. Unlike AdaMix, PPGD has several hyper-parameters: we manually searched for the best combination to ensure the best comparison; (NGD) An ablated version of AdaMix which uses fixed hyperparameters rather than the adaptive components.

Experiments
Mixed Privacy vs Full Privacy. In Table 1 we see that, perhaps surprisingly, Only-Public is always significantly better than Fully-Private even if it actually throws away most of the available data. This suggests that, in vision, collecting a small amount of public data may be preferred to collecting a much larger amount of private data (Fig. 2). However, we see that AdaMix is able to effectively use both the private and public data at the same time, and achieves a significant improvement even at relatively small value of (e.g., 10% improvement on MIT-67 w.r.t. Only-Public at = 3). Conversely, the method closest to us, PPGD, does not significantly improve over the Only-Public baseline even after our changes to adapt it better to vision tasks.
Ablation study and finer comparison. In Fig. 1 (left and center) we plot the average accuracy obtained by various methods and ablations of AdaMix for different privacy parameters . Both AdaMix and the ablated NGD are able to improve over the Only-Public baseline. Interestingly, this holds true even when considering relatively low privacy parameters ≈ 1 which is usually considered too restrictive to train in a fully private setting (as seen in Tab. 1). On the other hand, thanks to the MixDP training we can obtain high-accuracy models even at restrictive privacy settings. We note that AdaMix performs uniformly better than other methods at all privacy regimes. From the ablation of AdaMix, we see that initializing the model with the public data has the largest impact, followed by adaptive clipping and adaptive projection.
Membership attacks. Differential privacy is a very strong requirement, and is it often assumed that using higher value of may still provide valuable defense to attacks [7-9, 31, 35, 42, 43, 45, 61] even if the theoretical guarantees are weak. Conversely, [23] suggests using attacks to give a lower-bound on the privacy parameter of the algorithm. In Fig. 1 (right) we plot the Area Under Curve of a membership attack executed against models for different values of . We use a thresholding based membership attack as proposed in [43]. The loss for samples in the private training set are labelled as 0 and test samples are labelled as 1. Then we simply compute the AUC for this. We find that the sorting of the algorithms does not change: algorithms with better theoretical bounds are also more robust to attacks.
Performance Boost and size of public data. We hypothesize that, when enough public data is present, the contribution of using private data may be less noticeable. To test this, we define the Performance Boost of a Mixed Privacy method as PB = (err public − err paragon )/(err DP − err paragon ), where err paragon is the error obtained by training on nonprivate model on both public and private data, err public is the error obtained by training only on the public data, and err DP is the error obtained by using training a mixed privacy model. This measures how well we can learn from the private data in the MixDP setting compared to the non-private upper-bound. In Fig. 2 we plot the performance boost for different sizes of the public set. We observe that the performance boost derived of using mixed privacy is very high . The bottom green line shows the non-private paragon (training on all data as if they where public). By changing the privacy parameter , we can interpolate between the two extrema. We see that AdaMix performs uniformly better than other methods, and can use private and public data together to obtain significant boost at all . (Center) Same as the before, but we zoom in to show the behavior of the different solutions in the low-regime. (Right) For the same algorithms, we plot the robustness to adversarial attacks (measured by AUC) vs test error obtained using different values of (annotated near each point). AdaMix obtains the best trade-off between accuracy and robustness.
when the public data is scarce, disappears when the amount of public data is comparable or larger than the private data.
Multi-modal initialization. In Fig. 4 we compare CLIP models initialized with (1) a random initialization, (2) a zero-shot initialization based on the public label names (Sec. 3.3), and (3) using few public image samples. While the latter performs the best at a given privacy level , the zero-shot initialization still improves significantly over the random initialization, thus showing that even just small amount of textual information (which is often available) can be used to significantly boost accuracy. Multi-modal models may also learn a better lower-dimensional representation of the data that is more amenable to DP. In Fig. 4 we compare AdaMix using an ImageNet pretrained ResNet-50 and using CLIP. This is not a direct comparison, but we see a significant performance boost by using CLIP at a given privacy level , suggesting that the move to multi-modal model may be a logical next step for DP.
Effect of differential privacy on individual samples. DP is a worst-case guarantee which may penalize the accuracy of a model on unusual data, or data on the long-tails of the distribution, which however may play an important role for generalization in vision [17,18]. MixDP may ease the problem, since it allows to collect public data to ensure that each sub-population is sufficiently covered, lessening the accuracy cost of making that data private. We show this effect using the per-instance DP (pDP) analysis of [55], which measures the privacy loss incurred by each individual z during the private training. This allows us to provide a finer analysis of different methods by comparing the histogram of pDP loss for each individual in the dataset D on top of the worst case DP bounds, which we do in Fig. 3 (see Appendix for details and theoretical analysis). We observe that, when using AdaMix, the pDP losses of most samples are the same, and is close to the maximum privacy budget = 3, indicating that we are using the prescribed privacy budget more effectively and more uniformly across samples, thereby improving utility.
Domain shift. Often, the private and public data may come from slightly different domains. To test the robustness of AdaMix to domain shifts, we use the DomainNet dataset, which aims to classify objects in different domains. In particular, we train a model to classify objects in painting, us-   We see that AdaMix use the private data from the target domain (real images) to adapt the solution to the target task. This significantly improves over using only the public data from the wrong domain (red line) and for large approaches the non-private limit (green line).
ing however public data coming from real pictures (while the private data is in the painting domain). In Fig. 3 (right), we show that, even if the public comes from a different domain, AdaMix is still able to use the public data to significantly improve performance of private training.
Effect of σ. Outside of the learning rate η, the main other sensitive hyper-parameter of AdaMix is the noise variance σ. From Prop. 3 we expect that the best accuracy will be obtained using a large σ and training for a respectively larger amount of epochs T . In the Appendix, we plot the test error as a function of σ and we see that indeed, a larger σ give better results at the expense of longer training time.

Discussion
We study Mixed Differential Privacy learning in computer vision, and show that in this setting differential privacy can be used to provide high accuracy models while respecting a given privacy parameter. To do this, we introduce AdaMix, an adaptive differential privacy mechanism that uses the public data to initialize and compute, at each step, an optimal subspace and clipping threshold. We also show that multi-modal vision and text can significantly improve accuracy under a privacy constrain.
Limitations. In our analysis we train a linear model on pre-trained features, rather than fine-tuning the whole network. This is common in DP, since fine-tuning multiple layers may not significantly improve the accuracy while the additional parameters negatively affects the privacy bounds. This limitation is partially offset by new models that are trained to have generic and transferable last-layer features without the need of additional fine-tuning. We discuss several theoretical bounds that guide us in understanding the behavior of the algorithm. However, these bounds refer to a slighlty simplified version of AdaMix (see Appendix for details) and use hyper-parameters that are asymptotically op-timal, but may not be practical.
Conclusions. Differentially Private models in computer vision often cannot reach the same level of performance as non-private model for realistic privacy parameters. Using AdaMix in the MixDP learning setting, we have shown that, assuming the presence of a small amount of public data, accurate networks can be produced that reach better accuracies than fully private training without compromising the privacy of the data. We hope that further research in this field may help the adoption of private models in more areas of computer vision.  We observe that initializing the logistic weights to zero leads to the worst results under a given privacy parameter. Using the public label names to initialize the weights (language initialization) performs significantly better. However, using the few available public images to initialize the weights still outperforms the other choices.
(Right) Multi-modal models. We compare the performance of ResNet-50 model, and a CLIP model. We see that CLIP performs significantly better under a given privacy parameter. While the ResNet-50 model and the CLIP model are not directly comparable due to different pre-training, this further reinforces that stronger pre-training can indeed benefit the privacy setting and that the feature space learned by multi-modal models may be better suited for privacy than standard vision networks.

A. Supplementary Material
In the supplementary material we perform, (1) Ablation studies analyzing different components of our algorithm (Appendix A.1), (2) tuning the adaptive clipping threshold can further improve AdaMix (A.2), (3) show that using a larger σ (training for longer) is better (A.3), (4) provide additional experimental results (A.4), (5) provide details experimental details (A.5, A.6), and (6) proofs for all the theoretical results presented in the paper (Appendix B, C, D).

A.1. Ablation Studies
In Fig. 5, we ablate the two components of our algorithm, namely, Subspace Projection and Adaptive Clipping. We consider the Noisy-GD (NGD) as the baseline and analyze the improvement provided by the two components separately and finally in combination (AdaMix). We observe that adaptive clipping is the key component of the AdaMix algorithm. We show that using the two components together performs the best across multiple datasets. In the next section we show that further tuning the adaptive clipping threshold can improve the performance even more on some datasets. In Fig. 6, we plot the relative reconstruction error for the private gradients on the public gradient subspace and a random subspace. We observe that the reconstruction error on the public gradient subspace is at least half the random subspace throughout training, which suggests the importance of the public gradients for AdaMix. Ablation Studies Figure 5. Ablation Studies Box plot showing the relative decrease in the test error across multiple datasets when we add Subspace Projection, Adaptive Clipping and Subspace Projection + Adaptive Clipping (AdaMix) to NGD. We observe that adaptive clipping provides more improvement compared to subspace projection, and the combination of the two works the best across 6 datasets.

A.2. Effect of AdaMix clip threshold
We plot the effect of adaptive clipping threshold (percentile) on the test error for AdaMix (we use 90 percentile  Figure 6. Random Subspace Projection We plot the relative reconstruction error of the private gradients when projecting on the subspace spanned by the public gradients or on a random subspace during training (using AdaMix and = 3). The reconstruction error when projecting on the random subspace is generally more than twice the error obtained projecting on the subspace of public gradients, highlighting the importance of using the latter.
in all of our experiments) in Fig. 7. However for CUB-200 and Caltech-256 tuning it to 75 percentile works better indicating that AdaMix has more scope for improvement. Note, however that using 90 percentile for CUB-200 and Caltech-256 still outperforms all the baselines.

A.3. Longer training with more noise
Higher values of σ requires more training steps, however, Theorem 3 shows that it leads to better convergence, which leads to better generalization. In Fig. 8 we see that indeed, at the same level of privacy, using a large of σ significantly reduces the test error compared to using a smaller σ.

A.4. Additional Experiments
In the main paper we presented detailed experimental results on MIT-67, here we present detailed results on all the remaining datasets.  Figure 8. Larger values of σ performs better. We plot the test accuracy of NGD and AdaMix using different values of σ for = 3. A larger σ performs better but needs more training steps thus verifying the claim empirically across multiple datasets.

A.4.1 Test Error vs Privacy
We show the test error obtained by different methods for different levels of privacy and the robustness to membership attack, similar to   3 To create the public and private datasets, we take 2 samples (for Oxford-Flowers and CUB-200) and 5 samples (for MIT-67, Stanford Dogs, Oxford Pets, Caltech-256) from each class as the public dataset and the remaining samples as the private dataset. In this way, the public set is less than 10% of the private set. We repeat all the experiments with 3 random seeds and report its mean and std.
For all the experiments we try multiple values for the learning rate: {1e − 3, 2.5e − 3, 5e − 3} for ResNet-50 experiments and {1e − 6, 5e − 7, 1e − 7} for CLIP experiments, and report the best values across 3 random seeds. We use 1e − 2 as the L 2 regularization coefficient across all the experiments. For subspace projection we project the gradients on a 2000-dimensional subspace for experiments with ResNet-50 features and 500-dimensional subspace for experiments with CLIP features. For the clipping threshold percentile we use a constant value of 90 percentile across all the experiments in the paper. In Fig. 7, we show that further tuning the clipping threshold percentile can improve performance on certain datasets, however, even with a predecided value of 90 percentile it still out-performs all the other methods.
We train the logistic model on the public data (few shot data) for 200 epochs (sames as iterations since we use gradient descent) for multiple values of learning rate: {1e − 1, 5e − 2, 1e − 2} for ResNet-50 features and {1e − 4, 5e − 5, 1e − 5} for CLIP features and choose the best performing model. For the private training, we use σ = 20 for all the experiments and calculate the number of iterations required for private training using methods provided in Auto-DP. In the experiments we observe that choosing a higher value of σ (thus training for more iterations) generally results in better performance.

B. Differential privacy basics
In this section, we describes tools we need from differential privacy and use them to prove that Algorithm 2 and Algorithm 3 satisfies a family of differential privacy parameters.
Lemma 6 (Analytical Gaussian mechanism [5]). For a numeric query f : X * → R d over a dataset D, the randomized algorithm that outputs f (D) + Z where Z ∼ N (0, σ 2 I d ) satisfies ( , δ( ))-DP for all ≥ 0 and δ( 2 is the global L2 sensitivity of f and Φ is the CDF function of N (0, 1).
The above lemma tightly characterizes the ( , δ)-DP guarantee of a single invocation of the Gaussian mechanism, and the following lemma shows that we can use the same result for an adaptive composition of a sequence of Gaussian mechanisms.
Specifically, the noisy gradient descent (NoisyGD) algorithm (Algorithm 1) we use is a composition of T Gaussian mechanisms for releasing the gradients and its privacy guarantee is equivalent to that of a single Gaussian mechanism.
Proposition 9. Let ∇f (w) be a function of the private dataset with global L2 sensitivity smaller than L for any w ∈ W, then Algorithm 1 with parameter T, σ 2 such that ρ := T 2 L 2 2σ 2 satisfies √ 2ρ-Gaussian differential privacy.
Proof. The proof follows from Lemma 8 as Algorithm 1 is an adaptive composition of T Gaussian mechanisms with global sensitivity L.

C. Per-instance differential privacy
In this section, we provide details on the per-instance differential privacy [55] that we used to generate Figure 3. To cleanly define per-instance differential privacy, we first define indistinguishability. pDP loss is a function of one particular pair of neighboring datasets. It describes the formal privacy loss incurred to the particular individual z that is added (if z is not part of the input dataset) or removed (if z is part of the input dataset). pDP is a strict generalization of DP, as we can recover DP from pDP by maximizing (·) over D, z.
We emphasize that the pDP loss (·) itself is data-independent, but specific evaluations of the pDP losses (e.g., (D −z , z) or (D, z)) depends on the private dataset D, thus should not be revealed unless additional care is taken to privately release these numbers.
For our purpose, we are interested in the distribution of pDP losses of individuals in the dataset induced by different DP algorithms. This is used to provide a theoretically-sound alternative to the prevalent practices of using specific attacks (such as membership inference attacks) for evaluating the data-dependent privacy losses. Before we state the pDP bounds of our algorithms, we extend the standard ( (·), δ)-pDP definition to a per-instance version of the Gaussian DP.
Data: Public dataset D pub , private dataset D pri , privacy parameter ( , δ), noise variance σ, Lipschitz constant L 4 , population-level strong convex parameter c, regularization parameter λ and a constraint set W. Result:w // Public Pretraining Phase (OnePassSGD on D pub ): w 1 = 0. for t = 1, . . . , N pub do // In a shuffled order This allows us to obtain precise pDP bounds under composition.
Proposition 14 (pDP analysis of AdaMix). Let z 1 , ..., z n be the data points of the private dataset. Algorithm 3 satisfies µ(·)-pGDP with Similarly, Algorithm 2 satisfies µ(·)-pGDP with Proof. Both algorithms are the composition of T -Gaussian mechanisms. Thus the results follow by the composition of pGDP. The composition of pGDP is implied by the composition theorem of GDP (Lemma 8) by choosing the space of datasets to be just {D, D ∪ {z}}.

D. Proofs of the technical results
We will be using the following O(1/t) convergence bound due to Lacoste-Julien, Schmidt and Bach [28], which uses a decaying learning rate and a non-uniform averaging scheme.
Theorem 15 (Convergence of SGD for Strongly Convex Objectives [28]). Let f be a m-strongly convex and defined on a convex set W. Assume stochastic gradient oracle g t satisfies that E[g t |w t ] ∈ ∂f (w t ) and E[ g t 2 ] ≤ G 2 for all t = 1, ..., T . Then the (projected) stochastic gradient descent with learning rate η t = 2 m(t+1) satisfies and E[ w T +1 − w * 2 ] ≤ 4G 2 m 2 (T + 1) .
Proof. First check that N L + λB upper bounds the Lipschitz constant of J on because the Lipschitz constant of λ 2 w 2 is smaller than λB due to the bounded domain. Second, check that the noisy gradient oracle satisfies that it is unbiased, and the added noise has a variance of σ 2 per coordinate for all d coordinates. Thus Thus by taking expectation on both sides we verify that we can take G 2 = (N L + λB) 2 + dσ 2 .
It remains to substitute these quantities and apply the first statement of Theorem 15.
Corollary 17 (One-Pass SGD on public data). Assume the public data with N samples are drawn from the same distribution of the private data. Assume that the (population risk) R(θ) = E (x,y)∼D [ (θ * , (x, y))] is c-strongly convex at θ * for some constant c. Then the one-pass SGD algorithm below for t = 1, ..., N pub obeys that where w * = argmin w∈W R(w).
Proof. First note that since the data is drawn iid, running one-pass SGD by going through the data points in a random order uses a fresh sample to update the parameters. This is is equivalent to optimizing the population risk directly. Check that for any fixed w and all t = 1, ..., N pub E (xt,yt)∼D [∇ w (w, (x t , y t ))] = ∇R(w). Moreover, we need this stochastic gradient oracle to satisfy E (x,y)∼D [ ∇ (θ, (x, y)) 2 ] ≤ G 2 . Notice that by our assumption ∇ (θ, (x, y)) 2 ≤ L 2 , thus we can take G = L. By invoking the second statement of Theorem 15 the result follows.
With these two corollaries stated, we are now ready to prove Theorem 3 and Theorem 18.
Proof of Theorem 3. The proof relies on Corollary 16, and the following argument. When additional regularization with parameter λ, the utility we consider should still be considered in terms of L(ŵ) − L(w * ). Let w * be any comparator satisfying B > w * L(w) − L(w * ) = J(w) − J λ (w * λ ) Take expectation on both sides and apply Corollary 16 Finally, choosing λ = ρ 2 w * −wref dL 2 yields as claimed (dividing N on both sides to getR).
Theorem 18. Assume the private data and public data are drawn i.i.d. from the same distribution D and that R(w) = E (x,y)∼D [ (w, (x, y))] is c-strongly convex in W. Let w ref = w N pub +1 -the last iterate of a single pass stochastic gradient descent onR pub (w) (initializing from w 0 = 0) that goes over the public dataset exactly once one data-point at a time with learning rate η t = 2 c(t+1) . Let w ref be passed into Theorem 3's instantiation of NoisyGD, which returnsw (The pseudo-code of this algorithm is summarized in Algorithm 3 in the appendix), then at the limit when T is sufficiently large, the excess risk obeys that where w * = argmin w∈W R(w) and Gen(w, N ) := E[R(w) −R(w)] is the expected generalization gap of (a potentially data-dependent) w.
Proof of Theorem 18. Let w * = arg min w∈W R(w c 2 Npub . Now by plugging in the w * in theorem, take expectation over the public dataset, and substitute the above bound, we get Take T to be sufficiently large so that the second term dominates, we obtain the stated bound. Finally, to convert the above bound into that of the excess risk: We make two additional remarks. First, we do not require the empirical objective L pub to be strongly convex. In practice, we do not have strong convexity when N pub < d. The assumption of c-strong convexity is on the population-level risk function R. Second, our bound decomposes the excess (population) risk of the private learner into a (local) uniform-convergence bound (which is required by a non-private learner too) and an additional cost due to privacy. Note that Gen(N ) is usually O(1/ √ N ) but could be O(1/N ) when certain data-dependent "fast rate" conditions are met, e.g., realizability, low-noise, or curvature (see, e.g., [27]). Our results suggest that the cost of privacy asymptotically vanishes (fix ρ, N pub → ∞, and N pub /N → 0) even under these fast rate conditions relative to the non-private rate.


On the Role of Discount Factor in Offline Reinforcement Learning

Offline reinforcement learning (RL) enables effective learning from previously collected data without exploration, which shows great promise in real-world applications when exploration is expensive or even infeasible. The discount factor, $\gamma$, plays a vital role in improving online RL sample efficiency and estimation accuracy, but the role of the discount factor in offline RL is not well explored. This paper examines two distinct effects of $\gamma$ in offline RL with theoretical analysis, namely the regularization effect and the pessimism effect. On the one hand, $\gamma$ is a regulator to trade-off optimality with sample efficiency upon existing offline techniques. On the other hand, lower guidance $\gamma$ can also be seen as a way of pessimism where we optimize the policy's performance in the worst possible models. We empirically verify the above theoretical observation with tabular MDPs and standard D4RL tasks. The results show that the discount factor plays an essential role in the performance of offline RL algorithms, both under small data regimes upon existing offline methods and in large data regimes without other conservative methods.

Introduction
Online reinforcement learning has achieved great success in various domains, including video games (Mnih et al., 2015), class games (Silver et al., 2016) and continuous control (Lillicrap et al., 2015). However, it requires extensive interaction with the environment to learn through trial-and-error. In many real-world problems, like personalized recommendation systems (Swaminathan & Joachims, 2015) and autonomous driving (Shalev-Shwartz et al., 2016;*  Singh et al., 2020), exploration can be expensive and unsafe, which requires conducting RL in a supervised manner. In contrast, offline RL (Levine et al., 2020;Fujimoto et al., 2019) enables learning from previously collected datasets, which shows great potential for real-world applications.
One of the major challenges of offline RL comes from the distributional shift between the data collection policy and the learned policy (Levine et al., 2020), and the direct application of online RL algorithms is known to lead to poor performance (Fujimoto et al., 2019). One paradigm for algorithm design in offline RL incorporates proper conservatism to the learning algorithm. There are several conservative methods in existing empirical literature, including policy regularization (Fujimoto et al., 2019;Peng et al., 2019;Kumar et al., 2020), ensemble-based uncertainty (Wu et al., 2021;An et al., 2021) and model-based penalty (Yu et al., 2021;2020;Kidambi et al., 2020).
However, as an essential number in RL, the discount factor already provides a natural way of conservatism. The effect of γ is extensively discussed in online RL and specifically TD-learning. For instance, Jiang et al. (2015) shows that the discount factor can be regarded as a complexity control parameter for the class of policies. Amit et al. (2020) shows that it is equivalent to L2-regularization of Q-values in TDlearning to improve generalization. However, the analysis of the role of γ in the context of offline RL is missing, which naturally leads to the following question: What are the roles of the discount factor in the context of offline RL, and how does it contribute to proper conservative offline RL methods?
In this paper, we examine the two roles of the discount factor in offline RL that affect the performance in two distinct ways. First, we show that γ plays as a regulator upon exist-ing conservative methods and achieves a trade-off between optimality and sample efficiency. Second, we show that a lower discount factor resembles model-based pessimism. A lower discount factor is equivalent to maximizing the value function in the worst possible models among a confidence set. We summarize the applicability of the two effects in Table 1. To give a rigid characterization, we analyze the two effects above under the context of linear MDPs and derive two different performance bounds. These quantitive results also characterize how the impact of a lower guidance discount factor relies on other factors like the size of the dataset and the coverage coefficient in terms of optimal policies. We empirically verify the two effects on both tabular MDPs and the standard D4RL benchmark (Fu et al., 2020). Results indicate that the discount factor can significantly affect the performance of offline RL algorithms, both under small data regimes upon existing pessimism and in large data regimes without other pessimisms. We believe that our findings highlight the importance of setting a proper lower discount factor in offline RL practices.

Related Works
Role of Discount Factor. The discount factor is extensively analyzed in online RL. Petrik & Scherrer (2008) first shows that the approximation error bounds may be tightened with a lower discount factor in online RL. Jiang et al. (2015) gives a more rigorous analysis by analyzing the size of potentially optimal policy class; Amit et al. (2020) points out the equivalence between the L2 regularization and a smaller discount factor in TD-learning. Zhang et al. (2020) analyzes the discount factor in actor-critic algorithms from a bias-variance-representation trade-off perspective. In the practical aspect, Chen et al. (2018) observes a similar regularization effect in partial observable settings; Fedus et al.
(2019) uses a geometry discount factor to learn multiple values in an ensemble way. Some works (Xu et al., 2018;Sherstan et al., 2020;Romoff et al., 2019) suggest learning a sequence of value functions with lower discount factors for online RL.
Convervatism in Offline RL. There are extensive works on the conservative offline RL, which can be roughly divided into policy constraint-based and uncertainty estimationbased. Policy constraint methods attempt to enforce the trained policy to be close to the behavior policy via introducing a generative model (Fujimoto et al., 2019;Fujimoto & Gu, 2021), KL-divergence (Peng et al., 2019;Nair et al., 2020;Siegel et al., 2020;Wu et al., 2019) or value function regularization (Kumar et al., 2020;Agarwal et al., 2020;Kostrikov et al., 2021). Some more recent policy constraint methods (Yang et al., 2021;Ma et al., 2021;Ghasemipour et al., 2021;Kostrikov et al., 2021;Brandfonbrener et al., 2021) also suggested that only trusting the state-action pairs given in the dataset can solve complex tasks well. As for the uncertainty estimation of model-free methods, researchers attempt to take into account the confidence of the Q-value prediction using dropout or ensemble techniques (Wu et al., 2021;An et al., 2021). Differently, model-based offline methods incorporate the uncertainty in the model space (Yu et al., 2020;2021;Kidambi et al., 2020).
In addition, there are also some theoretical results for pessimism in offline RL. Jin et al. (2021) proves that using a negative bonus from the online exploration is sufficient for offline RL. Rashidinejad et al. (2021) proves that a UCBlike penalty is provably sufficient in tabular settings. Uehara & Sun (2021) studies the properties of model-based pessimisms under partial coverage.

Preliminaries
We consider infinite-horizon discounted Markov Decision Processes (MDPs), defined by the tuple (S, A, P, r, γ), where S is a state space, A is a action space, γ ∈ [0, 1) is the discount factor and P : S × A → ∆(S), r : S × A → [0, r max ] are the transition function and reward function, respectively. We also assume a fixed distribution µ 0 ∈ ∆(S) as the initial state distribution.
To make our analysis more general, we consider the linear MDP (Yang & Wang, 2019;Jin et al., 2020) as follows, where the transition kernel and expected reward function are linear with respect to a feature map. Note that tabular MDPs are linear MDPs with the canonical one-hot representation.
Definition 2.1 (Linear MDP). We say an infinite-horizon discounted MDP (S, A, P, r, γ) is a linear MDP with known feature map φ : S × A → R d , ψ : S → R l if there exist an unknown matrix parameter M ∈ R d×l and an unknown vector parameter θ ∈ R d such that for all (s, a, s ) ∈ S×A×S. And we assume φ(s, a) ∞ ≤ 1, ψ(s ) ∞ ≤ 1 for all (s, a, s ) ∈ S × A × S and max{ M 2 , θ 2 } ≤ √ d.
A policy π : S → ∆(A) specifies a decision-making strategy in which the agent chooses its actions based on the current state, i.e., a t ∼ π(· | s t ). The value function V π γ,M : S → R is defined as the γ-discounted sum of future rewards starting at state s for policy π in model M , i.e.
where the expectation is with respect to the trajectory τ induced by policy π. The action-value function Q π : S × A → R is similarly defined as (3) We overload the notation and define V γ,M (π) as the expected γ-discounted value of policy π under the initial dis- When it does not lead to confusion, we omit the index for γ and M for simplicity.
We define the Bellman operator as for any f : S → R and γ ∈ [0, 1). The optimal Qfunction Q * , and the optimal value function V * are related by the Bellman optimality equation while the optimal policy is defined as We define the suboptimality as the performance difference of the optimal policy π * γ and the policy π given the initial distribution µ 0 evaluated with discount factor γ. That is We also define the suboptimality for each state, that is

Pessimistic Offline Algorithms
In this section, we sketch two offline algorithms to characterize the effect of a lower guidance discount factor. The first one is pessimistic value iteration (PEVI; Jin et al., 2021), as shown in Algorithm 1, which uses uncertainty as a negative bonus for value learning. The second one is model-based pessimistic policy optimization (MBPPO; Uehara & Sun, 2021), as shown in Algorithm 2, which optimizes the worst possible performance of a policy over a set of models.
PEVI uses negative bonus Γ(·, ·) over standard Q-value estimation Q(·, ·) = ( B γ V )(·) to reduce potential bias due to finite data, where B γ is the empirical estimation of B γ from dataset D. We use the notion of ξ-uncertainty quantifier as follows to formalize the idea of pessimism.
Definition 2.2 (ξ-Uncertainty Quantifier). We say Γ : S × A → R is a ξ-uncertainty quantifier for B γ and V if with probability 1 − ξ, for all (s, a) ∈ S × A.

7:
Set V (·) ← E π Q(·, ·) . 8: end while 9: Return π Algorithm 2 Model-Based Pessimistic Policy Optimization 1: Require: Dataset D, discount factor γ, policy class Π, Model set M 2: Optimize policy with respect to the worst possible model: 3: Return π Intuitively, Γ(s, a) represents the uncertainty when estimating the value function. The negative bonus ensures that we do not overestimate the value function due to finite samples with high probability, which allows us to give a performance lower bound with respect to the number of samples in the dataset.
MBPPO, on the contrary, considers the uncertainty in the model space to reduce potential sampling bias. By optimizing the performance in the worst possible model, as shown in Algorithm 2, we obtain a model-based offline algorithm, which gives better suboptimality bounds compared to the model-free counterpart when we use a proper set of models.
Both Algorithm 1 and Algorithm 2 are meta descriptions rather than detailed implementations. We provide more details of the algorithms in Appendix A.

Theoretical Analysis
This section characterizes the effects of a lower guidance discount factor in offline RL. We first show that a similar regularization effect exists in offline algorithms as in online algorithms. We quantify this effect by providing a performance bound to analyze how other factors like the data size and the coverage coefficient affect this regularization effect. We then show an equivalence between a lower discount factor and the model-based pessimism. This equivalence leads to a performance guarantee with a lower guidance discount factor without other conservative regularizations. These two effects indicate that the discount factor plays a vital role in offline reinforcement learning.

Regularization Effect
As Jiang et al. (2015) suggests, the discount factor acts as a regularization coefficient to bound the complexity of the potential optimal policy class. However, it is unclear what affects the effectiveness of γ regularization in the offline setting, especially when the data coverage is poor and the algorithms have additional pessimism. Empirically, we found that the quality and size of the dataset are the main factors that affect the regularization from γ. To shed light on this observation, we first derive a performance bound in the linear MDP setting for model-free pessimistic algorithms like Algorithm 1. The analysis is analogous to (Jin et al., 2021), but we focus on the discount setting.
for all s ∈ S with probability 1 − ξ/2, where In Algorithm 1, we follow Equation (17) and (18), and set where c > 0 is an absolute constant and ξ ∈ (0, 1) is the confidence parameter. Then with probability 1 − ξ, the policy π generated by Algorithm 1 satisfies Proof. See Appendix B.1 for a detailed proof.
Equation (9) defines a finite coverage coefficient, namely c † , which represents the maximum ratio between the density of empirical state-action distribution and the density induced from the optimal policy. Intuitively, it represents the quality of the dataset. For example, the expert dataset has a low coverage ratio while the random dataset may have a high ratio. The probability 1−ξ/2 for a finite coverage coefficient is measured concerning the data collection process. That is, we are only making assumptions about the data collection process rather than the specific dataset. The dependence on γ in Lemma 3.1 suggests that the performance bound SubOpt π, s; γ decreases as the discount factor gets lower. However, a lower discount factor also biases the optimal policy, as characterized by the following lemma.
The bound above is tight in a trivial case, while it is usually very loose in practice. Together, we have the following bound with a guidance discount factor γ different from the true evaluation discount factor γ e . Theorem 3.3. Based on the same assumption and definition as in Lemma 3.1, we set ζ = log (4dN/(1 − γ)ξ), β = c · dr max √ ζ/(1 − γ) and λ = 1. Then with probability 1 − ξ, the suboptimality bound of the policy π generated by Algorithm 1 satisfies Proof. The result follows immediately from Lemma 3.1 and Lemma 3.2.
Theorem 3.3 gives an upper bound for pessimistic offline algorithms with two terms. Both terms monotonically depend on the guidance discount factor γ but in an opposite way, which suggests there exists an optimal trade-off γ * ∈ [0, γ e ].
It also suggests that this optimal trade-off γ * is dependent on other factors like the coverage ratio of the dataset and the size of the dataset. A small or poorly covered dataset (i.e., a large coverage coefficient) makes the first term's coefficient larger, requiring a lower discount factor to achieve optimal performance. We empirically observe this effect on both toy examples as well as large D4RL tasks, as shown in Section 4.

Pessimistic Effect
This section analyses the pessimism effect of a lower discount factor. We show that, perhaps surprisingly, learning with a lower discount factor is equivalent to one type of the model-based pessimism mechanism, as depicted in Algorithm 2. This is characterized by the following lemma.
Lemma 3.4. The optimal value function with a lower discount factor is equivalent to the pessimistic value function over a set of models. Formally, let where M ε = {M |P M (·|s, a) = (1 − ε)P M0 (·|s, a) + εP(·)} , and P(·) is an arbitrary distribution over S, then we have where ∆ is an absolute constant.
Proof. See Appendix B.2 for a detailed proof.
The equality in Lemma 3.4 shows that learning with a lower discount factor itself acts as a kind of model-based pessimism, which allows us to derive a bound without any other additional regularizations. We consider the modelbased pessimism, where the model parameters are learned through maximum likelihood estimation (MLE). With the techniques in (Geer et al., 2000) that allow us to estimate the concentration rate of the MLE estimator, we have the following theorem. The proof of the following theorem is analogous to the analysis in (Uehara & Sun, 2021).
Then, with probability 1 − ξ, Learning with a guidance discount factor γ yields a policy π such that where c 1 , c 2 , c 3 are constants.
Proof. See Appendix B.3 for a detailed description and proof.
Similar to c † in Equation (9), c ‡ can be interpreted as another coverage coefficient, and the difference between c † and c ‡ are technical. Theorem 3.5 shows that, with a properly chosen γ, we have a performance guarantee without any other offline techniques. We name this effect of the discount factor the pessimistic effect. Note that to make this bound meaningful, we need the dataset size N to be large enough so that 1 − ε > 0. This means that this theorem applies when the data is sufficient, contrary to the condition for the regularization effect. Compared to the bound in Theorem 3.3, we note that the bound in Theorem 3.5 is smaller with a factor of √ d because a lower γ resembles the model-based pessimism rather than a model-free one.
We empirically verify this effect on the tabular MDPs and the D4RL dataset, where simple discount factor regularization is enough to derive a reasonable performance. This pessimistic effect suggests that γ affects the performance in offline RL differently compared to online settings.

Empirical Results
In this section we examine the role of discount factor through various experiments and aim to investigate the following questions: 1. How effective is the regularization effect of γ and how other factors affect its performance? 2. How effective is the pessimistic effect of γ and how does it contribute to the performance? 3. Is a lower guidance discount factor effective and essential in practical offline settings? We answer the questions above by experiments on both tabular MDPs and D4RL tasks. Each experiment result is averaged over three random seeds with the standard  Table 2. Experimental results on noised D4RL tasks, such as walker2d (x), hopper (x) and halfcheetah (x), containing 50 medium and x noised trajectories. We conduct a comparison between original and lower guidance discount factor (e.g., BCQ and BCQ (γ)). deviation.

TABULAR EXPERIMENTS
We first adopt the BCQ-style offline method in a tabular MDP environment to investigate the effectiveness of the lower discount factor. We consider a random MDP, where the state space consists of a 30 × 30 grid, and each state has 10 actions. The reward and the transition probabilities are generated randomly. Given the tabular MDP, we compute the true optimal value Q * γe , where γ e = 0.95. Then, we calculate the behavior policy according to µ(· | s) = softmax(Q * γe (s, ·)) · mask(s, ·), where mask(s, ·) is randomly selected in state-action space to approximate the unseen pairs in offline tasks. Further, we calculate µ(· | s) = softmax(Q * γe (s, ·)) · mask(s, ·) to approximate the generative model in BCQ, where mask 1 − mask 1 > 0. The Noise Ratio = mask 1− mask 1 mask 1 * 100% represents the inaccuracy of the generative model. We calculate BCQstyle value function Q γ by constraining the maximization operator into the finite state-action space: In the experiments, the proportion of masked state-action pairs is 0.5, and the noise ratio coefficients are {4%, 6%, 8%, 12%} respectively. We compute the estimation error ( Q γ −Q * γe ) ∞ at seen state-action pairs for different noise ratio coefficients and different discount factors. The results are summarized in Figure 1. Each plot shows the average estimation error across 100 MDP instances. The experimental results demonstrate that the lower guidance discount factor significantly reduces the estimation error in the tabular offline task. Moreover, as the noise ratio increases, the optimal discount factor γ * marked by the star shapes becomes smaller. This indicates that discount regularization is more significant when function approximation error is large, which may result from insufficient data or poor data coverage.

EXPERIMENTAL RESULTS ON D4RL TASKS
This section investigates the regularization effect in complex tasks. Specifically, we evaluate various offline RL algorithms (TD3+BC (Fujimoto & Gu, 2021), BCQ (Fujimoto et al., 2019) and COMBO (Yu et al., 2021)) with a lower guidance discount factor on the limited and noised D4RL benchmark of MuJoCo tasks. To test performance in low data regimes and poor coverage scenarios, the training dataset in our experiments contains 50 medium trajectories and additional noisy trajectories ranging from 0 to 100. The noised trajectories are fragments of the random datasets in D4RL. We use the author-provided implementation or the recognized code to ensure a fair and identical experimental evaluation across algorithms. The experimental results are shown from two aspects: coverage ratio and data size.
Coverage Ratio. We report the final performance of TD3+BC with different amounts of noisy data in Table 2 and the detailed training curves in Appendix C. The training datasets contain 50 medium and x noised trajectories, with x ranging from 0 to 100. The noised trajectories are fragments from the random dataset. Results show that the performance of current offline RL methods with original discount facotr (γ = 0.99) degrades with more noisy data due to the poor coverage ratio in the dataset. In contrast, offline RL methods with a lower guidance discount factor (γ = 0.95) achieve stable and robust performance in most scenarios.
Further, the generated data of model-based offline RL is usually noisy since the challenges of the limited data (please see the performance gap between COMBO and COMBO (γ) in walker2d and hopper task).  Table 4. Experimental results on Adroit tasks in D4RL, where the Q-ensemble size N is 50. We select γ = 0.95 in pen-expert-v0, hammer-expert-v0 and relocate-expert-v0 tasks. We select lower γ = 0.9 in door-expert-v0 tasks.
Data Size. We evaluate TD3+BC on datasets containing x medium and 100 noised trajectories, with x ranging from 0 to 1000. We select the optimal discount factor γ * ∈ [0.89, 0.99]. Experimental results in Figure 4 show that the optimal discount factor γ * increases with the number of trajectories. That is, the effect of the discount factor is more significant when the size of the dataset is small, which is consistent with the analysis in Theorem 3.3. The experimental results also suggest we prefer a higher discount factor in large datasets (e.g., the standard datasets in D4RL tasks).
Sparse Reward. We evaluate EVL (Ma et al., 2021) with various γ on standard Antmaze tasks in D4RL, where the stitching (approximate dynamical programming) is necessary. Further, Antmaze is a sparse reward task that tightens the bound in Lemma 3.1 up to a 1/(1 − γ) factor, making the optimal γ larger. However, a lower γ still works better than the usual 0.99 even in large tasks (Please refer to experimental results in Table 5). These results show that the regularization effects and finetuning γ work generally, even in sparse reward tasks. (In the medium and large tasks, we set the terminal reward r T as 100 and 50, and the expectile ratio is 0.96.)  Figure 2. Relationship between γ and α of TD3+BC on halfcheetah task. The value is the normalized return metric. The optimal γ * is marked with orange color.

Pessimistic Effect
We conduct experiments on both tabular MDPs and D4RL tasks with a lower discount factor and no other offline regularization to investigate the pessimistic effect.
Tabular MDPs. We adopt the same setting and evaluation metric as the toy example in Section 4.1.1. In the experiments, we define the coverage ratio as the proportion of masked state-action pairs ranging from 50% to 90%. The experimental results in Figure 1 show that a lower discount factor promotes offline RL algorithms to have a better estimation, and the effect is more significant when the data coverage is poor.
D4RL Task. We evaluate the standard off-policy algorithm SAC with ensemble networks on standard D4RL datasets, which is shown in Table 3 and Table 4. Adroit tasks require dynamic programming to infer the complete action  Figure 4. The relationship between optimal discount factor γ * and datasize on noised D4RL tasks. sequence for finishing the task, while a lower γ works surprisingly well with Q-ensemebles. Moreover, the experimental results on mujoco tasks show that SAC achieves a noticeable performance with a lower guidance discount factor, demonstrating the role of the discount factor as a pessimistic mechanism. While the pessimism of lower γ is not as good as the state-of-the-art offline algorithms, it serves as a good baseline. It significantly surpasses online algorithms with no discount factor pessimism. The pessimistic mechanism of the discount factor is coarse, in the sense that it is a single parameter that affects all state-action pairs, which explains why the pessimism of lower γ is not as good as the state-of-the-art offline algorithms. We leave finding methods for more fine-grained discount factor control as interesting future work.

SENSITIVITY OF THE DISCOUNT FACTOR
This section tests the performance sensitivity regarding γ and whether we need to fine-tune γ for each task. To this end, we evaluate TD3+BC on datasets containing 50 medium and 25 noised trajectories with various γ. In Figure 3, TD3+BC achieves a high performance by decreasing γ from 0.99 to around 0.95. Different offline RL algorithms have minor differences in selecting γ on various tasks (e.g., the particular case in Table 2). The suitable area of γ is almost identical [0.95, 0.99].

DISCUSSION BETWEEN γ AND α IN TD3+BC
Many offline RL algorithms achieve a trade-off between conservation and generalization by some other parameter (e.g., the regularized hyper-parameter α in TD3+BC). This naturally leads to the following question: Is finetuning γ more effective than simple regularizations like behavior cloning? To answer this question, we evaluate TD3+BC on the halfcheetah task containing 100 medium and random trajectories fragments. Experimental results in Figure 2 show that by properly combining α and γ, we can solve tasks more effectively. This indicates that γ offers more flexibility than the original regularization. Moreover, note that the behavior cloning performance in this task is poor (the normalized score is 0.0). Therefore, the role of the lower discount factor is not equivalent to behavior cloning.
Further, the experimental results also suggest that other conservative regularization affects the optimal guidance discount factor (shown in orange in Figure 2). In general, the stronger the other regularization, the higher the optimal discount factor, matching our intuition that there is a trade-off between two regularizations.

Conclusion
This paper examines the two distinct effects of the discount factor in offline RL, i.e., the regularization effect and the pessimistic effect. On the one hand, the discount factor acts as a regulator to trade-off optimality with sample efficiency upon existing offline techniques like a negative uncertainty-based bonus. On the other hand, we show that a lower guidance discount factor is equivalent to the model-based pessimism, where we optimize the policy's performance in the worst possible models. We quantify the above effects by analyzing the performance bounds with a lower guidance discount factor in linear MDPs. Moreover, we verify the above theoretical observations in tabular MDPs and D4RL tasks. Empirical results show that a lower discount factor can significantly improve performance in two scenarios. The first is when the data size is limited or there is poor data coverage, and we can apply a lower discount factor with additional pessimism. The second is when the data is sufficient, and we can directly use a lower discount factor as a proper pessimistic mechanism.
Our work suggests that the discount factor plays a vital role in offline RL, promoting current offline RL methods in complex and diverse scenarios. This leaves several interesting future works: (i) Can a lower guidance discount factor be better integrated with current offline algorithms, like fine-grained guidance γ at each transition? (ii) Is there a better theoretical explanation for the success of a lower discount factor in offline RL? (iii) How to develop more efficient offline algorithms in limited data size and insufficient coverage scenarios?

Acknowledgements
This work is supported in part by Science and Technology Innovation 2030 -"New Generation Artificial Intelligence" Major Project (No. 2018AAA0100904) and National Natural Science Foundation of China (62176135).

A. Algorithm Details
In this section, we describe some details of the algorithms mentioned in Section 2.1.

A.1. Pessimistic Value Iteration
In linear MDPs, we can construct B γ V and Γ based on D as follows, where B γ V is the empirical estimation for B γ V . For a given dataset D = {(s τ , a τ , r τ )} N τ =1 , we define the empirical mean squared Bellman error (MSBE) as Here λ > 0 is the regularization parameter. Note that w has the closed form Then we simply let Meanwhile, we construct Γ based on D as Here β > 0 is the scaling parameter.

A.2. Model-based Pessimistic Policy Optimization
To give a proper performance bound, we consider the following model set M D = P (·|s, a) ∈ M E D D TV ( P (·|s, a), P (·|s, a)) 2 ≤ ξ , where P = argmax P E D [ln P (s | s, a)] and M is the set of linear models. In practice, we can parameterize the model P θ (·|s, a) and train the model via the following loss ln P θ (s τ +1 |s τ , a τ ).
When assuming the transitions are Gaussian, the MLE objective can be reduced to prediction loss as follows As to the minimax optimization in (8) Proof. For a sufficiently large λ, it is easy to see that T V := max a ( B γ V − Γ) is a contraction. Without loss of generality, we assume λ = 1. Then Algorithm 1 converges and we have V (·) = max a Q(·, a), From the definition of δ(·, ·), we have Under the condition of Lemma B.2, it holds that 0 ≤ δ(s, a) ≤ 2Γ(s, a), for all s, a.
From Lemma B.1, we have Here the first inequality follows from the fact that π(·|s) = argmax π Q(·, ·), π(·|s) and the second inequality follows from Equation (23). Then the following event holds with probability 1 − ξ/2. From the assumption in Equation (9), the following event also holds with probability 1 − ξ/2. Then from the union bound, the event E ∩ E † holds with probability 1 − ξ. We condition on this event here after. By the Cauchy-Schwarz inequality, we have for all s ∈ S. On the event E ∩ E † , we have .
Here {λ j (s)} d j=1 are the eigenvalues of Σ π * ,s for all s ∈ S, the first inequality follows from the definition of E in Equation (25), and the second inequality follows from Equation (26) and the definition of E † in Equation (9). Meanwhile, by Definition 2.1, we have φ(s, a) ≤ 1 for all (s, a) ∈ S × A. By Jensen's inequality, we have for all s ∈ S. As Σ π * ,s is positive semidefinite, we have λ j (s) ∈ [0, 1] for all s ∈ S and all j ∈ [d]. Hence, on E ∩ E † , we have for all x ∈ S, where the second inequality follows from the fact that λ j (s) ∈ [0, 1] for all s ∈ S and all j ∈ [d], while the third inequality follows from the choice of the scaling parameter β > 0. Then we have the conclusion in Lemma 3.1.
Lemma B.1 (Suboptimality Decomposition). We have where f, g = a∈A f (a)g(a)da.
Proof. We have The first term satisfies Combining the two equations above, we have the desired result.
For (i), we have where the first inequality follows from Cauchy-Schwartz inequality. The second inequality follows from the fact that ||Λ −1 || op ≤ λ −1 and Lemma B.3.
For notation simplicity, let τ = r τ + γ V (s τ +1 ) − φ τ w, then we have The term (iii) is depend on the randomness of the data collection process of D. To bound this term, we resort to uniform concentration inequalities to upper bound where V (s; w, β, Σ) = max a {φ(s, a) w − β · φ(s, a) Σ −1 φ(s, a)}. For all > 0, let N ( ; R, B, λ) be the minimal cover if V(R, B, λ). That is, for any function V ∈ V(R, B, λ), there exists a function V † ∈ N ( ; R, B, λ), such that Then we have Let † τ = r(s τ , a τ ) + γV † (s τ +1 ) − BV † (s, a), we have From the assumption for data collection process, it is easy to show that is the σ-algebra generated by the variables from the first τ step. Moreover, since τ ≤ 2V max , we have τ are 2V max -sub-Gaussian conditioning on F τ −1 . Then we invoke Lemma B.6 with M 0 = λ · I and M k = λ · I + k τ =1 φ(x τ , a τ ) φ(x τ , a τ ) . For the fixed function V : S → [0, V max ], we have for all δ ∈ (0, 1). Note that φ(s, a) ≤ 1 for all (s, a) ∈ S × A by Definition 2.1. We have where · op denotes the matrix operator norm. Hence, it holds that det(Λ) ≤ (λ + N ) d and det(λ · I) = λ d , which implies Therefore, we conclude the proof of Lemma B.2.

Lemma B.3 (Bounded weight of value function). Let
Proof. since w φ(s, a) = M, φ(s, a) + γ V (s )ψ(s ) M φ(s, a)ds , For w, we have B.2. Proof of Lemma 3.4 Proof. We consider the following iteration: It is easy to see that if the iteration in (45) converges, it is the value function for the policies specified in Equation (11). In fact, the iteration above has a unique stationary solution follows from the fact that it is a γ-contraction for V (s). Then it suffices to show that the solution to the value iteration with discount factor (1 − ε)γ is the same as the above stationary solution up to a constant. Let Q(s, a) and V (s) be the solution to the value iteration with discount factor (1 − ε)γ. This leads to This means that Q is the unique stationary solution to the iteration in (45). Then we have the value function for policies in Equation (11) has the same value function as the policies in Equation (12) up to a constant. Then we finish the proof of Lemma 3.4.

B.3. Proof of Theorem 3.5
Proof. We first specialize the algorithm for offline value iteration with a lower discount factor and an estimatied model, as depicted in Algorithm 3.  a)] ≤ ε}.

7:
Set V (·) ← E π Q(·, ·) . 8: end while 9: Return π Algorithm 3 is similar to the idea of a lower discount factor (1 − ε)γ, with only technical differences. It is easy to show that Algorithm 3 with discount factor γ and a lower yields the same policy as the following optimization problem Here M is the model obtained from MLE estimator and M is the set of all linear models. The proof is similar to Lemma 3.4 and we omit it for simplicity.
Then we prove the theorem with the following steps. Assumption B.4 (Regularity). We assume that the underlying linear MDP satisfies where p min = inf P(s |s,a)>0 P(s |s, a), p max = sup P(s |s,a)<1 P(s |s, a).
Note that this assumption is always true for tabular MDPs. It only rules out the case when there exists a sequence {s n } ∞ n=1 such that lim n→∞ P(s n |s, a) = 0 or lim n→∞ P(s n |s, a) = 1. Then we have Recall that M ε = M |P(·|s, a; M ) = (1 − ε)P(·|s, a; M ) + εP(·) . On the one hand, it is easy to see that the largest deviation in M ε from M happens when P(·|s, a; M )) is close to 0 or close to 1. On the other hand, we have D TV ((1 − ε)P(·|s, a; M ) + εP(·), P(·|s, a; M )) ≤ ε. Then we have the result in Equation (46). The following steps largely follows (Uehara & Sun, 2021). To do that, we calculate the entropy integral with bracketing. First, we have

Upper-bounding E
Here, we use two observations. The first observation is and Assumption B.4 that P (s | s, a) ≥ c 0 > 0. The second observation is when we have P < g < P , we also have (P + P )/2 < (g + P )/2 < (P + P )/2. Then, 47 is concluded.
From the second statement of Lemma B.8, Here, we have .

(C-S inequality)
On the Role of Discount Factor in Offline Reinforcement Learning The first term (a) is upper-bounded by V 2 max ξ + λd noting 0 ≤ V π * P ≤ V max . The term (b) is upper-bounded by x Σ(ρ)x , and The second inequality follows from the definition of c V , and the last inequality follows from the third statement in Lemma B.8. By taking λ s.t. λd V max ξ, We have the desired Equation (59).
Proof of Lemma B.5. See Lemma D.6 in (Jin et al., 2020) for a detailed proof.
Lemma B.6 (Concentration of Self-Normalized Processes (Abbasi-Yadkori et al., 2011)). Let {F t } ∞ t=0 be a filtration and { t } ∞ t=1 be an R-valued stochastic process such that t is F t -measurable for all t ≥ 1. Moreover, suppose that conditioning on F t−1 , t is a zero-mean and σ-sub-Gaussian random variable for all t ≥ 1, that is, Meanwhile, let {φ t } ∞ t=1 be an R d -valued stochastic process such that φ t is F t−1 -measurable for all t ≥ 1. Also, let M 0 ∈ R d×d be a deterministic positive-definite matrix and Then, the entropy integral of F is given by We also define the localized class of H: where h(P (· | s, a) P (· | s, a)) denotes Hellinger distance defined by Proof. The proof follows directly by adapting to conditional distribution from Theorem 7.4 in (Geer et al., 2000). Please refer to (Geer et al., 2000) for more details.