Transformation-Invariant Learning and Theoretical Guarantees for OOD Generalization
Authors: Omar Montasser
Han Shao
Emmanuel Abbe
Venue: NeurIPS 2024 poster (2024)
Keywords: pac learning guarantees
theory for distribution shifts
sample complexity
ood generalization
vc dimension
Primary area: learning_theory
TL;DR: We initiate a theoretical study for learning under distribution shifts when the shifts are captured by a collection of data transformation maps.

Abstract: Learning with identical train and test distributions has been extensively investigated both practically and theoretically. Much remains to be understood, however, in statistical learning under distribution shifts. This paper focuses on a distribution shift setting where train and test distributions can be related by classes of (data) transformation maps. We initiate a theoretical study for this framework, investigating learning scenarios where the target class of transformations is either known or unknown. We establish learning rules and algorithmic reductions to Empirical Risk Minimization (ERM), accompanied with  learning guarantees. We obtain upper bounds on the sample complexity in terms of the VC dimension of the class composing predictors with transformations, which we show in many cases is not much larger than the VC dimension of the class of predictors. We highlight that the learning rules we derive offer a game-theoretic viewpoint on distribution shift: a learner searching for predictors and an adversary searching for transformation maps to respectively minimize and maximize the worst-case loss.

Transformation-Invariint Learning and
Theoretical Guarantees for OOD Generalization
Omar Montasser Yale University omar monaasseassee............ edu
Han Shao Harvard University han@ttic. edu
Emmanuel Abbe EPFL and Apple emmanuel. www.ueeelaabe@@p.....m.
omar
Abstract
Learning with identical train and test distributions has been extensively investigated both practically and theoretically. Much remains to be understood, however, in statistical learning under distribution shifts. This paper focuses on distribution shift setting where train and test distributions can be related by classes of (data) transformation maps. We initiate theoretical study for this framework, investi- gating learning scenarios where the target class of transformations is either known or unknown. We establish learning rules and algorithmic reductions to Empirical Risk Minimization (ERM), accompanied with learning guarantees. We obtain upper bounds on the sample complexity in terms of the VC dimension of the class composing predictors with transformations, which we show in many cases is not much larger than the VC dimension of the class of predictors. We highlight that the learning rules we derive offer a game-theoretic viewpoint distribution shift: a learner searching for predictors and an adversary searching for transformation maps to respectively minimize and maximize the worst-case loss.
Introduction
It is desirable to train machine learning predictors that are robust to distribution shifts. In particular when data distributions vary based on the environment, or when part of the domain not sampled at training such in reasoning tasks. How distribution from which the training examples are drawn from? A common challenge that arises when tackling out-of-distiibution generalization is capturing the structure of distribution shifts. A common approach is to mathematically describe such shifts through distance or divergence measures, in prior work domain adaptation theory [e.g., [edko et al. 2020 and distributionally robust optimization [e.g.. Duchi and Namkoong (2021].
train predictors that generalize beyond the
In this paper. we forward new formulation for out-of-distribttion generalization. Our formulation offers a conceptually different perspective from prior work, where we describe the structure of distribution shifts through data transformations. We consider unknown distribution D over X x Y which can be thought of as the "training" or "source" distribution from which training examples are drawn, and collection of data transformation maps T {T X X3} which can be thought of as encoding "target" distribution shifts, hence denoted as (T(D))ren We consider a covariate shift setting where labels are not altered or changed under transformations E T, and we write T(D) for notational convenience. Our goal, which will be formalized further shortly, is to learn a single predictor h that performs well uniformly across all distributions (T(D))
We view this formulation as enabling a different way to describe distribution shifts through transfor- mations T (T: X + X). The collection of transformations T can be viewed as either: (a) given to the learning algorithm as part of the problem, or (b) chosen by the learning algorithm. View (a) represents scenarios where the target distribution shifts are known and specified by some downstream application (e.g., learning a classifier that is invariant to image rotations and translations). View (b)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

represents scenarios where there is uncertainty or there are no pre-specified target distribution shifts and we would like to perform maximally well relative to an expressive collection of transformations. We highlight next several problems of interest that can be captured by this formulation. We refer the reader Section for a more detailed discussion in the context of prior work.
Covariate Shift & Domain Adaptation. By Brenier's s theorem |Benier 1991 when X' = RR, then under mild assumptions, for any source distribution over X and target distribution Q over X, there exists transformation T X' + X' such that Q = (P).. Thus, by choosing an expressive collection of transformations T. we can address arbitrary covariate shifts.
Transformation-Ilvariaa Learning. In many applications, it is desirable to train predictors that are invariant to transformations or data preprocessing procedures representing different "environments" (c.g.. an image classifier deployed in different hospitals, or self-driving car operating in different cities).
Representative Sampling. In many applications, there may be challenges in collecting "represen- tative" training data. For instace, in learning Logic or Arithmetic tasks [Abbe et al. 2023). the combinatorial nature of the data makes it not possible to cover well all parts of the domain. E.g., there is always a limit to the length of the problem considered at training, or features may not be homogeneously represented at training (bias towards certain digits etc.). Choosing suitable collection of transformations T under which the target function is invariant can help to model in such cases.
Adversarial Attacks. Test-time adversarial attacks such as adversarial patches in vision tasks [Brown et al., 2017 Karmon et al. 20188) attack prompts in large language models (Zou et al.] 2023], and "universal attacks" " [Moosavi-Dezfooli et al. 2017 can all be viewed as instantiations
constructing specific transformations T.
Our Contributions. Let X' be the instance space and = [+1} the label space. Let H. C y be hypothesis class, and denote by ve(H) its VC dimension. Consider collection of transfor- mations T = T(TT= X' + } and some unknown distribution D over X' x y. Let err(h, T(D)) Pr(ny)= (x)) + y] be the error of predictor on transformed distribution T(D).
Given training sample S = ((11, vI),.., (Jm, D we are interested in learning predictor h with uniformly small risk across all transformations T E T. Formally,
sup err(h, verhh,T(D) T(D)) < OP + tE, where OPT := inf sup (err(h" T(D))) h ETE
(1)
rer
This objective is similar to that considered in prior work on distributionally robust optimization [Duchi and Namkoong 2021] and multi multi-distribution learning (Haghtalab et al. 2022). The main difference is that in this work we describing the collection of "target" distributions (T(D)) bret
as transformations of the "source" distribution D. This allows us to obtain new upper bounds on the sample complexity of learning under distribution shifts based on the VC dimension of the composition of H with T, denoted ve(H o T) (see Equation (3) We describe next our results (informally):
1. In Section (Teorem 2. we show that, given the knowledge of any hypothesis class 7t and any collection of transformations T, by minimizing the empirical worst case risk, Objective [ with sample complexity bounded by ve Furthermore, in Theorem 2.2 we show that the sample complexity of any proper learning rule is bounded from below by Ω vv H T)).
solve
2. In Section 3 (Theorem 3.I, we consider a more challenging scenario in which H is unknown. Instead, we are only given ERM oracle for H. We then present a generic algorithmic reduction (Algorithm|] [T) solving Objective Jsiin only an ERM oracle for H. when the collection T is finite. This is established by solving a zero-sum game where the H-player runs ERM and the T-player runs Multiplicative Weights [Freund and Schapire 1997].
In Section T (Theorem 4.1). we consider situations where we do not know which transformations are relevant (or important) for the learning task at hand, and so we pick an expressive collection and aim to perform well on as many transformations as possible. We then present a different generic learning rule (Equation (4)) that learns a predictor h achieving low error (say 8) on as many target distributions in [T(D)
(D)))DTe TTT as possible.
In Section (Theorems T.T
we extend our learning guarantees to slightly different objective, Objective] 7 that can be favorable to Objective I when there is heterogeneity in the noise

---

across different transformations. This is inspired by Agarwal and Zhang 2022 who introduced this objective.
2 Minimizing Worst-Case Risk
If we have access to, know, the hypothesis class H. and the collection of transformations T, then the most direct and intuitive way of solving Objective i minimizing the empirical worst-case risk. Specifically.
h E argmin max NEH TET
Σ (M(())))) + yal 1=1
(2)
We highlight that this learning rule offers game-theore theoretic perspective distribution shift, where the H-player searches for predictor h E H to minimize the worst-case error while the -pllayer searches for transformation T ' maximize the worst-case transformations T can be parameterized by neural network architectures, which is an interesting direction explore further. We note that similar min-max optimization problems have appeared before in the literature on adversarial examples and generative adversarial networks [c.g.. Madry al. 2018 Goodfellow al. 2020].
For instance, both predictors H and
We present next PAC-style learning guarantee for this learning rule which offers the interpretation that solving the min-max optimization problem in Equation 1 yields a predictor E H that generalizes the collection of transformations TT We show that the sample complexity of this learning rule is bounded by the VC dimension of the composition of H with T, where
HoT == o h E H.T T) ETTT where (h o (z) = h(T(x)) Vx X.
(3)
Theorem 2.1. For any class H. any collection of transformations T, any e, E (0, 1/2), any distribu- tion D, with probability at least over Dmlt..) where m(s, O
vo(HoT (1lo(11)) 6²
sup err err T(D) < OPT +E. TET
Proof. The proof follows from invoking uniform convergence guarantees with respect to the com- position H T (see Proposition A.1 in Appendix A) and the definition of h described in Equa- tion Let h E be an a-priori fixed predictor (independent of sample S) attaining OPT Tx inf suPrer err(h, T(D)) (or E-close to it). By setting m(=, 6) O vo(HoT))+oggl)
and
invoking Proposition A.1 we have the guarantee that with probability least over Dm),.5)
(vh H) (VT T) |err(h, T(S)) (rr s.
Since h, h² E H. the inequality above implies that
VT E T err(h, T(D)) < (rr(hT((S) + vT E T err(h", ar(h",T($)) I (((hh( +
Furthermore, by definition, since minimizes the empirical objective, it holds that
sup err(f,, T(S)) S sup err(h",T(S)) TET
TeT
By combining the above, we get
sup (r((hT(())) I sup eir err + sup (n((h",T(SS) + OPT + 2z. TET
TET
TET
We show next that ve(H T) can be much higher than vo(H) and the dependency on vo(H o T) is tight for all proper learning rules, which includes the learning rule described in Equation and more generally any learning rule that is restricted to outputting a classifier in H.
Theorem 2.2. Vk E N, 3X, H, T such that ve(H) = 1 but vo(HoT) 2 k; and the sample complexity of any proper learning rule & (X x V)* + H solving Objective 7 is at least D(ve(H T)).

---

A proof is deferred to Appendix C We remark that the sample complexity cannot be improved by proper learning rules and this leaves open the possibility of improving the sample complexity with improper learning rules. There are many examples in the literature where there are sample complexity gaps between proper and improper learning [e.g.. Angluin 1987 Daniely and Shaale-SSwwatz, [0014] Foster et al. 2018 Montasser et al. 2019 Alon et al. 2021]. In particular, it appears that we encounter in this work phenomena similar to what occurs in adversarially robust learning [Montasser et al. 2019). Nonetheless, even at the expense of (potentially) higher sample complexity, we believe that there is value in the simplicity of the learning rule described in Equation (2). and exploring ways of implementing it is an interesting direction beyond the scope of this work.
2.1 Examples and Instantiations of Guarantees
To demonstrate the utility of our generic result in Theorem 2.1 we discuss next a few general cases where we can bound the VC dimension of H composed with 7, ve(H o T)) This allows us to obtain new learning guarantees with respect to classes of distribution shifts that are not covered by prior work, to the best of our knowledge.
Linear Transformations. Consider T being a (potentially infinite) collection of linear transforma- tions. For example, in vision tasks, this includes many transformations that have been widely studied in practice such as rotations, translations. maskings, adding random noise (or any fixed a-priori arbitrary noise), and their compositions [Engstrom et al., 2019 Hendrycks and Dictterich] 2019].
Interestingly, for broad range of hypothesis classes H. we can show that vo(H T) S vo(H) without incurring any dependence on the complexity of T. Specifically, the result applies to any funetion class H. that consists of linear mapping followed by arbitrary mapping. This includes feed-forward neural networks with any activation function, and modern neural network architectures (e.g.. CNNs, ResNets, Transformers). We find the implication of this bound to be interesting, because it suggests (along with Theorem 2.T that the learning rule in Equation (2) can generalize to linear transformations with sample complexity that not greater than the sample complexity of standard PAC learning. We formally present the lemma below, and defer the proof to Appendix B
Lemma 2.3. For any collection of linear transformations T and any hypothesis class of the form H. = (f : + W E Rixd A R² + }}. it holds that ve(H T) S vv((H).
Non-Linear Transformations. Consider T being a (potentially infinite) collection of non-linear transformations parameterized by a feed-forward neural network architecture, where each T W, o o o W2 o Φ W1 and x(.) = max (0.-) is the ReLU activation function. Similarly, consider hypothesis class H. that is parameterized by (different) feed-forward neural network architecture, where each h sign oWH h o &o ....................... e W2 o Φ W, Observe that the composition H HoT T consists of (deeper) feed-forward neural networks, where h T sign oWir f o .......................... do W₂ bound ve(H o T) by appealing to classical
Wi- Wt Ø o & W₂ & o Wi. Thus, results bounding the VC dimension of feed-forward neural networks. For example, according to Bartlett et al. ( it holds that vc(H o T) < O ((Il + P> ()o))) where H/ + L is the depth of the networks in H o T and PHOT is the number of parameters of the networks in H o T (which is PH. + Pr). In this context, Theorem 2.1 and Equation (2) present new learning guarantee against distribution shifts parameterized by non non- linear transformations induced with feed-forward neural networks.
Transformations on the Boolean hypercube. The Boolean hypercube has also received attention recently a case-study for distribution shifts in Logic Arithmetic tasks(Abbe et al.] 2023)
We show next that when the instance space X = {0, 1] we can bound the VC dimension of H o T from above by the sum of the VC dimension of H and the VC dimensions of (T))
where each Ti {a + T(x); : T E T} is function class resulting from restricting transformations
T: : 1) + [0, E T to output only the 7th bit. The proof is deferred to Appendix B
Lemma 2.4. When X (0, for for any hypothesis class H and any collection of transformations T, vo(H o T) S Oloo d)) + Ei= vo(Ta)), where each T; = (a + T(x); : :T TT.).
In this context, Theorem 2.1 and Equation 2 present new learning guarantee against arbitrary distribution shifts parameterized by transformations on the Boolean hypercube, where the sample complexity (potentially) grows with the complexity of the transformations measured by the VC

---

8In dimension. We note however that this learning guarantee does not address the problem of length generalization, since we restrict to transformations that preserve domain length.
Adversarial Attacks. In adversarially robust learning, a test-time attacker is typically modeled as pertuhation function 4: X' 2x, which specifies for each test-time example x: set of possible adversarial attacks (xx) S X' that the attacker can choose from at test-time [Montasser et al. 2019]
The robust risk of a predictor h is then defined as: ((,,y)> supzee((s)
h(2)) *
On the
other hand, the framework we consider in this paper can be viewed as restricting test-time attacker to commit to a set of attacks T = {T: : + }} without knowledge of the test-time samples,
and the risk of predictor i is then defined as: suPreT (a..))> 1 [(((())) * w While less general, our framework still captures several interesting adversarial attacks in practice which constructed before seeing test-time examples, such as adversarial patches in vision tasks [Brown] al. 2017 Karmon et al.) 2018 and attack prompts for large language models (Zou al. 2023 can be represented with linear transformations.
Unknown Hypothesis Class: Algorithmic Reductions to ERM
Implementing the learning rule in Equation (2) crucially requires knowing the base hypothesis class
H. and the transformations T, which may not be feasible in many scenarios. Moreover, in many applications we only have black-box access to an off-the-shelve supervised learning method such as an ERM for H. Hence, in this section, study the following question:
Can we solve Objective T Jusing only ERM oracle for H?
We prove yes, and present next generic oracle-efficien reductions solving Objective Jsing only an ERM oracle for H. We consider two cases,
Realizable Case. When OPT = O, i.e., 3h" E H. such that VT E T crr(h",T(D)) = 0. there a simple reduction to solve Objective [ using a single call to an ERM oracle for H. The idea is to inflate the training dataset S to include all possible transformations T(S) {(T(x), y) : (x.,)) E S SATE T) (similar to data augmentation), and then run ERM on T(S). For- mal guarantee and proof are deferred to Appendix D It is also possible, via a fairly standard boosting argument, to achieve a similar learning guarantee using multiple ERM calls (specifically, Olog (T(S)) ) < O[ [T]))), where each ERM call is on sample of size O (vv(H)).. So, we get a tradeoff between the size dataset given to ERM on a single call, and the total number of calls to ERM.
Agnostic When OPT 0 0, the simple reduction above no longer works. Specifically, the issue is that running a single ERM on the inflation T(S) effectively minimizes average error over transformations T E T as opposed to minimizing maximum error over transformations T E T. So, OPT,> > 0, by definition, implies there is no predictor h E H that is consistent (i.e., zero error) on every transformation T(S),7 E T, thus minimizing average error over transformations can be bad.
To overcome this limitation, we present a different reduction (Algorithm[[ that minimizes Objective I by solving zero-sum game where the H-player runs ERM and the -player runs Multiplicative Weights [Freund and Schapire| 1997). This can be viewed as solving a sequence of weighted-ERN problems (with weights over transformations), where Multiplicative Weights determines the weight of each transformation.
Theorem 3.1. For any class H. collection of transformations T, distribution D and any E (0, 1/2). with probability least 8 over S ~ D)m(e,), where m(c, 5) S O (ob(H))) running n
g2
Algorithm 1 on S for R 2
rounds produces h = Er= hp satisfying
E
Pr [ht # vl < OPT +E. r-inif (1...)).
(2,))D
Remark 3.2. When T is a finite collection of transformations, we can bound vo(H o T) from above by Ovv(HH) + log (T) using the Saner-Shelah-Pereee Lemma [Sauer 1972]. See Lemma B. and proof in Appendix B
5

---

Algorithm 1: Reduction to Minimize Worst-Case Risk
Input: Black-box ERMH, dataset S {(11 211...1).................. (Ims Fmm and transformations T. For each 7 E T, set Q1 (T) = [T]
Set number of rounds R 8 [
for 1 S r < Rt do
Run ERMy on Mgax i..d. samples drawn from the distribution induced by Qr over T and Unif (S), and let h, denote its output.
For each 7 E T, update Qr+1 (T) Q.12)) -10- where Z, is a 2,
normalization factor such that Q++1 is a distribution.
Output: R Σ hr-
Proof of Theorem 3.1 Let S = (æ1. VI)...,, }m)} be an arbitrary dataset. By setting R
8lu|7| and invoking Lemma D.2, which is a helpful lemma (statement and proof in Appendix D
that instantiates the regret guarantee of Multiplicative Weights in our context, we are guaranteed that
Algorithm produces a sequence of distributions Qı,..., QR over T that satisfy
1 R
Σ
(hr, T(S))
1 Σ
E T~Q.
err(hr, T(S))
TET
At each round r, observe that Step 4 in Algorithm | draws an i..d. sample from a distribution P. over X' x ) that is defined by Qr over 'I and (S). and since ERMy is an (e, aln.taagnntiicPA--lleeee for H. Step guarantees that
B err(hr, T(S)) T~Q,
E T~Q
Σ 1 (h-(T(zs)) # #u
min E err(h, T(S) + c min max maxxerr(h", (oxxerr""TT(s))) hEM NEMT-Q.
EMEM TET
Combining the above inequalities implies that
n
max TET
Σ
err (h,, T(S))
S min max err(h" (h","()))))))))))))))))))(((())) + 6 h hE TET
Finally, by appealing to uniform convergence over H. T (Proposition A.I). with probability at least 1 over S D
max TET
Σ err (h,, T(D)) S max
err (h,, T(S))
min maxerr(h T(S) + K TET
< min max err(h" T(D)) + - OPT 0c te.
K. TET
On finiteness of T. We argue informally that requiring T to be finite is necessary in general when only an ERM oracle for H is allowed. For example, consider a distribution supported on a single point 5, and transformations' (z) + for all i induced by some
(z. -) on the real line where collection (T:) Calling ERM on a finite subset of these transformations T.,...., Ti, could return predictor that labels x. + 61, x + .2.....22 is with label and labels
ig 1,... with + (e.g.. H is thresholds) which fails to satisfy Objective But it would be interesting to explore additional structural conditions that would enable handling infinite T. and leave this future work.
4
Unknown Invariant Transformations
When we have large collection of transformations T and there is uncertainty about which trans- formations under-which we can simultancously achieve low error using base class H. the learning rule presented in Section 2 (Equation I can perform badly. We illustrate this with the following concrete example:
Example 1. Consider a class = (h1, h2, ha), collection of transformations T (Ti, To, Ta}. and distribution D with risks (errors) reported in the table.

---

(D)
(2(
(D)
h1
1%
1%
49%
h2
1%
49%
49%
hg
49%
49%
49%
Then, solving Objective may return predictor lig where vT E T err(hs, T(D)) 49%, since only need to compete with the worst-case risk OPT = 49%. However, predictor h is arguably better since it achieves a low error of 1% on at least two out of the three transformations.
To address this limitation, we switch to different learning goal-achieving low error under as many transformations as possible. We present next a different generic learning rule for any class H. and any collection of transformations T, that enjoys different guarantee from the learning rule presented in Section 2 In particular, can be thought of as greedy since it maximizes the number of transformations under which low empirical error is possible, but also conservative since it ignores transformations under which low empirical error is not possible. Specifically, given training dataset S, the learning rule searches for predictor h E H that achieves low empirical error on as many transformations T E T possible, say (rr (S)) S.
à E argmax NEW TET
Σ 1 (err(h, T(S)) S Ee].
Another way of thinking about this learning rule is that it provides us with more flexibility in choosing the collection of transformations T, since the learning rule is not stringent on achieving low error on all transformations but instead attempts to achieve low error on many transformations as allowed by the base class H. Thus, this is useful in situations where there is uncertainty in choosing the collection of transformations. We present next the formal learning guarantec for this learning rule, Theorem 4.1. For any class H. any countable collection of transformations T, any distribu- tion DD and any E, 5 E (0, with probability at least 8 over D where m 0 vc(HoT) log(1/e)+ then
Σ 1 TET
& 36
Σ 1 (er(((",((D))) T(D)) < =
max NE
TET
Furthermore, it holds that VT E TT err(h, T(D)) S err(h, T(S)) + Verr(h, T(S)) +
Remark 4.2. We can generalize the result above to any prior over the transformations. T, en- coded as a weight function weighted version of Equation (4) according w, holds that Σrer w(T)l (enth.c 2
[0, 1] such that Erer w(T) S 1. By maximizing the
max EH EteT w: (T) [err(h* (er(((),(()))))) ((D)) with high probability.
Proof. The proof follows from the definition and using optimistic generalization bounds (Propo-
sition A.2 By setting m(s,0 8) O ve(HoT) (eg(L and invoking Proposition A.2
have the guarantee that with probability at least 1 over S ~ Dmme..), (vh E H) E T):
err(h, err(h, ((S)) + (er(h
(5)
err(h, & err(h, T(D) + eer(h, T(D))
T(D))
+ + 3
(6)
Since h E H. inequality (4) above implies that 4T e T (h, T(S)) < then err T(D)) s 3E. Thus.
E1 e T(D) < 35
> 1 ss]
TET
TET
Furthermore, by definition, since h maximizes the empirical objective, it holds that
Σ TET
(er T())) Se)
Σ TET
1 [err(h" T(S)) < s].

---

Since h² E H. inequality (5) above implies that AT E T if err(h"T((D)) 1 s/s then
err(h" T(S)) S Thus,
Σ
1 1er((h' (err(hI((S)) < E1 [err(h", S s/s].
TET
TET
By combining the above three inequalities,
Σ1
f e T(D)) $ 3e] 2 Σ
1 (((T(
((D)) - s/s)]
TET
TET
5 Extension to Minimizing Worst-Case Regret
When there is heterogeneity in the noise across the different distributions, Agarwal and Zhang [022 argue that, in the context of distributionally robust optimization, solving Objective 1 may not be advantageous. Additionally, they introduced a different objective (see Objective 7 which can be
favorable to minimize. In this section, we extend our guarantees for ceaiformation-invaaiian learning to this new objective which we describe next.
For each T T. let OPT, infA; err(hi. T(D)) be the smallest achievable error on transformed distribution T(D) with hypothesis class H. Given training sample $ {(11, (mm. }m)) D would like to learn a predictor h X y with uniformly small regret across all transformations i' T,
sup err T(D)) OPT S inf sup (er(h""T(DD) - OPT + TET
A EET
We illustrate with a concrete example below how solving Objective can be favorable to Objective Example 2 (Risk vs. Regret). Consider class H = {h1, h a collection of transformations (Ti, T2, T3, T4 and a distribution D such that with errors as reported in the table:
TD(D)
T2(D)
T2(D)
TA(D)
h1
0
1/8
1/4
1/2
h2
1/2
1/2
1/2
1/2
Thus, solving Objective may return predictor h2 where VT E T err(h2, T(D)) = 1/2, since we only need to compete with the worst-case risk OPT x However, solving Objective 7 will return predictor h where VT: : T
S OPTT.
More generally, as highlighted by Agarwal and Zhang 2022 whenever there exists h+ E H satisfying VT T crr(h" T(D)) OPT, < solving Objective 7 is favorable. We present next generic learning rule solving Objective ( for any hypothesis class H and any collection of transformations T,
h E argmin max NEH TET
1 [M(T(x))) + y1l - OPT
(8)
We present next a PAC-style learning guarantee for this learning rule with sample complexity bounded by the VC dimension of the composition of H with T. The proof is deferred to Appendix E
Theorem 5.1. For any class H. any collection of transformations T. any e, 6 E (0, 1/2), any distribu- tion D, with probability at least 1 å over S ~ Dmlc.6) where m(s, 8) O vo(HoT)
err (h, T(D)) 7 inf sup (err(h", T(D)) OPT + E-E
sup TET
Algorithmic Reduction to ERM. Using ideas and techniques similar to those used in Section 3 we develop generic oracle-efficient reduction solving Objective using only an ERM oracle for H. Theorem, proof, and algorithm are deferred to Appendix

---

100%
90%
99%
Text Acunty
80%
70%
707
60%
60%
50%
Invariant Permutations
50%
Invariant Permucations
Baseline
200
25
75
100
125
150
175
200
Epochs
Epochs
Figure 1: Left plot is for learning ft. the full parity function in dimension 18, with train set size of 7000. Transformations are sampled from Ti: the set of all permutations. Right plot is for learning f2- a siforrtt-of-uubparttie function in dimension 21, with a train set size 5000. Transformations are sampled from T2: permutations which fg is invariant. In each case, the test set size is 1000.
6 Basic Experiment
We present results for basic experiment on learning Boolean functions on the hypercube {=1]".
We consider uniform distribution D over [=1]² and two target functions: (1) fi(z) = II the parity function, and (2) (1x) sign(
function. We consider transformations T1, Tz under which fi, are invariant, respectively (see Section 2
() Ej= (IT 4/3 (()))))+)))
Since D is uniform, note that for any h: suprer err T)) = err(h, Dy.).
Algorithms. We use two-layer feed-forward neural network architecture with 512 hidden units as our hypothesis class H. We use the squared loss and consider two training algorithms. First, the baseline is running standard mini-batch SGD on training examples. Second, as a heuristic to implement Equation (2). we run mini-batch SGD on training examples and permutations of them. Specifically, in each step we replace correctly classified training examples in mini-batch with random permutations of them (drawn from T), and then perform an SGD update on this modified mini-batch. We set the mini-batch size to and the learning rate to 0.01. Results are averaged over 5 runs with different seeds and are reported in Figure We ran experiments on freely available Google CoLab T4 GPUs, and used Python and Py Torch to implement code.
7 Related Work and Discussion
Covariate Shift, Domain Adaptation, Transfer Learning. There is substantial literature studying theoretical guarantees for learning when there "source" distribution and "target" distribution Q [see e.g., survey by Redko et al., 20200 Guinonero-Cander et al.) 2008). Many of these works explore structural relationships between P and Q using various divergence measures (e.g., total variation distance KL divergence), sometimes incorporating the structure of the hypothesis class H [e.g.. Ben-David al. 2010, [Hanneke and Kpotufe 2019]. Sometimes access to unlabeled (or few labeled) samples from is assumed. Our work difters from this line of work by expressing the structural relationship between P and Q in terms of transformation T where Q T(P).
Distributionally Robust Optimization. With roots in optimization literature [see e.g., Ben- Tal 2017. this framework has been further studied recently in the machine learning literature [see e.g., Duchi and Namkoong 2021). The goal is to learn a predictor that minimizes the worst-case error supger err(h, Q), where P. a collection of distributions. Most prior work adopting this framework has focused on distributions P that are close in some divergence measure [e.g., fidivergences Namkoong and Duchi 2016). Instead of relying on divergence measures, work describes the collection P through data transformations T of D: (T(D))TeT which may be operationally simpler.
et al. 2009 Shapiro
"source" distribution D
musti-Distribution Learning. This line of work focuses on the setting where there are & arbitrary distributions Di,..., Dr to be learned uniformly well, where sample access to each distribution D, is provided [see e.g., Haghtalab et al. 2022 In contrast, our setting involves access to

---

single distribution D and transformations Ti..... .......Ta. Tg, that together describe the target distributions: Ti (D). (D)..... (D). From sample complexity standpoint, multi-distribution learning requires sample complexity scaling linearly in k while in our case it is possible to learn with sample complexity scaling logarithmically in (see Theorem 3.1 and Lemma B.T). The lower sample complexity in our approach is primarily due to the assumption that the transformations Ti,.... Tx are known in advance, allowing the learner to generate h samples from a single draw of D. In contrast, in multi-distribution learning, the learner pays for k samples in order to see one sample from each of Di...., Dr. Therefore, while the sample complexity is lower in our setting, this advantage arises from the additional information//truccuree provided rather than an inherent improvement over the more general setting of multi diteriidistrbbttionn learning. From an algorithmic standpoint, our reduction algorithms employ similar techniques based on regret minimization and solving zero-sum games Freund and Schapire 1997].
Invariant Risk Minimization (IRM). This is another formulation addressing domain generalization or learning a predictor that performs well across different environments [Arjovsky et al.) 2019). One main difference from our work is that in the IRM framework training examples from different environments are observed and no explicit description of the transformations is provided. Furthermore, to argue about generalization on environments unseen during training, a structural causal model is considered. Recent works have highlighted some drawbacks of IRM [Rosenfeld et al. 2021 Kamath al. [021]. J. For example, how in some cases ERM outperforms IRM
cat-of-distribution generalization, and the sensitivity of IRM to finite empirical samples vs. infinite population samples.
Data Augmentation. A commonly used technique in learning under invariant transformations is data augmentation, which involves adding transformed data into the training set and training a model with the augmented data. Theoretical guarantees of data augmentation have received significant attention recently [see e.g..Dao Dao et al., 2019 Chen et al. 2020 Lyle et al. 2020 Shao et al., 2022] Shen et al. 2022]. In this line of research, is common to assume that the transformations form a group, and the learning goal is to achieve good performance under the "source" distribution by leveraging knowledge of the invariant transformations structure. In contrast, our work does not make the group assumption over transformations, and our goal is to learn a model with low loss under all possible "target" distributions parameterized by transformations of the "source" distribution.
Multi-Task Learning. [Ben-David and Borbely (0088 studied conditions underwhich a set of transformations 'T can help with multi-task learning, assuming that 'I forms group and that H is closed under T. Our work does not make such assumptions, and studies a different learning objective.
Acknowledgments
We thank Suriya Gunasckar for insightful discussions at early stages of this work. This work was done in part under the NSF-Simons Collaboration the Theoretical Foundations of Deep Learning. OM was supported by a FODSI-Simons postdoctoral fellowship at UC Berkeley. HS was supported in part by Harvard CMSA. This work was conducted primarily while HS was TTIC and supported in part by the National Science Foundation under grants CCF-2212966 and ECCS-2216899, and by the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003. The views expressed in this work do not necessarily reflect the position or the policy of the Government and official endorsement should be inferred.
References
E. Abbe, S. Bengio, A. Lotfi, and K. Rizk. Generalization on the unseen, logic reasoning and degree curriculum. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt. S. Sabato, and J. Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 31-60. PMLR, 2023. URL https://proceeddnggs mlr. www.mmwww.......e.. v20ss//222///// abbe23a. html
A. Agarwal and T. Zhang. Minimax regret optimization for robust machine learning under distribution shift. In P.-L.. Loh and M. Raginsky, editors, Proceedings Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 2729.. PMLR, 02-05 Jul 2022. URL httl//tttppp/ceeellleee
mlr. wwtpp/pwwsssseeeeeeee http://11////aaaaaaaa// html
10

---

N. Alon, S. Hanneke, R. Holzman, and S. Moran. A theory of PAC learnability of partial concept classes. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, Febrwary 7-10, 2022, pages 658-671 IEFF, 2021. doi: 10.1109/FOCS52979, 2021.00070. URL.
http///0.1109/F055599777 2021.00070
N. Alon, A. Gonen, E. Hazan, and S. Moran. Boosting simple learners. TheoretiCS, 2, 2023. doi: 10.4629//HEORETICSS 23..8. https:////ao http://0...rrr.11.4442//////eeee
4ww.//6te02eeeee 23.8
D. Angluin. Queries and concept learning. Mach. Learn., 2(4):319-342, 1987, doi: 10.1007/ BF001 16828. URL httph:h/tpoo. wtt..//.1000////00016602000
M. Arjovsky, L. Bottou, I. Gulrajani. and D. Lopez-Paz. Invariant risk minimization. CoRR, hts//997..02880 2019. httLptttt///axxv.oorr
02893
Bartlett, N. Harvey, C. Liaw, and Mehrabian. Nearly-tight vc-dimension and pseudodimension
bounds for piecewise linear neural networks. J. Mach. Learn. Res., 20:63:1-63:17, 2019. URL http://jmlr wwg/ wttgppaprs///2///11
612. html
S. Ben-David and R. S. Borbely. A notion task relatedness yiclding provable multiple-task learning guarantees. Machine learning, 73:273-287, 2008
S. Ben-David, J. Blitzer, K. Crammer, A. Kulesza, Pereira, and J. W. Vaughan. A theory of learning from different domains. Mach. Learn., 1111-1):1511775 2010. doi: 10. 10..007/$10994-00-515555 URL https: org/ 10. 1007 000007//111999400-5555522
A. Ben- Tal, E. Ghaoui, and Nemirovski. Robust Optimization, volume 28 of Princeton Series in Applied Mathemutics, Princeton University Press, 2009. ISBN 978-1-4008-31055 doi: 10.1515/978| 40083 URL httpps://dol www/ooo.o....... 1trg/10.111555 15111117//11008101000
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Learnability and the Shnnk-Chhrrvoeekis dimension. Journal of the Association for Computing Machinery, 36(4):929 965. 1989a.
A. Blumer, A. Ehrenfeucht, D.. Haussler, and M. K. Warmuth. Learnability and the vapnik- chervonenkis dimension. J. ACM, 36(4):929-965, 1989b. doi: 10.1145/76359.763711 URL https://doi.. http://ooo.orrg/////
org/oo///// 10. 1145/7635979. 76371
Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communica- tions on pure and applied mathematics, 44(4):375 417,, 1991.
T. B. Brown, D. Mané, A. Roy, M. Abadi, and J. Gilmer. Adversarial patch. arXiv preprint 1rXiv:1712.09665, 2017.
N. Resa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge University Press, doi: 10.1017/C800788511554400 https:////ddo org/
2006. ISBN 10. 1017/CB00780511556683
S. Chen, E. Dobriban, and J. H. Lee. A theorete framework for data augmentation. Journal of Machine Learning Research, 21:1-71, 2020.
C. Cortes, S. Greenberg, and M. Mohri. Relative deviation learning bounds and generalization with unbounded loss functions. Ann. Math. Artif. Intell., 85(1):45-70, 2019. doi: 10.1007/ 510472-018-9613--, URL pittps://doi... org/10. 1007 107010000/0047-01---961111
A. Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. In M. Balcan, V. Feldman, and C. Szepesvári, editors, Proceedings The 27th Conference Learning Theory, COLT 2014, Barcelona, Spain, June 13-15, 2014, volume 35 of JMLR Workshop and Conference Proceedings, pages 287-316. JoLR.org, 2014. URL http:/t:/prooceeiggss..uuu mlr, press/v35/ daniely14b.html
T. Dao, A. Gu, A. Ratner, V. Smith, C. Sa, and C. Ré. A kernel theory of modern data augmentation. In International Conference on Machine Learning, pages 1528-1537. PMLR, 2019.
C. Duchi and H. Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378-14000 2021.

---

A. Ehrenfeucht, D. Haussler, M. Kearns, and L. Valiant. A general lower bound on the number of examples needed for learning. Information and Computation, 82(3):247-261, 1989.
L. Engstrom, B. Tran, D. Tsipras, Schmidt, and A. Madry. Exploring the landscape of spatial robustness. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beuch, California, USA, volume 97 of Proceedings of Machine Leurning Research, pages 1802-1811. PMLR, 2019, URL http:://rroceeding
mlr. press/v97 v97/ engstrom19a... html
D. Foster, S. Kale, H. Luo, M. Mohri, and K. Sridharan. Logistic regression: The importance of being improper. In S. Bubeck, V. Perchet, and P. Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 167-208. PMLR, 2018 http::t/pocceeee//eee
mlr, press/
v75/foster188 html
Y. Freund and R. E. Schapire. A theision- generalization of on-line learning and an application to boosting. J. Comput. Syst. Sci., 55(1):119 139, 1997. doi: (..00//CSS.1197..111.
URL https:t/pp: /tcbps://doi.... org.:/..rr11..000 100./ jcss. 1997. 1504
I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. C. Courville, and Y. Bengio. Generative adversarial networks. Commun. ACM, 63(11):139-144, 2020. doi: 10.1 10.1145/342262.. URL/tttss:///oi.oooo
1145/3422622
N. Haghtalab, M. I. Jordan, and E. Zhao. On-demand sampling: Learning optimally from mul- tiple distributions. In Koyejo, Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL http: /ttppp:s/ppapps..... nips. cc/ wwcppaper_ttte filesf wtt.s///pppep//2111.111 paperr/022/hashl) 029170aee66433222799999000 -ww-:eo0--bbbbteeee Abstract Conf Conf erence. aatonceehtmll...
S. Hanneke and Kpotufe. On the value of target data in transfer learning. H. M. Wal- lach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu Buc, E. B. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural In- formation Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9867-9877, 2019. URL httttts:::/poceeeiiiiiic Abstract html
wwwpeeiiinnnnnuiipeg..ee nww.ips....... cc/paapr/2019/
D. Hendrycks and T. G. Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. In 7th International Conference on Learning Representatiinss ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net, 2019. URL https:://openrrrieww.tt net/ forum?id Berum?id-HJz6ticom HJz6ticqym
P. Kamath, A. Tangella, D. J. Sutherland, and N. Srebro. Does invariant risk minimization capture invariance? In A. Banerjee and K. Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Viriual Event, volume 130 of Proceedings of Machine Learning Research, pages 4069-4077. PMLR, 2021. URL http:: http::/proceedings mlr. pwtps//1100/aaaaaaaaaaaaaaa
html
D. Karmon, D. Zoran, and Y. Goldberg. Lavan: Localized and visible adversarial noise. In International Conference on Machine Learning, pages 2507-2515. PMLR, 2018.
C. Lyle, M. van der Wilk, M. Kwiatkowska, Y. Gal, and B. Bloem-Reddy. On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.0017 2020.
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver; BC, Canada, April 30- May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
net wttpaentee/oommmiidiella......
O. Montasser, Hanneke, and N. Srebro. Ve classes are adversarially robustly learnable, but only improperly. In A. Beygelzimer and D. Hsu, editors, Proceedings of the Thioly-Second Conference on Learning Theory, volume of Proceedings of Machine Learning Research, pages 2512-2530, Phoenix, USA, 25-28 Jun 2019. PMLR
12

---

S. Moosavi-Dezfoole A. Fawzi, O. Fawzi, and P. Frossard. Universal adversarial perturbations. In 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI. USA, July 21-26, 2017, pages 86-94 IEEE Computer Society, 2017. doi: 10.1 N0.100//CVP.2017.00 URL htttp:///do/ org/ 10. 20000//VPR.20......
H. Namkoong and J. C. Duchi. Stochastic gradient methods for distributionally robust opti- mization with f-divergences. In D. D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Con- ference Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages
2016. URL httpps://proceeddgggg wwwpdiinnnnnnnninneeeeeee www.neuu....paaappeppee cttp:cccppppppe cctp:cccppppe//11// haat//68886744350011965667776666 - Abstract. html
J. Quinonero-Candela, M. Sugiyama, A. Schwaighofer, and N. D. Lawrence. Dataset shift in machine learning. Mit Press, 2008.
I. Redko, E. Morvant, A. Habrard, M. Sebban, and Y. Bennani. A survey on domain adaptation theory. CoRR, abs/2004. 1829, 2020. URL
11829
E. Rosenfeld, K. Ravikumar, and A. Risteski. The risks of invariant risk minimization. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. JRKLhtttps//ppprrrvviee hwt.o//r.....t.tottmomeeeaaaaB.a
N. Sauer. On the density of families of sets. Comb. Theory, Ser. A, 13(1):145-147, 1972. doi: 10.1016/0097-336557)))000
https://////oi...... org/ 10. (0111/000097331167)))))00000
H. Shao, O. Montasser, and A. Blum. A theory of pac Icaraaillity under transformation invariances. Advances in Neural Information Processing Systems, 35:13999-14001, 2022.
A. Shapiro. Distributionally robust stochastic programming. SIAM J. Optim., 27(4):2258-2273 2017. 1137/16M1058297
doi: 10. 201113//6MM0588297. httllhttts///dii.rrrr
R. Shen, S. Bubeck, and S. Gunasekar. Data augmentation as feature manipulation. K. Chaudhuri, S. Jegelka, L. Song. C. Szepesvari. G. Niu, and S. Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 19773-19808. PMLR, 17-23 Jul 2022. URL lnttps://proceedinggg mlr press/v162 /v622/ shen22a.
V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-280, 1971.
V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974.
A. Zou, Wang. 7. Kolter, and M. Fredrikson. Universal and transferable adversarial attacks on aligned language models. CoRR, abs/2307. 15043, 2023. doi: 11.A5550AAXXI.2200...55 URL https: http:///oooo.o//1/// htgg//.48550/////.
(85500/rXXi0 2307 15043
13

---

A Uniform Convergence
We can use tools from VC theory |aanni and Chervonenkis/ 1971, 1974] to obtain uniform con-
vergence guarantees that will allow us to establish our learning guarantees and sample complexity bounds in the remainder of the paper. The starting point a simple but key observation concerning the hypothesis class H. and the collection of transformations T. Specifically, consider the composition of H. with T defined as:
H. o T == h TT. where (h o (x) = h(T(x)) Ve E X.
(9)
We next apply VC theory to the class H. o T to obtain our uniform convergence guarantees. Formally, Proposition A.I. For any class H. any collection of transformations T, any distribution D over X x V, and any E N, with probability at least 1 - 6 over S ~ D wh E H.YT VT ET,
ve(H o T) + log(1/)
((r)), - err(h, ((D)) S ev
Proof. Since the composition H. T is a hypothesis class consisting of functions o T where h H,T T. the claim follows from the definition of VC dimension and uniform convergence guarantees for VC classes (Vapnik and Chervonenkis, 1971 1974].
Proposition A.2 (Optimistic Rate). For any class H. any collection of transformations T, any distribution D, and any m E N, letting B(m, 5) == 1 (ve(H o T) vo(HoT) + 1lgg(//)) with probability at least over ~ D vh ET
2em
erI(h,T(D)) err(h, T(S) + 2 (h)) + 4B(m, (enhhTT(S) - (h, T(D)) + 2/ (D)) 6) + 4B(m, 6).
Proof. The claim follows from applying relative deviation bounds, or optimistic rates, for the composition class T [see e.g., Corollary in Cortes et 2019
B Bounding the VC dimension of H. composed with T
Given the relevance of ve(H. T) in our theoretical study, in this section we explore the relationship between vo(H 'T) and ve(H) which we believe can be helpful in interpreting our results and comparing them with the sample complexity of standard PAC learning [which is controlled by vo(H) Blumer et al.] 198 1989a Ehhenteucht et al.] 1989]. To this end, we consider below a few general cases and prove bounds on vo T) in terms of ve(H) and some form of capacity control for T. These results may be of independent interest.
Finitely many transformations. When T is finite collection of transformations, we can bound ve(H o T) from above by O(ve(H) + log (T) using the Sauer- Shelah-Perels Lemma Sauer 1972
Lemma B.l. For any class H and any finite collection T, ve(H o T) < O(ve (H) + log (T]).
Proof. Consider an arbitrary set of points P = [Zi...... Im C X. To bound ve(H T) from above, suffices to bound the number of behaviors when projecting the function class H o T on P, defined
THeT (P) =
Observe that
ve(H)
(MNT(P))
E H}| S |T|
(
vo((()
TET
where the first inequality follows from the definition of IIxoT (P) and the second inequality follows from the Simer-Shelah-Perik. Lemma [Sauer 1972]. Solving for m such that the above bound is less than 2 implies that ve(H T) O(ve(H) log [T]).
14

---

Linear transformations. Consider T being (potentially infinite) collection of linear transforma- tions. For example, in vision tasks, this includes transforming images through rotations, translations, maskings, adding random noise (or any fixed a-priori arbitrary noise), and their compositions. Sur- prisingly, for broad range of hypothesis classes H (including linear predictors and neural networks), we can show that ve(H 'T) S ve(H) without incurring any dependence on the complexity of 'T. Specifically, the result applies to any function class that consists a linear mapping followed by an arbitrary mapping. This includes feed-forward neural networks with any activation function, and modern neural network architectures (e.g., CNNs, ResNets, Transformers).
Lemma B.2. For any collection of linear transformations T and any hypothesis class of the form H = {f W. Rd + y W R Af: R >Y), it holds that ve(H T) I vv(H).
Proof. By definition of the VC dimension, it suffices to show that H. o T S H. To this end, consider an arbitrary f W H. where W Ed - R is linear map and f I2 y is an arbitrary map (see definition of H in the lemma statement), and consider an arbitrary linear transformation T T. Then, observe that for each x E 12d
(h ()) = (J
= - -(
where the last equality follows from Riesz Representation theorem and 7 is the adjoint transforma- tion of T. Thus, we have shown that there exists W = T (W) such that (T=z) = (z) for all x E Rd. Therefore, H. o C H.
Transformations on the Boolean hypercube. When the instance space X' = {0, 1)" is the Boolean hypercube, can bound the VC dimension of H a from above by the sum of the VC dimension of H and the sum of the VC dimensions of (Tr) where each T; = {ar + T(x);; function class resulting from restricting transformations T {0, - {0. d' E T to output only the ith bit.
E T) is
Lemma B.3. When X' {0,1)" for any hypothesis class H. and any collection of transformations T, ve(H o 7) s Olog d) (vc(H) - Σin ve(T))), where each T, = fa +
Proof. Every function h T E H o T can be viewed as x + ((T(x))........... T())a). which is a composition of h with d Boolean functions T(.),..... T())a : - {0, 1) where each T(.): is the restriction transformation T to the ith coordinate. The claim then follows from a direct application of Proposition 4.9 in Alon et al. [2023), which itself generalizes a classical result due to Blumer et al. [189b] bounding the VC dimension of composed function classes.
C Proofs for Section 2
Proof of Theorem 2.2 We note that the proof follows a standard no-free-lunch argument for VC classes, where the game will be to guess the support of distribution.
Let 21...., T3k be arbitrary points. For each P S [3k] where |P] = k, define a transformation Tp that maps II...., Zzk to some new and unique points Tr(Iz),.... Tr(Is)). Then, define classifier hp to be positive everywhere, except on the points (Tr(a;)) which are labeled negative. Let X {xI...., ., T3a Up (TT((I)).................) TP((x))) H = (hp: PCC [3k], IP| = k}, and T = k). k).
(Tp: C [3k3),, [P|
is easy to see that vc(H) 1, since classifiers in H. operate in different parts of X. Furthermore,
ve(H o T) > l where we can shatter 2 Dy with H. T as follows: for each yi...., ykk let I {i E [k] y/ -1 and P = IU fj s 2k [4], then (hp TT)(x,)
hr((Tr(;;) y: for all i E [A).
Consider now family of distributions {Dr: P 33 IP|
k) over X' y where each Dp is uniform over 2k points {(2;, +1)} For each / C [3k] where |P| = k. observe that by definitions of Dp. H. T, supreT and { are not in the support of Dp. That is to say, our lower bound holds the realizable setting where OPT 0 (see Equation
((Dp)) = O since hp only labels the points (Tp(z;))ee negative
15

---

Next, consider an arbitrary proper learning rule A (X' x + H. For distribution Dp chosen uniformly at random and upon receiving a random sample 5 ~ Di,, A needs to correctly guess which points from {TI,.... 234 } S lie in the support of Dp in order to choose an appropriate small error. However, since the support is chosen uniformly at random, A will most likely incorrectly guess a constant fraction of the support, leading
H. with
constant error. This is standard argument [see e.g., Montasser et al. 2019 Alon et al. 2021]. but we repeat it below for completeness.
Fix an arbitrary sequence S E {(z1, +1)..... (I3x, +1)}". Denote by Es the event that S E s)p for distribution Dp that picked uniformly random. Next,
sup err( (A(( Es TET
2
p
1
2
B
[[((S)(T((a)) + Bs
2k
i
2
Σ
[[A(S)(Tr(x))) # Es]
i1)N
2 4'
where the last inequality follows from the fact that (S)) E and that the remaining (at least k) points that are not in S but in supp(Dp) are chosen uniformly at random, because Dp is chosen randomly. From the above, by law of total expectation, we have
E E
sup err (A()(A))) 4 TET
P SNDD
By the probabilistic method, EswD, (SUPTET T(Dr))] 2 1. Using implies that Prowpp.
this means
there exists p such that variant of Markov's inequality, this
err (A))A)), T(Dr)) > A. 2
D Proofs for Section 3
Proposition D.1. For any class H. any ERK for H. any collection of transformations T, any distribution 'D such that OPT xc = 0, and any E, E (0, 1/2), with probability at least 1 - 8 over ~ D)mte,)), where mle, 8) 0 vo(HoT) (ox(1/))))oR(((8)
VT E T: err(h, ((D) SE
where h is the output predictor of running ERM on the inflated dataset T(S) = ((T(x)))) (I. ESATET)
Proof of Proposition D.1 Since OPT = 0, i.c. there exists h* H. such that VT E T , T(D)) = O, and since is the output predictor of rumning ERM on the inflated dataset T(S) = {(T(z). v) (x,z) S A T). it follows that VT e T err(h, T()) 0. Thus. by invoking the optimistic generalization guarantee (Proposition A.2 with probability at least - over ~ Dm,(,)); (vh E (VT e T) err(h, T(S)) = err T(D) < E. Since h E H. it follows that VT TT: err(h, T(D)) s..
Li
Lemma D.2. Let S = ((11,11)..... vi).... (xm. vm)} be an arbitrary dataset. For any distribution Q over T and any predictor h, define the loss function Es Q) = -1 Errrr er. (())), Then for any sequence of predictors hy,..., hn, running Multiplicative Weights with 1) = / 1n [T] (see Algorithm produces a sequence of distributions Q1. Qn over TT that satisfy
R
In In
(hy Q+) S min
(hr, T) +
R
TET R
2R
16

---

Proof of Lemma D.2 The proof follows directly from considering two-player game. where the T T-llaerr plays mixed strategies (distributions over T) Q....., Qn against predictors hi...., hR played by an arbitrary learning algorithm å, and in each round the -player incurs loss (s( Qr) [T-QQ. err( (S)). Then, the regret guarantee of Multiplicatiiv Weights [see e.g., Theorem 2.2 in Cesa-Bianchi and Lugosi 2006] implies that
R Σ
(s uin
1
E pml
(s T) +
T 2R
E Proofs for Section
Proof of Theorem 5.7 The proof follows from the definition of (Equation and using uniform convergence bounds (Proposition A.I). Let H. be an a-priori fixed predictor (independent of sample S) attaining
inf sup ferr(h" ;T()))()))))))))))))) - OPT hE
or is E-close to By setting m(= 6) = m(E, = = (x Yo((Ho7)+ogg/// and invoking Proposi-
tion A.1 we have the guarantee that with probability at least 1 - over S ~ Dmm(s.)),
(vh H. (VT T) (err(h,T(S)) ((T)),(D))) s.
Since h² E H. the inequality above implies that
T err(h, T(D)) S err T(S)) + VT T err(h" ((S)) S err(h", T(D)) +8.
VT TT: |PPT - - OPTT S.
Furthermore, by definition, since minimizes the empirical objective, it holds that
sup err err T(S)) OPT, S sup (T()""()))) - OPT,.
TET
TET
By combining the above, get
vT TTT err(h, T(D)) OPT) S sup err T(S)) OÝT, + 2e
TET
sup err(h" T(S)) - OPT, + 2
TET
sup err(h", T(S)) - OPT 3
TeT
This concludes the proof by definition of ht.
Similar to Section 3. develop in this section generic oracle-efficient reduction solving Objective 7 using only an ERM oracle for H. This reduction may be favorable in applications where we only have black-box access to off-the-shelve supervised learning method. The techniques used similar to those used Section 3] and Agarwal and Zhang [2022) who developed a similar reduction when having access to collection of importance weights instead of collection of transformations (which is the view we propose in this work).
Theorem E.1. For any class H. collection of transformations T, distribution D and any E, 8 E (0, 1/2). with probability at least 1 over S ~~D Dmm(c,5) where ml=, 6) I vo(HoT)) rumning Algorithm 2 on S S.oor R >
22
8 bn|7] 2²
rounds produces h 1 LR h, s.I.
VT E TT: err(h, T(D) OPTT < inf sup (err(h", OPT +
K*ER TET TET
17

---

Algorithm 2: Reduction to Minimize Worst-Case Regret
Input: Black-box learner ERMy, dataset S {[11 91)..... (am. ym J. and transformations T. For each T, run learner ERMy, on T(S) and denote its output by hy.
2 For each E T, set Qi(T) = [77-
Set R
8|n|7]
8²
4 for 1 r Rido
Draw megx i..d. samples (1),
Yi),..... ...).................... .x (X Ymw)). ) where each (X,, Y2) drawn by randomly drawing a transformation T according to Qi and randomly drawing (X, Y) from Unif(S), and letting (X,, Y,) (T(X),Y)
Run learner ERMy on (X1, K1), (X maxn mem), and let h,, denote its output.
For each T E T, update Qr+1 (T) Q.(T) exp(veemih, ((8)) ((18))-er(hhr orr(hrr or((hr,((5))) ((())) where Z, a
2.
normalization factor such that Q++1 is distribution.
Output: # E hy-
Proof of Theorem E.1 Let S = {(21, vi), (Im, fm)) be an arbitrary dataset, and let A be an (e, (agn))))gntcccPPaa PAC-lecre for H. Then, by setting R > 8ln/T1 and invoking Lemma D.2. guaranteed that Algorithm plrorichmmpprouuces a sequence of distributions QQ....,CC QT over 7 that satisfy
R
1 R
sup TET R
Σ
err(h,, - err(hr,T(S)) S
E T~Q,
|er((h,, T(S)) err(frr,(S))) T(S)) +
At each round r, observe that Step 3 in Algorithm I draws an i..d. sample from a distribution P. over X' x J' that is defined by Q, over T and US). and since ERMy an (e, aagooaagsooiiiPP--leeee for H. Steps 5-6 guarantee that
E err T(S)) T~Qr
E T~Q, m
Σ (h,(T(z)) + vi S inf crr(h, T(S)) + e.
T-HT
Combining the above inequalities implies that
sup err(h, T(S)) orr(hr, S Σ TeT
1 R
inf E Nih T~Q,
[er(hh, T(S)) - crr(hr, T(S)) +ate
inf sup ((S)) -(rr)))((((r,T((())) + + NET
Finally, by appealing to uniform convergence over H and T, with probability at least d over S ~ D we have
VT er((nr, T(S)) s err(,, < OPT, +
OPT, I ar (e()))T([D)) & err(hz ( T(S)) te.
Thus,
VT TTT err(h, T(D)) OPT, ( + 2e inf sup (rr h, T(S)) -er(eerrr(sss,) +
NET
inf sup [err(h, T(D)) OPT ( 69.
WeR TET
18

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The problem setup and the main theoretical results of the paper are described in the introduction, under "Our Contributions". They match the scope and the claims made in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our results immediately after the statements or the beginning of the next section. E.g., for the limitations the algorithm proposed in Section 2 we state its limitation immediately after Theorem 2.2 (i.e., the sample complexity cannot improved by such proper learning rules) and the beginning of Section (i.e.. the algorithm requires knowledge of H. and T). We also mention the limitation of Algorithm the introduction, i.e., the algorithm is limited to finite transformations.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
19

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All the theoretical results clearly state the required assumptions. Full proofs are provided either in the main text or the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide full description of the simple experiment that perfomed in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
also be provided via detailed
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
20

---

reproducible, they In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The data used in our experiment is synthetic and we provide full description of how to generate in Section 6
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ttp:p/ibbbgcggiiiiccoooceeeaaaa Swt.///oodSSssss.eoooea wwtpsuummmsssisnniii sswiiisiicciiiiiiicc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All is specified in Section 6
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Reported in Section and Figure
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
21

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: See Section b
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https:
Answer: [Yes]
Justification:
We see no violation of the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper contributes theoretical/foundattinal results addressing the problem statistical learning under distribution shifts. Our work will potentially lead to further theoretical study, as well as practical methodological development with direct impact on downstream applications. There are many potential societal consequences of our work, none of which we think must be specifically highlighted here.
22

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out, For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA].
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
23

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
24

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "L3CAplo46s", "reviewer": "Reviewer_Whvi", "summary": "This paper proposed a transformation-based invariant learning framework for OOD generalization. The authors initiated a theoretical study for this framework, investigating learning scenarios where the target class of transformations is either known or unknown. Upper bounds on the sample complexity in terms of the VC dimension of the class composing predictors with transformations were obtained.", "questions": "Please see the questions mentioned above.", "limitations": "N.A.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "Nice theoretical results, with various scenarios considered.", "weaknesses": "When proposing a new learning rule, it is better to demonstrate its utility by comparing it to existing and similar ones, such as ERM (at least) and DRO (similar).\n\nAs the authors mentioned in Related Work, IRM is another popular learning framework for OOD generalization, but some works concluded that ERM may outperform IRM in some cases. Some other works showed that ERM may outperform DRO. Will the learning framework proposed in this paper be underperformed by ERM under some scenarios?\n\nConsider a more realistic definition of $\\mathcal{T}$: T(X)=X+R(X), as in the ResNet, because Q and P should not be too far away. In such a case, what will the learning rule, the theoretical guarantee, and the algorithm be like?\n\nWhat's the connection between this work and the importance weighting for distributional shift (such as [1])?\n\n[1] T. Fang, etc. Rethinking Importance Weighting for Deep Learning under Distribution Shift. NeurIPS 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We address your comments below. \n\n> When proposing a new learning rule, it is better to demonstrate its utility by comparing it to existing and similar ones, such as ERM (at least) and DRO (similar).\n\nERM can be viewed as concerned only with the identity transformation map $T(x) = x$. Therefore, when interested in a collection of transformations e.g. rotations, then ERM can be provably shown to do worse than our proposed learning rule in Equation 2. Here is an **Example/Scenario** that further illustrates this difference: when the training set consists of images of upright cats, ERM might learn the feature of \"upright,\" leading the model to fail when the test set is composed of upside-down cat images. Our method, however, would still work in this scenario. \n\nWe discuss the relationship with the DRO line of work in (Lines 306–312). \n\n> As the authors mentioned in Related Work, IRM is another popular learning framework for OOD generalization, but some works concluded that ERM may outperform IRM in some cases. Some other works showed that ERM may outperform DRO. Will the learning framework proposed in this paper be underperformed by ERM under some scenarios?\n\nFrom a theoretical standpoint, ERM and our proposed learning rule (e.g., Equation 2) enjoy different guarantees. When we are only interested in performing well on a single source distribution, then ERM suffices. But, when interested in a collection of distributions parametrized by transformations  $\\mathcal{T}$, our learning rule outperforms ERM.\n\n> Consider a more realistic definition of $\\mathcal{T}$: $T(x)=x+R(x)$, as in the ResNet, because Q and P should not be too far away. In such a case, what will the learning rule, the theoretical guarantee, and the algorithm be like?\n\nIn this case, the learning rule/algorithm corresponds to solving an alternating minimization-maximization problem. The minimization is with respect to parameters of the model responsible for classification (e.g. an MLP on top of the ResNet architecture) and the maximization is with respect to transformations (e.g. the parameters of the $R$ function you describe). The theoretical guarantee is that with enough samples (scaling with VC dimension of ResNet), the learned model will minimize worst-case error (across all $R$ functions). \n\nAlso, please see Lines 144–155 for discussion of a similar example concerned with feed-forward neural networks.\n\n> What's the connection between this work and the importance weighting for distributional shift (such as [1])?\n\nImportance weighting addresses the problem of covariate shift / distribution shift from a different angle relying on *bounded* density ratios between source and target distributions. Our work instead considers transformations, i.e., when $P$ and $Q$ are related by a transport map such that $Q = T(P)$. This allows us to address classes of distribution shifts that may be difficult to address with importance weighting, specifically when the density ratio is not bounded. I.e., when distributions $P$ (source) and $Q$ (target) have disjoint supports, the density ratio is not bounded, and therefore we can not rely on importance weighting. However, it may still be possible to learn using the language of transformations that we contribute in this work.", "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": "QgyzKXopMc", "reviewer": "Reviewer_fcsB", "summary": "The work focuses on theoretical aspects of distribution shift, considering various frameworks that expand the standard PAC model of learning. \nThe paper considers a hypothesis class $\\mathcal{H}$ and a class of transformations of the domain $\\mathcal{T}$. The learning algorithm is given some data drawn i.i.d. from some distribution $D$ and the overall goal is to produce a classifier that does well not only on fresh samples from the source distribution $D$ but also when a transformation $T$ from $\\mathcal{T}$ is applied to $D$. \n\nOverall, the makes assumptions on the VC dimension of the class of functions obtained from composition of $\\mathcal{H}$ and $\\mathcal{T}$. In some parts of the paper it is further assumed that $\\mathcal{T}$ is finite. Various parts of the paper consider different loss functions that depend on the data distribution and the class of transformations $\\mathcal{T}$. The goal is to find a hypothesis $\\hat{h}$ for which the value of a loss function is not more by $\\epsilon$ greater than the best (i.e. smallest) value of the loss function among all functions in the hypothesis class $\\mathcal{H}$. (Note that this optimum value also depends on the choice of the loss function.)\n\nThe paper considers a number of specific goals in this broad setup:\n- In Section 2 the loss of a classifier $\\hat{h}$ equals to the worst-case population risk that $\\hat{h}$ will have as a result of applying a transformation $T$ from $\\mathcal{T}$ to the data distribution. Note that this loss function quantifies the worst-case impact that a transformation from $\\mathcal{T}$ can have on the population loss. Section 2 considers the classifier $\\hat{h}$ that has the smallest \n introduces and analyzes the classifier obtained by minimizing the empirical worst-case risk that a hypothesis will have as a result of applying a transformation $T$ from $\\mathcal{T}$ to the training dataset.\n- In Section 3 the class of transformations $\\mathcal{T}$ is assumed to be finite and the algorithm has access to an ERM oracle for the hypothesis class $\\mathcal{H}$. First, the realizable setting is considered (i.e. the setting in which there is some function in $\\mathcal{H}$ that perfectly desribes the data even if it is transformed by an arbitrary transformation in $\\mathcal{T}$). The paper shows that the classifier shown to exist in Section(2) can be obtained by (i) augmenting the training dataset by applying various transformations in $\\mathcal{T}$ and (ii) applying the ERM oracle to the resulting dataset.\n- In Section 3 the paper also considers the agnostic setting. In this setting there can potentially be  a transformation in $\\mathcal{T}$ that causes the empirical risk to be non-zero. The paper gives an efficient algorithm that combines calls to the ERM oracle with the multiplicative weight update method to obtain a classifier shown to exist in section 2. Note that the run-time of the algorithm does not include the time to actually minimize the empirical risk when the ERM oracle is called, which can potentially be slow.\n- Section 4 considers the case in which there is potentially no classifier whose error stays small when **any** transformation in $\\mathcal{T}$ is applied. Instead, Section 4 considers a loss function equal to the **number** of transformations in $\\mathcal{T}$ that make the population loss of the classifier greater then epsilon. The paper gives a statistical generalization bound with respect to this loss. \n- Section 5 again considers a different loss function. The loss of a hypothesis $\\mathcal{h}$ is defined as the worst-case difference (over transformation $T$ in $\\mathcal{T}$) between (i) the population risk of $\\mathcal{h}$ after transformation $T$ is applied (ii) the lowest population risk among all hypotheses in $\\mathcal{H}$. In other words, if there is some transformation $T$ makes the error of $\\mathcal{h}$ large, we do not penalize the algorithm if the worst-case error in the hypothesis class  $\\mathcal{H}$ is likewise large. With respect to this loss function as well, the paper again gives generalization bounds (similar to Sections 2 and 4) and an algorithmic reduction (Similar to Section 3).\n\nAdditionally, an experiment is presented in which a Boolean function is learned from synthetic data, and the function is invariant under a class of permutations.", "questions": "No questions.", "limitations": "Limitations are discussed adequately. However, I believe it would be helpful to additionally have a dedicated short section titled limitations that briefly summarizes the limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "- The question of mitigating distribution shift is central for modern machine learning.\n- The paper is written clearly and numerous examples are given.", "weaknesses": "- The technical results follow by a fairly direct use of standard generalization bounds, together with standard tools from convex optimization such as multiplicative weights.\n- One could argue that one of the most important use cases is when $\\mathcal{T}$ form a group of symmetry transformations. As discussed on page 9, in this setting the technique of data augmentation was studied previously. However, the previous work does not enjoy the worst-case error guarantees across transformations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review. We address one your comments below. \n\n> One could argue that one of the most important use cases is when $\\mathcal{T}$ form a group of symmetry transformations. As discussed on page 9, in this setting the technique of data augmentation was studied previously.\n\nAs mentioned in page 9 (Lines 333–338), we emphasize that the technique of data augmentation does not enjoy the worst-case error guarantees across transformations as we prove in this work (using a different learning rule). \n\n> Limitations are discussed adequately. However, I believe it would be helpful to additionally have a dedicated short section titled limitations that briefly summarizes the limitations.\n\nAs suggested, we will reiterate the limitations together in a single short section and discuss future open questions.", "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": "cKhMeAKPDW", "reviewer": "Reviewer_JZtQ", "summary": "The authors investigate transform-invariant binary classification problems in which the learner observes transformed features during the prediction phase and aims to construct a classifier robust against test-time transformations. Their first contribution is the derivation of a generalization error bound on the worst-case risk of transform-invariant classification, characterized by the VC dimension of the composite class. Subsequently, they propose an algorithm that achieves this generalization bound without direct access to the hypothesis class, relying solely on the empirical risk minimization (ERM) oracle associated with the hypothesis class. The second contribution is the establishment of a generalization error bound on the number of high-risk transformations, which is also characterized by the VC dimension of the composite class. The third result presents a generalization error bound on the worst-case regret, similarly characterized by the composite class's VC dimension. Empirical evaluations were conducted to demonstrate the behavior of the transform-invariant learning algorithm.", "questions": "- Can you provide more insight into the practical implications of your empirical evaluations? What specific benefits does your transform-invariant learning algorithm offer in real-world scenarios?", "limitations": "The authors adequately address the limitations and potential impacts.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is well-written and easy to follow. It addresses a crucial topic for machine learning: robustness against transformations. This focus on developing classifiers that remain effective under various input transformations is highly relevant to real-world applications and aligns well with the conference themes.\n\nThe authors provide generalization error bounds for various accuracy measures, each corresponding to potential practical scenarios. This comprehensive approach enhances the applicability of their work.\n\nThe methodology to minimize worst-case accuracy solely relying on the ERM oracle is innovative. While it adapts the Multiplicative Weights method to the transform-invariant classification problem, the application of this method to this specific domain represents a novel contribution.", "weaknesses": "The theoretical results appear to be direct applications of existing uniform bounds on empirical processes and VC dimension theory. The introduction of transform-invariance does not significantly impede the application of these uniform bounds, as they represent worst-case bounds for functions to be optimized. Specifically, Theorem 2.1 is derived by applying the original VC theory (by Vapnik and Chervonenkis) to the composite class. Theorem 4.1 is a straightforward consequence of the optimistic rate by Cortes et al. for the composite class. Theorem 5.1 is also obtained by directly applying the original VC theory to the composite class. Consequently, the technical novelty underlying the theoretical results is not clearly evident.\n\nThe authors do not sufficiently elucidate the implications of their experimental results. The significance and benefits of the empirical evaluation are not adequately explained, leaving the reader unclear about the practical impact of the proposed approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your detailed review. We address your comments below.\n\nWe emphasize that our contributions are conceptual and theoretical. At the conceptual-level, to the best of our knowledge, this is the first work to model the OOD/distribution shift problem through a transformation function class, which is relevant to many real-world scenarios as discussed in the introduction. As is well known, studying OOD/distribution shift problems requires specific modeling of the relationship between source and target distributions (e.g., bounded density ratios between source and target distributions, which often don't hold in real-world scenarios). Instead, we propose a new way of modeling the problem through the lens of transformations. This allows us to obtain new learning guarantees against classes of distribution shifts, and while these may not require new sophisticated tools, they nonetheless provide bounds that were not covered by prior work. \n\n> The theoretical results appear to be direct applications of existing uniform bounds on empirical processes and VC dimension theory. The introduction of transform-invariance does not significantly impede the application of these uniform bounds, as they represent worst-case bounds for functions to be optimized. Specifically, Theorem 2.1 is derived by applying the original VC theory (by Vapnik and Chervonenkis) to the composite class. Theorem 4.1 is a straightforward consequence of the optimistic rate by Cortes et al. for the composite class. Theorem 5.1 is also obtained by directly applying the original VC theory to the composite class. Consequently, the technical novelty underlying the theoretical results is not clearly evident.\n\nWe believe that it is an asset to be able to leverage the structure of the composition of hypotheses and transformations, and to obtain sample complexity bounds by utilizing existing VC theory (as also highlighted by reviewers RtrA and fSmB), to obtain new insights for this relevant OOD setting.  We further demonstrate this by providing in Section 2.1 several examples highlighting how a simple bound can imply several interesting results and guarantees that are not known before.\n\n> The authors do not sufficiently elucidate the implications of their experimental results. The significance and benefits of the empirical evaluation are not adequately explained, leaving the reader unclear about the practical impact of the proposed approach.\n\nWe will add this elaboration to the paper. Please see below for further clarification. \n\n> Can you provide more insight into the practical implications of your empirical evaluations? What specific benefits does your transform-invariant learning algorithm offer in real-world scenarios?\n\nWe only provide a simple illustrative experiment showing how the use of transformations can help learn with fewer samples / training data. Specifically, in Figure 1, both learning tasks can be learned better (i.e., higher accuracy) with the use of transformations compared with the baseline of standard training (with no transformations).\n\nInvestigating implications of our theoretical results in real-world scenarios is of course an interesting and important future direction, but it lies beyond the scope of this work.", "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": "kL67foCA6z", "reviewer": "Reviewer_RtrA", "summary": "This paper studies a theoretical model of out-of-distribution (OOD) generalization, where the possible distribution shifts are encoded by a collection $\\mathcal{T}$ of transformations on the domain. The goal in this setting is given a distribution $D$ to learn a hypothesis $h$ from some hypothesis class $\\mathcal{H}$, such that $h$ achieves the best possible risk on the distribution $T(D)$ under the worst-case shift $T\\in\\mathcal{T}$. The paper gives algorithms achieving this goal in a variety of settings including when $\\mathcal{H}$ and $\\mathcal{T}$ are both known, and when given an ERM oracle for $\\mathcal{H}$ and $\\mathcal{T}$ is finite. The bounds are given in terms of the VC-dimension of the composition $\\mathcal{H}\\circ\\mathcal{T},$ consisting of all function of the form $h\\circ T$.", "questions": "1. Could you explain the main differences between this model and that of multi-distribution learning? In particular, are there some natural instances of multi-distribution learning which do not fall into this model?\n\n2. As described above under weaknesses, why do the lower bounds for multi-distribution learning not apply to the results of Theorem 3.1? Have I misunderstood something about the model in this paper, or perhaps the lower bound instances from [1]?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The model introduced of a class of transformations corresponding to distribution shifts gives very mathematically clean results for sample complexity in terms of the VC-dimension of the composed class $\\mathcal{H}\\circ\\mathcal{T}$.\n\n2. The explanations of how the model can be applied to different practical settings involving distribution shift are clear and show broad applicability.", "weaknesses": "The primary weakness is in distinguishing these results from prior work, particularly that on multi-distribution learning. In particular,  when the class of transformations $\\mathcal{T}$ is finite, then every problem instance from this paper's model is also an instance of multi-distribution learning with $D_1,...,D_k$ given by $T_1(D),...,T_k(D)$. \n\nFurthermore, as pointed out on line 41, if the domain of the learning problem is $\\mathbb{R}^d$ then Brenier's Theorem implies that for any instance of a multi-distribution learning problem $D_1,...,D_k$ with sufficiently \"nice\" distributions, there is a distribution $D$ and set of $k$ transformation $T_1,\\dots,T_k$ such that $D_i = T_i(D)$. Thus, in the case of finite $\\mathcal{T}$ on domain $\\mathbb{R}^d$ these two models are equivalent so long as only \"nice\" distributions are considered. The setting of finite $\\mathcal{T}$ is particularly important, as it is the setting for which the main results in this paper give oracle-efficient algorithms (given an ERM oracle for $\\mathcal{H}$).\n\nThe above discussion leads to what may be an issue with Theorem 3.1 as stated. As far as I can tell, Theorem 3.1 combined with Remark 3.2 would imply a $O(d + \\log k)$ upper bound on sample complexity in the case that the VC-dimension of $\\mathcal{H}$ is $d$ and $|\\mathcal{T}|=k$. However, prior work on multi-distribution learning [1] suggests that in the setting of $k$ distributions $D_1,...,D_k$ and a hypothesis class of VC-dimension $d$ there is a lower-bound on sample complexity of $\\Omega(d + k\\log k)$. Perhaps I have missed something here, but I don't see any obstruction to instantiating the lower-bound family of instances from [1] as a family of instances in the model of this paper. So there seems to be some discrepancy between the known lower bounds and Theorem 3.1.\n\n[1] Haghtalab, Nika, Michael Jordan, and Eric Zhao. \"On-demand sampling: Learning optimally from multiple distributions.\" Advances in Neural Information Processing Systems 35 (2022): 406-419.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your detailed review. We clarify below how our work is different from multi-distribution  learning, and how the lower bounds on multi-distribution learning **do not** contradict our upper bound result in Theorem 3.1 / Remark 3.2. \n\n> Could you explain the main differences between this model and that of multi-distribution learning? In particular, are there some natural instances of multi-distribution learning which do not fall into this model?\n\nWe summarize the main differences below:\n\nIn our model, the learning algorithm has access to samples from a source distribution $D$ and access to transformations $T_1, …, T_k$. Thus, by drawing a **single** sample $(x,y)$ from $D$, the algorithm can generate $k$ samples: $(T_1(x), y), …, (T_k(x), y)$ from $T_1(D), …, T_k(D)$. And, we only count the number of samples drawn from $D$.\n\nIn contrast, in multi-distribution learning, the learning algorithm has access to samples from $k$ distributions $D_1, …, D_k$ and it **does not know** the relationship between $D_1, …, D_k$. And, what is counted is the number of samples drawn in total from all $k$ distributions. While, as you noted and based on line 41, it is possible in principle to find a distribution $D$ and $k$ transformations $T_1, …, T_k$ such that $D_i = T_i(D)$. But, that would require the algorithm to **learn** the transformations $T_1, …, T_k$ based on samples from $D_1, …, D_k$ which is going to be more costly than solving the original multi-distribution problem directly.\n\nIn our model, we only consider a covariate shift setting, i.e., the labels do not change under transformations (see Line 29). While multi-distribution learning is more general and allows different labeling functions across the $k$ distributions. \n\nThus, given the above, we can not in general reduce a multi-distribution learning problem instance to a problem instance in our model.\n\n> As described above under weaknesses, why do the lower bounds for multi-distribution learning not apply to the results of Theorem 3.1? Have I misunderstood something about the model in this paper, or perhaps the lower bound instances from [1]?\n\nThe lower bounds from [1] do not apply to Theorem 3.1, because in the setting of this theorem, the learning algorithm is provided access to transformations $T_1, …,  T_k$. And, given a dataset $S$ of $m$ samples from $D$ “source”, the learner can generate $S_1 = T_1(S), …, S_k = T_k(S)$ a total of $mk$ samples by applying the transformations $T_1, …, T_k$. We only count the number of samples drawn from $D$ which is $m$.\n\nWhile the lower bound instance from [1] (e.g. Theorem 4.2) involves $k$ distributions $D_1, …, D_k$ with **disjoint supports** and the learner **does not know** the transformations $T_1, …, T_k$ nor a source $D$ satisfying $T_i(D) = D_i$. The cost of learning such transformations $T_1, …, T_k$ based solely on samples from $D_1, …, D_k$ will be at least $k$ (i.e., drawing at least one sample from each distribution). In general, learning transformations is more costly (and likely an overkill) to achieve the goal of multi-distribution learning. \n\n> Furthermore, as pointed out on line 41, if the domain of the learning problem is \n then Brenier's Theorem implies that for any instance of a multi-distribution learning problem \n with sufficiently \"nice\" distributions, there is a distribution \n and set of \n transformation \n such that \n. Thus, in the case of finite \n on domain \n these two models are equivalent so long as only \"nice\" distributions are considered. The setting of finite \n is particularly important, as it is the setting for which the main results in this paper give oracle-efficient algorithms (given an ERM oracle for \n).\n\nAs alluded to above, another challenge here is: because our model only considers covariate shifts (i.e., the labeling doesn't change across transformations), in order to reduce multi-distribution learning to our model, the transformations that need to be learned have to be \"label preserving\". This is another challenge that will likely make it even more difficult to reduce a problem instance of multi-distribution learning to our model. \n\nWe hope that this clarifies the differences between multi-distribution learning and our model. We are happy to answer any further questions, and would appreciate an updated response from you.", "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": "WOVy5K2lNP", "reviewer": "Reviewer_fSmB", "summary": "The authors study a new framework for learning under distribution shift caused by a family of `invariance maps’ $\\mathscr{T}: X \\to X$. Informally, one may think of this as generalizing e.g. settings such as learning under invariance to rotation, where the maps may be rotation matrices and the learner should perform well at test time regardless of whether the raw data has been rotated.\n\nMore formally, the learner is given a hypothesis class $H$, a family of maps $\\mathscr{T}$, and sample access to a distribution $D$ over $X \\times {0,1}$, and wishes to train a classifier that minimizes the test error over all possible shifts $T(D)$ for $T \\in \\mathscr{T}$, either globally in the sense of outputting $h$ satisfying\n\n$$sup_T \\ \\{ err(h,T(D))\\} \\leq OPT + \\varepsilon$$\n\nWhere $OPT=min_{h_* \\in H} sup_T err(h^*,T(D))$, or where error is measured with respect to the best possible over each individual T (the authors call this regret minimizing):\n\n$$sup_T \\ (err(h,T(D))-OPT_T) \\leq min_{h^* \\in H} \\ (sup_T \\ (err(h^*,T(D))-OPT_T)) + \\varepsilon$$\n\nThis model captures a number of settings considered in the literature. In particular, under reasonable assumptions on distributions $D,D’$ over $X$, there is always a map $T$ such that $D=T(D’)$ (Breiman’s theorem), so the setup does not lose substantial generality over classical study of covariate shift. It may also model transformation invariances as mentioned above, as well as certain types of adversarial attacks (where the adversarial shift is chosen before the adversary sees the test example).\n\nThe main results concern the sample complexity of learning in this framework in the case were 1) H is known to the learner 2) H is unknown and the learner only has ERM access to H.\n\nIn the first setting, the authors show the sample complexity of (proper) agnostic PAC learning in this model is controlled by the VC dimension of the composed class VC(H \\circ T). In other words, it takes at least $VC(H \\circ T)$ samples to properly learn the class, and for any $k$ there exists a VC 1 class H and maps T with $VC(H \\circ T)=k$ which requires $\\Omega(k)$ samples to learn.\n\nTo complement their result, the authors also investigate $VC(H \\circ T)$ for a few special cases, including when $H$ is a composition $f \\circ W$ of an arbitrary linear map W and any fixed $f: X \\to \\{0,1\\}$ and $T$ is a family of linear maps (in which case $VC(H \\circ T) \\leq VC(H)$), some basic non-linear $T$ coming from neural net architectures, and transformations on the hypercube.\n\nWhen $H$ is unknown, the authors give a similar result in the realizable case using data augmentation, and a weaker variant for the agnostic setting for finite $\\mathscr{T}$ which ensures low error across a probabilistic mixture of hypotheses from H via an MWU type strategy.\n\nFinally the authors also consider a related setting in which the learner is in some sense allowed to ignore transforms with bad error, and the learner tries to return a hypothesis with low error across as many of the transforms $T \\in \\mathscr{T}$ as possible.\n\nAt a technical level, most of the results are the consequence of the basic duality of transforming input data and transforming the hypothesis class, allowing the authors to move between $T(D)$ and $H \\circ T$.", "questions": "See above", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The authors introduce a clean theoretical framework for various types of distribution shift and transformation invariance studied in the literature, capturing several interesting problems in the literature. The proposed framework should be of interest to the theory audience at NeurIPS, and is particularly nice in that it allows easy application of classical methods in VC theory to the problem.\n\nThe authors give a (weak) characterization of its statistical complexity in terms VC(H \\circ T), a natural combinatorial parameter of the concept and transformation class.\n\nThe authors discuss several natural scenarios in which their upper bound gives new sample complexity bounds on transformation invariant learning, including settings occurring in modern neural net architectures (namely the composition of linear transformations with activation functions).\n\nThe authors study several natural variants of the framework (global risk, regret, maximizing #transformations with low error) with similar corresponding upper bounds.", "weaknesses": "On the other hand, beyond the main upper bound and examples given by the authors, many of the further results feel somewhat incomplete. For instance:\n\nThe lower bound based on VC(H \\circ T) is weaker than what one typically hopes for in a combinatorial characterization. Namely while the authors show there *exist* classes for which this bound is tight, a strong lower bound (as holds for standard learning) would show this is tight for *every* class. Is there a parameter characterizing the model in this stronger sense? The lower bound also only holds for proper learners.\n\nIn the setting where H is unknown, the use of data augmentation is a bit troubling in the sense that the size of the augmented sample could be extremely large (indeed infinite for infinite T). This isn’t captured by the model the authors introduce which simply assumes the ERM oracle can handle a call of any size, but this does not really seem to capture the computational cost of learning even at an oracle level. Furthermore, the agnostic guarantees in this setting only hold for finite $T$. POST REBUTTAL: The authors have included some discussion re: the first point that helps ameliorate the issue (e.g. using boosting one can lower the batch size to ERM at the cost of log(T) calls).\n\nCombined with the fact that the authors main techniques are fairly standard (note in some cases, as mentioned in the strengths, it is an *advantage* of the framework one can use standard techniques! But this is less the case when these techniques do not seem to give the desired results), these issues prevent me from a stronger recommendation of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your detailed review. We address your comments below.\n\n> When $H$\n is unknown, the authors give a similar result in the realizable case using data augmentation, and a weaker variant for the agnostic setting for finite \n which ensures low error non-uniformly (that is, for each fixed map T, the strategy will do well, but this may not be the case for all T simultaneously as above) across a probabilistic mixture of hypotheses from H via an MWU type strategy.\n\nWe want to clarify and emphasize that in Theorem 3.1, we learn a mixture strategy (a randomized predictor) with a low error guarantee that holds simultaneously across all T (Exactly the same guarantee in Theorem 2.1). \n\n> The lower bound based on VC(H \\circ T) is weaker than what one typically hopes for in a combinatorial characterization. Namely while the authors show there exist classes for which this bound is tight, a strong lower bound (as holds for standard learning) would show this is tight for every class. Is there a parameter characterizing the model in this stronger sense? The lower bound also only holds for proper learners.\n\nThis is a great point, and it is an interesting open question for future work to have a full characterization of what is learnable in our model in terms of $\\mathcal{H}$ and $\\mathcal{T}$. \n\nAs mentioned in Lines 117–124, we think that improper learners could achieve better sample complexity but this remains an open question. One of the main reasons for including the lower bound (Theorem 2.2), is to argue that the sample complexity of the *simple* proper learner in Equation 2 is tight in general, and we can not hope to improve the sample complexity of this proper learner further. While there could be complex improper learners with better sample complexity, we believe that having a proper learner that has a simple description (similar to the ERM principle) is valuable even when it does not achieve the optimal sample complexity. \n\n> In the setting where H is unknown, the use of data augmentation is a bit troubling in the sense that the size of the augmented sample could be extremely large (indeed infinite for infinite T). This isn’t captured by the model the authors introduce which simply assumes the ERM oracle can handle a call of any size, but this does not really seem to capture the computational cost of learning even at an oracle level.\n\nThis is a great point. We argue that for the purpose of achieving the guarantee in Equation (1) in the realizable case, it is necessary to call ERM on the *full* augmented sample. Consider an example of a distribution supported on a single point $(x,-)$ on the Real line where $x = 5$, consider transformations of $x$: $z_i = x+i$ for all $i\\geq 1$ induced by some class $\\mathcal{T}$. Now, calling ERM on a finite subset of these transformations will return a predictor that labels $x, z_1, …, z_{k}$ with a label $-$, and labels $z_{k+1}, \\dots$ with +, which fails to satisfy our objective. \n\nPerhaps we should clarify that we are considering finite transformations (similar to the agnostic case). In which case, the computational cost of a single ERM call on $m*|T|$ samples, grows by a factor of $|T|$. But, with a fairly standard boosting argument, we can also run a classical boosting algorithm that makes multiple calls to ERM. Specifically, we run boosting starting with a uniform distribution on the *augmented sample*. In this case, each ERM call is on samples of size $O({\\rm vc}(\\mathcal{H}))$, and we make at most $O(\\log(m*|T|))$ many ERM calls. So, we have a tradeoff between the size of a dataset given to ERM on a single call, and the total number of calls to ERM. \n\n> Furthermore, the agnostic guarantees in this setting only hold for finite $T$, and hold in the seemingly much weaker non-uniform way mentioned above. It is fairly unclear if either of these constraints are actually necessary.\n\nIt is an interesting direction to extend the result in Theorem 3.1 to classes with infinite $\\mathcal{T}$, perhaps with a certain parametric structure.", "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:
We thank all the reviewers for their helpful input and feedback. 

We emphasize that our contributions are conceptual and theoretical. At the conceptual-level, to the best of our knowledge, this is the first work to model the OOD/distribution shift problem through a transformation function class, which is relevant to many real-world scenarios as discussed in the introduction. As is well known, studying OOD/distribution shift problems requires specific modeling of the relationship between source and target distributions (e.g., bounded density ratios between source and target distributions, which often don't hold in real-world scenarios). Instead, we propose a new way of modeling the problem through the lens of transformations. This allows us to obtain new learning guarantees against classes of distribution shifts, and while these may not require new sophisticated tools, they nonetheless provide bounds that were not covered by prior work.

We believe that it is an asset to be able to leverage the structure of the composition of hypotheses and transformations, and to obtain sample complexity bounds by utilizing existing VC theory (as also highlighted by reviewers RtrA and fSmB), to obtain new insights for this relevant OOD setting.  We further demonstrate this by providing in Section 2.1 several examples highlighting how a simple bound can imply several interesting results and guarantees that are not known before.

Meta-review: The authors introduce a new framework for studying transformation-invariant learning and OOD generalization. In this model, a class of invariances (i.e. transformations) are given to the learner. Therefore, each data point can be regarded as multiple data points across domains (sharing the same label). The model is closely related to multi-distribution learning and DRO. In the realizable setting, it is closely related to learning with the data augmentation, and learning under adversarial perturbations. 

Overall, the new setting and the theoretical results are interesting. The proof techniques are straightforward (e.g., standard use of uniform convergence). Some of the results are somewhat weak (e.g., the agnostic result only works for finite class of transformations, or the VC bound is tight only for some hypothesis classes). As such, this is a borderline paper. 

However, I think the new setting may be of interest to researchers in the field and the shortcomings can be addressed in follow up work. Therefore, I recommend acceptance.
Decision: Accept (poster)