Self-Challenging Improves Cross-Domain Generalization

Introduction

Imagine teaching a child to visually differentiate “dog” from “cat”: when presented with a collection of illustrations from her picture books, she may immediately answer that “cats tend to have chubby faces” and end the learning. However, if we continue to ask for more differences, she may start to notice other features like ears or body-size. We conjecture this follow-up challenge question plays a significant role in helping human reach the remarkable generalization ability. Most people should be able to differentiate “cat” from “dog” visually even when the images are presented in irregular qualities. After all, we did not stop learning after we picked up the first clue when we were children, even the first clue was good enough to help us recognize all the images in our textbook.

Nowadays, deep neural networks have exhibited remarkable empirical results over various computer vision tasks, yet these impressive performances seem unmet when the models are tested with the samples in irregular qualities (i.e., out-of-domain data, samples collected from the distributions that are similar to, but different from the distributions of the training samples). To account for this discrepancy, technologies have been invented under the domain adaptation regime , where the goal is to train a model invariant to the distributional differences between the source domain (i.e., the distribution of the training samples) and the target domain (i.e., the distribution of the testing samples) .

As the influence of machine learning increases, the industry starts to demand the models that can be applied to the domains that are not seen during the training phase. Domain generalization , as an extension of domain adaptation, has been studied as a response. The central goal is to train a model that can align the signals from multiple source domains.

Further, Wang et al. extend the problem to ask how to train a model that generalizes to an arbitrary domain with only the training samples, but not the corresponding domain information, as these domain information may not be available in the real world . Our paper builds upon this set-up and aims to offer a solution that allows the model to be robustly trained without domain information and to empirically perform well on unseen domains.

In this paper, we introduce a simple training heuristic that improves cross-domain generalization. This approach discards the representations associated with the higher gradients at each epoch, and forces the model to predict with remaining information. Intuitively, in a image classification problem, our heuristic works like a “self-challenging” mechanism as it prevents the fully-connected layers to predict with the most predictive subsets of features, such as the most frequent color, edges, or shapes in the training data. We name our method Representation Self Challenging (RSC) and illustrate its main idea in Figure 1.

We present mathematical analysis that RSC induces a smaller generalization bound. We further demonstrate the empirical strength of our method with domain-agnostic cross-domain evaluations, following previous setup . We also conduct ablation study to examine the alignment between its empirical performance and our intuitive understanding. The inspections also shed light upon the choices of its extra hyperparameter.

Related Work

We summarize the related DG works from two perspectives: learning domain invariant features and augmenting source domain data. Further, as RSC can be broadly viewed as a generic training heuristic for CNN, we also briefly discuss the general-purpose regularizations that appear similar to our method.

DG through Learning Domain Invariant Features: These methods typically minimize the discrepancy between source domains assuming that the resulting features will be domain-invariant and generalize well for unseen target distributions. Along this track, Muandet et al. employed Maximum Mean Discrepancy (MMD) . Ghifary et al. proposed a multi-domain reconstruction auto-encoder . Li et al. applied MMD constraints to an autoencoder via adversarial training .

Further, recent DG works forgo the requirement of source domains partitions and directly learn the cross-domain generalizable representations through a mixed collection of training data. Wang et al. extracted robust feature representation by projecting out superficial patterns like color and texture . Wang et al. penalized model’s tendency in predicting with local features in order to extract robust globe representation . RSC follows this more recent path and directly activates more features in all source domain data for DG without knowledge of the partition of source domains.

DG through Augmenting Source Domain: These methods augment the source domain to a wider span of the training data space, enlarging the possibility of covering the span of the data in the target domain. For example, An auxiliary domain classifier has been introduced to augment the data by perturbing input data based on the domain classification signal . Volpi et al. developed an adversarial approach, in which samples are perturbed according to fictitious target distributions within a certain Wasserstein distance from the source . A recent method with state-of-the art performance is JiGen , which leverages self-supervised signals by solving jigsaw puzzles.

Key difference: These approaches usually introduce a model-specific DG model and rely on prior knowledge of the target domain, for instance, the target spatial permutation is assumed by JiGen . In contrast, RSC is a model-agnostic training algorithm that aims to improve the cross-domain robustness of any given model. More importantly, RSC does not utilize any knowledge of partitions of domains, either source domain or target domain, which is the general scenario in real world application.

Generic Model Regularization: CNNs are powerful models and tend to overfit on source domain datasets. From this perspective, model regularization, e.g., weight decay , early stopping, and shake-shake regularization , could also improve the DG performance. Dropout mutes features by randomly zeroing each hidden unit of the neural network during the training phase. In this way, the network benefit from the assembling effect of small subnetworks to achieve a good regularization effect. Cutout and HaS randomly drop patches of input images. SpatialDropout randomly drops channels of a feature map. DropBlock drops contiguous regions from feature maps instead of random units. DropPath zeroes out an entire layer in training, not just a particular unit. MaxDrop selectively drops features of high activations across the feature map or across the channels. Adversarial Dropout dropouts for maximizing the divergence between the training supervision and the outputs from the network. leverages Adversarial Dropout to learn discriminative features by enforcing the cluster assumption.

Key difference: RSC differs from above methods in that RSC locates and mutes most predictive parts of feature maps by gradients instead of randomness, activation or prediction divergence maximization. This selective process plays an important role in improving the convergence, as we will briefly argue later.

Method

As a generic deep learning training method, RSC solves the same standard loss function as the ones used by many other neural networks, i.e.,

At each iteration, RSC inspects the gradient, identifies and then mutes the most predictive subset of the representation $\mathbf{z}$ (by setting the corresponding values to zero), and finally updates the entire model.

This simple heuristic has three steps (for simplicity, we drop the indices of samples and assume the batch size is 1 in the following equations):

Locate: RSC first calculates the gradient of upper layers with respect to the representation as follows:

where $\odot$ denotes an element-wise product. Then RSC computes the $(100-p)$th percentile, denoted as $q_{p}$. Then it constructs a masking vector $\mathbf{m}$ in the same dimension of $\mathbf{g}$ as follows. For the $i$th element:

In other words, RSC creates a masking vector $\mathbf{m}$, whose element is set to if the corresponding element in $\mathbf{g}$ is one of the top $p$ percentage elements in $\mathbf{g}$, and set to $1$ otherwise.

Mute: For every representation $\mathbf{z}$, RSC masks out the bits associated with larger gradients by:

Update: RSC computes the softmax with perturbed representation with

to update the entire model for $\widehat{\theta}_{t+1}$ with optimizers such as SGD or ADAM.

We summarize the procedure of RSC in Algorithm 1. No that operations of RSC comprise of only few simple operations such as pooling, threshold and element-wise product. Besides the weights of the original network, no extra parameter needs to be learned.

2 Theoretical Evidence

To expand the theoretical discussion smoothly, we will refer to the “dog” vs. “cat” classification example repeatedly as we progress. The basic set-up, as we introduced in the beginning of this paper, is the scenario of a child trying to learn the concepts of “dog” vs. “cat” from illustrations in her book: while the hypothesis “cats tend to have chubby faces” is good enough to classify all the animals in her picture book, other hypotheses mapping ears or body-size to labels are also predictive.

On the other hand, if she wants to differentiate all the “dogs” from “cats” in the real world, she will have to rely on a complicated combination of the features mentioned about. Our main motivation of this paper is as follows: this complicated combination of these features is already illustrated in her picture book, but she does not have to learn the true concept to do well in her finite collection of animal pictures.

This disparity is officially known as “covariate shift” in domain adaptation literature: the conditional distribution (i.e., the semantic of a cat) is the same across every domain, but the model may learn something else (i.e., chubby faces) due to the variation of marginal distributions.

With this connection built, we now proceed to the theoretical discussion, where we will constantly refer back to this “dog” vs. “cat” example.

As the large scale deep learning models, such as AlexNet or ResNet, are notoriously hard to be analyzed statistically, we only consider a simplified problem to argue for the theoretical strength of our method: we only concern with the upper layer $h(\cdot;\theta^{\textnormal{top}})$ and illustrate that our algorithm helps improve the generalization of $h(\cdot;\theta^{\textnormal{top}})$ when $\mathbf{Z}$ is fixed. Therefore, we can directly treat $\mathbf{Z}$ as the data (features). Also, for convenience, we overload $\theta$ to denote $\theta^{\textnormal{top}}$ within the theoretical evidence section.

We expand our notation set for the theoretical analysis. As we study the domain-agnostic cross-domain setting, we no longer work with i.i.d data. Therefore, we use $\mathcal{Z}$ and $\mathcal{Y}$ to denote the collection of distributions of features and labels respectively. Let $\Theta$ be a hypothesis class, where each hypothesis $\theta\in\Theta$ maps $\mathcal{Z}$ to $\mathcal{Y}$. We use a set $\mathcal{D}$ (or $\mathcal{S}$) to index $\mathcal{Z}$, $\mathcal{Y}$ and $\theta$. Therefore, $\theta^{\star}(\mathcal{D})$ denotes the hypothesis with minimum error in the distributions specified with $\mathcal{D}$, but with no guarantees on the other distributions.

$\theta^{\star}(\mathcal{D})$ can be “cats have chubby faces” when $\mathcal{D}$ specifies the distribution to be picture book.

Further, $\theta^{\star}$ denotes the classifier with minimum error on every distribution considered. If the hypothesis space is large enough, $\theta^{\star}$ should perform no worse than $\theta^{\star}(\mathcal{D})$ on distributions specified by $\mathcal{D}$ for any $\mathcal{D}$.

$\theta^{\star}$ is the true concept of “cat”, and it should predict no worse than “cats have chubby faces” even when the distribution is picture book.

where $e(\cdot;\cdot)$ is a function defined as

As the result shows, whether RSC will succeed depends on the magnitude of $\xi(p)$. The smaller $\xi(p)$ is, the tighter the bound is, the better the generalization bound is. Interestingly, if $\xi(p)=0$, our result degenerates to the classical generalization bound of i.i.d data.

While it seems the success of our method will depend on the choice of $\Theta$ to meet Condition 6, we will show RSC is applicable in general by presenting it forces the empirical counterpart $\widehat{\xi}(p)$ to be small. $\widehat{\xi}(p)$ is defined as

where the function $h(\cdot,\cdot)$ is defined as

We will show $\widehat{\xi}(p)$ decreases at every iteration with more assumptions:

Discarding the most predictive features will increase the loss at current iteration.

The learning rate $\eta$ is sufficiently small ($\eta^{2}$ or higher order terms are negligible).

If Assumption A4 holds, we can simply denote

where $h(\cdot,\cdot)$ is defined in Equation 7. $\gamma_{t}(p)$ is an arbitrary number greater than 1, also a function of RSC’s hyperparameter $p$. Also, if Assumption A5 holds, we have:

Notice that $\widehat{\xi}(p)=\Gamma(\widehat{\theta}_{\textnormal{RSC{}}})$, where $\widehat{\theta}_{\textnormal{RSC{}}}$ is $\widehat{\theta}_{\textnormal{RSC{}}}(t)$ at the last iteration $t$. We can show that $\widehat{\xi}(p)$ is a small number because $\Gamma(\widehat{\theta}_{\textnormal{RSC{}}}(t))$ gets smaller at every iteration. This discussion is also verified empirically, as shown in Figure 2.

The decreasing speed of $\Gamma(\widehat{\theta}_{\textnormal{RSC{}}}(t))$ depends on the scalar $\gamma_{t}(p)$: the greater $\gamma_{t}(p)$ is, the faster $\Gamma(\widehat{\theta}_{\textnormal{RSC{}}}(t))$ descends. Further, intuitively, the scale of $\gamma_{t}(p)$ is highly related to the mechanism of RSC and its hyperparameter $p$. For example, RSC discards the most predictive representations, which intuitively guarantees the increment of the empirical loss (Assumption A4).

Finally, the choice of $p$ governs the increment of the empirical loss: if $p$ is small, the perturbation will barely affect the model, thus the increment will be small; while if $p$ is large, the perturbation can alter the model’s response dramatically, leading to significant ascend of the loss. However, we cannot blindly choose the largest possible $p$ because if $p$ is too large, the model may not be able to learn anything predictive at each iteration.

In summary, we offer the intuitive guidance of the choice of hyperparamter $p$: for the same model and setting,

the smaller $p$ is, the smaller the training error will be;

the bigger $p$ is, the smaller the (cross-domain) generalization error (i.e., difference between testing error and training error) will be.

Therefore, the success of our method depends on the choice of $p$ as a balance of the above two goals.

3 Engineering Specification & Extensions

For simplicity, we detail the RSC implementation on a ResNet backbone + FC classification network. RSC is applied to the training phase, and operates on the last convolution feature tensor of ResNet. Denote the feature tensor of an input sample as ${\bf{Z}}$ and its gradient tensor of as ${\bf{G}}$. ${\bf{G}}$ is computed by back propagating the classification score with respect to the ground truth category. Both of them are of size $[7\times 7\times 512]$.

Spatial-wise RSC: In the training phase, global average pooling is applied along the channel dimension to the gradient tensor ${\bf{G}}$ to produce a weighting matrix $w_{i}$ of size $[7\times 7]$. Using this matrix, we select top $p$ percentage of the $7\times 7=49$ cells, and mute its corresponding features in ${\bf{Z}}$. Each of the $49$ cells correspond to a $[1\times 1\times 512]$ feature vector in ${\bf{Z}}$. After that, the new feature tensor ${\bf Z_{new}}$ is forwarded to the new network output. Finally, the network is updated through back-propagation. We refer this setup as spatial-wise RSC, which is the default RSC for the rest of this paper.

Channel-wise RSC: RSC can also be implemented by dropping features of the channels with high-gradients. The rational behind the channel-wise RSC lies in the convolutional nature of DNNs. The feature tensor of size $[7\times 7\times 512]$ can be considered a decomposed version of input image, where instead of the RGB colors, there are $512$ different characteristics of the each pixels. The $C$ characteristics of each pixel contains different statistics of training data from that of the spatial feature statistics.

For channel-wise RSC, global average pooling is applied along the spatial dimension of ${\bf{G}}$, and produce a weighting vector of size $[1\times 512]$. Using this vector, we select top $p$ percentage of its $512$ cells, and mute its corresponding features in ${\bf{Z}}$. Here, each of the $512$ cells correspond to a $[7\times 7]$ feature matrix in ${\bf{Z}}$. After that, the new feature tensor ${\bf Z_{new}}$ is forwarded to the new network output. Finally, the network is updated through back-propagation.

Batch Percentage: Some dropout methods like curriculum dropout do not apply dropout at the beginning of training, which improves CNNs by learning basic discriminative clues from unchanged feature maps. Inspired by these methods, we randomly apply RSC to some samples in each batch, leaving the other unchanged. This introduces one extra hyperparameter, namely Batch Percentage: the percentage of samples to apply RSC in each batch. We also apply RSC to top percentage of batch samples based on cross-entropy loss. This setup is slight better than randomness.

Detailed ablation study on above extensions will be conducted in the experiment section below.

Experiments

We consider the following four data collections as the battleground to evaluate RSC against previous methods.

PACS : seven classes over four domains (Artpaint, Cartoon, Sketches, and Photo). The experimental protocol is to train a model on three domains and test on the remaining domain.

VLCS : five classes over four domains. The domains are defined by four image origins, i.e., images were taken from the PASCAL VOC 2007, LabelMe, Caltech and Sun datasets.

Office-Home : 65 object categories over 4 domains (Art, Clipart, Product, and Real-World).

ImageNet-Sketch : 1000 classes with two domains. The protocol is to train on standard ImageNet training set and test on ImageNet-Sketch.

2 Ablation Study

We conducted five ablation studies on possible configurations for RSC on the PACS dataset . All results were produced based on the ResNet18 baseline in and were averaged over five runs.

(1) Feature Dropping Strategies (Table 1). We compared the two attention mechanisms to select the most discriminative spatial features. The “Top-Activiation” selects the features with highest norms, whereas the “Top-Gradient” (default in RSC) selects the features with high gradients. The comparison shows that “Top-Gradient” is better than “Top-Activation”, while both are better than the random strategy. Without specific note, we will use “Top-Gradient” as default in the following ablation study.

(2) Feature Dropping Percentage (choice of $p$) (Table 2): We ran RSC at different dropping percentages to mute spatial feature maps. The highest average accuracy was reached at $p=33.3\%$. While the best choice of $p$ is data-specific, our results align well with the theoretical discussion: the optimal $p$ should be neither too large nor too small.

(3) Batch Percentage (Table 3): RSC has the option to be only randomly applied to a subset of samples in each batch. Table 3 shows that the performance is relatively constant. Nevertheless we still choose $33.3\%$ as the best option on the PACS dataset.

(4) Spatial-wise plus Channel-wise RSC (Table 4): In “Spatial+Channel”, both spatial-wise and channel-wise RSC were applied on a sample at $50\%$ probability, respectively. (Better options of these probabilities could be explored.) Its improvement over Spatial-wise RSC indicates that it further activated features beneficial to target domains.

(5) Comparison with different dropout methods (Table 5): Dropout has inspired a number of regularization methods for CNNs. The main differences between those methods lie in applying stochastic or non-stochastic dropout mechanism at input data, convolutional or fully connected layers. Results shows that our gradient-based RSC is better. We believe that gradient is an efficient and straightforward way to encode the sensitivity of output prediction. To the best of our knowledge, we compare with the most related works and illustrate the impact of gradients. (a) Cutout . Cutout conducts random dropout on input images, which shows limited improvement over the baseline. (b) DropBlock . DropBlock tends to dropout discriminative activated parts spatially. It is better than random dropout but inferior to non-stochastic dropout methods in Table 5 such as AdversarialDropout, Top-Activation and our RSC. (c) AdversarialDropout . AdversarialDropout is based on divergence maximization, while RSC is based on top gradients in generating dropout masks. Results show evidence that the RSC is more effective than AdversarialDropout. (d) Random and Top-Activation dropout strategies at their best hyperparameter settings.

3 Cross-Domain Evaluation

Through the following experiments, we used “Top-Gradient” as feature dropping strategy, $33.3\%$ as Feature Dropping Percentages, $33.3\%$ as Batch Percentage, and Spatial+Channel RSC. All results were averaged over five runs. In our RSC implementation, we used the SGD solver, $30$ epochs, and batch size $128$. The learning rate starts with $0.004$ for ResNet and $0.001$ for AlexNet, learning rate decayed by 0.1 after 24 epochs. For PACS experiment, we used the same data augmentation protocol of randomly cropping the images to retain between $80\%$ to $100\%$, randomly applied horizontal flipping and randomly ($10\%$ probability) convert the RGB image to greyscale, following .

In Table. 6,7,8, we compare RSC with the latest domain generalization work, such as Hex , PAR , JiGen and MetaReg . All these work only report results on different small networks and datasets. For fair comparison, we compared RSC to their reported performances with their most common choices of DNNs (i.e., AlexNet, ResNet18, and ResNet50) and datasets. RSC consistently outperforms other competing methods.

The empirical performance gain of RSC can be better appreciated if we have a closer look at the PACS experiment in Table. 6. The improvement of RSC from the latest baselines are significant and consistent: $4.5$ on AlexNet, $5.2$ on ResNet18, and $4.5$ on ResNet50. It is noticeable that, with both ResNet18 and ResNet50, RSC boosts the performance significantly for sketch domain, which is the only colorless domain. The model may have to understand the semantics of the object to perform well on the sketch domain. On the other hand, RSC performs only marginally better than competing methods in photo domain, which is probably because that photo domain is the simplest one and every method has already achieved high accuracy on it.

Discussion

Standard ImageNet Benchmark: With the impressive performance observed in the cross-domain evaluation, we further explore to evaluate the benefit of RSC with other benchmark data and higher network capacity.

We conducted image classification experiments on the Imagenet database. We chose three backbones with the same architectural design while with clear hierarchies in model capacities: ResNet50, ResNet101, and ResNet152. All models were finetuned for 80 epochs with learning rate decayed by 0.1 every 20 epochs. The initial learning rate for ResNet was 0.01. All models follow extra the same training prototype in default Pytorch ImageNet implementationhttps://github.com/pytorch/examples, using original batch size of 256, standard data augmentation and $224\times 224$ as input size.

The results in Table 10 shows that RSC exhibits the ability reduce the performance gap between networks of same family but different sizes (i.e., ResNet50 with RSC approaches the results of baseline ResNet101, and ResNet101 with RSC approaches the results of baseline ResNet151). The practical implication is that, RSC could induce faster performance saturation than increasing model sizes. Therefore one could scale down the size of networks to be deployed at comparable performance.

Conclusion

We introduced a simple training heuristic method that can be directly applied to almost any CNN architecture with no extra model architecture, and almost no increment of computing efforts. We name our method Representation Self-challenging (RSC). RSC iteratively forces a CNN to activate features that are less dominant in the training domain, but still correlated with labels. Theoretical and empirical analysis of RSC validate that it is a fundamental and effective way of expanding feature distribution of the training domain. RSC produced the state-of-the-art improvement over baseline CNNs under the standard DG settings of small networks and small datasets. Moreover, our work went beyond the standard DG settings, to illustrate effectiveness of RSC on more prevalent problem scales, e.g., the ImageNet database and network sizes up-to ResNet152.

References

Appendix

A1 Assumptions

$\Theta$ is finite; $l(\cdot,\cdot)$ is zero-one loss for binary classification.

The assumption leads to classical discussions on the i.i.d setting in multiple textbooks (e.g., ). However, modern machine learning concerns more than the i.i.d setting, therefore, we need to quantify the variations between train and test distributions. Analysis of domain adaptation is discussed , but still relies on the explicit knowledge of the target distribution to quantify the bound with an alignment of the distributions. The following discussion is devoted to the scenario when we do not have the target distribution to align.

Since we are interested in the $\theta^{\star}$ instead of the $\theta^{\star}(\mathcal{D})$, we first assume $\Theta$ is large enough and we can find a global optimum hypothesis that is applicable to any distribution, or in formal words:

$L(\theta^{\star};\mathcal{D})=L(\theta^{\star}(\mathcal{D});\mathcal{D})$ for any $\mathcal{D}$.

The true concept of “cat” is the same for any collection of images.

The challenge of cross-domain evaluation comes in when there exists multiple optimal hypothesis that are equivalently good for one distribution, but not every optimal hypothesis can be applied to other distributions.

For the distribution of picture book, “cats have chubby faces” can predict the true concept of “cat”. A model only needs to learn one of these signals to reduce training error, although the other signal also exists in the data.

The follow-up discussion aims to show that RSC can force the model to learn multiple signals, so that it helps in cross-domain generalization.

Further, Assumption A2 can be interpreted as there is at least some features $\mathbf{z}$ that appear in every distributions we consider. We use $i$ to index this set of features. Assumption A2 also suggests that $\mathbf{z}_{i}$ is i.i.d. (otherwise there will not exist $\theta^{\star}$) across all the distributions of interest (but $\mathbf{z}$ is not i.i.d. because $\mathbf{z}_{-i}$, where $-i$ denotes the indices other than $i$, can be sampled from arbitrary distributions).

$\mathbf{z}$ is the image; $\mathbf{z}_{i}$ is the ingredients of the true concept of a “cat”, such as ears, paws, and furs; $\mathbf{z}_{-i}$ is other features such as “sitting by the window”.

We use $\mathcal{O}$ to specify the distribution that has values on the $i$th, but s elsewhere. We introduce the next assumption:

A2 Proof of Theoretical Results

We first study the convergence part, where we consider a fixed hypothesis. We first expand

We first consider the term $|L(\theta^{\star}_{\textnormal{RSC{}}}(\mathcal{S});\mathcal{S})-L(\theta^{\star}_{\textnormal{RSC{}}}(\mathcal{S});\mathcal{D})|$, where we can expand

Also, because of Assumption A4, if samples in $\mathcal{S}$ are perturbed versions of samples in $\mathcal{O}$, then samples in $\mathcal{O}$ can also be seen as perturbed versions of samples in $\mathcal{S}$, thus, Condition 6 can be directly re-written into:

which directly leads us to the fact that $|L(\theta^{\star}_{\textnormal{RSC{}}}(\mathcal{S});\mathcal{S})-L(\theta^{\star}_{\textnormal{RSC{}}}(\mathcal{S});\mathcal{D})|$ has the expectation 0 (A4) and bounded by $[0,\xi(p)]$.

For $|L(\widehat{\theta}_{\textnormal{RSC{}}}(\mathcal{S});\mathcal{S})-L(\theta^{\star}_{\textnormal{RSC{}}}(\mathcal{S});\mathcal{S})|$, the strategy is relatively standard. We first consider the convergence of a fixed hypothesis $\theta_{\textnormal{RSC{}}}$, then over $n$ i.i.d samples, the empirical risk ($\widehat{L}(\theta_{\textnormal{RSC{}}})$) will be bounded within $$with the expectation$L(\theta_{\textnormal{RSC{}}})$.

Before we consider the uniform convergence step, we first put the two terms together and apply the Hoeffding’s inequality. When the random variable is with expectation $L(\theta_{\textnormal{RSC{}}})$ and bound $[0,1+2\xi(p)]$, we have:

Now, we consider the uniform convergence case, where we have:

Rearranging these terms following standard tricks will lead to the conclusion.

A2.2 Corollary 2

Recall that, by the definition of RSC, we have:

We apply Taylor expansion over $h(\widehat{\theta}_{\textnormal{RSC{}}}(t+1),\cdot)$ with respect to $\widehat{\theta}_{\textnormal{RSC{}}}(t)$ and have:

where $\sigma$ denotes the higher order terms.

Assumption A6 conveniently allows us to drop terms regarding $\eta^{2}$ or higher orders, so we have:

We can simply drop the absolute value sign because all these terms are greater than zero. Finally, we rearrange these terms and prove the conclusion.