Generalizing Importance Weighting to A Universal Solver for Distribution Shift Problems
Authors: Tongtong Fang
Nan Lu
Gang Niu
Masashi Sugiyama
Venue: NeurIPS 2023 spotlight (2023)
Keywords: importance weighting
distribution shift
deep learning
TL;DR: We generalize importance weighting for distribution shift problems so that we no longer require the support of the test distribution must be covered by the support of the training distribution.

Abstract: Distribution shift (DS) may have two levels: the distribution itself changes, and the support (i.e., the set where the probability density is non-zero) also changes. When considering the support change between the training and test distributions, there can be four cases: (i) they exactly match; (ii) the training support is wider (and thus covers the test support); (iii) the test support is wider; (iv) they partially overlap. Existing methods are good at cases (i) and (ii), while cases (iii) and (iv) are more common nowadays but still under-explored. In this paper, we generalize importance weighting (IW), a golden solver for cases (i) and (ii), to a universal solver for all cases. Specifically, we first investigate why IW might fail in cases (iii) and (iv); based on the findings, we propose generalized IW (GIW) that could handle cases (iii) and (iv) and would reduce to IW in cases (i) and (ii). In GIW, the test support is split into an in-training (IT) part and an out-of-training (OOT) part, and the expected risk is decomposed into a weighted classification term over the IT part and a standard classification term over the OOT part, which guarantees the risk consistency of GIW. Then, the implementation of GIW consists of three components: (a) the split of validation data is carried out by the one-class support vector machine, (b) the first term of the empirical risk can be handled by any IW algorithm given training data and IT validation data, and (c) the second term just involves OOT validation data. Experiments demonstrate that GIW is a universal solver for DS problems, outperforming IW methods in cases (iii) and (iv).

Generalizing Importance Weighting to A Universal Solver for Distribution Shift Problems
Tongtong Fang'
Nan Lu
Gang Niu Masashi Sugiyama 3.1
'Te University of Tokyo, Japan
University of Tübingen, Germany
RRIKEN, Japan
Abstract
Distribution shift (DS) may have two levels: the distribution itself changes, and the support (i.e., the set where the probability density is non-zero) also changes. When considering the support change between the training and test distributions, there can be four cases: (i) they exactly match; (ii) the training support wider (and thus covers the test support); (iii) the test support is wider; (iv) they partially overlap. Existing methods are good cases (i) and (ii), while cases (iii) and (iv) are more common nowadays but still under-explored. In this paper, we generalize importance weighting (IW), golden solver for cases (i) and (ii), to universal solver for all cases. Specifically, we first investigate why IW might fail in cases (iii) and (iv); based on the findings, we propose generalized IW (GIW) that could handle cases (iii) and (iv) and would reduce to IW in cases (i) and (ii). In GIW, the test support is split into an in-training (IT) part and an out-of-trainnng (OOT) part, and the expected risk is decomposed into a weighted classification term over the IT part and standard classification term over the OOT part, which guarantees the risk consistency of GIW. Then, the implementation of GIW consists of three components: (a) the split of validation data is carried out by the one-class support vector machine, (b) the first term of the empirical risk can be handled by any IW algorithm given training data and validation data, and (c) the second term just involves OOT validation data. Experiments demonstrate that GIW is universal solver for DS problems, outperforming IW methods in cases (iii) and (iv).
1 Introduction
Deep supervised classification has been successful where the training and test data should come from the same distribution (Goodfellow et al., 2016). When this assumption does not hold in practice, suffer from distribution shift (DS) problems and the learned classifier may often generalize poorly DQuionero-Candel et al., 2009; Pan and Yang, 2009; Sugiyama and Kawanabe, 2012). Let and y be the instance (i.e., input) and class-label (i.e., output) random variables. Then, DS means that the underlying joint density of the training data Per (zr y) differs from that of the test data Pte (z. y).
There are two levels in the DS research. At the first level, only the change of the data distribution is considered. With additional assumptions, DS can be reduced into covariate shift (ar( * (ar). class-prior shift Per (y) # pte (y), class-posterior shift Per (y x) A Pto x) and class-conditional shift Par(ar y) # ( y) (Quionero-Candee et al., 2009). We focus on joint shift Ptr y) * Pre (x:, y). as is the most general and difficult case of DS. At the second level, the change of the support of the data distribution is also considered, where given any joint density p(æ, y), its support defined as the set {(x, y) p(æ,, y) > 03. More specifically, denote by S and Sie the support of Per (x,, y) and (xx y), respectively. When considering the relationship between S.e and Sie. there can be four cases:
(i) Sur and Ste exactly match, i.e., St: = Stei
Correspondence to: GN <gang.niu.ml ml@ @maailmmmalmmm,mm. TF <fang ms. -utoko.oooo.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

train
test
i
train/test
(ii)
(iii)
(iv)
train
test
test
train
Figure 1: An illustration of the relationship between the training support and the test support.
(ii) Sur is wider and covers Ste. i.e., Sur C Ste and Sir Ste * 0:
(iii) See is wider and covers Ste. i.e., Sur C Sie and Ste
Sie 7 0;
(iv) Sur and Ste partially overlap, i.e., Sur N Ste 7 0, Str Ste 7 0, and S.e S + 0.'
The four cases are illustrated in Figure We focus on cases (iii) and (iv), as they are more general and more difficult than cases (i) and (ii).
Problem setting Denote by X and y the input and output domains, where y (1,... C} for C'-laas classification problems. Let f X + TRC be classifier (to be trained) and é: :C² x y - (0, +00) be loss function (for training f).² Then, the risk is defined follows (Vapnik, 1998):
R(f) (x) v)],
where EE|] denotes the expectation. In the joint-shift problems, we are given a training Dir {(a)" ye lid. Pte (at y) and validation set D, {(x) .. "= iid Pte (z, y), where Drr is much bigger than Dr, i... fhr > nly The goal is to reliably estimate the risk from Der and D. and train f by minimizing the empirical risk, which should outperform training f from only D...
Motivation Importance weighting (IW) has been a golden solver for DS problems (Sugiyama and Kawanabe, 2012), and there are many great off- shel IW methods (Huang et al., 2007; Sugiyama et al., 2007a,b; Kanamori et al., 2009). Recently, dynamic IW (DIW) was proposed to make IW compatible with stochastic optimizers and thus it be used for deep learning (Fang et al., 2020). However, all IW methods including DIW have assumed cases (i) and (ii)-in cases (iii) and (iv), IW methods become problematic. Specifically, though they become ill ill-defined on S.e \ S... IW itself is still well-defined. Nevertheless, in such situation, the IW identity will become an inequality (i.e., Theorem 2), which means that what minimize for training is no longer an approximation of the original risk R(f) and thus IW may lead to poor trained classifiers (i.e., Proposition 3). Moreover, some IW-like methods based on bilevel optimization share similar issue with IW (Jiang et al., 2018; 8; Ren et al., 2018; Shu et al., 2019), since f is only trained from D.r where D, is used to determine the importance weights on D..- In fact, cases (iii) and (iv) are more common nowadays due to data-collection biases, but they are still under-explored. For example, class has several subclasses, not all subclasses are presented in Drr (see Figure 2). Therefore, we want to generalize IW to universal solver for all the four cases.
the importance weights
only used on S.,,
Contributions
Our contributions can be summarized as follows.
Firstly, we theoretically and empirically analyze when and why IW methods can succeed/may fail.
We reveal that the objective of IW is good in cases (i) and (ii) and bad in cases (iii) and (iv). Secondly, we propose generalized IW (GIW). In GIW, See is split into an in-training (IT) part S.e n Str and an out-of-training (OOT) part Si Sur. and its objective consists of weighted classification term over the IT part and standard classification term over the OOT part. GIW is justified as its objective is good in all the four cases and reduces IW in cases (i) and (ii). Thus. GIW is strict generalization of IW from the objective point of view, and GIW is safer to be used when we are not sure whether the problem be solved a good case Thirdly, we provide practical implementation of GIW: (a) following the split of Su.. D, is split into an IT set and an OOT set using the one-class support vector machine (Schölkopf et al., 1999);
bad case for IW.
'When Str and Ste differ, they differ by a non-zero probability measure; otherwise, we regard it as case (i). For example, See \ S.. * ( in cases (iii) and (iv) means that Σ, (( Pee (z, f)dæ >> 0.
"The positivity of f, i.e., {(f(x), y) > 0 rather than (x), y) 2 O. is needed to prove Theorem 2. This assumption holds for the popular cross-entropy loss and its robust variants, since f(x) must stay finite.
"Even though we have divided all DS problems into four cases according to support shift (SS), we cannot empirically detect tiny or huge SS (under joint shift). Given that there is already DS, existing two-sample test methods for detecting DS not good at detecting whether there is SS not- their results must be positive.

---

The data
Val-only
IW (DIW)
GIW
Seen
Unseen
10
24
Seen
Unseen
25
52 This is binary classification to distinguish red and blue synthetic data that are uniformly distributed in 2-by-2 grid (consisting of 4 squares different positions). The training distribution (te v) includes only the left 2 squares, the distribution Pte Pte(ae, 2) includes all the squares; there are only 4 validation data, in each square. "Val-only" means using only the validation data to train the model, "DIW" refers proposed method.
24 to
"o 12
14
Fang (2020), and "GIW" IW and GIW perform well, but in the bottom panel. IW completely fails and GIW still perferms well. The performance of Val-only is not validation data. details and discussions about experiment can be found the part Section satisfactory Figure Two concrete examples of the success and failure of IW case (iii).
decision boundaries are plotted compare
metheds. the top panel.
(b) the IT set, instead of the whole Dy, is used for IW; and (c) the OOT set directly joins training together with Dur since no data in D.. comes from the OOT part.
Finally, we design and conduct extensive experiments that demonstrate the effectiveness of GIW in cases (iii) and (iv). The experiment design is also a major contribution since no experimental
setup is available for reference to simulate case (iii) or (iv) on benchmark datasets.
Organization
The analyses IW are in Section the proposal of GIW in Section 3, and the experiments are in Section 4. Related work and additional experiments are in the appendices.
2 A deeper understanding of IW
First, we review the traditional importance weighting (IW) and its modern implementation dynamic importance weighting (DIW). Then, analyze when and why IW methods can succeed/may fail.
(x, review IW Let w (x,y) y) = Pre( y) /trptr(e (a, y). which is the ratio of the test density pte (x, y)
over the training density (x y). known the importance function. Then, the expected objective of IW can be expressed as
(ff Ep. (f.))((f())))...))))))))))))))))
(2)
In order to empirically approximate J(f) in (2), we need to have an empirical version w(x y) of w" (æ, v). so that the empirical objective of IW is*
J( = = II (( w.)
The original IW method is implemented in two steps: (1) weight estimation (WE) where ((x,y) y) is obtained and (II) weighted classification (WC) where J() is minimized. The first step relies on the training data D.. and the validation data D,, and it can be either estimating the two density functions separately and taking their ratio or directly estimating the density ratio (Sugiyama et al., 2012).
As an empirical risk estimator, J(f) in Eq. (3) is not unbiased to J(f) ) in Eq. (2), since w y) is not unbiased to w² (x, v). As far know, in IW, there is no unbiased importance-weite weight estimator and thus no unbiased risk estimator. That being said, J(f) can still be (statistically) consistent with J (f)) under mild conditions if @ is consistent with wf (x. y).

---

A review of DIW The aforementioned two-step approach is very nice when the classifier f is simple model, but it has serious issue when f is deep model (Fang et al., 2020). Since WE not equipped with representation learning, in order to boost its expressive power, we need an external feature extractor such as an internal representation learned by WC. a result, we are trapped by a circular dependency: originally we need w² to train f; now we need trained f to estimate w".
DIW (Fang et al., 2020) has been proposed resolve the critical circular dependency and to make IW usable for deep learning. Specifically, DIW uses a non-linear transformation я created from the current f (being trained) and replaces w"(x, y) with w² u²(2) = Pte (z)/Pt+ (z), where <(2. y) is the current loss-value or hhidden-layer-ouppe
representation of (æ. y). DIW iterates between WE for estimating w* (z) and WC for training f and thus updating π in seamless mini-batch-wing manner. Given that WE enjoys representation learning inside WC, the aeportance-weigeee estimation quality of WE and the classifier training quality of WC can improve each other gradually but significantly.
Risk consistencylinconiisteer tives under different conditions. To this end, we adopt the concepts of risk consistency and classifier consistency from the label-noise learning literature (Xia et al., 2019, 2020; Yao et al., 2020).
of IW Now, consider how to qualify good or bad expected objec-
Definition 1. Given an (expected) objective [f), we say it is risk-consistent if J(f) R(f) fff for any f. i.e., the objective is equal to the original risk for any classifier. On the other hand, we say J(f) is classifier-consistent if arg min JJ) = arg min R(f)) where the minimization is taken over all measurable functions, i.e., the objective shares the optimal classifier with the original risk.
In the definition above, risk consistency is conceptually stronger than classifier consistency. If an objective is risk-consistent, it must also be classifeer-consisten;; if it is classifier-consisten,, it may sometimes be risk-inconsistent. Note that a risk-inconsistent objective is not necessarily very bad, as it can still be consister- Hence, when considering expected objectives, risk consistency is a sufficient condition and classifier consistency is necessary condition for good objectives.
In what follows, analyze when and why the objective of IW, namely J(f) in (2), can be good objective or may be a bad objective.
Theorem 1. In cases (i) and (ii), IW risk-consistent."
Proof. Recall that S., {[xx,)) y) (2, y) > 0} and S.. = {(x, v) : Pto (æ, v) > 0J. Under case (i) or (ii), let us rewrite R(f) and J(f) with summations and integrals:
R(f) Ey=1 J. ((f(x), v) y)dx,
J(f) = ES J(mita))ss.)) ((f(z), y)u (x, y) y)
= =E J.a: (f((r), y) (2. y)dx,
where w" (xx, v) Pro(a, p)rpar (x. y) is always well-defined over Sur and we safely plugged this definition into the rewritten J(f). Subsequently, case (i), S = See and thus J(f) R(f). In case (ii, S.t 2 Ste and then further have
J J(f) = y-1 Eyn [(o:(ew)ES.) ((f(x), y)P (x, y)dx [Ia: (tad:::)ddt.t.....eeee......... e(f(x)) yie (æ, y)
By definition, Pte (I. y) = 0 outside S.e including Su \ Stes and thus J(f) = R(f).
Theorem In cases (iii) and (iv), IW is risk-inconsistent, and it holds that J(f) < R(f) for any f- Proof. Since w* (ax, y) is well-defined over Str but it becomes ill-defined over Swo \ Ser. we cannot naively replace the integral domain in J(f) as in the proof of Theorem 1. In case (iii), Sur C Sto. and consequently
R(f) = Ey ((.W))))) ((f(x), y) (re y)dæ
+ +E Sar (( (z)) (ae y)dx.
'For example, =
= R(f)² minimizing (f)) will give exactly the same optimal
classifier minimizing H(f).
'In fact, if there is only the instance random variable æ but no class-label random variable y. this result is simply the importance make theoretical analyses self contained and make later theoretical results easier to present/understand.
inportance-sumpling sampling identity that can be found in many statistics textbooks. We prove it here to

---

According to Theorem I for case (i), the first term in the rewritten R(f) equals J(f). Moreover, the second term is positive, since ((f())))) y) > due to the positivity of and Pte (Z. y) > 0 over Sue including Sue \ Str. As a result, in case (iii), R(f) > J(f).
Similarly, in case (iv), can split Sie into Ste ntr and See \. Sir and decompose R(f) as
R(F) = Ey S S(sta..))ss.sss.... ((f(x), v) (2. v)da
+ (orite))ssss ( (()(),, P) y)dx.
Note that Ste NSr C Ser. so that according to Theorem 1 for case (ii), the first term equals J()). Following case (ii), the second term is positive. Therefore, in case (iv), R(f) > J(f).
0
Theorem I implies that the objective of IW can be good objective in cases (i) and (i). Theorem 2 implies that the objective of IW may be a bad objective in cases (iii) and (iv). As a consequence, the theorems collectively address when and why IW methods can succeed/may fail.?
When the IW objective may be bad and IW methods may fail, whether an IW method fails or not depends many factors, such as the underlying data distributions, the sampled data sets, the loss, the model, and the optimizer. To illustrate this phenomenon, here we give two concrete examples belonging to case (iii), where IW has no problem at all in one example and is poor as random guessing in the other example.
Two concrete examples We have seen the examples in Figure 2. In both examples, there are two classes marked with red and blue colors and distributed in four squares. Each square has a unit area and is the support of uniform distribution of x, i.e., p(æ, 1) 1 and p(æ, 0) O if its color is red, and (z, 0) = and p(æ, 1) = 0 its color is blue. There a margin of 0.1 between two adjacent squares. The training distribution consists of the two squares on the left, and the test distribution consists of all the four squares. In the first example, on Sie \ Sue. the label is red on the top and blue on the bottom, same the label on Su. In the second example, Sie \ Suz,, the label is blue on the top and red on the bottom, as opposite as the label on S.y.
We experimentally validated whether DIW works or not. The number of training data was 200. The number of validation data was only 4: we sampled one random point from each training square and added the center point of each test-only square. We can see that DIW performs very well in the first example, better than training from only the validation data; unfortunately, DIW performs very poorly in the second example, even worse than training from only the validation data.
The observed phenomenon should not be limited to DIW but be common to all IW methods. Here, we analyze why this phenomenon does not depend on the loss, the model, or the optimizer.
Proposition 3. In the first example, IW is classifir-coosiiten,, while in the second example, IW is incaisiiiiic 8 Proof. Without loss of generality, assume that é is classification
(Bartlett et al., 2006).
Let (c(), .((2) be the center of Ste. and then the four squares are located on the top-left, bottom- left, top-right, and bottom-right of (c()), For convenience, we abbreviate ((x ,(()) for x(1) > >c(1), (2) > cc22) as f(+,+), fxx()) ()) for (1)) > c(0) < c!2) as f(+, -), and so on.
Consider the first example. The minimizer of R(f) can be any Bayes-optimal classifier, i.e., any If such that f(, > 0 and f(.-)) < 0. Next, on the top-left square, we have Pte (x. 1) = 1/4, Pro (z,
(x, 0) = 0, Ptr 1) = 1/2, and Pte xz, 0) O, and thus w' v) 1/2. Likewise, on
the bettom-left square, we have w² "xx y) = 1/2. As a result, J(f) = 2 pp..(1)))) (m. ((f v)), meaning that the minimizer of J(f) can be any Bayes-optimal classifier on S i.e., any I such that f(-.+) 0 and f(-.-) < 0. The simplest manner for ff to transfer its knowledge from Pt, to Pte is to have a linear decision boundary and extend to Sie St,, so that f(.+) > 0 and f(. < < on S... We can see that the set of minimizers is shared and thus IW is classifierconniisentt.
FFor any possible implementation, as long as it honestly implements the objective of IW, the quality of the objective will be reflected in the quality of the implementation.
As the classifier f can only access the information on St: but must predict the class label on the whole See. we assume that f would transfer its knowledge about Pte (1, (æ, y) to Poe y) in the simplest manner. Furthermore, we simplify f f*) into f (1) (2))), since it is binary classification where x E R?.
The cross- coos-yy loss is caabbrraaede and thus classification-aalibee
(Sugiyama et al., 2022).
5

---

Consider the second example. The minimizer of J(f) is still the same while the minimizer of R(f)
significantly changes to any f such that f(-++) > 0, f(--)) O, f(+.+) < 0, and f(+ 0.
This non-linear decision boundary is checkerboard where any two adjacent squares have opposite
predictions. easy to see that IW is blasssfer-inconsistent and its test accuracy is 0.5. For binary
classification with balanced classes, this accuracy is as poor random guessing.
L
3 Generalized importance weighting (GIW)
We have seen two examples where IW is as good/had as possible in case (iii). In practice, we cannot rely on the luck and hope that IW would work. In this section, we propose generalized importance weighting (GIW), which is still IW cases (i) and (ii) and is better than IW in cases (iii) and (iv).
3.1 Expected objective of GIW
The key idea of GIW is to split the test support Ste into the in-training (IT) part Ste O Uir and the out-of-training (OOT) part Ste \ Stt- More specifically, we introduce a third random variable, the support-splittin variable s E {0. 1}, such that takes on Sir and 0 on Sue S As result, the underlying joint density p(x, y, 8) can be defined by Pto (2. y) as
p(x, y. 8) = Pce (x, y)
if (x, y) E Sur and 1, or (x, v) E Ste \ SSu and 0, if (ar, v) E Sür and s 0, or (æ,, y) E Sto \ Srr and 1.
(4)
Let a = p(s 1). Then, the expected objective of GIW is defined as Jf( (mp [w (z.
(f) y) + (1 ()..(=))))))) ((f()))))]
(5)
The corresponding empirical version Je (f) will be derived in the next subsection. Before proceeding to the empirical objective of GIW, we establish risk consistency of GIW.
Theorem 4. GIW is always risk-consistent for distribution shift problems.
Proof. Let us work on the first term of Ja in (5). When (æ, y) E Ser-
oow (ax, y) Ptr (ar, v) = arpto(2 ar v) = p(s 1))(2r y = 1) = p(a, y. 1), where (to y) = p(æ, y 1) given (x. 3) E S., according (4). Since p(x, y, s 1) on Sie Se,, we have
alE a. [w" (z, ()) = Ey (a () ((f(x)) p). y, s= 1)dx.
(6)
Next, for the second term of JG (f), since (1 a)p(p, 8 0) p( y. 0). we have
(1 - a -a ( xx) y) = Σg 2y=1 /1o: (zf(x), 1,), y u)pp(e p(< y. s = 0)dx.
Note that p(x: y, s = 1) + p(= y.s 0) = P (z. y) according to (4). By adding (6) and (7), we can obtain that ff( = R(f). This conclusion holds in all the four cases.
Theorem 4 is the main theorem of this paper. It implies that the objective of GIW can always be a good objective. Recall that IW is also risk-consistent in cases (i) and (ii), and it is interesting to see how IW and GIW are connected. By definition, given fixed Per (x, y) and Pre (x, y), if there exists a risk-consistent objective, it unique. Indeed, in cases (i) and (ii), GIW is reduced to IW, simply due to that a = and (G( = J(ff) for any f.
3.2 Empirical objective and practical implementation of GIW
Approximating (f) in (5) is more involved than approximating J(f) in (2). Following (3), need an empirical version (xx y). and we need further to split the validation data D. into two sets and estimate a. Obviously, how to accurately split the validation data is the most challenging part. After splitting D. and obtaining an estimate a, the empirical objective will have two terms, where
Here, p(æ, y, s) accepts (x, y) E Swa U St. rather than (x, y) E Sie. and actually splits S., U St, into Sir and Ste Str. This is exactly what want, since (re y) outside Stc.

---

Algorithm 1 Generalized importance weighting.
Require:
model fo parameterized by 8:
1:
procedure 2. MODELTRAIN(DLr Dv1, Dv2, ())
training data set Di::
2:
for t = 1 to T do
validation data set Dv;
3:
sample Str of size m from Der sample Syi of size ni from Dv1
batch sizes m, R1, and 722;
4:
number of iterations T
5:
sample S22 of size 122 from Dv2 forward the instances of Str & Sy1 compute the loss values as Lu Lv1 match the distributions of Lu and L
6:
1: procedure 1. VALDATASPLIT(D D.)
2: pretrain fa on Dir
7:
3: forward the instances of Drr & Dr
8:
to obtain an estimated w(x, y)
4: retrieve the transformed Zer & Zv
5:
train O-SVM on Zu g(z)
9:
weight L with the estimated w(x y) forward the instances of Sv2 backward JG (fo). and update 0 end for return the final fo
6:
compute g(2) for every 2 in Zv
7:
partition D, into Dv1 & Dv2
8: estimate â = [Dvil/De
12:
9: return Dvi, Dv2,
10: end procedure
14:
end procedure
the first term can be handled by any IW algorithm given training data and IT validation data, and the second term just involves OOT validation data.
To split D. and estimate o, employ the one-class support vector machine (O-SVM) (Schölkopf et al., 1999). Firstly, we pretrain a deep network for classification on the training data Dir a little bit and obtain a feature extractor from the pretrained deep network. Secondly, we apply the feature extractor on the instances in Drr and train an O-SVM based on the latent representation of these instances, giving
score function g(z) that could predict whether Per Per(a)) > 0 or not, where is the latent representation of æ. Thirdly, we apply the feature extractor on the instances in DD and then employ g(2) to obtain the IT validation data D.1 {ax:² y/ ) )= and the OOT validation data Dv2 = {xx² y1² ) Finally, a can be naturally estimated as Q nw1/nty
We have two comments the split of D.. The O-SVM g(z) predicts whether Pt (x) > 0 or not rather than whether (x. y) > 0 or not. This is because the æ-support change is often sufficiently informative in practice: when the x-suppoot changes, O-SVM can detect it; when the (æz, yu-pupp changes without changing the z-support, it will be very difficult to train an O-SVM based on the loss-value representation of (æ, y) to detect it, but such changes very rare. The other comment is about the choice of the O-SVM. While there are more advanced one-class classification methods (Hido et al., 2011 1; Zaheer et al., 2020; Hu al., 2020; Goldwasser al., 2020) (see Perera al. (2021) for a survey), the O-SVM is already good enough for the purpose (see Appendix C.I).
Subsequently, Dv1 can be viewed being drawn from p 0(z s 1), and Dva be viewed as being drawn from p(x, y s = 0). Based on Pú, and Dv1, we can obtain either ((x, y) or üū for each (a." v/²) by IW. IW has problem here since the split of D. can reduce case (iii) to case (i) and case (iv) to case (ii). In the implementation, we employ DIW (Fang et al., 2020) because is friendly to deep learning and it is state-of-the-arr IW method. Finally, the empirical objective of GIW can be expressed as
Jo(
En o(x)f, (f +,,, ET (((())))))))
Par
where the two expectations in (f) are approximated separately with Dir and Dvz
The practical implementation of GIW is presented in Algorithm 1. Here, we adopt the hidden-layer- output representation for O-SVM in VAL.ATASPPII and the loss-value representation for DIW in
"In GIW, although Jo Jc( = R(f), Fe. is not an unbiased estimator of (J))), exactly the same as what happened in IW. Nevertholess, Je can still he statistically consistent with Ja(f) under mild conditions if @0 a. y) consistent with w² (æt y). Specifically, though the outer weighted classification is an optimization problem, the inner weight estimation is an estimation problem. The statistical consistency of ((# 3) requires zero appreximation error and thus wan-paaamerric estimation is preferred. For kernel-based IW methods such Huang al. (2007) and Kanamori et al. (2009), holds that Rer, nly co, ① y) -> (a. 3) under mild conditions. If so, can establish statistical consistency of Ja(f) with Ja(f). f. If we further assume that the function class of f has bounded complexity and é is bounded and Lipschitz continuous, we can establish statistical consistency of H()) with R(f"), where f(x) and (x) are the minimizers of JG(f) and R(f).
7

---

Table 1: Specification of benchmark datasets, tasks, distribution shifts, and models.
Dataset
Task
Training data
Test data
Model
MNIST
odd and even digits 4 digits (0-3)
10 digits (0-9)*
LeNet-5
Color-MNIST
10 digits
digits in red
digits in red/blue/green
LeNet-5
CIFAR-20
20 superclasses
2 classes per superclass
5 classes per superclass
Re
See LeCun al. (1998) for MNIST and Krizhevsky and I Hinton (2009) for CIFAR 20, Color MNIST modifed from MNIST. The model is modified Leeet-5 (1 LCCn et al,, 1998) or ResNet-18 18 (He al, 2016), Please find in Appendix B.I the details. *All sctups in the table are for (ili); for MNIST in (iv), the test data consist digits (2-9).
MNIST, case (iii)
MNIST, case (iv)
Color-MNIST, case (iii)
CIFAR-20, case (iii)
2000
1.00
10
0.5
/W- like
5.85
0.7
0.80
0.00
06
5.75
Ualerty
R-DW)
0.775
8.5
0.70
Pectra vol
DNV
A 0.72
0.4
Beoreight
GNV
2.80
Hii hot
Est 250
0.82
0.2
1.0
Epoch
Eseih
Epoch
Eloch
1.00
1.0
2.5
0.05
0.0
0.6
0.0
3.8
0.7
DA
varly
DAM
0.73
Tost
Pretraitrool
0.72
0.4
0.55
0.5
130 200 250 202 150 602
200 150 203
250
0.0
202 150 250
250
50 120 150 200 500 292 400
tpech
Eooch
Epecs
Epech
Figure 3: Comparisons with IW-like and DA baselines under support shift (5 trails).
MODELTRAIN, This algorithm design is convenient for both O-SVM and DIW; the hidden-layer- output representation for DIW has been tried and can be found in Section 4.3.
4 Experiments
In this section, we empirically evaluate GIW and compare it with baseline methods." 12 To see how effective it is in cases (iii) and (iv), we designed two distribution shift (DS) patterns. In the first pattern, DS comes solely from the mismatch between the training and test supports, and we call it support shift (SS). Under SS, it holds that w" (æz, y) equals a in case (iii) and 0 or another constant in case (iv), simply due to renormalization after imposing SS. Hence, the challenge is to accurately split D.,. In the second pattern. there is some genuine DS (e.g., label noise or class- Mliss-prior shift) on top of SS, and we call it support- distrrt-dittiiuttio shift. Since w" (ar, y) is no longer constant, we face the challenge to accurately estimate w² (xr, y). Additionally, we conducted an ablation study to better understand the behavior of GIW. Detailed setups and more results are given in Appendices B & C.
The baseline methods involved in our experiments are as follows.
Val-only: using only D. to train the model from scratch. Pretrain-val: first pretraining on D.. and then training on Dy.
Reweight: learning to reweight examples (Ren et al., 2018).
MW-Net: meta-weight-net (Shu al., 2019), a parametric version of Reweight.
DIW: dynamic importance weighting (Fang et al., 2020).
R-DIW: DIW where IW is done with relative density-ratio estimation (Yamada al., 2011).
CCSA: classification and contrastive semantic aligmment (Motian et al., 2017).
DANN: domain-adversarial neural network (Ganin et al., 2016).
4.1 Experiments under support shift
We first conducted experiments under support shift on benchmark datasets. The setups summarized in Table I. For MNIST, our task was to classify odd and even digits, where the training set has only 4 digits (0-3), while the test set has 10 digits (0-9) in case (iii) and 8 digits (2-9) in case (iv). For Color-MNIST, our task was to classify 10 digits; the dataset was modified from MNIST in such a way that the digits in the training set are colored in red while the digits in the test/validation set are colored
12 Our implementation of GIW is available at https: / /ttgtttttuub...eeg hwtp://///ccooooooooo////////AA
8

---

Val-only Figure 4: Visualizations of the learned convolution kernels on Color-MNIST under support shift.
DIW
Pretrain-val
GIW
Label noise 0.2
Label noise 0.4
Class-prior' shift 10
Class-prior shift 100
2.00
1.07
1.00
1.00
3.93
0.03
0.85
0.25
2220
0..00
MNIST
0.80
0.00
5.75
Valordy
R.DWY
2 0.77
0.75
0.70
Fretre
DIt
0.70
0.70
0.70
2.9
Beoreight
GIV
0.55
0.65
52
102 150 220 250
300 202 402
100
150
213
250
300
100
150 300
250 300 350 400
Epoch
Eac-hh
Epoch
Epach
Color-MNIST
3.3.
20.0
0.7
0.7
0.7
0.7
0.
0.5
0.5
22.
30
200
150
200
250 507 150 400
0.2
50
100
152
200
251
200 350
400
0.2
35
202
150
278
290
500
330
400
04.
50
170
150
220
250
500
392 400
3.6
0.6
0.6
0.6
CIFAR-20
Tot AcuuEsy
Teot Bccuray
3.4
0.4
0.2
23.
0.1
010
Tpoch
tooch
Epecs
Epoch
Figure Comparisons with IW-like baselines under support-distribution shift (5 trails).
red/green/blue evenly. For CIFAR-100, our task was to classify the 20 predefined superclasses and thus we call it CIFAR-20 20; the training set contains data from 2 out of the 5 classes for each superclass while the test set contains all classes, For validation set, we sampled 2 data points per test digit for MNIST and Color-MNIST and 10 data points per class for CIFAR-100.
Figure 3 shows the results on MNIST, ColoT-MNIST, and CIFAR-20 under support ! where GIW generally outperforms IW-like and domain adaptation (DA) baselines. We also confirmed that a in (5) is accurately estimated in Appendix C.I. To further investigate how GIW works, we visualized the learned convolution kernels (i.e., weights) for Color-MNIST experiments in Figure 4, where the more observed color represents the larger weights learned that color channel. Only GIW recovers the weights of all color channels while learning useful features, however, other methods fail to do so.
4.2 Experiments under support-distribution shift
We further imposed additional distribution shift, i.e., adding label noise or class-prior shift, on top of the support shift following the same setup in Table 1. Here only show the results in case (iii) and defer the results in case (iv) to Appendix C.4 due to the space limitation.
Label-noise experiments In addition to the support shift, we imposed label noise by randomly flipping a label to other classes with an equal probability, i.c., the noise rate. The noise rates are set as {0.2, 0.4] and the corresponding experimental results are shown in Figure 5 and 6. We can see that compared with baselines, GIW performs better and tends to be robust to noisy labels.
Class-prior-shiff experiments On top of the support shift, we imposed class-prior shift by reducing the number of training data half of the classes to make them minority classes (as opposed to majority classes). The sample size ratio per class between the majority and minority classes is defined as A. chosen from (10, 100). To fully use the data from the minority class, we did not split the validation data in class-prior-shiff experiments and used all validation data in optimizing the two
Itt is difficult to have the same number of mini batches per epoch for the training and validation data. To this end, adopt the definition of an epoch single loop over the training data, not the validation data.

---

Label noise 0.2
Label noise 0.4
Class-prior shift 10
Class-prior shift 100
MNIST
0.7
0.7
0.7
0.7
0.5
0.5
100 30
200
250 592 250 403
50
100
150
200
251
100
330
400
30
202
150
278
290
500 330 400
50
120
150
220
250
500
251
400
1.0
1.0
1.0
1.5
Color- -MNIST
0.9
0.90
0.5
2.5
0.5
05
0.4
0.44
0.4
0.4
22.
0.2
0.0
0.2
tpech
Epoch
Epecs
Epoch
CIFAR 20
3.5
0.5
Tot Acourac
Tort Accurac
2.5
916
50
100
150
200
250
303
350 402
0.1
53
100
153
200
252
700
350
400
52
302
150
236
250
300
350
403
50
130
150
200
253 300 252 100
1poch
Epech
Figure 6: Comparisons with DA basclines under support- shift (5 trails).
3.50
1.00
1.00
1.05
3.85
0.05
0.03
2.50
9.0
0.80
0.80
Valerry
DIV
FI
OoT
0.80
0.00
0.83
DAV
GIW
2.00
0.3
0.00
10k
12.54
13%
13.54
23k
0.60
20
20
40
20
0.52
50
150 150 220
250 300 292 400 Fpech
Mioo rale
Nummer training date
Number vnlidttionn data
(a) Validation split error
(b) Training data size
(c) Validation data size
(d) -F/-L representation
Figure 7: Impact of different validation data splits, sample sizes, and data representations.
terms in (8). In Figure 5 and 6, we can see that GIW consistently performs better than the baselines. Note that though domain adaptation (DA) baselines (i.e., CCSA & DANN) may achieve comparable performance to GIW under the support shift in Figure 3, their effectiveness declines significantly when confronting additional distribution shifts (e.g., label noise or class class-prior shift) in Figure 6.
4.3 Ablation study
Finally, we performed an ablation study on MNIST under 0.2 label noise. Figure 7(a) and Table 2 in Appendix C.2 present the negative impact of validation data split errors by randomly flipping the IT/OOT data into the OOT/IT part. We can see that GIW is reasonably robust to split errors, and flipping OOT to IT is more problematic than the other direction since it makes the empirical risk estimator of GIW more similar to that of the standard IW. In Figure 7(b), the performance of all methods remains consistent across different values of The E {10000, 12500, 15000, 17500, 20000). In Figure 7(c), GIW performs better with more validation data, e.g., when n. increases from 10 to 20. Moreover, we compare the loss-value (-L) with the hidden loutoo---yy--ouuputtt (-F) representation of data used in the DIW and GIW methods. Figure 7(d) shows GIW-L outperforms others.
5 Conclusions
We characterized distribution shift into four cases according to support shift to gain deeper under- standing of IW. Consequently, we found that IW provably good in two cases but provably poor in the other two cases. Then, we proposed GIW which is a strict generalization of IW and is provably favorable in all the four cases. GIW safer to used in practice as it is difficult to know in which case the problem to be solved is. That said, there are still some potential limitations and thus future directions to work on: GIW requires exactly test-distributed validation data, which is restrictive; requires not very small validation data, which is demanding: small amount of OOT validation data joins training directly and is used for validation simultaneously, which might lead to imperceptible overfitting as well as overoptimism about the OOT part of the test support.
10

---

Acknowledgments and Disclosure of Funding
TF was supported by JSPS KAKENHI Grant Number 23KJ0438 and the Institute for Al and Beyond, UTokyo. NL was funded by the Deutsche Forschungsgemeinschafff (DFG, German Research Founda- tion) under Germany's 's Excellence Strategy EXC number 2064/1 Project number 390727645. MS was supported by the Institute for Al and Beyond, UTokyo.
References
P. L. Bartlett, M. 1. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473): 2006.
S. Ben-David J. Blitzer, K. Crammer, and F. Pereira. Analysis of representations for domain adaptation. In NewrlPS, 2006.
J. Duchi, P. Glynn, and H. Namkoong. Statistics of robust optimization: A generalized empirical likelihood approach. arXiv preprint arXiv: 2016.
Fang. N. Lu, Niu, and M. Sugiyama. Rethinking importance weighting for deep learning under distribution shift. In NeurlPS, 2020.
Ganin, E. Ustinova, H. Ajakan, P. Germain, Larochelle, Laviolette, M. March, and Lempitsky. Domain-adversarial training of neural networks. Journal of Machine Learning Research, 17(59)11-35, 2016.
Goldwasser, A. Kalai, Y. Kalai, and O. Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. In NeurlPS, 2020.
M. Gong, Zhang, T. Liu, D. Tao, C. Glymour, and B. Schölkopf. Domain adaptation with conditional transferable components. In ICML, 2016.
I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. The MIT Press, 2016.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR, 2016.
Hido, Y. Tsuboi, H. Kashima, M. Sugiyama, and T. Kanamori. Statistical outlier detection using direct density ratio estimation. Knowledge and information systems, 26:309-336, 2011.
W. Hu, M. Wang, Q Qin, Ma, and B. Liu. Hrn: A holistic approach one class learning. In NeurIPS, 2020.
J. Huang, A. Gretton, K. Borgwardt, B. Schölkopf, and A. Smola. Correcting sample selection bias by unlabeled data. NeurlPS, 2007.
S. Loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. ICML, 2015.
L. Jiang, Z. Zhou, T. Leung, L.-J. Li, and L. Fei-Fei. Mentornet: Learning data-driven curriculum for very deep neural networks corrupted labels. In JCML, 2018.
T. Kanamori, S. Hido, and M. Sugiyama. A least-squares approach to direct importance estimation. Journal of Machine Learning Research, 1017):1391-1445, 2009.
D. P. Kingma and J. L. Ba. Adam: A method for stochastic optimization. In ICLR. 2015.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
LeCun, L. Bottou, Y. Bengio, Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--224, 1998.
Motiaan, Piccirilli, generalization. In ICCV, 2017.
Adjeroh, G. Doretto. Unified deep supervised domain adaptation and
Pan and Yang. A survey transfer learning. IEEE Transactions on Knowledge and Data Engineering, 22 (10):1345-1399, 2009. 2009.
Perera, P. Oza, and V. M. Patel. One-class classification: survey. arXiv preprint arXiv:2101.0300 2021.
J. Quionero Candela, M. Sugiyama, A. Schwaighofer, and N. Lawrence. Dataset shift in machine learning. The MIT Press, 2009.

---

M. Ren, W. Zeng, B. Yang, and R. Urtasun. Learning to reweight examples for robust deep learning. In ICML, 2018.
K. Saito, Y. Ushiku, and T. Harada. Asymmetric tri-training for unsupervised domain adaptation. In ICML,, 2017.
B. Schölkopf, R. C. Williamson, A. Smola, J. Shawe-Taylor, and J. Platt. Support vector method for novelty detection. In NeurlPS, 1999.
J. Shu, Q. Xie, L. Yi, Q. Zhao, S. Zhou, Z. Xu, and D. Meng. weta-weight-net: Learning explicit mapping for sample weighting. In NeurlPS, 2019.
M. Sugiyama and M. Kawanabe. Machine learning in non-stationary environments: Introduction covariate shift adaptation. The MIT Press, 2012.
M. Sugiyama, M. Krauledat, and K. Müller. Covariate shift adaptation by importance weighted cross validation. Journal Machine Learning Research, 8(5):985-1005, 2007a.
M. Sugiyama, S. Nakajima, H. Kashima, P. Buenau, and M. Kawanahe. Direct importance estimation with model selection and its application covariate shift adaptation. In NewrIPS, 2007b.
M. Sugiyama, T. Suzuki, and T. Kanamori. Density ratio estimation in machine learning. Cambridge University Press, 2012.
M. Sugiyama, H. Bao, T. Ishida, N. Lu, T. Sakai, and G. Niu. Machine learning from weak supervision: An empirical risk minimization approach. The MIT Press, 2022.
V.N. Vapnik. Statistical learning theory. John Wiley & Sons, 1998.
X. Xia, T. Liu, N. Wang, B. Han, C. Gong, G. Niu, and M. Sugiyama. Are anchor points rcally indispensable in label-noise lcarning? In NeurlPS, 2019.
X. Xia. T. Liu, B. Han, N. Wang, M. Gong, H. Liu, G. Niu. D. Tao, and M. Sugiyama. Part-dependent label noise: Towards detende-de label noise. In NeurlPS, 2020.
M. Yamada, T. Suzuki, T. Kanamori, H. Hachiya, and M. Sugiyama. Relative density-ratio estimation for robust distribution comparison. In NeurlPS, 2011.
Y. Yao. T. Liu, B. Han, M. Gong, J. Deng, G. Niu, and M. Sugiyama. Dual T: Reducing estimation error for transition matrix in label-noise learning. In NewrlPS, 2020.
M. Z. Zaheer, J. Lee, M. Astrid, and S.-L Lee. Old is gold: Redefining the adversarially learned one-class classifier training paradigm. In CVPR, 2020.
12

---

Supplementary Material
A
Related work
In this section, we discuss relevant prior studies for addressing distribution shift problems, including importance weighting (IW), IW-like methods, and domain adaptation (DA).
Importance weighting (IW) IW has been a powerful tool for mitigating the influence of distribution shifts. The general idea is first to estimate the importance, which is the test over training density ratio, and then train a classifier by weighting the training losses according to the importance. Numerous IW methods have been developed in this manner, utilizing different techniques for importance estimation.
The kernel mean matching (KMM) approach (Huang et al., 2007) learns the importance function by matching the distributions of training and test data in terms of the maximum mean discrepancy in a reproducing kernel Hilbert space, while the Kullback- Leibber importance estimation proce- dure (KLIEP) (Sugiyama et al., 2007b) employs the KI. divergence for density fitting and the least-squares importance fitting (LSIF) (Kanamori et al., 2009) employs squared loss for importance fitting. The unconstrained LSIF (uLSIF) (Kanamori et al., 2009) is an approximation version of LSIF that removes the non negaaiviy constraint in optimization, allowing for more efficient computation. To boost the performance of such traditional IW methods, dynamic importance weighting (DIW) (Fang et al., 2020) is recently proposed to make them compatible with stochastic optimizers, thereby facilitating their effective integration with deep learning frameworks.
However, in order to establish a well-defined notion of importance, all IW methods including DIW assume cases (i) and (ii), while they become problematic in cases (iii) and (iv).
IW-like methods A relevant IW invariant is the relative unconstrained least-squares importance fitting (RuLSIF) (Yamada et al., 2011), which considers a smoothed and bounded extension of the importance. Instead of estimating the importance w" (ax, y) Pto (t, v)/ptr(a: y). they estimate the v--relative importance w (at, y) = (to(ar,)) (NPto( (x. y) + (1 - n)Prr (at, y)) where 0 < 7 S 1. While the relative importance is well-defined in cases (iii) and (iv), experiments have demonstrated that it is inferior to GIW, since its training does not incorporate any out-of-training (OOT) data.
Moreover, some reweighting approaches based bilevel optimization look like DIW in the sense of iterative training between weighted classification on the training data for learning the classifier and weight estimation with the help of small set of validation data for learning the weights (Jiang et al., 2018; Ren et al., 2018; Shu et al., 2019). However, they encounter a similar issue as IW and RuLSIF, where validation data is solely used for learning the weights, while the training data (without any OOT data) is used for training the classifier. This makes them hard to handle the cases (iii) and (iv).
Domain adaptation (DA) DA relates to DS problems where the (t. y) and the Ptr(ax y) are usually named as target and source domain distributions (Ben- al., 2006), or in-domain and out-of-domanl distributions (Duchi et al., 2016). It can be categorized into supervised DA (SDA) or unsupervised DA (UDA): the former has labeled test data while the latter has unlabeled test data. The setting of SDA is similar as that of GIW. One representative SDA work is classification and contrustive semantic alignment (CCSA) (Motiian et al., 2017) method. CCSA, a contrastive semantic alignment loss is added to the classification loss, for minimizing the distances between the samples that come from the same class and maximizing the distances between samples from different classes. In DA research, UDA is more popular than SDA. Based on different assumptions, UDA involves learning nomain-invariant (Ganin et al., 2016) or conditional domain-invariant features (Gong et al., 2016), or giving pseudo labels to the target domain data (Saito et al., 2017).
Note that DA can refer to either certain problem settings or the corresponding learning methods (or both). When regarding it as problem settings, SDA is exactly the same as joint shift and UDA is fairly similar to covariate shift, which assumes p(y) az) doesn't change too much between the training and test domain. When regarding it as learning methods, the philosophy of both SDA and UDA is to find good representations to link the source and target domains and transfer knowledge from the source domain to the target domain, which is totally different from the philosophy of IW.
13

---

Label:
Label:
Label: 1
Label: 1
Label: 2
Label: 0
Label:
Label:
Label:
Label: 2
2
Label: 2
Label: 3
Label: 3
Label: 4
Label: 4
Label: 2
Label: 3
Label:
Label: 4
Label: 4
2
3
4
4
2
3
4
Label:
Label:
Label: 6
Label: 6
Label: 7 5
Label: 5
Label: 5
Label:
Label: 6
Label: 7
S
6
5
6
6
7
Label:
Label:
Label:
Label: 9
Label: 9
Label:
Label:
Label:
Label:
Label:
7
g
g
9
9
7
8
8
9
9
Validation data Figure 8: A plot of the training data and validation data ColOT-MNIST dataset.
Training data
B
Supplementary information experimental setup
In this section, present supplementary information the experimental setup. All experiments were implemented using PyTorch 1.13. and carried out on NVIDIA Tesla V100 15
B.1 Datasets and base models
MNIST MNIST (LeCun al., 1998) is 28*28 grayscale image dataset for 10 hand-written digits (0-9). The original dataset includes 60,000 training data and 10,000 test data. See http: //yann. lecun. com/ exdb/ exdb/mnist/ for more details.
In the experiments, we converted it for binary classification to classify even/odd digits as follows:
Class O: digits '0', '2', '4', '6', and '8;; Class digits '1', '3', '5', '7', and '9'.
In our setup, the training data only included 4 digits (0-4). The test data could access all digits (0-9) in case (iii) and digits (2-9) in case (iv). Since the number of training data was reduced, we added two data augmentations to the training and validation data: random rotation with degree 10 and random affine transformation with degree 10. translate of (0.1, 0.1) and scale of (0.9, 1.1). Note that the data augmentations were only added during procedure 2 MODELTRAIN in Algorithm 1.
Accordingly, modified LeNet-5 (LeeCun et al., 1998) the base model for MNIST:
Oth (input) layer: (32*32)-
1tt layer: C(5*5,6)-8(2*7)
2nd layer: C(5+5,16)-S(2*2))
3rd layer: FC(120)-
4th to 5th layer: FC(84)-2,
where C(5*5,6) represents 5*5 convolutional layer with 6 output channels followed by ReLU, S(2*2) represents max-pooling layer with a filter of size 2*2, and FC(120) represents fully connected layer with 120 outputs followed by ReLU, etc. The hidden-layer-ouupnn representation of data used the implementation was the normalized output extracted from the 3rd layer.
Color-MNIST Color-MNIST was modified from MNIST for 10 hand-written digit classification, where the digits in training data were colored in red and the digits in test/validation data were colored either red, green blue evenly. See Figure 8 for plot of the training data and validation data. We did not add any data augmentation for experiments on Color-MNIST.
14 "nttpa://pytorda 15 hhttps: /tttps:://ww nvidia. com/ ee///enuuuua an-us//ae data- dat.aaaaaetteeeo10o////
14

---

To process RGB imput data, we modified LeNet-5 as the base model for Color-MNIST:
Oth (input) layer: (32*32"3)-
st layer: -()+5,20)-((++2)
2nd layer: C(5+5,50)-S(2+2)
3rd layer: FC(120)-
4th to 5th layer: FC(84)-10,
where the abbreviations and the way of extracting the hidden-layer-output representation of data were the same as that in MNIST.
CIFAR-20 CIFAR- (Krizhevsky and Hinton, 2009) a 32*32 colored image dataset in 100 classes, grouped in 20 superclasses. It contains 50,000 training data and 10,000 test data. We call this dataset CIFAR-20 since we use for 20-supess classification and classes shown below, where each superclass includes five distinct classes. See https: / //www.cc cs toronto........................t sduu/Krizz cifar html for more details.
predefined superclasses
Superclass
Class
aquatic mammals
(beaver, dolphin), otter, seal, whale (aquarium fish, flatfish), ray, shark, trout (orchids, poppies), roses, sunflowers, tulips (bottles, bowls), cans, cups, plates (apples, mushrooms), oranges, pears, sweet peppers (clock, computer keyboard), lamp, telephone, television (bed, chair), couch, table, wardrobe (bee, beetle), butterfly, caterpillar, cockroach (bear, leopard), lion, tiger, wolf (bridge, castle), house, road, skyscraper (cloud, forest), mountain, plain, sea (camel, cattle), chimpanzee, elephant, kangaroo (fox, porcupine), possum, raccoon, skunk (crab, lobster), smail, spider, worm (baby, boy), girl, man, woman (crocodile, dinosaur), lizard, snake, turtle (hamster, mouse), rabbit, shrew, squirrel (maple, oak), palm, pine, willow (bicycle, bus), motorcycle, pickup truck, train (lawn-mower, rocket), streetcar, tank, tractor
fish
flowers
food containers
fruit and vegetables
household electrical devices household furniture
insects
large carnivores
large man-made outdoor things large natural outdoor scenes large omnivores and herbivores medium-sized mammals
non-insect invertebrates
people
reptiles
small mammals
trees
vehicles
vehicles
In setup, the training data only included the data in 2 out of the 5 classes per superclass, i.c., the classes in () were seen by the training data as shown above. The test data included the data in all classes. Since the number of training data was reduced, we added several data augmentations to the training and validation data: random horizontal flip, random vertical flip, random rotation of degree 10 and random crop of size 32 with padding 4. Same that in MNIST experiments, the data augmentations were only added during procedure 2 MODELTRAIN in Algorithm 1.
As for the base model for CIFAR-20, we adopted ResNet-18 18 (He et al., 2016) follows:
Oth (input) layer: (32*32*3)-
1st to 5th layers: C(3#3, 64)-(C(3*3, 64), C(3*3, 64)]
6th 9th layers: [C(3*3, 128), C(3*3, 128)]*2-
10th to 13th layers: [C(3*3, 256), C(3*3, 25
14th 17th layers: [C(3*3, 512), C(3*3, 5-
18th layer: Global Average Pooling-200
where [ denotes a building block (He al., 2016) and [-]22 means 2 such blocks, etc. Batch
normalization (loffe and Szegedy, 2015) was applied after convolutional layers. The hidden-layer- output representation of data was the normalized output after pooling operation the 18th layer.
B.2 Experiments under support shift
For compared methods except Val-only, we pre-trained the model 10 epochs as the initial- ization. For the one-class support vector machine (O-SVM) (Schölkopf et al., 1999), we adopted
15

---

the implementation from scikit-learn', 16 where the radial basis function (RBF) kernel was used: k(x,, v3)) = e 7||=;=,,1| with y 10000. All other hyperparameters about O-SVM were set the default. For the distribution matching by dynamic importance weighting (DIW) (Fang et al., 2020), again used the RBF kernel where y was the median distance between the training data. And used K + wI as the kernel matrix K, where I was an identity matrix and w was set to be 1e-05. The upper bound of weights was set as 50.
In experiments under support shift, Adam (Kingma and Ba, 2015) was used as the optimizer, the learning rate was 0.0005, decaying every 100 epochs by multiplying factor of 0.1, and the batch size was set as 256. For MNIST, Color-MNIST, and CIFAR-20 experiments, the weight decay was set as 0.005, 0.002, and 0.0001, respectively.
B.3 Experiments under support-distributioo shift
For experiments under support-distribttion shift, all the setups and hyperparameters about the initialization, O-SVM, and distribution matching by DIW were the same as that in Section B.2. Moreover, the same that Adam was used as the optimizer, the learning rate was 0.0005, decaying every 100 epochs by multiplying factor of 0.1, and the batch size was set as 256. Next we show the setups and hyperparameters specific to the support- distribbiit shift.
Label-noiss experiments On top the support shift Section B.2, we added a symmetric label noise the training data, where a label may flip to all other classes with an equal probability (this probability was defined as the noise rate, set as {0.2, 0.43). The type of label noise and the noise rate were unknown to the model. For MNIST, Color-MNIST, and CIFAR-20 experiments, the weight decay was set as 0.005, 0.002, and 0.008, respectively.
Class-prior shift experiments We induced class-prior shift in the training data by randomly sampling half of the classes minority classes (other classes were the majority classes) and reducing the number of samples in minority classes. The sample size ratio per class between the majority and minority classes was p. chosen from {10, 100}. The randomly selected minority classes in class-prior shift experiments were shown as follows:
MNIST: class of odd digits;
Color-MNIST: digits '1', '2', '7' and '8':
CIFAR-20: superclasses of 'fish', 'fruit and vegetables', "household electrical device", 'household furniture', 'large carnivores', 'large omnivores and herbivores', imedium-sized mammals', 'people", 'small mammals', and 'vehicles l'.
For MNIST, COIST,MNIST, and CIFAR-22 20 experiments, the weight decay was set as 0.005, 1e-05, and lc-07, respectively. Since we did not split the validation data in class fass-priorr shift experiments, set the a in (5) as 0.5 for class-prior shift experiments on all datasets.
C Supplementary experimental results
In this section, we present supplementary experimental results, including the histogram plots of the learned O-SVM score, more ablation study results on the validation data split error, visualizations of convolution kernels for all methods under label noise, additional experimental results for case (iv). and the summary of classification accuracy.
C.1 On the learned O-SVM score
Figure 9 shows the histogram plots of the learned O-SVM score MNIST, ColoT-MNIST, and CIFAR-20 under support shift. From the histogram plots, we observe that the score distribution consists of two peaks without overlapping; therefore, any value between the two peaks (e.g., 0.4) could be made as a threshold to split the validation data into two parts. If the score of validation data higher than the threshold, then the data is identified as (in-training) IT validation data; otherwise, it is an (out-of-training)) OOT validation data.
16 hnttps://sccitt Learn. http://///aaeeeeottleeeee///enee
saaararrneeeeeeeeeneeaaaaaa OneClassSVA html
16

---

400
330
130
(a) MNIST
(b) Color-MNIST
(c) CIFAR-20
Figure 9: Histogram plots of the learned O-SVM score under support shift.
Table 2: Mean accuracy (standard deviation) in percentage MNIST the last epochs under support shift with label noise (5 trials). OOT/IT is short for out-oof-rainingiinntaanne data. OOT IT means OOT data flips IT data and vice versa. LN is short for label noise. Flip rate is the percentage of OOT/IT data that randomly flipped to IT/OOT data.
OOT IT
OOT
Flip rate
IN 0.2
L.4.44
0.2
IN 0.4
0
94.60 (0.22)
93.74 (0.53)
94.60 (0.22)
93.74 (0.53)
0.1
94.54 (0.31)
94.04 (0.54)
94.76 (0.33)
93.66 (0.44)
0.3
92.09 (0.99)
92.38 (1.14)
94.62 (0.26)
92.78 (0.90)
0.5
88.98 (1.73)
88.83 (2.26)
94.03 (0.64)
92.25 (1.36)
0.7
86.76 (1.28)
85.94 (2.14)
93.55 (0.82)
90.53 (1.22)
After splitting the validation data, a in (5) is estimated as the ratio of the sample size between the IT validation data and the whole validation data, i.e., ā Mw1/Bly For example, in Figure 9(),, ā = 8+12 0.4, which is equal to the true value in MNIST experiments. Similarly, it can be verified that the a in Figure 9(b) and 9(c) are also accurately estimated.
8
C.2 Additional results on the validation data split error
As mentioned in the main paper in Figure 7(a), generally GIW is quite robust to split errors and OOT-+IT is more problematic than the other direction. Here we present additional results on MNIST under 0.4 label noise in Table 2. We further observe that as the label noise increases from 0.2 to 0.4, OO- is more susceptible to such negative impacts than the other direction.
C.3 Visualizations of convolution kernels under label noise
Then, we visualized the learned convolution kernels for all methods Color-MNIST under 0.2 label noise. From Figure 10, we can see that the results aligned with the discussions about Figure Previous IW IW-like methods (i.e., DIW, R-DIW, Reweight and MW-Net), DA methods (i.e., CCSA and DANN), and Pretrain- val learned most weights on the red channel, which may cause the failure the test data with green/blue color. Although Val-only had weights all color channels, may fail to learn useful data representation due to its limited training data. Only GIW could successfully recover the weights all color channels while capturing the data representation.
C.4 Additional experimental results for case (iv)
Here we present the results on MNIST in case (iv) under distribution-support shift, comparing with IW-like and domain adaptation (DA) baselines. From Figure 11, we can see that GIW outperforms other methods by large margin in case (iv) under both label-noise and class-prior-shie shift settings.
C.5 Summary of classification accuracy
Table 3 and 4 present the mean accuracy (standard deviation) in percentage on MNIST, Color-MNIST: and CIFAR-22 over the last ten epochs under support shift, comparing with IW-like methods and domain adaptation (DA) methods respectively, corresponding to Figure 3. Table 5 and 6 present such results under dusport-iistriuution shift, corresponding Figure 5 and Table and shows the summary of results in case (iv) on MNIST, corresponding to Figure 11.
17

---

Reweight
MW-Net
R-DIW
DIW
Val-only
Pretrain-val
GIW Figure 10: Visualizations of the learned convolution kernels Color-MNIST under 0.2 label noise.
CCSA
DANN
Label noise 0.2
Label noise 0.4
Class-prio shift 10
Class-prior shift 100
1.0
IW like
0.30
0.05
335
2.80
0.80
8.00
3.30
5.75
Vaierdl
2.90
Beaneight ght
GTV
8.55
0.85
3.60
330
0.62
52
233
134
Ex0
132
05
433
2.0
1.0
1.0
3.0
DA
Winnnl
DANK GIM
Prctroin val
Spuch
Epoch
Epoch
Esoch
Figure 11: Results on MNIST in case (iv) under distribution-support shift (5 trails).
18

---

Table 3: Mean accuracy (standard deviation) in percentage on MNIST, Color-MNIST, and 21 over the last ten epochs under support shift in case (iii) with IW-like baselines (5 trials). Best and comparable methods (paired r-test at significance level 5%) are highlighted in bold. This result corresponds to the top row in Figure 3.
Data
Case
Val-oniy
Pretrain-val
Reweight
MW-Net
R-DIW
DIW
GIW
MNIST
(ii)
78.94 (0.99)
88.31 (1.02)
82.03 (0.13)
82.17 (0.32)
81.73 (0.42)
80.53 (1.23)
95.16 (0.20)
MNIST
(i)
79.86 (0.26)
86.25 (0.95)
71.78 (0.91)
76.73 (0.63)
77.11 (0.63)
75.11 (1.43)
90.94 (0.91)
Color-MNIST
(ii)
31.19 (0.65)
80:40 (3.62)
(1.03)
39.26 (0.01)
39.28 (0.03)
39.50 (0.18)
93.87 (0.19)
CIFAR-20
(i))
28.61 (0.66)
42.79 (0:41)
56.17 (0.29)
57.90 (0.18)
58.02 (0.35)
55.78 (0.34)
59.73 (0.47)
Table 4: Mean accuracy (standard deviation) in percentage on MNIST, Color-MNIST, and CIFAR-20
over the last ten epochs under support shift in case (iii) with DA baselines (5 trials). Best and comparable methods (paired /-test at significance level 5%) are highlighted in bold. This result corresponds to the bottom row in Figure 3.
Data
Case
Val-only
Pretrain-val
CCSA
DANN
GIW
MNIST
(ii)
78.94 (0.99)
88.31 (1.02)
94.37 (0.46)
87.24 (1.58)
95.16 (0.20)
MNIST
(v)
79.86 (0.26)
86.25 (0.95)
88.76 (0.86)
82.92 (1.89)
90.94 (0.91)
Color- MNIST
(i0)
31.19 (0.65)
80.40 (3.62)
80.13 (5.90)
64.34 (5.08)
93.87 (0.19)
CIFAR-20 20
(ii)
28.61 (0.66)
42.79 (0.41)
60.87 (0.39)
58.12 (0.44)
59.73 (0.47)
Table 5: Mean accuracy (standard deviation) in percentage on MNIST, Color-MNIST (C-MNIST), and shift in case (iii) with IW-like baselines (5 trials). Best and comparable methods (paired r-test at significance level 5%) are highlighted in bold. LN/CS is short for label noise/class prioor shift. This result corresponds to Figure 5.
CIFAR-20 over the last ten epochs under support-distributin
Data
Shift
Val-only
Pretrain-val
Reweight
MW-Net
R-DIW
DIW
GIW
MNIST
LN 0.2
78.94 (0.99)
86.34 (0.77)
89.28 (0.64)
82.29 (0.80)
82.70 (0.76)
80.12 (2.90)
94.60 (0.22)
LN 0.4
78.94 (0.99)
85.43 (0.97)
84.73 (1.27)
80.92 (0.52)
81.19 (0.39)
79.00 (0.33)
93.74 (0.53)
CS
78.94 (0.99)
86.43 (0.71)
(0.67)
79.76 (0.60)
80.15 (0.38)
79.73 (0.38)
93.43 (0.40)
CS 100
78.94 (0.99)
(1.61)
80.65 (0.71)
77.06 (0.71)
76.53 (0.45)
78.58 (0.96)
91.52 (0.59)
C-MNIST
I.N 0.2
31.19 (0.65)
60.21 (4.47)
30.82 (1.04)
40.00 (0.44)
38.25 (0.46)
38.04 (1.83)
90.99 (0.61)
LN 0.4
31.19 (0.65)
$7.13 (5.48)
27.26 (0.41)
39.98 (0.06)
39.08 (0.02)
39.02 (0.50)
90.09 (0.88)
CS 10
31,22 (0.69)
87.63 (1.97)
38.61 (0.62)
39.16 (0.19)
39.15 (0.19)
39.18 (0.19)
94.43 (1.87)
CS 100
31.22 (0.69)
79.70 (3.29)
37.70 (0.21)
36.81 (0.10)
36.75 (0.17)
36.98 (0.23)
88.34 (0.87)
CIPAR:20 20
LN
29.18 (0.30)
42.48 (0.55)
47.01 (0.87)
49.19 (0.31)
50.13 (0.29)
48.70 (0.36)
54.19 (0.69)
LN 0.4
29.18 (0.30)
(0.47)
38.94 (1.10)
43.29 (0.42)
43.10
43.23 (0.29)
45,48 (0.36)
CS 10
28.45 (0.27)
37.31 (0.28)
42.25 (0.68)
44.96 (0.21)
45.19 (0.20)
39.68 (0.14)
49.17 (0.40)
100
28.45 (0.27)
36.55 (0.29)
31.95 (0.77)
34.66 (0.28)
34.87 (0.12)
26.39 (1.05)
40.27 (2.17)
Table 6: Mean accuracy (standard deviation) in percentage on MNIST, Color-MNIST (C-MNIST), and CIFAR-20 over the last ten epochs under distort-distribution shift in case (iii) with DA baselines (5 trials). Best and comparable methods (paired /-test at significance level 5%) are highlighted in bold. LN/CS is short for label noise/class-prior shift. This result corresponds to Figure 6.
Data
Shift
Vul-only
Pretrain-val
CCSA
DANN
GIW
MNIST
0.2
78.94 (0.99)
86.34 (0.77)
92.95 (0.20)
87.33 (3.22)
94.60 (0.22)
LN
78.94 (0.99)
85.43 (0.97)
89.83 (0.52)
65,56 (8.31)
93,74 (0.53)
CS 10
78.94 (0.99)
86.43 (0.71)
89.18 (0.33)
73.23 (0.66)
93.43 (0.40)
CS 100
78.94 (0.99)
84.54 (1.61)
72.67 (1.75)
49.28 (0.00)
91.52 (0.59)
C-MNIST
L.2
31.19 (0.65)
60.21 (4.47)
84.32 (4.57)
60.65 (5.96)
90.99 (0.61)
LN 0.4
31.19 (0.65)
57.13 (5.48)
80.32 (0.93)
70.27 (9.09)
90,09 (0.88)
CS 10
31.22 (0.69)
87.63 (1.97)
67.39 (3.07)
49.65 (7.98)
94,43 (1.87)
CS 100
31.22 (0.69)
79.70 (3.29)
64.15 (6.80)
36.16 (5.80)
88.34 (0.87)
CIFAR-20
LN
29.18 (0.30)
42.48 (0.55)
52.49 (0.58)
48.31 (0.44)
54.19 (0.69)
LN 0.4
29.18 (0.30)
39.46 (0.47)
40.68 (0.70)
42.29 (0.70)
45,48 (0.36)
28.45 (0.27)
37.31 (0.28)
46.17 (0.20)
41.58 (0.34)
(0.40)
CS 100
28.45 (0.27)
36.55 (0.29)
34.79 (0.35)
33,90 (0.14)
40.27 (2.17)
19

---

Table 7: Mean accuracy (standard deviation) in percentage MNIST the last epochs under support-distributin shift in case (iv) with IW-like baselines (5 trials). Best and comparable methods (paired r-test at significance level 5%) are highlighted in bold. LN/CS means label noise/class-prie shift. This result corresponds to the top row in Figure 11.
Shift
Val-only
Pretrain-val
Reweight
MW-Net
R-DIW
DIW
GIW
0.2
79.86 (0.26)
85.08 (0.71)
86.69 (0.80)
78.16 (1.30)
78.36 (1.08)
75.96 (1.39)
91.44 (0.85)
LN 0.4
79.86 (0.26)
83.26 (1.08)
(1.73)
75.60 (0.49)
75.76 (0.56)
72.12 (0.86)
88.84 (0.97)
CS
79.86 (0.26)
83.44 (1.24)
76.41 (1.28)
74.67 (0.84)
74.94 (0.59)
74.75 (0.69)
90.20 (0.66)
100
79.86 (0.26)
82.09 (0.93)
74.84 (1.10)
71.42 (0.99)
71.11 (0.54)
73.66 (1.32)
87.14 (0.51)
Table 8: Mean accuracy (standard deviation) in percentage MNIST the last epochs under support-distriiution shift in case (iv) with DA baselines (5 trials). Best and comparable methods (paired f-test at significance level 5%) are highlighted in bold. LN/CS means label noise/class-price shift. This result corresponds to the bottom row in Figure 11.
Shift
Val-only
Pretrain-val
CCSA
DANN
GIW
LN 0.2
79.86 (0.26)
85.08 (0.71)
88.06 (0.48)
85.32 (1.11)
91.44 (0.85)
LN 0.4
79.86 (0.26)
83.26 (1.08)
84,00 (0.70)
58.02 (6.63)
88.84 (0.97)
CS 10
79.86 (0.26)
83.44 (1.24)
83.60 (0.53)
64.30 (0.42)
90.20 (0.66)
CS 100
79.86 (0.26)
82.09 (0.93)
66.31 (0.92)
50.06 (0.00)
87.14 (0.51)
20


Reviews:
[{"review_id": "0kn8RoeZ4Z", "reviewer": "Reviewer_UAYX", "summary": "The paper considers a distribution shift problem where the test distribution $D_\\text{te}$ is different from the training distribution $D_\\text{tr}$.\nSpecifically, the learner is given training data sampled according to $D_\\text{tr}$ and (typically a much smaller size of) validation data sampled according to $D_\\text{te}$, and is required to output a classifier with small generalization error (measured by $D_\\text{te}$).\nThe paper first exemplifies a particular pair of $D_\\text{tr}$ and $D_\\text{te}$ such that the existing method called the importance weighting fails, and then\nimproves the method to better handle such hard cases.", "questions": "I wonder why the authors divide the problems into four cases according to the supports of $D_\\text{tr}$ and $D_\\text{te}$. \nApparently, any distribution $D$ with support $S$ is empirically indistinguishable from a distribution $D'$ with support $S'$ if $D$ (and $D'$, resp.) has very small but non-zero probability mass for all $x \\notin S'$ ($x \\notin S$, resp.).", "limitations": "It seems to be impossible to establish a perfectly risk-consistent estimator in general. So we may need to put some assumptions about the difference between $D_\\text{tr}$ and $D_\\text{te}$ and investigate to what extent an estimator is risk-consistent.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Give a hard example where the existing method has significantly poor performance but the proposed method has reasonable performance.\n\nRevise the objective function so as to be risk-consistent, and then propose its empirical version to be minimized, which gives a learning algorithm that outperforms the existing method in experiments.", "weaknesses": "First of all, Theorem 4, claimed as the main theorem, is just a simple rewrite of the generalization risk and thus straightforward.\nMoreover, the theorem does not give any justification of the proposed method. Instead, the consistency of the estimator (the empirical objective) should be investigated. (Generally, the notion of consistency is defined for esitimators.)\nI do not think that the expectation of $\\hat J_G(f)$ coincides $R(f)$.\n---\nMy concern is addressed thru the discussion with the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing but there seem to be some serious factual misunderstandings. We will clarify the issues one by one.\n\n***1. \"generally, the notion of consistency is defined for estimators\"***\n\nHere, we guess estimators meant the empirical objectives from the previous sentence. This claim is NOT true in machine learning, especially in weakly supervised learning.\n\nLet's go back to the origin of consistency. Ronald Fisher created the notion of consistency in 1922 for *point estimation* in *parametric statistics*. This consistency asserts that \"if the estimator were calculated using the entire population rather than a sample, the true value of the estimated parameter would be obtained\". Let $\\theta$ be the fixed but unknown parameter for $F_\\theta$ and $T$ be an estimator that $\\hat{\\theta}=T(\\hat{F}\\_n)$. Then, $T$ is said to be consistent if $T(F\\_\\theta)=\\theta$ or $T(\\lim\\_{n\\to\\infty}\\hat{F}\\_n)=\\theta$. The definition is NOT $\\lim\\_{n\\to\\infty}T(\\hat{F}\\_n)=\\theta$, even though they are equivalent in parametric statistics.\n\nThey are not equivalent and Fisher's is stronger than the commonly used one in *non-parametric statistics*. This is particularly true in ML where the target of convergence (an optimal classifier) is defined by optimization rather than being a fixed but unknown function: even in discriminative learning, a deterministic function cannot generate the observed labels. People care more about learned classifiers (risk minimizers) than risk estimators. *A bad risk estimator may still lead to a good classifier*, for example, $\\hat{R}(f)=2R(f)$ and $\\hat{R}(f)=R(f)^2$. Therefore, ML people talk about *consistency of classifiers rather than consistency of risk estimators*.\n\n***2. Types of guarantee in ML and WSL***\n\n\"Fisher consistency\" is a bit ambiguous in ML: the original definition became *classification-calibration* [1] and the limit definition became *strong consistency*. In the former case, the true risk minimizer is the true error minimizer (error is risk with 0-1 loss), where the *surrogate loss* is consistent. In the latter case, the empirical risk minimizer approaches the Bayes optimal classifier (using a surrogate loss), where the empirical risk minimizer is consistent. There is also *weak consistency* replacing the Bayes optimal classifier with the optimal classifier within a *function class*. Sorry that we cannot give detailed difference between them due to limited space. In ML, the term consistency usually means weak consistency.\n\nIn WSL, training data are not from the test distribution, and thus we need more types of guarantee (see our paper, [2], and the references therein). First, *risk consistency* (RC) means that we can express the true risk as an expectation over the training distribution and this holds *for every classifier*, which is the most fundamental guarantee in WSL. Second, when a RC obj can be naively approximated, we enjoy *unbiased risk estimators* (URE) that can easily lead to statistical consistency (SC). However, the new obj may be complicated (e.g., a max operator in *non-negative correction* [3] or a weight estimator in IW); sometimes, a risk estimator is asymptotically unbiased and we can still have SC. Third, *classifier consistency* (CC) can be regarded as the WSL version of classification-calibration/the original Fisher consistency.\n\nAs classification-calibration is the weakest condition in supervised learning [1] (which should always be satisfied), CC is also the weakest condition in WSL. RC and SC are both stronger than CC and *they cannot imply each other*, for example, $J(f)=R(f)^2$ gives SC empirical risk minimizers but it's not RC. URE is stronger than RC and SC. Sorry that we cannot give detailed difference between them due to limited space but we can discuss it later.\n\n[1] Convexity, classification, and risk bounds. JASA 2006.\n\n[2] Machine Learning from Weak Supervision: An Empirical Risk Minimization Approach. The MIT Press 2022.\n\n[3] Positive-unlabeled learning with non-negative risk estimator. NeurIPS 2017.\n\n***3. Our theoretical contributions***\n\nWe proved that the standard IW is not RC and may be even not CC in some cases, and then proved that GIW is always RC in all cases.\n\n***4. \"I do not think that the expectation of $\\hat{J}_G(f)$ coincides $R(f)$\"***\n\nWe never claimed so. Instead, we explicitly mentioned that $\\hat{J}_G(f)$ is not URE (see Footnote 3 on Page 7). As far as we know, *there doesn't exist any URE in IW*. On the other hand, $\\hat{J}_G(f)$ can be consistent (and asymptotically unbiased) if its weight estimator has no approximation error. That's why we rely on non-parametric weight estimation.\n\n***5. \"the consistency of the estimator (the empirical objective) should be investigated\"***\n\nSee Footnote 3 on Page 7. See also the reply to Reviewer jhs4 (https://openreview.net/forum?id=KmdlUP23qh&noteId=6CQeO3yhmm) for a related discussion.\n\n***6. \"I wonder why the authors divide the problems into four cases\"***\n\nPlease don't mix up the theoretical and empirical perspectives. The theoretical contributions hold even if support shift is only a little. On the other hand, the experiment design considered the cases that the training support is 40% (for sub-class shift) or 33% (for color shift) of the test support, where *support shift matters* for IW. Two-sample tests aren't good at detecting support shift even if it's huge. That's exactly why we proposed GIW.\n\n***7. \"we may need to put some assumptions about the difference between $D_{tr}$ and $D_{te}$\"***\n\nLearning under distribution shift requires either *distributional assumption* or test-distributed validation data. For joint shift, some test-distributed validation data are given and thus no additional distributional assumption is needed. If a distributional assumption is given such as $p(x)$ doesn't change, joint shift will reduce to the 4 easier types. The only assumption here is that the training and test distributions *must have some overlap*."}, {"review_id": "GnJddmRbdu", "reviewer": "Reviewer_uQtu", "summary": "The paper introduces a Generalized Importance Weighting (GIW) method designed to address distribution shift problems, where the support of the probability density function varies between training and test data. The authors demonstrate that GIW outperforms existing methods in scenarios where the test support is wider or partially overlaps with the training support.", "questions": "- Can the proposed GIM perform well on other model architectures such as VGG/Vision Transfomer and large real-world datasets such as ImageNet?\n\n- The authors utilize O-SVM to split D_v to IT and OOT validation data. How to make sure the O-SVM correctly split the D_v set and how does the quality of O-SVM splitting affect the performance of the  proposed GIW?", "limitations": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "**Originality**: The paper introduces a novel method called Generalized Importance Weighting (GIW) that extends the traditional Importance Weighting (IW) method.\n\n**Quality**: The paper is well-structured and provides a thorough analysis of why IW may fail in certain cases and how GIW addresses these issues.\n\n**Clarity**: This paper is well-written and easy to follow. \n", "weaknesses": "- This paper evaluates GIW on a few small datasets. However, it would be beneficial to evaluate the method on a large and complex dataset such as ImageNet.   This would provide a more comprehensive understanding of the performance and applicability of GIW.\n\n-  All experiments in this paper are based on small models LetNet-5 and resnet-18. It would be beneficial to evaluate the method on other modern architectures such as vision transformers and VGG.  This would provide a more comprehensive understanding of whether the proposed method is sensitive to model architectures. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments!\n\nThe experiment scale is concerned by 3 reviewers (i.e., 3 reviewers commented on the size of datasets and 2 commented on the size of models), so please find our reply *\"1. On the common concern about the experiment design\"* in the top-level rebuttal above. In addition, do you have any suggestions for the type of support shift that we could simulate on ImageNet? We'd like to hear your advice.\n\nFor O-SVM related issues, please find our reply *\"3. About one-class SVM\"* in the top-level rebuttal as well.\n\nAs far as we know, there are only very few instance weighting/reweighting methods that can properly deal with joint shift and are compatible with deep learning at the same time: Learning to Reweight (ICML 2018), Meta-Weight-Net (NeurIPS 2019), and Dynamic Importance Weighting (NeurIPS 2020). All of them conducted experiments at the MNIST/CIFAR-10 scale. This is because researchers don't use those high-quality benchmark datasets as they are, but many experiment setups are generated to simulate distribution shift problems. For each experiment setup, we used 5 random seeds to simulate distribution shift (a key point is that *we need to simulate support shift at the same time*), and hence it can easily take a lot of time for training deep networks even though they are not big deep networks. Hyperparameter tuning is also needed, which makes the experimenting time even longer than what people usually expect. We understand it shouldn't be an excuse that in this small research area previous researchers did so and then we are doing the same. However, the current experiment scale may already be a limit beyond which we cannot practically afford.\n\nFortunately, *GIW is NOT sensitive to the model architecture* if we replace the models with smaller deep networks. The accuracy of all methods would be lower but the overall trend would not change --- GIW would still generally outperform the baselines. This has been verified in our preliminary experiments.\n\nThanks again for your positive review and hope our rebuttal clarifies your major concerns."}, {"review_id": "j4dyj1lh5p", "reviewer": "Reviewer_jhs4", "summary": "This paper focuses on an important technique in the field of learning under distribution shift. Compared to previous importance weighting techniques, this paper consider more general scenarios: support shift. This paper first investigates how the previous techniques fail on general support-shift scenarios, then proposes a theoretical-justified objective to consider such scenarios. To this end, the whole pipeline is proposed based the objective. In the experiments, necessary empirical justification is included, verifying the effectiveness of the proposed method.", "questions": "1. It is not well-motivated why we need to introduce risk consistency/inconsistency from label-noise literature. It is a plain definition and should be motivated from its own.\n\n2. Theorem 4 is important to justify the designed objective. However, the most important part, how estimation/observation of s influences the generalization ability is not explored. Necessary discussions should be considered to strengthen the theoretical contribution of this paper.\n\n3. In the experiment, the considered dataset is relatively small. Tasks from partial domain adaptation problem can be used for validating the performance on case (iii). Some large training sets should be considered, e.g., ImageNet.\n\n4. It is unclear how the performance of one-class classifier influences the performance of the proposed method. More experimental analysis should be considered towards this direction. \n\n", "limitations": "This paper does not have potential negative societal impact to be addressed. Paper’s technical limitations can be found in the above comments.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1.  The problem setting is interesting and important to the field. In the real world, cases (iii) and (iv) are very common. However, previous techniques do not consider such scenarios. \n\n2. This paper contributes a principle to the field: what kind of objective is classifier-consistency when solving the general distribution-shift problem (i.e., the support-shift problem). \n\n3. The experiments justify the proposed component. The selected baselines cover a lot of existing methods, which is very appreciated.\n", "weaknesses": "1. The four cases are clearly defined. However, potential practical scenarios can be justified better. In my opinion, test distribution’s support set containing training distribution’s support set might less happen in the current era (as researchers tend to train networks with a lot data). Case (iv) is the most common one, instead of case (iii).\n\n2. In Figure 2, the word “unseen” will cause confusion. We indeed have validation data that come from the test distribution. Thus, it is better to use training data instead of seen/unseen data in Figure 2, or clearly show the decision boundary to avoid potential confusion.\n\n3. It is not well-motivated why we need to introduce risk consistency/inconsistency from label-noise literature. It is a plain definition and should be motivated from its own.\n\n4. Theorem 4 is important to justify the designed objective. However, the most important part, how estimation/observation of s influences the generalization ability is not explored. Necessary discussions should be considered to strengthen the theoretical contribution of this paper.\n\n5. In the experiment, the considered dataset is relatively small. Tasks from partial domain adaptation problem can be used for validating the performance on case (iii). Some large training sets should be considered, e.g., ImageNet.\n\n6. It is unclear how the performance of one-class classifier influences the performance of the proposed method. More experimental analysis should be considered towards this direction. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments!\n\nFor *Questions 2 to 4*, please find our replies in the top-level rebuttal above as well as the reply to Reviewer uQtu (https://openreview.net/forum?id=KmdlUP23qh&noteId=m5Q81fgcQF). In addition, do you have any suggestions for the type of support shift that we could simulate on ImageNet? We'd like to hear your advice.\n\nNext, for *Question 1* and partially *Question 2*, our Theorem 4 studies risk consistency, where *neither estimation nor optimization is involved*. This made theoretical analysis easier and was exactly why we introduced risk consistency.\n\nThe theoretical analysis of the quality of estimating $s$ is more difficult than the theoretical analysis of the quality of estimating $w_i$, while even the latter was not included in previous papers such as Reweight or DIW (note that the convergence analysis in Reweight was for its optimization convergence). This is simply because *representation learning* plays an extremely important role (which was the sole motivation of DIW) but its own quality is actually not guaranteed *under joint shift* in the worst case.\n\nOn the other hand, if the model is a linear model (including linear-in-input and linear-in-parameter models), the quality of estimating $s$ and that of estimating $w_i$ can be guaranteed by the existing theory of linear *one-class classification* [1,2] or *positive-unlabeled classification* [3,4] and that of linear *distribution matching* [5] or *density ratio estimation* [6]. Since we are only interested in *IW for deep learning*, we left the aforementioned theoretical analyses as open problems.\n\nNevertheless, we have provided some empirical analyses in the supplementary material (see Figure 8 in https://openreview.net/attachment?id=KmdlUP23qh&name=supplementary_material) and the rebuttal, which illustrated the concerned quality in the average case.\n\nThanks again for your positive review and hope our rebuttal clarifies your major concerns.\n\n[1] Kernel Methods for Pattern Analysis (Chapter 7), Cambridge University Press 2004.\n\n[2] Advances in Statistical Models for Data Analysis (Chapter 24), Springer 2015. \n\n[3] Semi-supervised novelty detection, JMLR 2010.\n\n[4] Machine Learning from Weak Supervision: An Empirical Risk Minimization Approach (Chapter 4), The MIT Press 2022.\n\n[5] Dataset Shift in Machine Learning (Chapter 8), The MIT Press 2008.\n\n[6] Density Ratio Estimation in Machine Learning (Chapters 13 to 16), Cambridge University Press 2012."}, {"review_id": "p5jHfQNquT", "reviewer": "Reviewer_G7Ea", "summary": "The paper studied importance weighting that is a fundamental technique in machine learning and data mining. It pointed out a serious issue of existing importance weighting methods that has not been realized or considered carefully --- the support of the training distribution may not fully enclose the support of the test distribution. Then, it proposed a generalized version of importance weighting that can solve the serious issue and has some nice theoretical properties.", "questions": "A point in the motivation should be clarified. As I mentioned above in \"the motivation is clear\", when the importance weights are ill-defined outside the training distribution, importance weighting itself is still well-defined. So have people not noticed the serious issue of importance weighting, or have they noticed it but thought it not a big deal and then ignored it? BTW, you only argued that \"IW methods become ill-defined and problematic\", which is not enough as an explanation. The importance weights may be ill-defined, but those ill-defined importance weights will not be used for training. As a result, IW methods are not ill-defined, but they are not good for training and may lead to poor trained classifiers. However, if we are lucky, they can lead to good trained classifiers, as shown in Figure 2. Am I right?\n\nBefore Proposition 3, you have assumed that \"the classifier would transfer its knowledge about ptr(x,y) to pte(x,y) in the simplest manner\". Why do you need this assumption, or can you explain the implicit meaning of this assumption? If I am not wrong, importance weighting can only train linear classifiers given such training and validation data.\n\nIn this paper, the definition of importance weighting is to use pte(x,y)/ptr(x,y) as the importance weights. There is a more general definition of importance weighting: weighting the loss function on training data to emphasize the loss on some or de-emphasize it on others with the objective of correcting the mismatch between the training and test distributions (see Corinna Cortes, Yishay Mansour, Mehryar Mohri, \"Learning Bounds for Importance Weighting\", NIPS 2010). This more general definition can include your \"IW-like methods\" as IW methods. You theoretically and empirically analyzed when and why IW methods can succeed/may fail. Can your results still hold for this more general definition?\n\nI think importance weighting is not good at the case where the support of the training distribution may not fully enclose the support of the test distribution. This is the motivation of generalizing importance weighting in this paper. However, transfer learning and domain adaptation should also be good at the case which importance weighting is not good at and generalized importance weighting is good at. I found transfer learning or domain adaptation was not mentioned or discussed in this paper. So can you comment on their potential and compare their ability with generalized importance weighting?", "limitations": "Labeled validation data coming from the test distribution are required for estimating the importance weights and training. Such validation data may be hard to obtain in practice.", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The motivation is clear. People employ importance weighting where the importance weights are defined as pte(x,y)/ptr(x,y), and people assume pte(x,y)=0 whenever ptr(x,y)=0, to avoid unbounded importance weights. Consider the case that the support of the training distribution may not fully enclose the support of the test distribution. Since the importance weights are only used for the training distribution, even though they become ill-defined when pte(x,y)>0 and ptr(x,y)=0, importance weighting itself is still well-defined and it seems to be fine... However, this paper pointed out that in such a case the importance-weighting \"identity\" becomes an \"inequality\", which means that what we minimize for training will not be an approximation of the original risk and thus training may be biased. Indeed, this paper constructed a toy example (Figure 2 and Proposition 3) where training is still unbiased or totally biased. I like Proposition 3 very much that emphasizes what people have overlooked so far.\n\nThe idea is novel. It splits the validation data coming from the test distribution into two parts based on one-class classification and pretrained representation (note that pretraining is on the distribution-shifted training data and the proposed method is still end-to-end). Then, the original importance-weighting term is based on one part of the validation data and there is a second term based on the other part of the validation data. In such a way, what we minimize for training is an approximation of the original risk and thus training is still unbiased, as long as the split of validation data is not wrong. As far as I know, this idea or a similar idea has not been explored in importance-weighting research.\n\nThe experiments look very interesting. The Color-MNIST experiments (both the design and the results) are thought-provoking.", "weaknesses": "The experiments are all done on benchmark datasets at the MNIST/CIFAR scale and there is no big data experiment like ImageNet.\n\nThe biggest model in the experiments is ResNet-18 and there is no big model experiment involving WideResNet, DenseNet, or ViT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for spending a lot of time reviewing our manuscript!\n\n***1. Experiment scale***\n\nPlease find our reply *\"1. On the common concern about the experiment design\"* in the top-level rebuttal above as well as the reply to Reviewer uQtu (https://openreview.net/forum?id=KmdlUP23qh&noteId=m5Q81fgcQF). In addition, do you have any suggestions for the type of support shift that we could simulate on ImageNet? We'd like to hear your advice.\n\n***2. Have people not noticed the serious issue, or have they noticed it but thought it not a big deal and then ignored it?***\n\nWe are not sure, but it might be the latter case. Before deep learning got so popular in the wild, even if there was support shift it must be *only a little* support shift, and it shouldn't be a big deal. Now, it's a different story. After being deployed in the wild, a model will see so many new concepts (i.e., classes or sub-classes) that it has *never seen during training*. Then, it can be a big deal.\n\nBy the way, for the motivation, your understanding is perfectly correct.\n\n***3. Why do you need this assumption, or can you explain the implicit meaning of this assumption?***\n\nYes, as you said, \"importance weighting can only train linear classifiers given such training and validation data\". However, a richer function class is required to allow true risk minimization to train non-linear classifiers and recover the Bayes optimal classifier (i.e., there is *zero approximation error*). Otherwise, comparing the classifiers obtained by IW and true risk minimization, we cannot know that IW is as bad as random guessing.\n\n***4. Can your results still hold for this more general definition?***\n\nIt depends. The key point is *to what extent the validation data join the optimization of models*. When validation data directly join model training, an IW-like method should behave similarly to GIW (i.e., good performance); when validation data indirectly join model training,  it should behave similarly to the original IW (i.e., bad performance). For example, Reweight has a primary objective where the empirical risk on validation data is minimized to update the instance weights $w_i$ and a secondary objective (i.e., the constraint) where the empirical risk on weighted training data is minimized to update the model $\\theta$ itself, so that only some but not all classifiers would be the candidates in the primary objective. In this way, the validation data don't directly join model training, and we can see from the experimental results in our manuscript that Reweight looks like DIW and R-DIW. We can also see that Meta-Weight-Net looks like Reweight, because it is roughly a parametric version of the non-parametric Reweight.\n\n***5. Domain adaptation***\n\nPlease find our reply *\"2. About domain adaptation\"* in the top-level rebuttal.\n\nThanks again for your positive review and hope our rebuttal clarifies your major concerns."}]

Author rebuttal:
***1. On the common concern about the experiment design***

We sincerely thank all the reviewers. First of all, since 3 reviewers asked for additional experimental comparisons of the proposed method against the baseline methods on ImageNet, we'd like to explain why it is difficult to do so. We will try our best to provide such results later.

**(a) Computational efficiency** All existing IW and IW-like methods are slow. It would be difficult to compare GIW with the baselines on large-scale datasets (we are using V100). The inner optimization of GIW (indeed DIW [1]), namely *kernel mean matching*, needs to be solved by a standard QP solver. However, convex programming solvers (including CPLEX, Gurobi, CVX, and CVXOPT) do not support GPUs and have no plan to do so. This is because they focus on sparse linear algebra that should be MIMD rather than SIMD. As a result, the inner optimization (obtaining importance weights) is done on CPUs and the outer optimization (training deep networks) is done on GPUs, where moving data between CPUs and GPUs is really time-consuming. Moreover, IW-like methods based on bilevel optimizations are also very slow due to complicated technical reasons. We monitored the training time of CIFAR-20 experiments with ResNet-18. On V100, GIW took 27.89s per epoch and Reweight [2] took 67.51s per epoch, respectively. This baseline is even slower than GIW and thus it is difficult to train big models on ImageNet for both of them and compare their accuracy.

Note that even if we replace KMM with similar methods like *least-squares importance fitting* [3], we can still not get rid of a QP solver. We may hand-crafted a rough QP solver that can run on GPUs, but it is already beyond the scope of the current paper. What we are extending is the objective function of IW but not the implementation of DIW because the plug-and-play weight estimator in GIW is not limited to DIW.

[1] Rethinking importance weighting for deep learning under distribution shift. NeurIPS 2020.

[2] Learning to reweight examples for robust deep learning. ICML 2018.

[3] A Least-squares Approach to Direct Importance Estimation. JMLR 2009.

**(b) Problem difficulty** As mentioned in our introduction (see also the ICLR keynote by Masashi Sugiyama), joint shift is much harder than the other 4 types of distribution shift. Any algorithm must be very careful when handling joint shift. Though the experiments simulated 2 easier types, GIW and the baselines didn't know it, and we cannot ask an algorithm to identify the type of easier shift since the joint shift may not fall into the 4 easier types in practice. Given that the problem of interest is so hard, we shouldn't expect too much for GIW or the baselines. Note that CIFAR-20 and CIFAR-100 share the same instances with two-level labels, making it a natural test bed for joint shift in case 3/4. We'll study how to simulate the same case on ImageNet, but it's indeed non-trivial.

***2. About domain adaptation***

**(a) Conceptual difference** DA can refer to either certain problem settings or the corresponding learning methods (or both). There are *Supervised DA* and *Unsupervised DA* in DA research. SDA was proposed in 2006 and UDA was proposed in 2007; UDA is now much more impactful than SDA (we don't see new powerful SDA methods in recent years). Regarding DA as problem settings, SDA is exactly the same as joint shift and UDA is fairly similar to covariate shift, where distribution shift research has a slightly longer history (dated back to 2000). Regarding DA as learning methods, the philosophy of both SDA and UDA is to find good representations to link the source and target domains and transfer knowledge from the source domain to the target domain, totally different from the philosophy of IW. In fact, *importance sampling* as a sister of IW can be dated back to 1978 in statistics and 1949 in statistical physics.

Please note that the main focus of this paper is conceptually extending IW and making it more applicable to harder problems, rather than finding better solutions for the harder problems. That's why we didn't focus on comparing GIW with DA.

**(b) Empirical results** We added 2 representative DA baselines: *classification and contrastive semantic alignment* (CCSA) [4] (for SDA, 700+ citations) and *domain-adversarial neural network* (DANN) [5] (for UDA, 7000+ citations). The experimental results are given as Tables 1&2 in the attachment, where GIW generally outperformed CCSA and DANN. Specifically, when there was no distribution shift other than support shift, CCSA was as good as (or slightly better than) GIW, since this is what SDA is good at and there is nothing to do with DIW inside GIW. When there was also class-posterior shift (label noise) or class-prior shift, CCSA became confused, since this is what IW is good at and the source domain can mislead the learned representation of CCSA. DANN was even worse than CCSA, simply because it didn't use target domain labels. To sum up, IW and DA have different philosophies and there are situations that GIW is good at but CCSA and DANN cannot properly handle.

[4] Unified deep supervised domain adaptation and generalization. ICCV 2017.

[5] Domain-adversarial training of neural networks. JMLR 2016.

***3. About one-class SVM***

As mentioned in our paper, while there are more advanced one-class classification, the O-SVM is already good enough for the purpose (see Figure 8 in Appendix C.1). This is because *the underlying representation learning is very powerful*. To further investigate the negative impact of split errors, we added an ablation study by randomly flipping the IT/OOT data into the OOT/IT part. From Table 3 in the attachment, we can observe that GIW is quite robust to split errors and that OOT-->IT is more problematic than the other direction. This is because OOT-->IT makes the empirical risk estimator of GIW more similar to that of the standard IW.

Meta-review: The paper has a clear explanation of importance weighting's assumptions and its identification of biases in scenarios where training and test distribution supports differ. The reviewers highlight the novelty of the proposed idea that splits validation data using one-class classification and pretrained representation to maintain unbiased training. The Generalized Importance Weighting (GIW) method's effectiveness in addressing distribution shift problems is emphasized.
Decision: Accept (spotlight)