Out-Of-Domain Unlabeled Data Improves Generalization

We would like to thank the reviewer for reading our paper and giving us feedback. The reviewer has raised three primary concerns, to which we offer the following responses:

• There are several previous works in this area, and the current work should be positioned w.r.t. them: In the forthcoming revised version, we will provide clarification on the identified issue. Specifically, we will contextualize our work in relation to Najafi et al. (2019), [R1] and [R2]. For now, let us briefly delve into these works and highlight their connections to our paper. Najafi et al. (2019) employs DRO in a semi-supervised setting; however, their methodology is fundamentally different from ours. Their approach involves the utilization of 'self-training' to assign soft/hard labels to unlabeled data, subsequently merging all portions of the dataset for model training via ERM. In contrast, our approach utilizes unlabeled data exclusively to constrain the set of classifiers, aiming to avoid crowded regions. In other words, we exclusively consider classifiers whose decision boundaries are distanced from the unlabeled data. DRO serves as a tool in our approach, though not necessarily as the primary objective. [R1] has already been discussed within Najafi et al.'s paper, where strong assumptions are made regarding the extent of adversarial shifts in distributions, placing it outside the precise scope of our work. [R2] shares similarities with Najafi et al. (2019); however, instead of assigning artificial labels to unlabeled samples, [R2] employs them to delimit the ambiguity set and enhance understanding of the marginals. Consequently, i) the consideration of out-of-domain samples is omitted, and ii) the focus on unlabeled data is directed towards acquiring insights into the marginals, as opposed to restricting the set of classifiers in our work.

• The distribution shift assumed in the paper seems too simplistic and straightforward to address by DRO methods (small change in the covariates' marginal): We believe that our assumptions regarding distribution shifts are maximally inclusive. Our singular assumption regarding the covariates' marginals is that they should reside within a known Wasserstein distance of the true distribution. It is crucial to emphasize that no assumptions about the 'labeling rule' have been made, since we will not have access to labels for the unsupervised data anyway. Conversely, establishing a bound on the distance (Wasserstein distance in this study) between the marginals of the true and shifted distributions is necessary (also mentioned by Reviewer Nric). Without such constraints, unlabeled data fails to provide meaningful utility. In other words, one could consistently generate unlabeled samples from some fixed and unrelated distribution for 'any' machine learning problem, irrespective of the inherent characteristics of the datasets under consideration. Additionally, it is noteworthy that numerous significant works in this domain have assumed a very similar constraint on distribution shifts, as exemplified by [P1], [P2], [P3], [P4].

[P1] Deng, Z., Zhang, L., Ghorbani, A. and Zou, J., 2021, March. Improving adversarial robustness via unlabeled out-of-domain data. In International Conference on Artificial Intelligence and Statistics (pp. 2845-2853). PMLR.

[P2] Kumar, A., Ma, T. and Liang, P., 2020, November. Understanding self-training for gradual domain adaptation. In International Conference on Machine Learning (pp. 5468-5479). PMLR.

[P3] Lee, J. and Raginsky, M., 2018. Minimax statistical learning with wasserstein distances. Advances in Neural Information Processing Systems, 31.

[P4] Sinha, A., Namkoong, H. and Duchi, J., 2018, February. Certifying Some Distributional Robustness with Principled Adversarial Training. In International Conference on Learning Representations.

• Authors should extend the experimental results, compare with existing methods for semi-supervision and use more common benchmark datasets: In response to the reviewer's suggestion, we are committed to augmenting our experimental results in the revised version. It is important to emphasize, however, that our primary contribution lies in the realm of theory. The experiments serve the dual purpose of demonstrating the implementability of our method, ensuring its polynomial-time nature, and empirically illustrating the efficacy of leveraging unlabeled data, even from different domains, particularly when employing our proposed approach.

We would like to thank the reviewer once again for their fast response. In the following, we present the remainder of our response from Round 2:

We believe it is noteworthy to emphasize again that our work resides at the intersection of Distributionally Robust Optimization (DRO) and Semi-Supervised Learning (SSL) when unlabeled data are out-of-distribution. With all due respect, the reviewer did not mention any specific papers in this particular intersection. Since the reviewer is concerned about the level of contribution in our work, we find it useful to enumerate some of our findings here:

• We present a non-asymptotic bound on the joint utilization of labeled and unlabeled samples for adversarially robust learning, as detailed in Theorem 4.1. This result stands as the first of its kind and extends the findings of [p2] and [p3]. While these previous studies concentrate on the efficacy of unlabeled samples when a single labeled sample is adequate for linear classification of a non-robust classifier, they do not offer insights into the requisite number of unlabeled samples when multiple labeled samples are involved, especially in scenarios where the underlying distribution exhibits limited separation between the two classes.

• We introduce a non-asymptotic bound for the integration of labeled and unlabeled samples in semi-supervised learning, as articulated in Theorem 4.2. We posit that the outcomes of this theorem are unparalleled in the existing literature. To underscore the significance of our findings, consider the following example: contemplate the sample complexity of supervised learning for a linear classifier. In the realizable setting, where positive and negative samples can be completely separated by a hyperplane, the sample complexity is $\mathcal{O}(d/\epsilon)$. In the non-realizable setting, this sample complexity escalates to $\mathcal{O}(d/\epsilon^2)$. A pivotal question in learning theory revolves around how to approach the sample complexity of $\mathcal{O}(d/\epsilon)$ in the non-realizable setting. For instance, the insights provided by Namkong et al. in [P4] delve into this inquiry. Notably, even with the awareness that the underlying distribution is a Gaussian mixture, the optimal sample complexity, as per [P5], exceeds $\mathcal{O}(d/\epsilon^2)$. Our work's outcome demonstrates that in the scenario where the underlying distribution is a Gaussian mixture and we possess $m = \mathcal{O}(d/\epsilon)$ labeled samples, coupled with $n = \mathcal{O}\left(\frac{d^3}{m^2\epsilon^8}\right) = \mathcal{O}\left(\frac{d}{\epsilon^6}\right)$ unlabeled samples (without knowledge of the class to which the underlying distribution belongs), one can achieve an error rate lower than or equal to the case of having access to $\mathcal{O}(d/\epsilon^2)$ labeled samples.

• We formalize the incorporation of out-of-domain unlabeled samples into the generalization bounds of both robust and non-robust classifiers. We contend that this represents a novel contribution to the field, with its closest counterpart being [P6]. Notably, [P6] addresses a scenario where the underlying distribution is a Gaussian mixture with well-separated Gaussian components, a condition that is not a prerequisite for our results.

[P4] Namkoong, H. and Duchi, J.C., 2017. Variance-based regularization with convex objectives. Advances in neural information processing systems, 30.

[P5] Ashtiani, H., Ben-David, S., Harvey, N., Liaw, C., Mehrabian, A. and Plan, Y., 2018. Nearly tight sample complexity bounds for learning mixtures of gaussians via sample compression schemes. Advances in Neural Information Processing Systems, 31.

[P6] Deng, Z., Zhang, L., Ghorbani, A. and Zou, J., 2021, March. Improving adversarial robustness via unlabeled out-of-domain data. In International Conference on Artificial Intelligence and Statistics (pp. 2845-2853). PMLR.

We express our gratitude to the reviewer for dedicating time to read our paper and offering valuable feedback, as well as for providing a favorable score. In addressing the concerns raised by the reviewer, we present the following responses.

Concerning the weaknesses:

• How does this method compare against large-margin based methods? What if one treats the "slightly out-of-distribution" data as in distribution? Some comparison with similar approaches is warranted.: There are some similarities between our method and large-margin approaches in the sense that assuming a large margin in the distribution of data likely yields favorable bounds using our method. Regarding the second question, treating "slightly out-of-distribution" data as in distribution may introduce the distance between distributions ($\alpha$)in the upper bound. This effect intensifies with an increase in the number of unlabeled samples compared to labeled ones, potentially resulting in a loss of the upper bound. We appreciate the reviewer for raising these valuable questions, and in our revised version, we will provide a more detailed explanation as requested.

• "given" is misspelled in the abstract.: Thank you for bringing this to our attention; we will correct it.

• While I did not work through all the details, the "new set" of bounds appear to be based heavily on an upper bound of the Rademacher complexity. I feel this really ought to be stated in the abstract and main body of the paper. I don't think that comparing Rademacher complexity with VC dimension based bounds is really an advancement.: We have refrained from making assumptions about the set of linear classifiers in our hypothesis set, allowing the norms of weight vectors to remain unbounded. Consequently, our derivation of a generic upper bound for Rademacher complexity relies on VC dimension, leveraging Massart’s lemma and Sauer’s lemma. This connection is evident in the appearance of dimension $d$ in our bounds. Our results are therefore comparable to the VC dimension-based bounds highlighted by the reviewer. However, it is essential to note that our primary objective in establishing these upper bounds was to elucidate the impact of the number of unlabeled samples in the denominator. While our approach aligns with VC dimension-based bounds, should someone impose assumptions on the class of classifiers leading to a superior upper bound compared to VC dimension in the numerator, such enhancements would be reflected in our bounds as well.

• Why doesn't the amount of "slightly out of domain" enter into the bound $n > \Omega(\frac{m^2}{d})$? Certainly data from totally different domains wouldn't improve generalization, right?: Due to the result of Theorem $4.2$, the upper bound for the generalization error is $\mathcal{O}\left(\left(\frac{d\alpha}{m} + \frac{d}{m}\sqrt{\frac{d}{m+n}}\right)^{1/4}\right)$.Therefore, if we have unlabeled samples from a totally different domain, the parameter $\alpha$ will increase, worsening the upper bound. On the other hand if we have $\alpha \leq \frac{d}{m}$, the lower bound for the number of unlabeled samples to achieve a better generalization bound is $n > \Omega(\frac{m^2}{d(1-\frac{\alpha m}{d})^2})$.The bound mentioned by the reviewer in Corollary 4.4 assumes a negligible distance between distributions. Additional explanation on this matter will be provided in the final version.

Concerning the Questions:

• Can the authors add more details about the nature of their bounds in the main text to either confirm or soften claims of novel methodology?: Of course, we will add adequate details about this matter.

We hope most of the reviewer's concerns have been addressed through the above explanations.

We would like to thank the reviewer for taking the time to read our paper and providing valuable feedback. Regarding the concerns raised by the reviewer, the following responses are suggested:

Concerning the weaknesses:

• The comparison with related works isn't thorough: In the final version, we will incorporate additional explanations and provide a more detailed comparison with existing works to ensure that our contribution is distinctly highlighted.

Concerning the Questions:

• There are multiple anomalies that are unexplained in the experiments: We appreciate the reviewer for highlighting this issue. In our final version, we will conduct additional experiments and provide a detailed discussion of these anomalies. Regarding the two examples mentioned by the reviewer: i) We will include these values in our revised version. ii) The purpose of the table was not to compare the two settings where unlabeled samples came from the same or different distributions, but rather to illustrate the impact of using more unlabeled samples in each case. Therefore, we used different test sets and search spaces for hyperparameter search in these two settings, resulting in different accuracies in these two parts. However, we recognize the need for clarity and will regenerate the table, accompanied by an explanation comparing these two settings in our final version.

• It should be possible to empirically verify the dimension dependence?: Yes, we will add some experiments regarding the relationship between the number of samples and dimension in our final version.

• What is "crowded areas"?: By "crowded areas," we are referring to locations where the probability density function exhibits higher values. Our constraints, based on Distributionally Robust Optimization (DRO) and relying solely on unlabeled data, inherently force the classifier boundaries to maintain a distance from these identified areas.

• In Theorem $4.1$, why is the expectation only w.r.t $P_0$ since we also get unlabeled samples from $P_1$. If this is included in the high probability statement, then that seems strange because I would assume the algorithm randomness to be separately considered from the unlabeled dataset randomness.: The expectation in Theorem 4.1 is solely with respect to $P_0$, as these terms constitute the definition of generalization risk within the distribution for which we aim to develop a proficient classifier. Although we utilize labeled samples from $P_0$ and unlabeled samples from $P_1$ to construct a robust classifier, the stochastic nature associated with these samples is reflected in the upper bound provided for the Rademacher complexity and the high probability statement.

• Is there any intuition for why the error in robust loss increases with $\gamma$?: The parameter $\gamma$ exhibits an inverse relationship with the robustness of the classifier, indicating that a lower value of $\gamma$ leads to a more robust classifier with reduced risk. Additionally, it is a well-established fact that a more robust classifier tends to have lower variance compared to a less robust one. Consequently, a higher value of $\gamma$ corresponds to increased variance and a less favorable upper bound.

• Minor comment: I found the notation in (1), $\hat{R}(\theta, S)$ confusing and also not used later (unless in the proofs). Isn't this just $R(\theta, \hat{P}^{m}_S)$ ?: The reviewer's observation is accurate. We will rectify this issue to eliminate any potential confusion.

We hope most of the reviewer's concerns have been addressed through the above explanations.

We would like to thank the reviewer for taking the time to read our paper and providing valuable feedback. Regarding the concerns raised by the reviewer, the following responses are suggested:

Concerning the weaknesses:

• The paper's linear Gaussian mixture model is very restrictive.: It is crucial to emphasize that the algorithm and methodology outlined in the paper do not rely on specific assumptions about the distributions of the data, and consequently are NOT confined to a Gaussian mixture model. Our approach is inherently general. While conducting a theoretical analysis in the paper, we chose to assess the algorithm's performance within the framework of a Gaussian mixture model for two primary reasons: i) this assumption is prevalent in the existing literature [p1][p2][p3], thereby facilitating comparisons between our theoretical advancements and prior findings (a point also underscored by Reviewer v7JJ). Additionally, ii) employing a Gaussian mixture model allows us to derive mathematically explicit bounds, enabling us to elucidate the potentially surprising aspects of our findings.

[p1] Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K. and Madry, A., 2018. Adversarially robust generalization requires more data. Advances in neural information processing systems, 31.

[p2] Carmon, Y., Raghunathan, A., Schmidt, L., Duchi, J.C. and Liang, P.S., 2019. Unlabeled data improves adversarial robustness. Advances in neural information processing systems, 32.

[p3] Alayrac, J.B., Uesato, J., Huang, P.S., Fawzi, A., Stanforth, R. and Kohli, P., 2019. Are labels required for improving adversarial robustness?. Advances in Neural Information Processing Systems, 32.

Regarding the questions raised:

• When $n=0$, no out-of-domain samples are utilized, and the problem reduces to simple ERM. But in Theorem $4.2$, when $n=0$, the dependence of the error on the dimension is $d^{3/8}$, meaning that this reduction in the exponent of the dimension is not related to the utilization of out-of-domain samples. Furthermore, in the case of n=0, why is the non-robust error better than the error obtained through ERM?: Let us clarify this issue. When we do not use any unlabeled samples (i.e., $n=0$), our bound becomes $\mathcal{O}\left((\frac{d}{m})^{3/8}\right)$, which is actually worse than the upper-bound of ERM ($^*$), $\mathcal{O}\left((\frac{d}{m})^{1/2}\right)$, and thus the ERM algorithm gives a better generalization bound. It's also important to highlight that these bounds are meaningful only when $\frac{d}{m} \leq 1$. Additionally, in the presence of unlabeled samples, there is no requirement for $m$ to be greater than $d$ in our method. The upper-bound then becomes $\mathcal{O}\left(\left(\frac{d}{m + n}\right)^{3/8}\right)$ , and it tends to zero as $n$ approaches infinity. We will further elucidate this matter in the final version to avoid any ambiguity. Specifically, we acknowledge that Remark 4.3 may have contributed to this misunderstanding. Therefore, we are committed to revising its statement in the final version to ensure clarity.

(*) The performance gap between our method and ERM when $n=0$ can be effectively minimized to zero by intentionally diminishing the impact of the constraint (reducing $\lambda$ in our primary optimization criteria) when $n$ is small. However, it is important to note that the primary emphasis of this study is on extreme regimes, particularly when $n\gg m$. Consequently, we have chosen to omit these secondary derivations to enhance the overall readability of the paper.

We hope most of the reviewer's concerns have been addressed through the above explanations.

Thank you, Hongxin, for expressing interest in our work. Should the paper get accepted, we will make sure to incorporate a more thorough revision of existing works, including those you mentioned, in the final version.