Tight Rates in Supervised Outlier Transfer Learning
Authors: Mohammadreza Mousavi Kalan
Samory Kpotufe
Venue: ICLR 2024 poster (2024)
Keywords: Minimax rate
outlier detection
transfer learning
Neyman-Pearson
unbalanced classification
Primary area: learning theory

Abstract: A critical barrier to learning an accurate decision rule for outlier detection is the scarcity of outlier data. As such, practitioners often turn to the use of similar but imperfect outlier data from which they might \emph{transfer} information to the target outlier detection task. Despite the recent empirical success of transfer learning in outlier detection, a fundamental understanding of when and how knowledge can be transferred from a source to a target in outlier detection remains elusive. In this work, we adopt the traditional framework of Neyman-Pearson classification---which formalizes \emph{supervised outlier detection}, i.e., unbalanced classification---with the added assumption that we have access to both source and (some or no) target outlier data. Our main results are then as follows:

We first determine the information-theoretic limits of the problem under a measure of discrepancy that extends some existing notions from traditional balanced classification; interestingly, unlike in balanced classification, seemingly very dissimilar sources can provide much information about a target, thus resulting in fast transfer.

We then show that, in principle, these information-theoretic limits are achievable by \emph{adaptive} procedures, i.e., procedures with no a priori information on the discrepancy between source and target distributions.

Published as a conference paper at ICLR 2024
TIGHT RATES IN SUPERVISED OUTLIER TRANSFER LEARNING
Mohammadreza M. Kalan Statistics, Columbia University mm 62 4 4 col umbi columbiaa a. edu
Samory Kpotufe
Statistics, Columbia University samo ryêco leeeeoolubbia... edu umbia
ABSTRACT
A critical barrier to learning an accurate decision rule for outlier detection is the scarcity of outlier data. As such, practitioners often turn to the use of similar but imperfect outlier data from which they might transfer information to the tar- get outlier detection task. Despite the recent empirical success of transfer Iearn- ing approaches in outlier detection, a fundamental understanding of when and how knowledge can be transferred from source to a target outlier detection task remains elusive. this work, we adopt the traditional framework of Neyman- Pearson classification which formalizes supervised outlier detection-wee with the added assumption that one has access to some related but imperfect outlier data. Our main results
follows:
We first determine the information-theorett limits of the problem under measure of discrepancy that extends some existing notions from traditional balanced classification; interestingly, unlike in balanced classification, seem- ingly very dissimilar sources can provide much information about a target, thus resulting in fast transfer.
We then show that, in principle, these information theoretic limits are achiev- able by adaptive procedures, i.e., procedures with no priori information on the discrepancy between source and target outlier distributions.
INTRODUCTION
A primary objective in many data science applications is to learn decision rule that separates com- mon class with abundant data from a rare class with limited or no data. This is a traditional problem which often appears under the umbrella term of outlier detection or rare class classification, and has seen resurgence of interest in modern applications such as malware detection in cybersecurity and loT (Jose et al., 2018; Kumar Lim, 2019), fraud detection in credit card transactions (Malini & Pushpa, 2017), disease diagnosis (Bourzac, 2014; Zheng et al., 2011), 1),, among others. A main goal distinguishes from traditional classification where performance is
in these applications- asssessed on average all classes- is to achieve low classification error the rare class, while at the same time maintaining low eтrоr w.r.t the common class. Such a constrained objective is com- monly referred to as Seyman-Pearson classification. Formally, letting Ao fa denote the common and rare class distributions, Neyman- classification takes the form:
Minimize f1-error over classifiers in some hypothesis space subject to keeping the рo-error of such h under a threshold
In this work, we focus on the common supervised setting where practitioners have access to not only training data from the common class, but also some (limited amount of) data from the rare class or, pertinently, from a related distribution they hope has information on the rare class. Henceforth, for simplicity of notation, we denote the target rare class distribution by Pı,T and the related but imperfect rare class distribution by j1.s, where "S" stands for source. As an example, such related rare-class data may be from a different infected device in loT applications, or from similar cancer types in medical applications, from laboratory simulations of class. This is thus transfer learning problem, however for supervised outlier detection rather than for traditional classification as is usual in the literature.

---

Published as a conference paper at ICLR 2024
PL.
MLT
o²) Figure I: noo [ao, ) is the common distribution, and 51,s, M1,7 (a Naa,T, o²) the source and target distributions. The universally optimal decision rules for the source and target are identical, i.c., hs.a af in fact for any value of a [0, 1] (see Section 3).
While this outlier transfer problem is quite common in applications due to the scarcity of rare class data (Su et al., 2023; Wen & Keyes, 2019; Aburakhia et al., 2020), the problem has far received little rigorous attention. Our main aim is therefore to further theoretical understanding of this timely problem, and in particular to gain much needed insight the extent to which related but imperfect rare class data may improve performance for the target Neyman-Pearse problem. Such achievable transfer performance of course must depend on how far the related rare class distribution fi,s is from the target M1,T sonhhoo properly formalized related rare-class distribution P1,5 induces similar optimal decision rules as for the target rare class distribution j1,r-
classification
or whether the
We first argue that, unlike in traditional classification, seemingly very different source and target distributions f1,5, M1,r may induce the same exact (universally) optimal decision rules in Neyman- Pearson classification; this obtained as a consequence of simple extension of the classical Jeyman-Pearson Lemma (Lehmann & Lehmann, 1986) to the of transfer (see Proposition 3.6). This is illustrated in Fig and explained in detail in Section 3. As a consequence, unlike in usual classification, we can approximate the universally best classifier hT under the target arbitrarily well asymptotically, i.e., with sufficiently large data from a seemingly unrelated source.
However, the story turns out such approximation (in terms of relevant sample sizes), even when f1,s and M1, admits the same optimal classifiers. That is, two different sources 11,5 and pL.s may yield considerably different transfer rates in finite-sample regimes even if both of them share the same optimal classifier as the target p1,7 this is because given source may yield more data near the common decision boundary h fr than another source, thus revealing h at faster rate. In particular, we show our first main result of Theorem 4.5 a minimax lower-bound -that the rate of convergence of any autlier-transfe approach is in fact controlled by relatively simple notion of outlier-transfee exponent (adapted from transfer results traditional classification) which essentially measures how well source may reveal the unknown decision boundary. Theorem 4.5 is in fact rather general: the minimax lower-bound holds for any hypothesis space H of finite VC dimension (at least 3), and any number of sample sizes from po, M1.s MI,T. including the case of no sample from the rare target class W1, Morcover, the result holds generally h5.o. and hT, are the same or not.
nuanced in finite sample regimes, i.e,
consider the rate of
We finally turn our attention to whether such rates may be achieved adaptively, i.e., from samples alone without prior knowledge of the discrepancy between f1,s and μ1. as captured by both the cransfer-xpponeee and the amount of difference between optimal classifiers h and hi We show in Theorem 4.6 that this is indeed the case: the minimax lower-bounds of Theorem 4.5 can be matched up to logarithmic factors by some careful adaptation approach that essentially fine-tunes classifiers learned using source data with whatever target data is available. This is described in Section 4.8.
1.1 RELATED WORK
Outlier detection and transfer learning have mostly been studied separately, despite the clear need for transfer learning in applications of outlier detection where the rare class of data is by definition, always scarce.
As such, transfer learning works have mostly focused on traditional classification and regres- sion starting from seminal works of Mansour et al. (2009); David et al. (2010); Ben-Dane David et al. (2010; 2006), to more recent works of Hanneke & Kpotufe (2019; 2022); Kalan et al. (2022); Mousavi Kalan et al. (2020); Lei et al. (2021). The works of Hanneke & Kpotufe (2019; 2022) most closely related as notion of ounfier-rransfeeeeexponnnt may be viewed as extention
2

---

Published as a conference paper at ICLR 2024
however, besides for the fact that both notions capture discrep- ancies around decision boundaries, transfer in outlier detection is fundamentally different from the case of traditional classification studied in the above works: for instance, as stated earlier, distribu- tions that are significantly different in traditional classification can be quite close in outlier transfer as revealed in this work.
of their notion of
Theoretical works on outlier detection on the other hand have mostly focused on unsupervised and supervised settings, but without considering the more practical transfer setting. Unsupervised outler-ddtection assumes that only data from the common class μ40 is available; theoretical works include studies of density-level set estimation (Steinwart et al., 2005; Polonik, 1995; Ben-David & Lindenbaum, 1997; Tsybakov, 1997) where outliers are viewed as data in low density regions, or in works on so-called one-class classification that aim to learn a contour of the common class Jo (Schölkopf et al., 2001). Supervised outlier-detection has commonly been formalized via Neyman- Pearson classification,, where some data from both the common and rare classes are used to optimize and constrain empirical errors. Early works include (Cannon et al., 2002; Scott & Nowak, 2005; Blanchard et al., 2010; Rigollet & Tong, 201 1) which establish convergence rates in various distri- butional and model selection settings, but all exclude the question of transfer.
Transfer learning for outlier detection has in fact received much recent attention in the methodologi- cal literature (Xiao et al., 2015; Andrews et al., 2016; Idé et al., 2017; Chalapathy et al., 2018; Yang et al., 2020) where various approaches have been proposed that aim to leverage shared structural aspects of source and target rare class data.
On the theoretical front however, much less is understood about outlier transfer. The recent work of Scott (2019) initiates theoretical understanding of the problem: they are first show that, in some situations where both source and target share the same optimal classifiers, various procedures can guarantee consistency (i.e., taking sample size to infinity) even as source and target M1.s Mi.r appear different. Our Proposition 3.6 shows that in fact optimal classifiers may be shared in even more general situations, similarly implying consistency for seemingly very different source and target rare-class distributions. Our main results of Theorems 4.5 and 4.6 reach further in deriving the first insights into the sample regimes of limits of the problem, along with notions of discrepancies between source and target that tightly capture such limits.
by establishing ieformation-theorette
SETUP
We first formalize the Neyman- Pearson classification framework, followed by its extension to the transfer case.
2.1
NEYMAN-PEARSON CLASSIFICATION
Let Po and μ1 denote probability distributions on some measurable space (X, Σ). Furthermore, suppose that 7 is a hypothesis class consisting of measurable 0-1 functions on the domain X. where we view h(x) = 0 or 1 as predicting that æ is generated from class No or f4g We view No and μn as representing common and rare class of (future) data.
Definition 2.1. We are interested the so-called Type-I and Type-II errors defined as follows:
Rypo (h) = po(h(z)) = 1), Ry, (h) = 41 (1(())) = =).
Neyman-Pearson classification then refers to the problem of minimizing Type-Il error subject to low Type-I error: erro::
Minimize R,, (h) hEH
s.t. Rypo (h) S
(2.1)
Under mild conditions, the universally optimal classifier, i.c., taking H. as the set of all measurable 0-1 functions, fully characterized by the classical Neyman-Pearson Lemma (see Appendix A) in terms of density ratios. Namely, let Pa and denote densities of /o and μn w.r.t. some dominating measure v, then the minimizer of (2.1) has the form h (x) 11, (2r(a)>A) whenever there exists
such that Ryo (ht) is exactly a..
'If we further allow for randomized classifiers, then Neyman Pearson I Lemma fully characterizes universally optimal solutions of (2.1) and establishes uniqueness almost-surely under mild restrictions.
3

---

Published as a conference paper at ICLR 2024
In the Section 3 ask when such universal minimizer transfers across source and target cless distributions.
2.2 TRANSFER LEARNING SETUP
Population Setup. We consider the following two source and target Seyman-Pearsenn problems, defined for a fixed common class distribution μo. and source and target rare-class distributions F1,5 and p1,r:
Minimize Rp (h) heal
Minimize R Ru (h) he7l
s.t. Rugg (h)
(2.2)
s.t. Rgg (h)
(2.3)
We let ( (No, s1 a) and (No, MI,T, a) denote these source and target problems. We will see later that the limits of transer- especially finite-sample regimes, are well captured by discrepancies between these two problems. In particular, we will be interested in discrepancies between optimal solutions and the measure of the corresponding decision boundaries under involved distributions. We henceforth let his and Traa denote (not necessarily unique) solutions of (2.2) and (2.3) (which we assume exist).
Finite-Sample Setup. We assume access to To, Rt i.i.d. data points respectively from (o: (41,8, (1,,7, M,,,, where we allow nr = 0. The transfer-learning procedure then allowed return e H satisfying
Ry (h) S a ED.
for some slack 6, = (o()), usually order no 1/2 The goal of the learner is to minimize the target-excess error
(hr(h) max (0, R (h) R (bT
A main aim of this work is to understand which rates of (h) are achievable in terms of sample sizes n, and re,, and which notions of discrepancy from source to target helps capture these limits.
3 EQUIVALENCE OF POPULATION PROBLEMS
As discussed in the introduction, we may have seemingly very different source and target distribu- tions f1.s and ML. which however yield the same (universally) optimal classifiers. We investigate this phenomena in this section, the main aim being to illustrate how fundamentally different outlier transfer is from traditional classification. To this end consider the set of all possible measurable 0-1 functions on X, and let = 4I in the dicussion below.
We will henceforth say that the source problem (No- M1.s. ax) is equivalent to the target problem (Pos Mr,,, a:) (at the population level), if all solutions to (2.2) are also solutions to (2.3). Clearly, when this is the case, source samples alone can drive down the target risk at least asymptotically.
We first notice that Neyman- Pearson Lemma offers some immediate answers under mild conditions. To see this, let Pi.s, PI,T' denote densities w.r.t. common dominating measure In what follows we will simply let the dominating measure v μo f4,S + PI,T. As previously discussed, Neyman-Pearson Lemma characterizes optimal classifiers in terms of level sets of density ratios.
Po(a) 2 A). Here, when the denominator of a fraction is zero we view it as infinity no matter if the nominator is zero or nonzero.
Definition 3.1 (Level sets). D (x:
Pis(#) 2 A} and C := {x Pir(a)
Po(z)
The following then establishes equivalence between source and target under mild conditions direct consequence of Neyman-Pearse Lemma.
Proposition 3.2. Suppose (40,,1,S, (11 are mutually dominating. Assume further that Ho (o(C5) is continuous and strictly monotonic in (0, 1) as a function of X. Then, if (CE) x20 c <(cT) X20- we have for all 0 a that any hisaa is solution of the target problem (2.3).
The above statement was already evident in the work of Scott (2019) where it is assumed that source density ratios are given as a monotonic function of the target density ratios; this immediately implies (L (4T)-
4

---

Published as a conference paper at ICLR 2024
M1.T Target
140
Figure 2: Pa,Ma, M1.8,,1,7 = (au, decision rules differ.
where 01.5 01. and d' < a. Optimal
The statement is illustrated in the examples of Fig I with Gaussian distributions where the source may appear significantly different from the target (and in fact would yield different Bayes classifiers in traditional classification). To contrast, consider the example Fig 2 where the source problem yields different level sets than for the target problem (simply by changing the Gaussian variance), and we hence do not have equivalence.
Remark 3.1 (Issue with Disjoint Supports). We have assumed in the Proposition 3.2 that all 3 distributions are mutually dominating, while in practice this might rarely be the case. However, without this assumption (essentially of shared support), we may not easily have equivalence between source and target.
For intuition, consider a region A of space where (1.s(A) O while (A) > O. Then let hig. on A and h/5,a both optimal under the source problem; clearly we may have R1r((ss,) (1,r( since (A) > O.
The rest of this section is devoted to handling this issue by restricting attention to more reasonable classifiers that essentially classify any point outside the support No as The right notion of support is critical in establishing our main relaxation of the above proposition, namely Proposition 3.6 below.
We require the following definitions and assumptions.
Definition 3.3 (Restricted Universal Hyposthesis Class). We let lt consist of all 0-1 measurable functions the domain X such that for every h e U"" h= 1 on {a po(x) 0} a.s. v. Definition 3.4. We say that a achievable if there exist thresholds and X such that po( a and po ( a.
Definition 3.5 (a-level set), Whenever a achievable, we define (a) as the level set in the source whose measure under pa is a. The definition of L (ox) which corresponds the target is the same.
Remark 3.2. Definition 3.4 ensures that (a) exists, but it may not be unique. However, we will show in Appendix A by Proposition A.2, is unique a.s. v.
The following proposition relaxes the conditions of Proposition 3.2 above by restricting attention to universal classifiers ld" Its proof is technical to various corner cases described in the Appendix. Proposition 3.6. Let 0 S a < 1 and suppose that o is achievable. Then (Ho, a) is equivalent to (PosPs MI,,, a) underU" l iff (a)) e {C() } Xzo a.s. In particular, if a is achievable for all 0 S a < 1 and (a) {CX) a.s. for all 0 S a < 1, then (Ho.M1,5,0t is equivalent to (po, PL,T; for all S 1.
Remark 3.3. Notice that the statements of Proposition 3.6 trivially also hold over any hypothesis class H. (rather than just U² containing the level sets (c) (CT H. and where, for every h H. h = on {x: (x()) 0} a.s. V.
We illustrate this final Proposition in Figure 3: the simple restriction to 't2 reveals more scenarios where source is equivalent to target (at the population level) even when the distributions appear significantly different.
FINITE SAMPLE RESULTS
Neyman-Pearee Pearson Lemma offers the solution(s) of the optimization problem (2.3) when we have the knowledge of the underlying distributions. However, in practical scenarios, typically lack infor-
5

---

Published as a conference paper at ICLR 2024
14
M1.5
P1T
1
(b) Source and target so- lutions.
(c) K is an optimal so- lution for source but not for target.
(a) nax P1,.. Pr,
Figure 3: Illustration of Example (see Appendix A.3), where h3... hr. U", while hgg,. U is also optimal for source but not for target. In other words, the source problem remains equivalent to the target over the more reasonable decision rules of
mation about these distributions and only possess some samples drawn from them. In addressing this challenge, Cannon al. (2002) embarked cation and introduced a relaxed version of Neyman- Pearson classification problem. Let and nr be the number of i..d. samples generated by μo and μ1,7. respectively, and eg > 0. Cannon al. (2002) proposed the following optimization problem:
empirical study of Neyman-Pearson classifi-
h arg min R (h) he7f
S.I. Ryno (h) ax
60
(4.1)
where Ry (h) 1 Σ 1()(X.)=0) and R (h)
1 Σ ((((x))+1)) and then derived X.mir
X,-pa
the convergence rate of excess error in terms of the number of samples and VC dimension of the hypothesis class.
Neyman-Pearson classification in the setting of transfer finite-sample scenarios remains unexplored. In this section, Our objective is understand the fundamental limits of transfer outlier detection in the finite-sample regime, where there are ng. ny i.id. samples from Po, A1.Ss (1.T, under measure of discrepancy between source and target. We first define discrepancy measure transfer outlier detection and then characterize the fundamental limits of the problem by deriving minimax lower bound in terms of the number samples as well as the notion of discrepancy. Finally, we show that this lower bound is achievable through an adaptive procedure which does not require the prior knowledge of the discrepancy between source and target.
4.1 OUTLIER TRANSFER EXPONENT
In this section, we define an appropriate notion outlier transfer distance between source and target under hypothesis class. Here we adapt the transfer exponent notion defined in Hanneke & Kpotufe (2019) to a notion of discrepancy between source and target in Seyyann-Pearsee classification with shared common distribution μtg
Definition 4.1 (Outlier transfer exponent). Let St H denote the set of solutions of source (2.2). Furthermore, let (po, P1,s, a)) and (Mo.HH,,, denote the source and target problems, respec- tively. We call p(r) outlier transfer exponent from (Ho, a1 to there exist C(r)) > 0 such that
under H. if
Ca(r max (0, (h) Ry (1s, max fo, (0, R Ru (hisa))
p())
(4.2)
for all h H with Ryo (h) a r,, where lis.a mrg (h).
hesg
The following example shows that for fixed target and for any arbitrary 1, there exists source such that it shares the same optimal decision rule as the target and attains the outlier transfer exponent P with coefficient C, 1.
Example 4.2. Let po (-1,,1),, pI,T Uni 1], Pi.s px--2 1 [2 for p where Pı,s the density of p1,s w.r.t. Lebesgue measure. Furthermore, let vo[[0, 1)) H {1(1ses1) (I:)

---

Published as a conference paper at ICLR 2024
[-1,1]), and r be small enough. Then, we have hi,a h's,a (0sss1)) Moreover,for h (tsast) for 2 we obtain
Rp (h) Rys. ( and Rus.s (h) Rys. (1is,a) = =t"
Hence, the outlier transfer exponent is and the coefficient Cp is 1.
Following proposition shows the effect of on the outlier transfer exponent p(r)). some cases, for small enough value of r. p(r) could be small, whereas for a large value of r, p(r) is infinite.
Proposition 4.2. There exist Pos P1.S, P1., H. a. such that for any h e H. with Ryo (h) a + (4.2) holds for p(r) 1 and there exists h H with Ryo (hi a + for which (4.2) does not hold for any < 0o.
4.3
MINIMAX LOWER BOUND FOR OUTLIER TRANSFER LEARNING
Equipped with the notion of outlier transfer exponent, we characterize the fundamental limits of transfer outlier detection by establishing a minimax lower bound. To achieve this objective, first we need specify the class of distributions for which the minimax lower bound is derived.
Definition 4.3 (Class of distributions). Fix a hypothesis class H with finite VC dimension dx. Let (p a. C, A) denote the class of triplets of distributions (Ho. H1,8 H1,T) for which a is achiev- able according Definition 3.4, ε (h',a) S &A, and there exist p(r) S p. CdCr)) S for any 2a according to Definition 4.1.
o<r<
du
Remark 4.4. Deriving minimax lower bound for the class of distributions satisfying a achiev- ability is a stronger result than for the class without necessarily satisfying that, as the former is contained in the latler.
We also need to formalize the class of learners.
Definition 4.4. Let 0 <o < 1, 0 dg 1. We cull i an (en, dn) apprrxxmmtt c-learner if it maps any three independent i.i.d. samples Spo 16 Spi,s H1,s. Spit M1,7 to a function in
Hatey (atc (he H Rup (h) sa+tn)
with probability at least 1 1-6 5u Sp
Theorem 4.5 (Minimax lower bound). Fix a hypothesis class H with finite VC dimension dæ 2 3. Moreover, let a < 1. 2 1, s 1, and du > Furthermore, suppose that there are Tuy ngg Be i.i.d. samples from po: P1,s, M1,r, denoted by S Sp Assume that there sufficiently many samples such that min(A A + dus I0 (dx ) s 2. Then, for any (2x appproxxxeee a-learner h, there exist (No, M1,5 H1,T) ) E FuC.. at, 1, A) and universal constants e' such that
ns
(
HHp TiT
(h) min min n1.
(4.3)
Sup Sp SHL.
Remark 4.5. In Theorem 4.5, if (PorM1,s, M1,s, a.) is equivalent to (Po. Mi,T, under H. (see Remark 3.3), then (h',,))) O and the minimax lower bound reduces to e- c-min( case, by only having access to unlimited source samples, achieving an arbitrary small target-excess error is possible.
mg ) ((x) In this
Remark 4.6. The outlier transfer exponent in the term ( ( captures the relative effectiveness of source samples in the target domain. If source and target share the same optimal decision rules, and = 1, source samples would be equally effective as target samples. However, even if the source and target share the optimal decision rules, source samples may result in poor transfer performance when is large.
Remark 4.7. In Theorem 4.5, the learner is allowed to output classifier h with Type-I error that slightly exceeds the pre pre-defined threshold a. However, in certain applications, it is imperative to uphold the threshold without any exceeding. The minimax lower bound in Theorem 4.5, implies that (4.3) holds even the learner only allowed output classifier h from {h H. Ryo (h) s a) with probability 1 do. i.e., (0, 6 -approxixii a-learner
7

---

Published as a conference paper at ICLR 2024
4.8 ADAPTIVE RATE (UPPER BOUND)
In Section 4.3, we establish a minimax lower bound that can be attained by an oracle that effectively disregards the least informative dataset from either the source or target. Let Ha-eo (Po) {h e H Ryo (h) to). hT= arg min heHorrg((((a)
Rys.r (ht, and hg arg min he
Russ (h). Then we get
hs, hr Hateo (No), and
) and ( s ng
dn
(hs))ss s (1),,)
with high probability. However, Deciding whether hs or hr achieves smaller error requires the knowledge of outlier transfer exponent and the target-excess error of the optimal source decision rule, which are available in practical scenarios.
In this section, we show that by using an adaptive procedure that takes source and target samples as input and produces hypothesis h E H without using any additional information such as prior knowledge of the outlier transfer exponent, the minimax lower bound 4.3 is achievable. To accom- plish this, adapt the procedure introduced in Hanneke & Kpotufe (2019). Let d > and define
du log log(8/0)
An
128
n
Consider the following procedure:
Define h hg if Ryn (hs) R (br) Anrs
otherwise, define h- hrg
(4.4)
Theorem 4.6. Let H. be hypothesis class with finite VC dimension du 3. Further- more, let (Ho,Hi.s a) and (po, a1) denote a source and a target problem. Suppose that there are no, ngg Dy i.i.d. samples from Po: M1,5 P1,s, respectively. Let du, ô > O, Eo
V 128 dr log nottog((//))) Moreover, suppose that there exist r 2 ED, Cplr). and p(r) according to Definition 4.1. Let be the hypothesis returned by Procedure (4.4). Then, with probability at least 1- 8g. h Harro (Ho). Furthermore, with probability at least - ôb 25 we have
Eir(1) & min EiT((is,,) C. A C. C.A
(4.5)
where C' e (0, oo) is a constant depending on C((r).
Proof. Consider the intersection of the following events which happens with probability at least
1- 1-8 (Devroye et al., 2013): 1) (su (h) (h) (h)l 2 2) {sup) Rys. (h) Ry (h) hEal
hell
Ang }. and helt
Since hāsa Hlomea/((H)), get Ru, (îs) Ry (h)) ANz
Rys.s (h²,a)) Therefore, we obtain
Ry,,shi Ranss (his,) s [Rp, (hs) - R (hs)]+ (R - Ran, (1is,)) s Ang-
Furthermore, we have Ryo (ha) S a + +r, which implies that
R ( R S AFG.
Hence,
Ry, (hs) R (hir;a) = Ra (fs) Rpp. (hisaa) Ru Sonr(hj.
$ (1,r(his,))
A
(4.6)
8

---

Published as a conference paper at ICLR 2024
Now if Rys,r (hs) Rys,r (Prr), we get
R (hs) Rys. (HT) s
R (hs))(s)) Rys. R Rus, (hT) s Anr
which shows that the constraint in Procedure (4.4) holds, implying that h = his and the upper bound (4.6) holds for (h.) Rps,7 (h) On the other hand, if R (hg) ( then R (hT) R (hT,a) ) < Rys. (hs) - Rpr. (b),a).
So, regardless of whether h hg or h hr,, the upper bound (4.6) holds for R (h) Ry (hT .a) Moreover, Since h satisfies the constraint in Procedure (4.4), we get
(hira)) )= R (h) Rys.r (fr) + Rus, (hr) Ru (hir,a) S 3eT R (h) R
which completes the proof.
OVERVIEW OF PROOF OF THEOREM 4.5 (MINIMAX LOWER BOUND)
We follow Tysbakov's method (Tsybakov, 2009) for derivng the minimax lower bound.
Theorem 5.1. Tsybakov (2009) Assume that M 2 2 and the function disi(;;)) is semi-metric.
Furthermore, suppose that (Ilg, J0,e0 is a family of distributions indexed over a parameter space, O and O contains elements o, 01..... BM such that:
(i) dist(O,;0) 0,) 2 28 0, VOsicjsM
(ii) II No: V 1,... M, and J Ey (IL( 7og M with 1/8 and y 11 -e, = 0, 0,1,..., M and Dai denotes the KL-divergence.
Then, we have inf sup (diiti 0, 6c
M 1+VM 1
11-27- 27
27 log M
We also utilize the following proposition for constructing a packing of the parameter space. Proposition 5.2. GGilbertVVarshane bound) Let d 2 8. Then there exists subset TM. of {11,+1) such that do = (1, 1),
d
dist(aj, σk) 2 zg vOsj<k sosjsks M and M 2 24/8 where dist(o, o') card(i [m] (i) di)) is the Hamming distance.
First note that
min [ +
d#
dH nr
1 s 2 min( max [A,
dip 3p
dip $ n2
ns
ns
dx +
dx
max (min
min
ni
ToT
'1T
So it sufficess to show that the minimax lower bound is larger than both min (
dx
20, (
and
ng
min A, dx ) We divide the proof into three parts:
Minimax lower bound is larger than min ( dz 20 dxx b for du 17 (see Section C.I). nī.
Minimax lower bound is larger than min ( (dy 1.
di for 16 2 dx 2 3 (see Section Fig
C.2).
Minimax lower bound larger than min A dx ) (see Section C.3).
In each part, Following Theorem 5. we construct a family of pairs of source and target distributions that belong to the class Fz. To accomplish this, we pick some points from the domain X' shattered by the hypothesis class 7/ and then define appropriate distributions on these points. Additionally, metric space using
this family of distributions is indexed by d which can be treated the Hamming distance. To meet the requirement of condition (i) in Theorem 5.1, is necessary for these indices to be well-separated, condition that can be satisfied through utilizing Proposition 5.2.

---

Published as a conference paper at ICLR 2024
REFERENCES
Sulaiman Aburakhia, Tareq Tayeh, Ryan Myers, and Abdallah Shami. A transfer learning framework for anomaly detection using model of normality. In 2020 11th IEEE Annual Information Tech- nology. Electronics and Mobile Communication Conference (IEMCON), pp. 0055-0061. IEEE, 2020.
Jerone Andrews, Thomas Tanay, Edward Morton, and Lewis D Griffin. Transfer representation- learning for anomaly detection. JMLR, 2016.
Shai Ben-David and Michael Lindenbaum. Learning distributions by their density levels: A paradigm for learning without a teacher. Journal of Computer and System Sciences, 55(1):171- 182, 1997.
Shai Ben-David, John Blitzer, Koby Crammer, and Fernando Pereira. Analysis representations for domain adaptation. Advances in neural information processing systems, 19, 2006.
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wort- Vaughan. A theory of learning from different domains. Machine learning, 79(1-2):151-175. 2010.
Gilles Blanchard, Gyemin Lee, and Clayton Scott. Semi-supervised novelty detection. The Journal of Machine Learning Research, 11:2973-3009, 2010.
Katherine Bourzac. Diagnosis: early warning system. Nature, 513(7517):S4 S6, 2014.
Adam Cannon, James Howse, Don Hush, and Clint Scovel. Learning with the neyman-pearson and min-max criteria. 2002.
Raghavendra Chalapathy, Aditya Krishna Menon, and Sanjay Chawla. Anomaly detection using one-class neural networks. arXiv preprint arXiv:1802.063360 2018.
Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál. Impossibility theorems for domain adaptation. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, pp. 129-136. 136. JMLR Workshop and Conference Proceedings, 2010.
Lue Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, vol- ume 31. Springer Science & Business Media, 2013.
Steve Hanneke and Samory Kpotufe. On the value of target data in transfer learning. In Advances in Neural Information Processing Systems, pp. 9867 9877, 2019.
Steve Hanneke and Samory Kpotufe. A no-free-lunch theorem for multitask learning. The Annals of Statistics, 50(6):3119-3144 2022.
Tsuyoshi Idé, Dzung T Phan, and Jayant Kalagnanam. Multi-task multi-mode models for collective anomaly detection. 2017 IEEE International Conference on Data Mining (ICDM), pp. 177- 186. IEEE, 2017.
Shijoe Jose, Malathi, Bharath Reddy, and Dorathi Jayaseeli. A survey on anomaly based host intrusion detection system. In Journal of Physics: Conference Series, volume 1000, pp. 012049. IOP Publishing, 2018
Seyed Mohammadreza Mousavi Kalan, Mahdi Soltanolkotabi, and A Salman Avestimehr. Statis- tical minimax lower bounds for transfer learning in linear binary classification. In 2022 IEEE International Symposium Information Theory (ISIT), pp. 282 287. IEEE, 2022.
Ayush Kumar and Teng Joon Lim. Edima: Early detection of iot malware network activity using machine learning techniques. In 2019 IEEE 5th World Forum Internet of Things (WF-loT)), pp- 289-294. IEEF, 2019.
Erich Leo Lehmann and EL Lehmann. Testing statistical hypotheses, volume 2. Springer, 1986.
10

---

Published as a conference paper at ICLR 2024
Qi Lei, Wei Hu, and Jason Lee. Near-optimal linear regression under distribution shift. In Interna- tional Conference on Machine Learning, pp. 6164-6177 PMLR, 2021.
N Malini and M Pushpa. Analysis on credit card fraud identification techniques based on knn and outlier detection. In 2017 third international conference on advances in electrical, electronics, information, communication and bio-informatics (AEEICB), pp. 255-258. IEEE, 2017.
Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. arXiv preprint arXiv:0902.38:: 33300, 2009.
Mohammadreza Mousavi Kalan, Zalan Fabian, Salman Avestimehr, and Mahdi Soltanolkotabi. Min- imax lower bounds for transfer learning with linear and one-hidden layer neural networks. Ad- vances Neural Information Processing Systems, 11119999-9999 2020.
Wolfgang Polonik. Measuring mass concentrations and estimating density contour clusters-an ex- cess mass approach. The annals of Statistics, pp. 855-881, 1995.
Philippe Rigollet and Xin Tong. Neyman-pearson classification, convexity and stochastic con- straints. Journal of Machine Learning Research, 2011.
Bernhard Schölkopf, John C Platt, John Shawe- Taylor, Alex J Smola, and Robert C Williamson. Estimating the support a high-dimensional distribution. Neural computation, 13(7):1443-144 2001.
Clayton Scott. A generalized neyman-pearson criterion for optimal domain adaptation. In Algorith- mic Learning Theory, pp. 738-761. PMLR, 2019.
Clayton Scott and Robert Nowak. A neyman-pearson approach to statistical learning. IEEE Trans-
actions on Information Theory, 51((1):3806-3819 2005.
Ingo Steinwart, Don Hush, and Clint Scovel. A classification framework for anomaly detection. Journal of Machine Learning Research, 6(2), 2005.
Yueyang Su, Di Yao, and Jingping Bi. Transfer learning for region-wide trajectory outlier detection. IEEE Access, 2023.
Alexandre B Tsybakov. On nonparametric estimation of density level sets. The Annals of Statistics, 25(3):448-96 1997.
Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer series in statistics. Springer, Dordrecht, 2009. doi: 10. 10.1007/b13794.
Tailai Wen and Roy Keyes. Time series anomaly detection using convolutional neural networks and transfer learning. arXiv preprint arXiv:1905. 13228, 2019.
Yanshan Xiao, Bo Liu, Philip S Yu, and Zhifeng Hao. A robust one-class transfer learning method with uncertain data. Knowledge and Information Systems, 44(2):407 2015.
Ziyi Yang, Iman Soltani Bozchalooi, and Eric Darve. Anomaly detection with domain adaptation. arXiv preprint arXiv:2006.0366 2020.
Yefeng Zheng, Maciej Loziczonek, Bogdan Georgeseu, S Kevin Zhou, Fernando Vega-Higuera, and Dorin Comaniciu. Machine learning based vesselness measurement for coronary artery segmen- tation in cardiac volumes. In Medical Imaging 20/1: Image Processing, volume 7962, pp. 489-500. Spie, 2011.

---

Published as a conference paper at ICLR 2024
A APPENDIX A (EQUIVALENCE OF POPULATION PROBLEMS)
We begin by stating Neyman-Pearson lemma (Lehmann & Lehmann, 1986) for deterministic tests. In the following, classifier h X {0, 1} aims at classifying Ho μo against the alternative H1 f1. In the context of hypothesis testing, h is called deterministic test. Moreover, Rya (h) and 1 Rp, (h) are called size and power, respectively.
Theorem A.1 (Neyman-Ba #leyman-Pearson Pearson Lemma (Lehmann & Lehhann, 1986)). Let po and μr be proba- bility distributions possessing densities po and pı respectively with respect to dominating measure v.
(i) Sufficient condition for an optimal solution of the optimization problem (2.1). Let h be a classifier for Ho po against the alternative H1 f1 such that for a constant À the followings hold
Ruo (h) =a
(A.1)
and
(1 when pi(x) 2 Apo
Mxx) = -1 when Pı(x) < (x)
(A.2)
Then h is an optimal solution of (2.1).
(ii) Necessary condition for an optimal solution of the optimization problem (2.1). Suppose that there exist a classifier h and a constant À such that (A.1) and (A.2) hold. Then, any solution of (2.1), denoted by h", satisfies the following a.s. V
h- (<x)= when pı pı(x) > )po(x) when pi(x) < >po(x)
(A.3)
h² also satisfies Ra (h²)== =a a unless there exists classifier h' with Rpo (h') <a and Rys (h') = 0. Remark A.1. To obtain solution of the optimization problem (2.2 ) in the source (or (2.3) in the target) it suffices to take the level set L (CX in the target) whose measure under μm is a, and then define a classifier h h igg in the source (h 1cg, in the target). Obviously, the classifier satisfies (A.I) and (A.2), and therefore it is an optimal solution.
Proposition A.2. Suppose that there exist classifier h with h= 1 on (x: (c:pp<x)= = 0} a.s. and constant À such that (A.1) and (A.2) hold for h. Then any solution of (2.1), denoted by h", such that h" 1 on {I: p0(2)= = =0} a.s. v and Ryo (hr
satisfies (A.2) a.s. V.
Proof. Let S₁ = fx: : (x) h(x)), S2 = (x : 11" (x) + M(x), (x) # (po())), Sa {x he (x) (x).,1(1)) = {p)(=)). By Neyman-Pearson Lemma part (ii), know that v(82) 0. Moreover, we have
a= f ht podv
SS. 11" podov+++ + f
Jsa 1e" h'podu+ + Sss
{ h"" hopo
Since v(S2) O, we conclude that Js, h² podv O. Furthermore, on Sy we have h = and h h². So h on S3 and Ss, h² 1ppod = O. Hence,
Ssp h' ''podd= Sa. hpody
On the other hand, we have
f hpodv=
SS. hpodv+
Ss hpody + Sa. hppdy
[ hpndd
= +
JSs
Therefore, Ss, hp fs, Podv= = O, because = on Sz. We claim that (Sa)) By contradic- tion assume that v(Ss) > 0. First we show that Po is positive on S3 a.s. v. The reason is that on S3 we have h = 1 and h # h". In addition, for x satisfying po(x)= O. we have h(z)) = h² (x) 1 a.s. v. Therefore, po must be positive on S3 a.s. v. However, we have Ss, Podv = which cannot be true since v(5)) 0 and Pn > 0 a.s. 2/ on Sy. Hence, we conclude that v(aa) = Finally, we obtain that uS2 u 83) O. where 5g u {ar: h" (x)) hx)))
12

---

Published as a conference paper at ICLR 2024
Remark A.2. Proposition A.2 implies that _ (a) in Definition 3.5 is unique a.s.
Now we are ready to prove Proposition 3.6 in Section 3, which characterizes equivalent source and target. First we show the following technical lemma.
Lemma A.3. Suppose that a is achievable. If a < 1, then (2.2) cannot have any other solution with Ry (h) and Rys. (h) 0.
Proof of Lemma A.3. By contradiction, suppose that there exists an optimal solution h1 of (2.2) with Boo (hi) < a and Rys.s (h1) Furthermore, let (*) Since both h and h1 are optimal solutions of (2.2),
have R (h) R (h1)
By Neyman-Pearson Lemma part (ii),
know that fu = f2 on {x (x) + Ap1.s(z)) a.s. Let us define the sets S1 {x: fx (x) h(x)) and S2 = {x Po(2) )p).s(z)}- Then we have S1 c S2 a.s. v. Since h = 1 on S2, we must From R (h) Ryn.s (h1) 0 conclude that (1.s(S1)
have h1 0 on S1
0 and
conclude that (S() 0. Let Si {a E S1 (2) 0}. Hence Ho (S())) and v(S)) > 0. Then, let us define the set A = {a a & S (1.sss(()) = 0}. We have
from Ru (h1) Ryg (h)
(1,s(S() SS pl S S/ Pi, 0.
Since p 0 on S AA, we conclude that (SS\AA) which implies that v(A) 0. On A. Pi.s = and Po > and a.s. v. Hence, we should have which implies that (0 (a)) 1. However, we assumed that < 1.
L
Proof of Proposition 3.6. (Sufficiency) Suppose that L (a) E (4) X2o a.s. v. Due to Neyman- Pearson Lemma part (i), (a) is an optimal solution of (2.2). Let 1 e U be any arbitrary optimal solution of (2.2). First we consider the case that R (1 ) 0 (or the power of h in the source problem is less than 1). By Neyman-Pearson Lemma part (ii) have Ryo (h3) a. Then by Proposition A.2, h
1l (a) a.s. We claim that h is optimal solution of (2.3). Since L (a) ε { xxo. there exists Z3 such that (a) = CJ a.s. v. Hence, 2o(( = a and 1 cy an optimal solution of (2.3). Furthermore, h (1(((a)) lcp a.s. which implies that h an optimal solution of (2.3).
If Rpp. (h3) and Ryo (h+) a. would be similar to the previous case. Furthermore, by Lemma A.3, we cannot have a solution S with R (hr) ) O and Ryo (12) <...
(Necessity) Suppose that any optimal solution of (2.2) is also optimal solution of (2.3). Since (a) an optimal solution (2.2), we conclude that also an optimal solution of (2.3). Since Rpo (a)) = a, by Proposition A.2 and achievability, IgT(a) (()) a.s. v. Therefore, L (a) = (a) a.s. v and (a) (ET) 0s a.s. V.
J
A.3 EXAMPLE CORRESPONDING TO FIG 3
Example A.4. Let be the Lebesgue measure, and U be all the measurable 0-1 functions on R. Furthermore, let fi,s ~ Unif[1, [1,2] PI. Uni I. and
r
~2
(o(x) =
1
2
=x
0<I52
Then, we have (a = CT = -2) too). Consider the hypothesis 1 (zel 2.21)
which is a solution in the source but not in the target. However, source is equivalent to target under 4r
13

---

Published as a conference paper at ICLR 2024
B APPENDIX B (OUTLIER TRANSFER EXPONENT)
B.1 PROOF OF PROPOSITION 4.2
1.1] where A₂ > A 0, 6 0, 4 < 1, 24p- -1> 1 and A (26 - - - A2(2 26g) Moreover, H (1xx)c.1])/bb (4) : lo a a 1,4, b (o). Let a -Ho[(6. 1]) and r < (
Proof. Let 140 ~ (N 1). M1. 4[0,1], Pr. A (1, 26g - -
1,40]) -a. Clearly by Neyman-Pearee Pearson Lemma the unique source and target optimal solutions are Mg.a = 1 [tosas1)- Then for any h with Ryo (h) & +r, h is of the form h [[aa[a.1jubb.e for some [lo.1] 1] and b [2tg- 1, Hence, Rys.s (h) R (ho,,)
b 21o and R (h) Rui. (h A2 b 2to) which implies that p(r) 1. However, if we take h (216-11- 1-csusto) (z) for small enough 0 (1--)) which violates the condition R,,, (h) + (4.2) does not hold for any p co.
A1
C APPENDIX C: PROOF OF THEOREM 4.5 (LOWER BOUND)
C.I MINIMAX LOWER BOUND IS LARGER THAN min min(( # des FOR dH 17
Let d = du - and du be odd (If du is even then define d du - 2). Then pick du points S= (z0, F1,1, F1.......,,1, 1 22,1 22.43 from X' shattered by H (if du even then we pick du points). Moreover, let H be the projection of onto the S with the constraint that all h H classify zo O.
Next we construct a distribution 1i0 and a family of pairs of distributions (nī,s: indexed by E (-1,+1)š, In the following, we fix = er min (( determined.
dis ng
dd )å} for constant ei 1 to be
Distribution No: We define No on S as follows:
2a for i= 1,
po(x),)) = =0(
and po(x0) 11 22.
Distribution "i,7: We define ni,r on S as follows:
(x1.) (a:/2) é for i= 1, 1,...
d
2
(12()))) (a./2) c for i 1, 1,. 2
and 11 (mr) = 0.
Distribution vi.s: We define ni,s S follows:
1
e
d
(11,) (0,/2)
d for i 1,...
d
2
1
e
d
(12))
(a./2).
for i 1, 1,... 2
and pi, (xo)
Verifying the transfer distance condition. For any o & [-1,+1] let h E H. be the minimizer of Ryg, and Ryg,, with type-I error w.r.t. oo most a. Then h satisfies the following:
ho(11,) = (x :0
[1
d if for i= 1, 1,... 2 otherwise
14

---

Published as a conference paper at ICLR 2024
2a For any h H with 2a < po(h) <a d we have
k
11r = =) 11 1)=
d c
k
11,s(ho 1) - -
m1
c
d
for some non-negative integer & 5 also satisfied for h H with (h) s d' In this case we have
2. So the outlier transfer exponent is with Cp 1. The condition
kge
Ml, (ho 1) - 1lz (h =
+
2d
k1
Mig (h. 1) - 1 ( 1)
d
2d
for some integers k 1 and 22 s d. Using inequality (a b)* 2 (a + b²) the condition can be easily verified.
Reduction to a packing. Any classifier π S - {0,1) can be reduced to a binary sequence in the domain {-1,+1}². We can first map h to (i(z1,1), h(. ((., (2,2,))...., 0,,,,, )) and then convert any element 0 -1 We choose the Hamming distance as the distance required in Theorem 5.1. By applying Proposition 5.2 we can get subset of {-1.+1} with |2] M 24/16 such that the hamming distance of any two a,a' E is at least d/16. Any a, o Σ can be mapped to binary sequences in the domain [+1,-1] by replicating and negating, i.e., (a,-o), (a', e (+1,-1) and the hamming distance of resulting sequences in the domain [+1,-1} is at least d/8.
Then for any à H with (o = 1) a+ 20 binary sequence of h and the domain -+1, o is at least d/8 then we have
a and o E, if the hamming distance of the corresponding
P1, (he =1 M1,r(h 1) d
In particular, for any a, o E. we have
E
MI.T (ha 1) M1,T = 1) d
KL divergence bound. Define II, (f ( For any a E, our aim is to bound the KL. divergence of II, HTg. We have
D (T, ns. (Hs(siss) nr. (
The distribution HT,s can be expressed as P& pypx where PX is uniform distribution over the set (1, 5) and Prixas is Bernoulli distribution with parameter 2 (a./2) c². Hence we get
1 + (d./2) .co) Ber( v + (aa/2)) -)0) Ber( (eer 2
Da(uissluiss)
DEi
1-1 d/2
$ co
2p
4
1
dx
$ - c0o
4
d
2
(C.I)
ng.
for some numerical constant cp. Using the same argument we can obtain D (u ( s coot
Hence we get
(I, 2c0eid.
15

---

Published as a conference paper at ICLR 2024
Then, for sufficiently small 6₁ get (I((I, & log M which satisfies condition (ii) in Proposition 5.1.
Therefore, for any learner that outputs hypothesis from {h e H: (o(h) s a+ 2a with probabil- du
ity 1- dg. there exist M1,5; H1,T) (r ax 1, A) such that condition on (h E H. po s
2e we have + dyg
e-min(A > min(4
dz (
dz ) (
P Soo S SpLT which implies that the unconditional probability is follows
20 d
ns
nrr
(Eax((1)> > c. --mi A
dx ng
de )&} 2 (1 -11-80 50) 2d
Spg: SSSL
C.2 MINIMAX LOWER BOUND IS LARGER THAN min (
d2z ns
* ) FOR 16 2 dx 2
Pick three points S = foro, x2) from X' shattered by H. Then we construct a distribution μo and two pairs of distributions (ui,s; pi.r) for k 11 Also fix ei min m ( for constant C₁ 1 to be determined.
Distribution No: We define 4o on S as follows:
(o(#o) 1 2a, Mo(x1) =o(0))
Distribution ,i.ri We define vi, on S as follows:
k 2 2
(x)) O, (1)) 2 (()((2))
&
Distribution pi.s: We define p4,s S follows:
1 k (ro) 0, (x1) - e,, (1))(12) Let II, = (ph.s) ))2 x (m ) where e is numerical constant. Furthermore, let h& be the optimal solution with type-I error most a for the distributions (Ho. (i,)),,s) and (N4, (²,r) is easy to see that Ry (h-x) - R, (hx) 6.
k 2
c
" for k -1,, Then using the same argument we get D (ILi
Using Le Cam's method we get that for any h chosen from Ha {h H. mo(h) + 2a there exist (Ho, M1.1) Fre a. 1,0) such that
P Soo Sui, SuL.
(h,r(h) min{(
_
)
) 2d
nn
nT
Since du 5 16 we conclude that
P Spo S S
Ei.r (h)
min(( ns
dH
) t
) 2
mr
some numerical constants c, c,
C.3 MINIMAX LOWER BOUND IS LARGER THAN min A,
de )
We only show it for the case where du 17. The other case follows the same idea in Section C.2.
We follow the same idea in the previous part. Let min(A, ( (dw ) and pick the same set from X' shattered by H construct the distributions on S follows:
16

---

Published as a conference paper at ICLR 2024
Distribution μo: We define Ni S follows:
po(21,) = (0(22,) d for i= 1, 1,... 2
and po(zo) = 1 2o..
Distribution vÎ,r: We define Mî, on as follows:
(1))) + (a:/2)
d for i= 1, ...
2
(x2,)) (0:/2) for i 1 ..... 2
and (z)) O.
Distribution 1i,s: We define wis on S as follows:
(Ls(())) a (1/2) "
for i= 1, 1,.... d
(1,( (1/2) for i= 1
d
and (z))
Note that unlike previous part, all the distributions 1 are the same for different o's.
Verifying Ei,r(h%, s A. For every pair of (4q,s.1.,1 we have
d
(1 s 2 d SA
verifying the transfer distance condition and reducing to packing parts follow the same idea. We just bound the corresponding kL-divergence.
KL divergence bound. Define IT (Hi (MT We have
(II n. (RI nr (T(()),
Since source distributions are the same, the first term is zero. Following the same argument we get
(iili, s coc s coc
where co is the same numerical constant used in (C.1). Then for sufficiently small e get Dua (Tl s log M which satisfies condition (ii) in Proposition 5.1.
17


Reviews:
[{"review_id": "3mz5oDu1Eg", "reviewer": "Reviewer_Ag52", "summary": "The paper adopts the traditional framework of Neyman-Pearson classification to formalize supervised outlier detection of transfer learning. The added assumption is that one has access to some related but\nimperfect outlier data. The authors first determine the information-theoretic limits of the problem. Next, they also show that, in principle, these information-theoretic limits are achievable by adaptive procedures.", "questions": "1. If the size is large, will the results have special asymptotic properties?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "1. The outlier detection in transfer learning is an interesting and valuable topic in the learning community.\n\n2. The literature part is very clear.\n\n3. The structure of the paper is easy to follow.\n\n4. The setup of the paper is clear\n\n5. The paper provided solid theoretic results on the minimax bounds and rates.", "weaknesses": "1. Only finite-sample results are provided. There is no further analysis of asymptotic properties on the large dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bqgWuDXLDr", "reviewer": "Reviewer_3fJQ", "summary": "This paper provides a rigorous theoretical analysis of transfer learning in outlier detection. It first considers a simplified setting in which the optimal outlier classifier is the same between source and target distributions to illustrate how outlier detection differs from standard classification. The paper then addresses the much more difficult setting in which the outlier classifiers could differ, proposing an adaptive algorithm with a theoretical guarantee.", "questions": "See \"weaknesses\".", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The paper is very well-presented.\n- The theory is compelling and elegant.\n- I think that the \"same optimal classifier\" setting between source and target distributions seems unrealistic (e.g., the setting of Figure 1) but I can see why from a theoretical standpoint, analyzing this simpler setting is a good starting point and already there are interesting insights, especially in contrasting this outlier setup to traditional classification.\n- The extension of the transfer exponent to the outlier setting is a valuable contribution.", "weaknesses": "- As far as I can tell, this paper does not actually follow the ICLR LaTeX template. For instance, the margins don't appear correct? Please fix this.\n- There are no numerical experiments. I think this paper would improve dramatically with experimental results, especially on real data, and especially on showing how well the adaptive method in Section 4.8 works in practice.\n- Detailed discussion of how applied researchers address this outlier transfer problem in practice would be helpful to provide some point of reference (even if these existing approaches lack guarantees): for instance, even getting a rough understanding of whether there are common conceptual ideas used would be helpful or if actually the methods are just completely different (if so, maybe some discussion of what the key conceptual differences are would be helpful).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kIf8Z90x15", "reviewer": "Reviewer_kTQ3", "summary": "This paper studies the outlier transfer problem, that is, the problem of transfer learning under the setting of outlier detection or rare class classification. The objective of the Neyman-Pearson classification problem, which formalizes the rare class classification problem, is to achieve low classification error on the rare class, while keeping the classification error on the common class under a threshold. However, in practice, we usually have only limited amount of or even none data from the target rare class, but some data from a related source rare class. This is where transfer learning comes into play. The goal of this paper is to theoretically understand when and how the knowledge from a source class can improve the classification performance on a target class under the setting of rare class classification.\n\nThe authors first show that at the population level, under certain assumptions, all the solutions to the source Neyman-Pearson classification problem are also solutions to the target Neyman-Pearson classification problem. Then the authors turn their attention to the finite-sample setting. The authors first define the outlier transfer exponent, which is a notion of discrepancy between source and target under a hypothesis class. With that discrepancy, the authors give a minimax lower bound on the target-excess error, which measures the difference between the expected error of the solution obtained by transfer learning and of the optimal solution. Furthermore, the authors propose an algorithm that does not need any prior knowledge of the discrepancy between the source and target class distributions.", "questions": "There are several typos, including:\n\n(1) Page 4, in the 5th line in Section 3, the source and target problem are denoted by the same notation.\n\n(2) Page 4, in the last line, the LHS and RHS of the second to last inequality are the same.\n\n(3) Page 6, in the 5th line in Section 4.3, $n_S$ should be $n_T$.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The paper studied an important practical problem.", "weaknesses": "(1) A lower bound on the target-excess error is not as informative as an upper bound. Is it possible to derive an upper bound on the target-excess error under appropriate conditions?\n\n(2) The algorithm proposed in Section 4.8 requires as input the VC dimension of the hypothesis class. However, in practice, the exact VC dimension may be unknown. Could you please give some practical suggestions on using this algorithm when the exact VC dimension is unknown?\n\n(3) The notation in inequality (4.1) is a little redundant. Since $h_{S, \\alpha}^*$ is a solution to the source problem, the difference between the expected error of any $h$ in the hypothesis class and of $h_{S, \\alpha}^*$ w.r.t. the source distribution must be non-negative. So, there is no need to use the max function.\n\n (4) The theoretical results mainly rely on the previous techniques.\n\n(5) There is no experiment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)