On the Statistical Mechanisms of Distributional Compositional Generalization
Authors: Jingwen Fu
Nanning Zheng
Venue: ICML 2025 poster (2025)
Keywords: Compositional Generalization
Primary area: theory->learning_theory

Abstract: Distributional Compositional Generalization (DCG) refers to the ability to tackle tasks from new distributions by leveraging the knowledge of concepts learned from supporting distributions. In this work, we aim to explore the statistical mechanisms of DCG, which have been largely overlooked in previous studies. By statistically formulating the problem, this paper seeks to address two key research questions: 1) Can a method to one DCG problem be applicable to another? 2) What statistical properties can indicate a learning algorithm's capacity for knowledge composition in DCG tasks? \textbf{To address the first question}, an invariant measure is proposed to provide a dimension where all different methods converge. This measure underscores the critical role of data in enabling improvements without trade-offs. \textbf{As for the second question}, we reveal that by decoupling the impacts of insufficient data and knowledge composition, the ability of the learning algorithm to compose knowledge relies on the compatibility and sensitivity between the learning algorithm and the composition rule. In summary, the statistical analysis of the generalization mechanisms provided in this paper deepens our understanding of compositional generalization, offering a complementary evidence on the importance of data in DCG task.

On the Statistical Mechanisms of Distributional Compositional Generalization
Jingwen Fu'
Nanning Zheng'
Abstract
Harari, 2014). This remarkable ability empowers humans generate an infinite array of ideas and constructs from finite building blocks of knowledge. For example, humans can un- derstand the concept of the "red triangle" after grasping the "red rectangle" and "blue triangle". To mimic human abili- ties, this paper explores the question whether machines can generalize to new data distributions that require recombin- ing knowledge from previously learned distributions. For example, this involves generalizing to the distribution of "red triangle" after learning about "red rectangles" and "blue triangles." " We refer to this type of generalization as Distributional Compositional Generalization (DCG).
Distributional Compositional Generalization (DCG) refers to the ability to tackle tasks from new distributions by leveraging the knowledge of concepts learned from supporting distributions. In this work, we aim explore the statistical mechanisms of DCG, which have been largely overlooked in previous studies. By statistically formulating the problem, this paper seeks to address two key research questions: 1) Can a method to one DCG problem applicable to an- other? 2) What statistical properties can indicate learning algorithm's 's capacity for knowledge composition in DCG tasks? To address the first question, invariant measure is proposed to provide a dimension where all different methods converge. This measure underscores the critical role of data in enabling improvements without trade-offs. As for the second question, we reveal that by decoupling the impacts of insufficient data and knowledge composition, the ability of the learning al algorithm to compose knowledge relies on the compatibility and sensitivity between the learning algorithm and the composition rule. In summary, the statistical analysis of the generalization mechanisms provided in this paper deepens our understanding of compositional gen- eralization, offering a complementary evidence the importance of data in DCG task.
Nevertheless, machines have consistently struggled to em- ulate this level of compositional generalization, as it fun- damentally challenges the prevalent assumption of inde- pendent and identically distributed (IID) between training and test data, cornerstone principle in the machine learn- ing literature (Kawaguchi et al., 2017; Bartlett & Mendel- son, 2002; Bousquet & Elisseeff, 2002; Mohri et al., 2018 8;; McAllester, 1998; Fu & Zheng, 2023; Fu et et., 2023). When faced with the data significantly divergent from the train- ing (support) distribution, achieving meaningful generaliza- tion becomes virtually insurmountable (Koh et al., 2021; Sagawa et al., 2021; Dong & Ma, 2022). This stark real- ity underscores the critical need for a rigorous theoretical examination of DCG, as it holds the key to bridging the gap between human-likk like adaptability and the limitations of current machine learning models in handling unforeseen, complex combinations of concepts.
A dominant theoretical approach to understanding the gen- eralization properties of learning systems is the statistical method. Over the decades, numerous statistically babistically-bbaedd methods have been developed to enhance our understand- ing of generalization behavior under the IID assumption within the PAC learning framework (Vapnik et al., 1998; Vapnik, 1999). A key aspect of these approaches the use of statistical methods to formulate tasks and generalization mechanisms. This shift allows for focus on the statistical properties common across various problems, rather than on specific problems themselves. However, similar results have not been achieved in the area of Distributional Composi- tional Generalization (DCG). Although various explorations of DCG have been conducted. these methods often take dif- ferent perspectives, such identification (Wiedemer et al.,
1. Introduction
Compositional Generalization (CG) represents the capacity to comprehend novel combinations of familiar concepts, an intellectual feat widely regarded as a pivotal milestone in human cognitive evolution (Pearl & Mackenzie, 2018;
Nattiona Key Laboratory of Human-Machine Hybrid Aug- mented Intelligence. National Engineering Research Center for Visual Information and Applications, and Institute of Artificial Intelligence and Robotics, Xi' an Jiaotong University, Correspon- dence to: Nanning Zheng <nnzheng @ mail. wit.ll..j.udu..c.....
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On the Statistical Mechanisms of Distributional Compositional Generalization
2024; 2023) and group invariance (Ito et al., 2022; Lee et al.,
challenge in this theory is to determine an effective measure of the complexity of the function space. Several methods have been proposed for this purpose, such as VC dimension (Vapnik & Chervonenkis, 2015), Rademacher complexity (Bartlett & Mendelson, 2002), and covering number (Shalev- Shwartz & Ben-David, 2014). Besides the complexity of function space, researchers also explore algorithm-based methods, such as algorithm stability (Bousquet & Elisseeff, 2002; Hardt et al., 2016) and information-theoreti analysis (Xu & Raginsky, 2017; Russo & Zou, 2016), to understand generalization. These approaches, like the previous ones, rely on the IID assumption to model data and use statistical laws to understand the generalization mechanism. However, these theories don't fully address the DCG problem, which violates the IID assumption. In this paper, we aim fill this research gap by proposing a theory applied to DCG, using statistical methods to model data and generalization mechanisms.
2024). The statistical properties and constraints of DCG remain unclear. In this work, we aim to explore the statisti- cal properties of DCG. Our research focuses on two main questions:
QI: Can a method for one DCG problem be useful for another DCG problem, and under what circumstances a general method applicable to all DCG problems?
Q2: What statistical properties can indicate a learning algorithm's 's capacity for knowledge composition in DCG tasks?
For Q1, we propose an invariant measure that indicates the existence of a dimension where all different methods for DCG are equivalent. This measure helps us under- stand the mechanisms behind both trade-off and non-trade- off improvements. We demonstrate the critical role of method adaptivity to data in achieving non-trade-off im- provements, which supports the importance of a data-centric approach (Zha et al., 2023) in the DCG problem. Regarding Q2, we present a new generalization bound for the gener- alization error in DCG tasks. By decoupling the effects of insufficient data and knowledge composition, our bound demonstrates that the ability of the learning algorithm to compose knowledge depends on two key factors: 1) the compatibility between the learning algorithm and the com- position rule (Definition 5.1), and 2) the influence of the composition rule on the algorithm's 's output, as measured by mutual information.
Distributional Compositional Generalization (DCG) DCG is a subfield within compositional generalization that has garnered significant attention in recent years. Here, we provide a brief overview of both the applications and theoretical research related to DCG. From an application perspective, DCG is crucial for addressing unseen scenar- ios and mitigating the issue of data scarcity. For instance, in text-to-image generation (Liu et al., 2022: Okawa et al., 2024; Li et al., 2024; Du et al., 2023), solving the DCG problem enables the creation of entirely novel images, such as generating an image of a red panda. Even though red pandas don't 't exist, the distributions of different pandas and animals with red coloration. Similar applications include content and style generalization (Jing et al., 2019; Jin et al., 2022), among others. In reinforcement learning (Silver & Ciosek, 2012; Li et al., 2021; Sutton et al., 1999; Tasse et al., 2022: Bacon et al., 2017), we can only collect the data of the preliminary task and model can solve more complex task by compos- ite. However, without the DCG ability, we have to collect all possible combination of the tasks. From a thcoretical perspective, researchers focus on understanding the mech- anisms for solving DCG problems. Various mechanisms have been analyzed, including disentanglement (Lippl & Stachenfeld, 2024; Wang et al., 2022; Bengio et al., 2013), identifiability (Wiedemer et al., 2024; 2023), and others (Ito et al., 2022: Lee et al., 2024). However, the statistical prop- erties of DCG and its constraints remain largely unexplored. This paper seeks to address this gap by analyzing the sta- tistical properties of DCG, an area that has been mostly overlooked in previous research.
infer this image by combining
In summary, the key contribution of this paper is providing statistical analysis of the generalization mechanisms in the DCG problem, offering complementary perspective to prior research. Specifically, it provides an invariant measure and explores the relationship between the learning algorithm and the composition rule.
2. Related Works
Statistic Generalization Theory Statistical generaliza- tion theory (Vapnik et al., 1998; Vapnik, 1999) is subfield of statistical learning theory that seeks to understand the mechanisms of generalization from a statistical perspec- tive. In this context, data is typically modeled under the IID assumption, meaning that both the training and test data are assumed to come from the same independent and identically distribution. The theory explores generaliza- tion mechanisms through the central limit theorem, often within the PAC-learning framework. In this framework, the learning process involves finding a function from a function space that fits the training data. Due to the central limit theorem (Rouaud, 2013), simpler function space tends to result in a smaller gap between the training error and the test error, known as the generalization error. Therefore, a key
2

---

On the Statistical Mechanisms of Distributional Compositional Generalization
3. Problem Definition
3.2. Compositional Distributions
3.1. Preliminary
Subdistribution We denote the two compositional com- ponents a E A and b E B. The other components, including randomness, are denoted as Ç. The overall data distribution P= can be divided into several subdistributions based on the different values of the compositional compo- nents. These distributions are {Pa. (a..).eA.bBBB. The Pa,)(z) satisfies that Pa,o(=) A| [B] (a. a))((__m)) where a.. by are the corresponding fact values of the sample z. To ensure that each sample has only one determined factor value for each factor, the distribution should satisfy that for any a1, b1, 02 b2 where 01 o 02 or b1 * b2, we have supp Pay,b. O Suup Pag = 0.
Notations In this paper, we employ P to signify the dis- tribution and P(.) to denote its corresponding density. Bold symbols represent random variables, while unbold symbols represent their corresponding values. For random vari- able æ, Pa represents its distribution. The calligraphic font is used to denote the space or learning algorithm. I(::-) denotes the mutual information. And E denotes the expecta- tion.
P=(=)
Sample Space and Distribution In this analysis, we consider data space 2, which can be decomposed into two parts in some case, i.e. 2 = X x Y. where X' and ) are two spaces. We use the notation z to denote random variable that takes value in the space Z. The distribution of this random variable is represented by the notation Pz.
Distribution split We denote E = A x B as the all possible combinations of the component a, b. We define S, U as a partition of the set E, i.e Uns = 0 and UUS E. Based on the partition, the distribution can be divided into the support distribution Ps (a. and target distribution Py = (a. We denote err(Ps. f) [)] and similarly for err(Pu. f). We denote f& as the random variable sampled from A(Ps) and the same for fo and fg-
Function space The function space is denoted by the symbol F. where f : 2 + R F. The function f assigns loss to the corresponding data point. Given the data distribution Pz. the error is denoted as err(Ps, f) Ez-r, Similarly, the corresponding error can be ex- pressed as err( f) = 1. ExeD. f(z) for the finite sam- ples D, ~ p For supervised learning, where 2 = yz. we can decompose the function ff as f = [(h(z), z). where 1 the loss function and h is the function that maps the input to its corresponding prediction.
Remark 3.1. In this paper, we primarily focus on DCG involving two components. The analysis of two-component DCG serves as a fundamental basis for addressing more complex DCG issues. (Dong & Ma, 2022; Wiedemer et al., 2024; Ren et al., 2024; Petrache & Trivedi, 2024; Chomsky, 2002; Partee et al., 1995; Gordon et al., 2019; Silver & Ciosek, 2012; Li et al., 2021; Sutton et al., 1999; Tasse et al., 2022; Bacon et al., 2017; Wiedemer et al., 2023; Brady et al., 2023).
Learning algorithm Given the function space, the role of the learning algorithm is to find suitable functions for the given problem. Here, we denote the learning algorithm as A: DD- + PF,, where 'D denotes the space of all training data and PF denotes the space of all distribution on the function space. The output of the learning algorithm is regarded as a distribution over the function space, rather than single function because the learning algorithms typically encompass a degree of uncertainty, for instance, stochastic noise in optimization. We denote the operation on dataset Dr as ADD,), and similarly, we denote the operation on the infinite data sampled from P2 as A(2z). In this paper, the learning algorithm includes not only the optimizer (e.g. SGD, Adam), but also any constraints or techniques that influence the selection of functions from the function space.
In the following, we give several examples:
Example 3.2. (Image) the context of single object images, let A denote the shape of the object and its size. We define Pa,b as the distribution of images of shape a and size b.
Example 3.3. (Robot) We consider a task distribution for robots consisting of walking task and an operational task. Let set A denote sequence of walking subtasks, while set B denotes a collection of operational subtasks. We define distributions such as Pay, for slow walking and object picking tasks, Paz,b for regular walking and object pick- ing lasks, and Pay for slow walking and object stacking tasks. The target distribution, labelled Pay,yy is specifi- cally tailored for tasks involving slow walking and object stacking.
Induced Distribution Given the learning algorithm A, we use ((4) to denotes the distribution induced by the learning algorithm A. Given a data distribution Pz, we denote / A A(Pz) and the corresponding density is denoted as 0/1p, (f)Pz) and the random variable as f. We will drop the subscript Pl 2 if no ambiguity caused.
Remark 3.4. Certain DCG tasks require models to mas- ter basic components before progressing to more complex challenges. Take robot learning as an example: initial tasks may focus only on activities such as walking and retrieving objects independently. Subsequently. the network needs to extend its understanding to situations where the robot
3

---

On the Statistical Mechanisms of Distributional Compositional Generalization
performs both activities simultaneously. In such cases we introduce the null component U. The distribution related to single component can be represented as Pa. or Pa.b- We can set A'= = A U @ and B' = B U.
4. Invariant Measure
When tackling a problem, it's common to wonder what the approach will entail. The central question is whether universal method can be applied specialized methods are required for each. To determine this, we must explore how methods for different tasks relate to one another. If a method that works well for one task also proves effective for others, a general approach might be feasible. However, if a method succeeds in one task but fails in others, it becomes essential to develop task-specific strategies rather than relying on a single general method, This section will propose an invariant measure to answer this question.
range of tasks or if
3.3. Distributional Compositional Generalization
In this section, we set out to formulate the DCG. The re- lationship of the DCG problem can be summarised in the diagram:
T
A
s
B
T
(1)
P
err err(Pt (P () fs)
4.1. Analysis
Composition Rules and Data Generation For any two different distributions, Pe.: Pez E Pg. there exists a com- position rule T that connects them. This composition rule acts bridge for these different distributions to become part of a problem. We define a generation function g(-) such that P/ = g(T,E), where (T) is used to emphasise that the distribution generated by the composition rule T, and & refers to all the other information needed to generate the distribution. For example, if we consider the shape and color composition of an object, then T contains the shape and color components and their composition method. The & represents the information other than shape and color, such as position. Usually the & follows certain distribution Pe- We denote this as P g(T)), where the & is omitted to indicate that it is randomly sampled from the distribution Pe.
In this section, we aim to analyze the learning algorithm's s ability to predict the correct composition rule. However, a gap exists because the outputs of the learning algorithm lie in the function space, while the composition rules reside in a different space. To bridge this gap, we introduce the function 3(.). which connects these two spaces and allows us to make this comparison.
Definition 4.1. We consider a rule prediction function 3 FF - T, such that for any function F, we have Ty B(J) ET.
Remark 4.2. Normally we expect that (()) can satisfy the a small value. However, the choice of ((-) is not important in this paper, since the following theorem holds for all B()). as long as their output is a valid composition rule in space T. When B(-) operate on the random variable f. we can obtain an- other variable π = B(f). Its correspoding distribution is denoted as ((A..9) The subscript is omitted if no ambiguity caused.
condition that for all f(-), err(f, crr(f.Pfr)) pffr) )
Example 3.5. In image creation, the composition rule can be represented as (set of shapes, set of colors, "Draw the contour of <shape> and fill it with <color>."). Similarly, for robotic task, the composition rule can be expressed as (set of subtaskl, set of subtask2, "First, complete <subtaskl>> >,, then <sublask2>."), Keep in mind that we use text to describe the compositional rule here, but it can take any form as long as it defines how two com- ponents are combined.
The learning algorithm identifies the composition rule based on two mechanisms: the inherent bias of the learning algo- rithm and the adaptivity of the learning algorithm. The first refers to the learning algorithm's 's preference for one compo- sition rule over another, and the second refers to the learning algorithm's 's ability adjust its predictions in response to the data provided. This leads to the following research question:
Function Space and Learning Algorithm Typically, the method for solving machine learning problem involves two options: 1) design a function space that is more suit- able for the given problem, and 2) design a better learning algorithm. In this paper we assume that we are given a large and fixed function space that contains almost all possible functions. We can consider the design of suitable func- tion space as hard constraint on the learning algorithm. More specifically, this hard constraint means that only part of the function space can be a legal output of the learning algorithm, although the learning algorithm operates on the rather large function space.
How can these two mechanisms be modelled and combined in the statistical framework??
To give analysis, we first need mathematical modelling of these two mechanisms:
1) Inherent Bias First, we represent the bias of the learn ing algorithm as ((A.A)(T) which is the marginal distri- bution over all possible training data, The T indicates the
4

---

On the Statistical Mechanisms of Distributional Compositional Generalization
prediction of the composition rule using 9(.). This formula- tion is appropriate because the prediction is not conditioned on any specific data. For two composition rules Ti and T2, if Q(A.8) (T Ti)= > Q(A.8) (T T2), we say that A is biased towards Ti over 72.
(2) For any A1:A2. the following equation holds
(3((A)) =1a(AA2)
(3)
where p(A) = Σr B Bpg ( P(T) A).
Remark 4.3. Inductive bias refers to model's inherent preference for certain compositional rules before it is posed to any training data for given task. This bias can be introduced in two primary ways: 1) Model Architecture De- sign: By carefully structuring the model, we can constrain its outputs to adhere to specific compositional rules. 2) Pre- training and Objective Function: The inductive bias can also be shaped through pretraining strategies or the choice of objective function, either suppressing reinforcing the model's tendency toward certain compositional behaviors.
4.3. Discussion
In the following, we refer the a as the one that satisfies the invariant property listed in Theorem 4.5. We rewrite the definition of the y-measure as follows,
Ma(A) Σ
B pm (T, P .A)
T
(T= TT-
(4)
E
Pm ~g(T)
(T,((T,P'))
T
2) Adaptivity The second is the adaptivity of the learning algorithm, which refers to its ability to adjust its predictions in response to the data provided. Based the definition, intuitive method is to represent as (T. T; P!)). We denote this as -:) because the calculation of mu- tual information relies Q(A.8), which is influenced by
constant.
Recall that if we obtain the composition rule, then we can reconstruct the ground truth distribution p(T) Therefore, the composition rule is the core of our concern in the DCG problem. Q(A.9)(T = TIPS") is the probability that the learning algorithm will predict the correct composition rule,
the learning algorithm A and the rule prediction function B.
Based on this, we use the probability Q(A.9)) (f P as a measure performance.
4.2. Theorem
Based the previous statistical formulation, we go into the definition of the invariant measure. Invariance means that this measure is the same for different learning algorithms. As a result, it can serve as a tool for analyzing both the trade-offs and non-trade-off improvements between differ- ent tasks.
Trade-off Recalling the definition of the DCG task in section 3.3, we can specify a DCG task with the T, PS In this sense, the calculation of (x( can be seen as an aggregation of the value of the μ measure across different tasks. If (T, (S)) is fixed, we can get clear trade- off between performance on different tasks. This can be achieved by choosing a different learning algorithm but with the same value of a, (T, P!?)) for different tasks. In this situation, increasing the performance of one task with non-zero a (T. P(T)) will result in decreasing the performance of other tasks.
Definition 4.4. Given the composition rule T, the distribu- tion Pss. the learning algorithm A and the rule prediction function 3. and function aA. T x P + RR, we define the y measure as
(T (ST , .A Qf (TPP5)))
(2)
(T,
Beyond Trade-off' Then we come to the other problem, which is how to improve performance on one task without sacrificing performance on other tasks. The inituition is that if we can improve the performance by fixing its corre- sponding p-measure fixed. Recall the definition of the μ measure that (3, P(T), ,A) (T=7))=)))
where p(fs) (fs is the prediction made by the Lean- ring algorithm) and P!T) is the support distribution gener- ated by the composition rule T.
aA.s(T.P,))) So we need to increase 0,4,3 (!T) and QT (TT at the same rate. In this way, we improve performance without altering the μ measure. making it a non-trade- off improvement. Moreover, Based the equation that E Pg. log (A), = LA,o(T = T.P? we can conclude that the statistical dependence TA,
With the μ measure defined above, we provide the invariant property of this measure with respect to different methods:
Theorem 4.5. (Invariant Property) There exists at least one function a such that for any B, the p-measure satisfies the following conditions:
(1) For any
T, P! and A. we have
T: p!!)) plays an important rule in non-tree non-trade-ofi improve- ment.
E p log (. P ) IA, ( T; T:P (())
5

---

On the Statistical Mechanisms of Distributional Compositional Generalization
The analysis suggests that de- veloping methods adaptable data, with careful data gineering, is promising approach for effectively solving DCG. The relationship between non- con-trade-off improvements and (T = T; ) highlights the inevitable sensitiv- ity of data methods applicable across various tasks. As result, careful data engineering is essential, supporting the data-centric Al approach (Zha et al., 2023).
Implication for practice
likely to occur in practice.
5.1. Decouping the influence of insufficient data
Unlike the generalization analysis in the IID assumption, the generalization error of the DCG comes from two sources: The first one is due to the insufficient data and the second one is due to the fairness of combining the prior knowledge to handle the new situation. We refer to the first as the IID error and the second as the CG error. This leads us to the research question:
Compared with previous studies. 1) Research in DCG. Previous work (Dong& & Ma, 2022; Dziri et al., 2024) has discussed how a method that is effective for one task may struggle to solve another. While these studies are similar to ours in exploring the relationship between method's s performance on different tasks, they primarily focus on DCG problems with specific composition rules. In contrast, our work proposes an invariant measure that reveals the underlying mechanism and is applicable to a wider range of situations, as it considers the relationships between all different composition rules. 2) Compare with No free lunch theorems. Another well-known theorem addressing the trade-off between method's performance across dif- ferent tasks is the "No Free Lunch" (NFL) theorem, which primarily focuses on problems in optimization (Wolpert & Macready, 1997), search (Wolpert et al., 1995), and super- vised learning (Sterkenburg & Grünwald, 2021; Wolpert, 2021; 2002). Further details on the NFL theorem can be found in references (Adam et al., 2019; Joyce& & Hermaann, 2018; Ho & Pepyne, 2001; Ho et al., 2003; Yang, 2012; Rowe et al., 2009). The NFL theorem states that, when averaged across all possible problems, any two methods are essentially equivalent. The main difference between our study and the NFL. framework lies in two key areas: 1) Our work focuses on the composition rule T, and our theorem is not limited any specific learning problem, such super- vised learning (Wolpert & Macready, 1997; Wolpert al., 1995) or unsupervised learning (Sterkenburg & Grünwald, 2021; Wolpert, 2021; 2002). As long as the problem falls within the DCG category (defined in Section 3.3), our the- ory applies. 2) While the NFI. theorem discusses trade-offs between tasks, our theory highlights non-trade-off improve- ments specifically within the DCG problems.
How to seperate the influence of insufficient data and lack of knowledge composition on generalization error?
To make such an analysis possible, we first need to identify the influence of the insufficient data, and then we need to model this influence in a mathematical way.
1) Evaluation. Given a function f. the generalization error refers to the gap between the error on the target distribution, err (Pu; f), and that on the training data, i.e., err err(Dn: J). To understand this gap, decompose the generalization error into two terms:
err( (u. 1) err( (Dn;
err(Ps, - err err(prr) J) + err (er((Pu.)) err(Pss)))
ITD error
CG emror
(5)
The "IID error" can be thought of as the generalization error under the IID assumption. The "CG error" is the focus here.
2) Function selection. As for the CG error, even though we eliminate the aforementioned influence by evaluating all functions/ f on the target distribution Pv. there is still an uneliminated influence from the insufficient data. This influ- ence comes from the fact that the function f is sampled from A (w)) instead of A(PS")) ) In short, the learning algorithm operates on the insufficient data. Based on this, we introduce le. [r)(Pe.fss-err('s..
p. (note that JD. ~ A(D.)) to decouple these influences. Kn quantifies the variation in the performance gap between the support distribution and the target distribution over dif- ferent numbers of training samples. The Ki. satisfies that 1im Kn, = 1. This indicates that the influence of Kn. disappears when given infinite data to learn.
Kn A max Pp)
5. Statistic Mechanism of Knowledge Composition
Summary Based on the above analysis, we can decom- pose the generalization error as:
In the previous section, we are concerned with the situation over all possible composition rules. However, composi- tion rules have different probability of occurring in certain scenarios. Therefore, in this section we consider the prob- lem that the composition rule follows a certain distribution T PT and p! (T)). Dn, is the data set sampled from the distribution P(T). By modifying the distribution Pr, we can emphasize the composition rules that are most
jerr(Pu, fD..)
-..uff..-eer(00 err(Dn, DD S |err((ss f fD.)) ) err((D,, fDD (6) + knreer( Ss) ()) err( fs)l-
As |eere (Ps, -er,))r((D.... fD.)) can be an upper bound using any generalization theory with IID assumption,
6

---

On the Statistical Mechanisms of Distributional Compositional Generalization
is focused in this paper, this term comes from the nature of compositional general- ization.
(PrrPPu fss (sr fs) s)]
Kn min /2, - where lim fin Note that 4 (x) monotonically increasing function with respect to
5.2. Theorem
5.3. Analysis
In this part, we aim to provide generalization bounded by the statistical properties of the DCG problem. We start with the assumptions used:
1. Knowledge composition. As shown in the previous analysis, the generalization error of the DCG comes from two sources: insufficient data and knowledge composition. In this paper, we examine our generalization bound when infinite data is given so that we can focus on the knowledge composition. In this situation, we come to the following conclusion:
Definition 5.1. The incompatibility between the composi- tion rule and the learning algorithm is defined
sup T (T. =B PTT) p() ~a(T) Mc MMCM
sup
(7)
Corollary 5.8. Under Assumption 5.3 and 5.5, and 1im GenITD = 0, then have
(err(P Mi f M1) err(( err(P (P)
M1 Ma2 Aaa)
where M, ~ A(PM, and f M, A(P M.)) Remark 5.2. Given a random variable T, (T, ET-P, (T)
Feler((Pu,5e Jss
(9)
S SoLAafssT(PP! + AT),
Assumption 5.3. (L-bounded) The error function err(::) is L--ounded, i.e. for all valid inputs P. we have lerr(P. f)l < L.
where x(x) /./mnn (x/2, min exp(-x))
Remark 5.9. In this corollary, we assume that O. Recall that GenIID can be
lim GenIID equal to any generalization bound under IID condition. There are many IID generalization bound that can ensure lim GenITD - O, including VC dimension (Vapnik & Chervonenkis, 2015), Rademacher complexity (Bartlett & Mendelson, 2002), covering number (Shalev-Shwartz & Ben-Davin 2014), algorithm stability (Bousquet & Elis- seeff, 2002; Hardt et al., 2016) and information-theored analysis (Xu & Raginsky, 2017; Russo & Zou, 2016).
Remark 5.4. Assumption 5.3 requires that the error is bounded. the solution performs poorly on small subset of data points but performs well on the rest, the average error could be disproportionately large due extreme errors in that small subset without this assumption. This assumption can be easily satisfied by modifying the original error using a min(err, bound) operation. Alternatively, a bounded error measure, such as 1-accuracy, which ranges between 0 and I, can be used.
Remark 5.10. This corollary reveals small value of (Ta s: T: (T, is essential for knowledge composition.
Assumption 5.5. Given the distribution Pf7) g),, there exist functions me; my such that 7 = mr((P) (TT) and & = m for any E and * 0.
Remark 5.6. Assumption 5.4 requires that the DCG prob- lem is solvable. Our bound does not apply to DCG problems that are entirely vnsolvable. This assumption ensures that, given all distributions, we can learn how the given compo- nents are combined. For example, if provided with images of various shapes and colors, we should be able to under- stand how shape and color interact to form specific images, such as a the image of red triangle. This assumption guaran- tees that there exists way recover these compositional rules from the data.
2. Trade-off between the compatibility and ML The previous analysis reveal the relation between @La(f T T(P(")) + -(T,A) and knowledge composition.
However, the relationship between
(LA(s s: TIP(")) and r(T, is still unclear. To under- stand this relation, we must first examine the relationships among the elements involved the calculation of mutual information, as illustrated in the following diagram:
((T)
fs
A
Theorem 5.7. Under Assumption 5.3 and 5.5, given training data D,, E n sampled from the support distribution Ps, learning algorithm A, then we have
(10)
T
(TT,A)
(ferr(Pu: f p..) err(Dnn, f p,)Il
(8)
From this diagram, we discover that trade-off exists be- tween & (TA(f s; ( T)) and (TT,AA. More specifi- cally, when constraint is placed on T), fs and T are independent such that L:(fs:Tip T = 0. In this scenario, the generalization bound can become very large
< GenITD T. (T (T, where GenIID denotes any generalization error bound with IID assumption, the subscript of L((;-) de- notes influence of A through Q(A), and (x(x) A

---

On the Statistical Mechanisms of Distributional Compositional Generalization
because 7 (A,,T) can be very large. One possible solution is to impose a constraint such that T (A,,) T) S when design the learning algorithm. By applying this constraint, we cre- ate dependency between T and A through conditioning on (), which leads a non-zero value of LA(fs: si T)PS")
And we construct 64 composition functions, referred as Ti, ,.,..., ,To4
2. Distribution Split: The support distribution takes the elements in the set {(e1, e2))(e,,)) E x b1 Uag x b1 U an x 62). The target distribution take elements in the set {(e1,e2)((e) e2)(((),))) e2) C 02 x 62). It is easy to verify that these designs satisfy the requirement listed in Section 3.
3. Compared with previous studies 1) From tech- nique perspective, this is the first paper that decouples the influence of finite samples and knowledge composition in generalization analysis in out of distribution. (Netanyahu et al., 2023; Qiu et al., 2021; Oren et al., 2020; Hosseini et al., 2022). This decoupling allows us to focus on the influence of knowledge composition on generalization error, which is at the core of DCG problems. What's more, it allows us to reuse the knowledge from the generalization analysis in the IID situation and reduce the duplication of work. 2) Compared with generalization bounds in DCG, Previous works (Netanyahu et al., 2023; Dong & Ma, 2022) provide generalization bound methods for DCG problems that are tailored to specific tasks. This means that their works mainly consider the problem using specific compo- sition rule. The unique features of our theory are that: 1) Our bound is tractable for different composition rules; 2) Our bound connects the generalization behaviour with the y"; this further reveals the statistical mechanism of the compositional generaliza- tion. 3) To illustrate the tightness of our bounds, we compare our bound with that of Ben-David et al. (2010), which is a general bound for out-of-distributin generaliza- tion and is therefore comparable to ours. The details are given in the Appendix B.4. Here we list the results of the comparison. We find that cannot simply say that one method is tighter than the other. We divided the DCG tasks into two types: one dominated by the learning algorithm and one dominated by the function space. In the first situation, the performance of the DCG is highly dependent on the learning algorithm and our bound is much better than Ben- David al. (2010). This is reasonable because Ben-David al. (2010) doesn't 't take into account the influence of the learning algorithm. When it comes to the second situation, we find that our bound is better when there are relatively good support distributions, i.e. when |S] is large. On the other hand, the (Ben-David et al., 2010) is better when |S| is small.
3. Sequence design: The input sequence is "ei, e2, I1, r2, r3, where 72, 13 are random words that simulate the randomness. The expected completed sequence is "e1, E2, ri, 72, r3,#t e1, e1, e2, e1, e1,e1" if the composi- tion rule is (e1,02) - G1, C2 61, C2, C1, C1-
4. Learning algorithm design: our paper, we define the learning algorithm as the mapping between data and the learned function, encompassing a broader concept than just the optimizer. To simulate learning algorithms with vary- ing inductive biases and adaptivity, we adopt the following approach:
1) We employ the GPT-2 model with two configurations:
Setting 1: 4 layers, 4 attention heads, and an embed- ding size of 128.
mutual information "Ia(f s: T
Setting 2: 6 layers, 8 attention heads, and an embed- ding size of 256.
2) We pretrain the GPT-2 model using different pretraining data schedules. The pretraining data is generated from a subset of composition rules same to those in the downstream task, but with entirely different words. This setup allows us to create learning algorithms with different inductive biases and adaptivity while preventing data leakage.
6.2. Experiemnts trade-off and non-trade-off' improvement
On of the key point in this paper is that the non-trade-off improvement has to rely on the adaptivity of learning algo- rithm (detail see beyond trade-off page 5). To verify this conclusion, calculate AA, (? = T, Ps), which is measure of adaptivity used in out paper, and GACC, which is the average performance across all the tasks with compositional rule in T2, TT,,.... ,To1. The results are given in Table 1.
6. Experiment
6.3. Experiments on Generalization Bounds
6.1. Experiment Design
We conduct the experiments with different rule complexity using the best pretrain setting in previous section. Rule complexity refers to the length of the rule on the output side. For example, the rule complexity of (e1, + e,, C2, C1, 62, el is 6, while the rule complexity of (c1,e2) + e1, E2; C2,6,, c1, e1, c1, is 8. The results (given table 2) indicate that our generalization bound
1. Components and Compositional rule: We construct two words set A,B satisfying AA| = |B] = 1000 and their corresponding element Ø1, .2 C A and b,, b2 C B. an 02 is a partition of A and the same as b1, bz. |ai| = [22] = [611 = |b2] = 500. The composition rule can be any function that satisfy the following form: e2) + e1ege1e2e1e1-
8

---

On the Statistical Mechanisms of Distributional Compositional Generalization
LA Ps)ss)
0.073
0.115
0.125
0.281
0.362
0.462
0.481
0.505
0.527
0.564
GACC
0.605
0.591
0.565
0.633
0.696
0.750
0.772
0.789
0.752
0.776
Table 1. Values LA = T, Ps) and GACC over 10 instances
is more tighter than the bound of Ben-Davis et al.
1) (Section 4) Improving the adaptivity of the proposed method is crucial. Without adaptivity, we run the risk of facing zero-sum situation, where improving performance on one task may lead to reduced performance on others.
Rule Complexity
6
8
10
12
CG Error
0,223
0.262
0.301
0.342
Ben-David et al.
0.622
0.680
0.701
0.690
2) (Section 5) We have found that the knowledge compo- sition ability of method for given task can be assessed using (f s;
Ours
0,271
0.295
0.351
0.372
(TT)))) +T, This reveal the im- portance of the learning algorithm that not only be compati- ble with the compositional rule but also be sure its output less influenced by the compositional rule.
Table Performance comparison across rule complexities
7. Discussion
In summary, this work offers insights into the generalization mechanisms underlying DCG problems. These insights, along with the introduction of new paaccctts-particlaary the connection between statistical relations and generaliza- tion error can be leveraged to guide the development of methods.
Q: What are the key properties of data-centric approaches solving the DCG problem?
Our theory suggests that data-centric approach is funda- mental for achieving non-trade-ofi improvements. It high- lights the following key properties of data-centric methods:
Data-centric methods should effectively leverage infor- mation from the data itself. Injecting human task-specific knowledge into method design-such as using special- ized model architectures or loss functions may hinder the method's ability to learn directly from the data.
9. Conclusion
This paper aims to understand the generalization mecha- nisms of the DCG from a statistical perspective. This serves as a complementary view to previous studies. More specif- ically, our findings include: 1) We propose new way to model the internal bias and the adaptivity of the learning al algorithm separately. Based on this, we propose the μ mea- sure to analyse the trade-off and non-trade-off improvement. 2) To bridge the statistic properties of the learning algorithm with its knowledge composition capacity, we first provide way to separates the influence of the insufficiency data and that of the knowledge composition. Then, we identify that small & (f s: P + (T),A) is important for better knowledge composition ability.
2. Theory 5.7 further asserts that compatibility between the learning algorithm and the data is crucial. This implics that the learning algorithm should achieve uniform performance across different compositions within the support distribu- tion. For example, if the support distribution includes red triangles and blue rectangles, the model's 's performance red triangles and blue rectangles should be similar.
3. Regarding the requirements for the data engineering phase, our theory supports the co-design of both the solution (including network structure and objective function) and data collection. Since the value of IA.o(T = T. Ps) in theory depends on both the learning algorithm and the data, theory cannot prescribe universally optimal data development method independent of the specific approach. However, certain data quality requirements, such as the absence of label noise, are absolutely essential.
Acknowledgements
The authors gratefully acknowledge the support from the National Natural Science Foundation of China (Grant No. 62088102).
Impact Statement
8. Limitation
The primary goal of this paper is deepen human under- standing of specific machine learning problem. Our work doesn't it have direct influence society. However, future works based on our work may influence society but it is unpredictable currently.
This paper aims to provide theoretical understanding of compositional generalization. Consequently, the analysis presented here does not directly address specific DCG prob- lems. However, we argue that the theoretical insights are valuable and can inspire the development of better methods. These findings include:
9

---

On the Statistical Mechanisms of Distributional Compositional Generalization
References
Fu, J., Zhang, Z.,, Yin, D., Lu, Y., and Zheng, N. Learning trajectories generalization indicators. arXiv preprint arXiv:2304.12579, 2023.
Adam, S. P., Alexandropoulos, S.-A. N., Pardalos, P. M., and Vrahatis, M. N. No free lunch theorem: A review. Approximation and optimization: Algoritims, complexity and applications, pp. 57-82, 2019.
Gordon, J., Lopez-Paz, D., Baroni, M., and Bouchacourt, D. Permutation equivariant models for compositional generalization language. In International Conference on Learning Representations, 2019.
Bacon, P.-L., Harb, J., and Precup. D. The option-critic architecture. Proceedings of the AAAI conference on artificial intelligence, volume 31, 2017.
Harari, Y. N. Sapiens: A brief history of humankind. Ran- dom House, 2014.
Bartlett, L. and Mendelson, Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 462-2882 2002.
Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. In Inter- national conference machine learning, pp. 1225-1234. PMLR, 2016.
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
Ho, Y.-. and Pepyne, D. free lunch theorem of optimization. In Proceedings of the 40th IEEE conference on decision and control (Cat. No. 01CH37228), volume 5, pp. 4409-4414, IEEE, 2001.
L. Simple explanation of the no
Bengio, Y.. Courville, A., and Vincent, P. Representation
learning: A review and new perspectives. IEEE transac- tions on pattern analysis and machine intelligence, 35(8): 1798-1828, 2013.
Ho, Y.-C., Zhao, Q.C.., and Pepyne, D. L.. The no free lunch theorems: Complexity and security. IEEE Transactions on Automatic Control, (8(5))7835))))79 2003.
Hosseini, A., Vani, A., Bahdanau, D., Sordoni, A., and Courville, A. On the compositional generalization gap of in-context learning. arXiv preprint arXiv:2211.08473, 2022.
Bousquet, O. and Elisseeff, A. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Brady, J.. Zimmermann, R. S., Sharma, Y., Schölkopf. B., Von Kügelgen, J., and Brendel, W. Provably learning object-centric representations. In International Confer- ence on Machine Learning, pp. 3038-3062. PMLR, 2023.
Ito, T., Klinger, T., Schultz, D., Murray, J., Cole, M., and Rigotti, M. Compositional generalization through ab- stract representations in human and artificial neural net- works. Advances in neural information processing sys- tems, 35:32225-32233 2022.
Chomsky, N. Syntactic structures. Mouton de Gruyter, 2002.
Jin, D., Jin, Z., Hu, Z., Vechtomova, O., and Mihalcea, R. Deep learning for text style transfer: A survey, Computa- tional Linguistics, 48(1):155 205, 2022.
Dong, K. and Ma, T. First steps toward understanding the extrapolation of nonlinear models to unseen domains. arXiv preprint arXiv:2211.11711 2022.
Jing, Y., Yang. Y., Feng, Z., Ye, J., Yu, Y., and Song, M. Neural style transfer: A review. IEEE transactions on visualization and computer graphics, 26(1 26(11):3365-3385 2019.
Du, Y., Durkan, C., Strudel, R., Tenenbaum, J. B., Diele- man, S., Fergus, R., Sohl-Dickstein, J., Doucet, A., and Grathwohl, W. S. Reduce, reuse, recycle: Composi- tional generation with energy-based diffusion models and meme. In International conference on machine learning, pp. 8489-8510. PMLR, 2023.
Joyce, T. and Herrmann, J. M. A review of no free lunch theorems, and their implications for metaheuristic optimi- sation. Nature- inspired algorithms and applied optimiza- tion, pp. 27-51, 2018
Dziri, N., Lu, X.. Sclar, M. Li, X. L., Jiang, L., Lin, Y., Welleck, S., West, P., Bhagavatula, C., Le Bras, R., al. Faith and fate: Limits of transformers compositionality. Advances in Neural Information Processing Systems, 36, 2024.
Kawaguchi, K., Kaelbling, L. P., and Bengio, Y. Generaliza- tion in deep learning. arXiv preprint 171i::17 1(8), 2017.
Koh, P. W., Sagawa, S., Marklund, H., Xie, S. M., Zhang, M., Balsubramani, A., Hu, W., Yasunaga, M., Phillips, R. L., Gao, I., et al. Wilds: A benchmark of in-the- wild distribution shifts. In International Conference on Machine Learning, pp. 5637-5664. PMIR, 2021.
Fu, J. and Zheng, N. Generalization error bounds for iter-
ative learning algorithms with bounded updates. arXiv preprint 2r09 200.0770 2023.
10

---

On the Statistical Mechanisms of Distributional Compositional Generalization
Lee, J. H., Mannelli, S. S., and Saxe, A. Why do animals need shaping? theory of task composition and curricu- lum learning. arXiv preprint 2402
Qiu, L.,, Shaw, P., Pasupat, Nowak, P. K., Linzen, T., Sha, F., and Toutanova, K. Improving compositional general- ization with latent structure and data augmentation. arXiv preprint arXiv:21 2021.
2024.
Li, B., Lin, Z.,, Pathak, D., Li. J., Fei, Y., Wu, K., Xia, X., Zhang, P., Neubig, G., and Ramanan, D. Evaluating and improving compositional text-to- text-to-visual generation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 5290-5301, 2024.
Ren, Y., Lavoie, S., Galkin, M., Sutherland, D. J., and Courville, A. C. Improving compositional generaliza- tion using iterated learning and simplicial embeddings. Advances in Neural Information Processing Systems, 36, 2024.
Li, Y. Wu, Y., Xu, H., Wang, X., and Wu, Y. Solving compositional reinforcement learning problems via task reduction. arXiv preprint arXiv:2103.0760) 2021.
Rodríguez Gálvez, B., Bassi, G., Thobaben, R., and Skoglund, M. Tighter expected generalization error bounds via wasserstein distance. Advances in Neural Information Processing Systems, 34:19109-19121, 2021.
Lippl, S. and Stachenfeld, K. When does compositional structure yield compositional generalization? kernel theory. arXiv preprint arXiv:2405. /6331) 2024.
Rouaud, M. Probability, statistics and estimation. Propaga- tion of uncertainties, 191:1110, 2013.
Liu, N., Li. S., Du, Y., Torralba, A., and Tenenbaum, B. Compositional visual generation with composable dif- fusion models. In Europeun Conference on Computer Springer, 2022.
Rowe, J. E., Vose, M. D., and Wright, A. H. Reinterpreting no free lunch. Evolutionary compatation, 17(1); 17-12,, 2009.
Vision, pp.
McAllester, D. A. Some pac-bayesian theorems. In Proceed- ings of the eleventh annual conference Computational learning theory, pp. 230-234, 1998.
Russo, D. and Zou, J. Controlling bias in adaptive data anal- ysis using information theory. In Artificial Intelligence and Statistics, pp. 1232-1240. PMLR, 2016
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of machine learning. MIT press, 2018.
Sagawa, S., Koh, W., Lee, T., Gao, I., Xie, S. M., Shen, K., Kumar, A., Hu, W., Yasunaga, M., Marklund, H., et al. Extending the wilds benchmark for unsupervised adaptation. arXiv preprint arXiv:2112.05000, 2021.
Netanyahu, A., Gupta, A., Simchowitz, M., Zhang, K., and Agrawal, Learning to extrapolate: transductive ap- proach. arXiv preprini arXiv:2304. 14329, 2023.
Okawa, M., Lubana, E. S., Dick, R., and Tanaka, H. Com- positional abilities emerge multiplicatively: Exploring diffusson models on synthetic task. Advances in Neural Information Processing Systems, 36, 2024.
Shalev-Shwartz, S. and Ben-David, S. Understanding ma- chine learning: From theory algorithmss. Cambridge university press, 2014.
Silver, D. and Ciosek, K. Compositional planning using optimal option models. arXiv preprint arXiv:1206.6473, 2012.
Oren, I., Herzig, J., Gupta, N., Gardner, M., and Berant, Improving compositional generalization in semantic parsing. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 2482-24222 2495, 2020.
Sterkenburg, T. F. and Grünwald, P. D. The no-free-lunch theorems of supervised learning. Synthese, 199()):9979- 10015, 2021.
Partee, B. et al. Lexical semanties and compositionality. An invitation to cognitive science: Language, 1:311-360, 1995.
Sutton, R. S., Precup, D., and Singh, S. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2): 181-211, 1999.
Pearl, J. and Mackenzie, D. The book of why: the new science of cause and effect. Basic books, 2018
Petrache, M. and Trivedi, S. Position paper: Generalized generalization beyond classical equivariance for lexical tasks and transduction. arXiv preprint arXiv2242.001629 2024.
grammar rules and structure-
Tasse, G. N., Jarvis, D., James, S., and Rosman, B. Skill machines: Temporal logic composition in reinforcement learning. arXiv preprint arXiv:2205. /2532, 2022.
Polyanskiy, Y. and Wu, Y. Lecture notes on information theory. Lecture Notes for ECE563 (UIUC) and, 6(2012- 2016):7, 2014.
Vapnik, V. An overview statistical learning theory.
IEEE transactions on neural networks, 10(5):988-99) 1999.

---

On the Statistical Mechanisms of Distributional Compositional Generalization
Vapnik, V. N. and Chervonenkis, A. Y. On the uniform con- vergence of relative frequencies of events their proba- bilities. In Measures of complexity, pp. 11-30. Springer, 2015.
Vapnik, V. N., Vapnik, V., et al. Statistical learning theory. 1998.
Villani, et al. Optimal transport: old and new, volume 338. Springer, 2009.
Wang. X., Chen, H., Tang, S., Wu, Z., and Zhu, W. Disentangled representation learning. arXiv preprint arXiv:2211.11699 2022.
Wiedemer, T., Brady, J., Panfilov, A., Juhos, A., Bethge, M., and Brendel, W. Provable compositional gener- alization for object-centric learning. arXiv preprint arxiv:2310.05327, 2023.
Wiedemer, T., Mayilvahanan, P., Bethge, M., and Brendel, W. Compositional generalization from first principles. Advances in Neural Information Processing Systems, 36, 2024.
Wolpert, D. H. The supervised learning no- no-free-lunch theo- rems. Soft computing and industry: Recent applications, pp. 25 42,42,220 2002.
Wolpert, D. H. What is important about the free lunch theorems? In Black box optimization,, machine learning, and no-free lunch theorems, pp. 373-388. Springer, 2021.
Wolpert, D. and Macready, W. No free lunch theo- rems for optimization. IEEE transactions on evolutionary computation, 1(1):67-82, 1997.
Wolpert, D. H., Macready, W. G., et al. No free lunch theorems for search. Technical report, Citeseer, 1995.
Xu, A. and Raginsky, M. information-theoreee analysis of generalization capability of learning algorithms. Ad- vances in Neural Information Processing Systems, 30, 2017.
Yang, X.-S. Free lunch no free lunch: that is not just question? International Journal on Artificial Intelligence Tools, 124001: 2012.
Zha, D., Bhat, Z. P.. Lai, K.-H., Yang. F., Jiang, Z., Zhong, S., and Hu, X. Data-centric artificial intelligence: A survey. ACM Computing Surveys, 2023.
12

---

On the Statistical Mechanisms of Distributional Compositional Generalization
A. Proof of Invariant Measure
Theorem A.1. (Invariant Property) There exists at least one function a such that for any B, the p-measure satisfies the following conditions:
For any T, P and A, have Er, log a A. LA. -A -T:P
(2) For any AI, Az, the following equation holds
(1I)
where u(A) = Er p ~ (T, P( ,A)
Proof. The key to prove this theory is to find a a that satisfies the condition (1) and (2).
We construct a,A.s (T, P)
Q(A.))(P!"))
In Proposition A.2, we prove that the satisfies the condition (1)
In Proposition A.3, we prove that the satisfies the condition (2).
Combine the results above, the theorem is proved.
Proposition A.2. For any learning algorithm A, given two random variable T, P we have
E p( log a (T.P.) IA,S( - T
(12)
Proof. According the equation
a (T)
we have
Qla.))(!!
E T Nogar(A) (A
= Σ (1A.9) (Ā = T, p(T)) log (P() TT)
Q(A.0(
T
(13)
(UATT( - = T)
Σ QiA.3)( ( T, T.P! log (PA
(T) Q(A.))
T)P(T)
LA, T T, P (T
where (+) is due to the definition of the mutual information. Therefore, the Proposition is established.
Proposition A.3. For any AI, and B, we have
Ma(Ai) (4((22)
(14)
where u(A) ET (T, P(T) AA)
Proof. According the bayes rule, have
- TTQ(==
Q(==T)P!)
(15)
Q(P!T))
13

---

On the Statistical Mechanisms of Distributional Compositional Generalization
Since T is the prediction, therefore T' is available when T = T. Based this, we have
((A (P T) Q (PS p T). T
(16)
According to the definition of 9.3 ) we have
(A Q = T)
(17)
First, we consider the learning algorithms that a P))) # for all T, Ps According the definition of f(-), we have
E Bpm c Up (T, Ps: A)
B pg (T) Q =
(A.
Ppp (T) Q( (f=)
(18)
Σ Q(1 ( T)
PST
Q(A.))) TT).
For all A, we have
Σ =T) = Σ (T) =1
(19)
T
Combined all the equation above, we have
E pp MCT (a As)
pgn ((A110) (T= = IT)
(20)
Σ pgT (T( Q (( (f (T=T)
Σ
E Epg u A2,
Given learning algorithm A, there exists set V.such that for (Ps, T E V), we have (A1, p(f)) = 0. The learning algorithm Ag satisties that og (A1, P 0 for all T, Ps. If this theorem holds, expect that
E pgT u u8 Ma(() (s,)s,A)) A2)
T
E pgm ~ Ps.Ai
(21)
Σ pm - u8 (T, Ps. AT) Ps) & V]
+ Σ P MT) uo (T, Ps, (T) Ps) V
Because (T Ps, A1) > holds for all inputs, we have
Σ E pgr 4y (T,
(T, Ps. A) & V 20
(22)
Σ E p N (ss A) Ps) v 0.
(23)
14

---

On the Statistical Mechanisms of Distributional Compositional Generalization
Obviously, we have
E ~ -CTT~~(T)MBTTTT.. Ps, (T) Ps) V
T
(24)
Σ E M us Ai) = 1.
Therefore, we can find value assignment that assign the value between and to pa( Pi) for all (Ps.T) E V such that the Theorem holds.
B. Proof of Generalization Bound
B.1. Preliminary: Definition and useful lemma
In the following, we give the measure for the distribution, i.e. Wasserstein Distance and the common used function assumption, i.e. Lipschitz assumption and homeomorphis assumption.
Definition B.1. (Wasserstein Distance). For any 2 1, the p- D-Wasserstein distance between two pobability measures P, Q on the space W with metric dw defined as:
W (P, Q)
inf (d W' Mer(n.)
(25)
where T'P, Q) denotes the collection of all measures W x W with the marginals P and Q on the first and second components respectively.
Definition B.2. (Lipschitz) Given two metric spaces (M, dm) and (W, dx). where dM and dy denote the metrics on M and N. A function M A' L-Lipsehitz if for all m1. m2 E M. have (hy(mm)1), h((())) Ldm(mm,
Lipschitz assumption is commonly used assumption The majority of research relies the Lipschitz assumption when analyzing generalization behavior. Some studies attempt to alleviate this assumption by substituting it with its weaker counterpart. However, as the primary focus of this paper does not lie in removing the Lipschitz assumption, we defer this task to future work.
Definition B.3. (homeomorphism) continuous function f is called homeomorphism if it is a bijection function and its inverse function f-1 is continuous well.
Definition B.4. (Total Variation) The total variation between two probability distributions P and Q on W is
TV(P,Q) & sup (P(A) - Q(A))
(26)
AEW
Definition B.S. (Discrete Metric) The discrete metric is d(a,, y) A 1[x + v). where is the indicator function.
Lemma B.6. (Rademacher Complexity (from Mohri et al. (2018))) Let F be a family of functions. Given distribution and a samples D, '.,, } p8n, the following holds for all g F:
D. pe. (eer(P..f err(Dn, f(l (F),
(27)
where R, = Eo.D,, [Sup 1 En 0s (xx)) with being independent uniform random variables taking values in +1}.
Lemma B.7. For two pobability measures P. Q on the space W with metric dw, the 1- Wasserstein distance between P and Q can be represented
(P,
sup Eh(wh(w) - Ew-ch(w), heH
(28)
L
where denotes the function spaces containing function with Lipsehitz constant less or equal T..
15

---

On the Statistical Mechanisms of Distributional Compositional Generalization
B.2. Proof of Theorem
To prove this theorem, we first start with a important lemma:
Lemma B.8. Under Assumption 5.3, given training data Dn E z" sampled from the support distribution Ps. learning algorithm A, then we have
err() err AII S GenlID + Kn KnLWI(Q ( + (T),
(29)
where GenIID denotes any generalization error bound with IID assumption, ((x) - /min(x/2/ exp(-x)) and
Pg PglerrpPe -emrr (note that D. A(D,)).
fin
max
(err(Po.fs) -ammm(Ps.
Proof. We can decomposite err err
Elerr(Pu,f) err(Dn,, f)] Elerr(Ps: f fD.. - err(Dni f fD..) BBerr(Pu, fD. err( fD..
(30)
Because (1) is the generalization bound in IID situation, upperbound it with any IID bound. Therfore, bound "(1)" term with GenIID to denotes any upper bound of IID. Then, we only need to focus the (2) term, which is the essential part of DCG.
Then, we have
crr(Pl) .s) err(P3 fs))
eer(p( .ss) err(P)) S ) err(Pt (fx) - fss)
(31)
(er(pp() .ss) (ss) err(p)) St) + + ffx err(P! ,fs)
|er((p) ffs) err(p/) f fE) + A(T.AA
According to Lemma B.7, we have
1
Q)(P,Q) = sup Bw- - Bwwch((). L hew
(32)
By replacing h in Equation 32 with err(Pu, -), P in Equation 32 with 0/22) and Q in Equation 32 with Pr, we obtain that
(4) fo 2
1
B Byroreeerr(Pts -E (yyooser((Pu))))
T.
(33)
(err(Po. fs) err(Pu,
I
By rearranging the equation, we obtain that
err(Pu, err(Pu, LWW (Q))) 2(1)).
(34)
According to the Definition of Kn., we have
err(Pu, D.,) (rr(Ps, f (err err fs))
(35)
Combining the equations above, the result established.
Theorem B.9. Under Assumption 5.3 and 5.5, given training data D,, E 2 sampled from the support distribution Ps- learning algorithm A, then we have
Eierr(Pu. -er)-errDDn.. fo.)ll S GenIID Ln P T
(36)
where GenIID denotes any generalization error bound under IID assumption, (x) L min(2x/2222 11111-1epp(pp000
Bon--P(lerrPPu5 (err(Pu-J (er (note that f D.. A(D,))).
and Kn A max jerr(Pu-f -err eerrerrrPP. (Ps.
16

---

On the Statistical Mechanisms of Distributional Compositional Generalization
Proof. Start from Lemma B.8, we the metric between the function space, i.e. dz the discrete metric defined in Definition B.5. Based this metric, because the err(-) is L-bounded, have for any distribution Q and fi, f2 F, err(Q.f (Gr.(allll 1 L, i.. the err(.) L-Lipschitz.
(x(
Then, we can bound W1(0 (A) 2/2e in Lemma B.8 with & g
Wi(Q)) (1 ) WI(0 OJ3)
((4)
TV 0/! & {(LLO) 0f2
(37)
where (4) is due the Theorem 6.15 of Villani et al. (2009), is due to the statement in Theorem 6.5 of Polyanskiy & Wu (2014) and Lemma Rodríguez Gálvez al. (2021). With some misuses, we denote 0//²) as 4 IPs, where denotes the condition and the same for ((A) and Pfu- Then, we have
KL(O 0 (L((O (PL. ( (Ps))
(A)
(Pss (0)))Ps))
(38)
-KI(1O} A4) (Fl. 1 Ps)
= Puls:
The notation (2(44) Pu) indicates that the condition Po only take effect the distribution Q/A). While the KL(,,-1P3 indicates that the condition Ps take effect on all the distributions.
According to the Assumption 5.5, there exists bijection function between I'' and Pt when Ps is given. Based on this, we have
Pol:) [A(F:T(Ps)
(39)
Combine the equations above, the Theorem is estabilished.
B.3. Proof of Corollary Corollary B.10. Under Assumption 5.3 and 5.5, and lim GenlID = -0, then we have
- El - (rrrrss [sss < ([ (T)
(40)
Proof. Recall that the generalization bound in Theorem 5.7, that
(eerr(PP. SD.) err(Dr, JD.)ll s GenJID + &n (IA(s s; T P(T)) + +T(
(41)
Taking n - 00, we have
lim - fDr
" mx
|Elerr(Pu err fs)]
lim (GenlID (4 sT +T(,
(42)
n
(T) lim 4 (J: (T) ) +T
n
A), where (+) is due to the condition lim GenlID and lim Kn
(fAA T T(
B.4. Tightness
Our ability to assert whether our bound is tighter or looser than previous bounds is contingent upon considering the nuanced intricacies the problems at hand. According to whether the problem more influenced by the design of learning algorithm or the function space. We have delineated the issue into two distinct categories
17

---

On the Statistical Mechanisms of Distributional Compositional Generalization
Example (Function Space)
Example (Learning Algorithm)
1.0
1.-
Ours
Ours
0.5
CG Loss
M&N
0.5
NAN
CG Loss
0.0
0.0
100
20
40
60
80
100
|S|
|S|
Figure 1. Generalization bounds on the toy problem. The example considers the where the function space has some bias while the learning algorithm has no bias. The example 2 consider the learning algorithm has certain bias while the function space is powerful fit data. We find that I) our bounds can capture the decrease of generalization error in example and 2) our can align with the generalization error in example 2.
Function space dominated problem. In this problem, we posit that the learning algorithm randomly selects functions that minimize loss on the training data, within a function space tailored specifically for the problem at hand.
learning algorithm dominated problem. Here, we assume that the function space is pwerful enough to accommodate any distribution, while the learning algorithm is inclined to favor certain functions over others, provided they minimize loss on the training data.
To illustrate these components, we provide two examples: Example 1 exemplifies a scenario where the function space dominates, whereas Example 2 exemplifies a scenario where the learning algorithm holds sway. In summation, our analysis yields the following conclusion: We ascertain that our bound achieves greater tighmess in the context of the learning algorithm dominated problem. Conversely, in the scenario where the function space dominates, our bound achieves greater righteess solely when provided with extensive array of supporting distributions.
Example setting We consider thet |A| = | = 10. The two examples are explored. Example 'The function space F has the properties that 1) For each function f E F, we have Ea,b Terr(Pa...)) = 10 or Σa, Herr(Pa..f) = 0. 2) Va E b, b E B, M,.rr(Pa.. [) = or (Pr(, f) = O. The learning algorithm satisfies that V(a, b) E S and for all supp Q/A)) and for all (a, b) S, we have err f) O. Example For all f supp ((44) for all (a, b) S, we have err(Pa, f) = 0 and for all (a,b) b) & S. we have err(Pa, f) = 0 with probability Ca.b Ca.dTE] else err(Pa, f) = 1, where Ca.b is a ramdonly assigned value for each (a, b) and it takes value between 0.8 and 1. We choose the distance measure (f(fi, f2) su E[(err(Pa,t f1) err(Pa,6, f2))..
|S|
Remark B.11. In Example 1, we delve into the bias stemming from the function space. Here, the function space is relatively constrained, containing only a limited set of functions, including the correct one that attains zero loss. The learning algorithm uniformly selects a function only if achieves minimal loss on the support distribution. Consequently, the learning algorithm exhibits no inherent bias towards specific functions as long they achieve minimal loss on the support distributions. In Example 2, we explore the bias inherent in the learning algorithm. In this instance, the function space is expansive, encompassing all possible outputs. However, the learning algorithm may assign varying probabilities to functions that achieve zero loss on the support distribution.
We revisit the bounds here:
1) The results of Ben-David et al. (2010). Ben-Davia et al. (2010) has the following conclusion that:
err err(Pu,fe fs) err(Ps, fs) drar Ps) AA), where the draF is defined as dr 2sup,./'eF [B--ry [f(x) # ['(x)) - Ez-Pa (f(x) ( + [x())]
(43)
2) Ours. The Corollary 5.8 in our work indicates that
err(Ps. D(A TP DUA +
(44)
Results We compute the generalization bounds and error depicted in Fig. 1, revealing two key observations: Our bound effectively incorporates the impact of the support distribution. In Example 1, our generalization bound accurately reflects
18

---

On the Statistical Mechanisms of Distributional Compositional Generalization
the decreasing trend of the generalization error. Similarly, in Example 2, bound aligns with the generalization trends across various support distributions. Our bound accounts for the influence of the learning algorithm. Notably, in Example the approach proposed by Ben-David et al. (2010) fails to capture the dynamics accurately. This failure can be attributed to its predominant focus on the function space influence, whereas our analysis recognizes the dominance of the learning algorithm's influence in this example.
19


Reviews:
[{"review_id": "wYoQPuYSvr", "reviewer": "Reviewer_XpR4", "summary": "This paper proposes a theoretical statistical framework for analyzing Distributional Compositional Generalization (DCG). An invariant measure is proposed to evaluate the generalizability of methods across DCG tasks and derive a generalization bound separating the effects of insufficient data from knowledge composition capabilities. Their findings highlight the role of mutual information and algorithm-rule compatibility in DCG performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## 1. Experiments\n\n### 1.1. Experiment Design:\n\n**1. Components and Compositional rule**： We construct two words set A,B satisfying |A|=|B|=1000 and their corresponding element $a_1,a_2\\subset A$ and $b_1,b_2\\subset B$. $a_1,a_2$ is a partition of $A$  and the same as $b_1,b_2$. $|a_1 |=|a_2|=|b_1|=|b_2|=500$.\nThe composition rule can be any function that satisfy the following form:\n$(e_1,e_2)→e_1 e_2 e_1 e_2 e_1 e_1$. \nAnd we construct 64 composition functions, referred as  $T_1,T_2,\\cdots,T_{64}$\n\n**2. Distribution Split** The support distribution takes the elements in the set $\\lbrace(e_1,e_2)|(e_1,e_2 ) \\in a_1 \\times b_1 \\cup a_2\\times b_1 \\cup a_1\\times b_2 \\rbrace$. The target distribution take elements in the set $\\lbrace(e_1,e_2)|(e_1,e_2) \\subset a_2\\times b_2 \\rbrace$. It is easy to verify that these designs satisfy the requirement listed in Section 3.\n\n**3. Sequence design** The input sequence is “$e_1,e_2,r_1,r_2,r_3,$#”, where $r_1, r_2, r_3$ are random words that simulate the randomness. The expected completed sequence is “$e_1,e_2,r_1,r_2,r_3,$#$,e_1,e_2,e_1,e_2,e_1,e_1$” if the composition rule is $(e_1,e_2)\\rightarrow e_1,e_2,e_1,e_2,e_1,e_1$.\n\n**4. Learning algorithm design** \nIn our paper, we define the learning algorithm as the mapping between data and the learned function, encompassing a broader concept than just the optimizer. To simulate learning algorithms with varying inductive biases and adaptivity, we adopt the following approach:  \n\n1. We employ the GPT-2 model with two configurations:  \n   - **Setting 1:** 4 layers, 4 attention heads, and an embedding size of 128.  \n   - **Setting 2:** 6 layers, 8 attention heads, and an embedding size of 256.  \n2. We pretrain the GPT-2 model using different pretraining data schedules. The pretraining data is generated from a subset of composition rules same to those in the downstream task, but with entirely different words. This setup allows us to create learning algorithms with different inductive biases and adaptivity while preventing data leakage. \n\n\n### 1.2. Experiemnts on trade-off and non-trade-off improvement\n\nOn of the key point in this paper is that the non-trade-off improvement has to rely on the adaptivity of learning algorithm (detail see beyond trade-off page 5). To verify this conclusion,  calculate $I_{\\mathcal{A},\\beta}(\\tilde{T}=T,P_S)$, which is a measure of adaptivity used in out paper, and GACC, which is the average performance across all the tasks with compositional rule in $T_1,T_2,\\cdots,T_{64}$. The results are:\n\n\n| $I_{\\mathcal{A},\\beta}(\\tilde{T}=T,P_S)$ | 0.073 |\t0.115 |\t0.125 |\t0.281 |\t0.362 |\t0.462 |\t0.481 |\t0.505 |\t0.527 |\t0.564 |\n| --- | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- |\n| GACC | 0.605 |\t0.591 |\t0.565 |\t0.633 |\t0.696 |\t0.750 |\t0.772 |\t0.789 |\t0.752 |\t0.776 |\n\n\n\n\n\n### 1.3. Experiments on Generalization Bounds\n\nWe conduct the experiments with different rule complexity using the best pretrain setting in previous section.\n\nRule complexity refers to the length of the rule on the output side. For example, the rule complexity of $(e_1, e_2) \\rightarrow e_1, e_2, e_1, e_2, e_1, e_1$ is 6, while the rule complexity of $(e_1, e_2) \\rightarrow e_1, e_2, e_1, e_2, e_1, e_1, e_1, e_2$ is 8.\n\n| Rule Complexity | 6 | 8 | 10 | 12 |\n| --- | --- | --- | --- | --- |\n| CG Error | 0.223  | 0.262 | 0.301 | 0.342 |\n| Ben-David et al. | 0.622 | 0.680 | 0.701 | 0.690 |\n| Ours | 0.271 | 0.295 | 0.351 | 0.372 |\n\n\nThe results indicate that our generalization bound is more tighter than the bound of Ben-David et al. \n\n## 2. Question\n\n> Q1: empirical validation\n\nSee 1.Experiments.\n\n> Q2: envision practical influence?\n\nSee **Q1 in the response to Reviewer nkeW**\n\n> Q3: justify the assumptions\n\nAssumption 5.3 requires that the error is bounded. If the solution performs poorly on a small subset of data points but performs well on the rest, the average error could be disproportionately large due to extreme errors in that small subset without this assumption. This assumption can be easily satisfied by modifying the original error using a  $\\min(\\text{error}, \\text{bound})$ operation. Alternatively, a bounded error measure, such as 1-accuracy, which ranges between 0 and 1, can be used.\n\nAssumption 5.4 requires that the DCG problem is solvable. Our bound does not apply to DCG problems that are entirely unsolvable. This assumption ensures that, given all distributions, we can learn how the given components are combined. For example, if provided with images of various shapes and colors, we should be able to understand how shape and color interact to form specific images, such as a the image of red triangle. This assumption guarantees that there **exists** a way to recover these compositional rules from the data.\n\n> w1: concrete examples. \n\nSee **''More background and Examples'' of the rebuttal to Reviewer nkeW**", "claims_and_evidence": "The claims presented in the paper are largely theoretical and mathematical. However, they lack empirical validation or experimental evidence to demonstrate their practical applicability and effectiveness. Specifically:\n1. Although mathematically derived and proven, the claim regarding its practical utility or interpretability lacks empirical demonstration.\n2. The theoretical bound separating data insufficiency from compositional errors is presented; however, the absence of empirical or simulation-based evidence makes it challenging to assess its practical tightness or usefulness.\n\nThus, while theoretically sound, the primary problematic claim is the applicability and practical relevance of these theoretical results without supporting empirical validation or concrete examples.", "methods_and_evaluation_criteria": "The proposed methods—namely, the invariant measure, i.e., invariant measure and the derived generalization bound, are conceptually appropriate and logically consistent with the theoretical objectives of understanding DCG. However, the paper lacks specific evaluation criteria or benchmark datasets to practically validate these theoretical contributions. Introducing empirical evaluation or clearly defined benchmarks would significantly strengthen the practical relevance and interpretability of the theoretical findings.", "theoretical_claims": "Check claims and evidence", "experimental_designs_or_analyses": "NA", "relation_to_broader_scientific_literature": "The paper extends statistical learning theory (e.g., PAC learning, NFL theorem) specifically to DCG. Unlike prior work focusing on specific DCG scenarios, it offers a general theoretical foundation.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Check claims and evidence", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Could you provide examples or scenarios (even simulated) that empirically validate the theoretical invariant measure and generalization bound?\n2. How do you envision your theoretical findings practically influencing algorithm design or improvement in real-world DCG tasks?\n3. Could you explicitly discuss and justify the assumptions used in your generalization bound? Under what real-world conditions might these assumptions fail?", "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": "UjvHZeJd35", "reviewer": "Reviewer_errU", "summary": "The authors analyze the problem of Distributional Compositional Generalization (DCG). Compositionality in this sense is the ability to model different features in the dataset and the statistical dependency between them. They try to provide statistical tools to assess whether it  is possible to transfer one  DCG problem to another and the capacity of the learning algorithm for DCG tasks.\nThey propose a measure (mu) which is based on the prediction function and invariant to the learning algorithm. They argue this measure can give insights on the DCG problem, with respect to different tasks and the respective learning algorithm.\nThe work is highly abstract and hard to follow. There are many notations and definitions, it appears the work is intended for a nich group who specializes in this topic and formulation. Although the authors try to give some intuition and examples words in the beginning, they do not go back to it later. There is no example, no illustration, not even a toy problem, let alone a real learning problem where the theory is applied.\nAlthough some intresting insights may be learned here, I do not believe the venue of this conference is a good fit for this work.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1:  There is no example, no illustration, not even a toy problem\n\nActually, we provide the Example 3.2, Example 3.3 and an illustration in Appendix (Page 17). \n\nWe have added more examples and background (detail **See ''More background and Examples'' of the rebuttal to Reviewer nkeW**) and experiments on a simulation problem (See **''Experiments'' of rebuttal to Reviewer  XpR4**).\n\n\n\n> W2: There are many notations and definitions, it appears the work is intended for a nich group who specializes in this topic and formulation.\n\nOur work presents the first statistical formalization of the DCG problems. We acknowledge that the paper introduces many notations and definitions, but this complexity reflects the inherent difficulty of the problem. To improve clarity, we have taken significant steps to simplify the presentation:\n\n1)  We include schematic diagrams (Eq.1 and Eq.12) and provide the examples(Example 3.2 and Example 3.3). \n2)  In the revised version, we have expanded the number of examples and added synthetic experiments to empirically validate our theoretical findings  (**see W1**). \n\nIf you have any **concrete suggestions**, we would gladly incorporate them and revise the paper **promptly**. And this paper is **never** intended for a nich group — if you believe there are aspects that may inadvertently limit its accessibility, we would appreciate further details on which groups might find the presentation challenging.\n\n> W3: Do not review literature on current compositional representations and methods.\n\nThank you for your suggestions. \n\nIn the Related Work section, we already cover disentangled representation learning, which we view as a subset of compositional representation learning. \n\nAnd, to better address your point, we have expanded this section to include a dedicated discussion on current compositional representation learning methods, incorporating your suggested direction. Additionally, we will integrate the following literature into this new discussion:\n\n[1] Compositional Generalization in Unsupervised Compositional Representation Learning: A Study on Disentanglement and Emergent Language\n\n[2] CORL: Compositional Representation Learning for Few-Shot Classification\n\n[3] Representation Learning of Compositional Data\n\n[4] Measuring Compositionality in Representation Learning\n\n[5] Rule-Guided Compositional Representation Learning on Knowledge Graphs\n\n[6] THE ROLE OF DISENTANGLEMENT IN GENERALISATION\n\n[7] Where’s the Learning in Representation Learning for Compositional Semantics and the Case of Thematic Fit\n    \n> W4: I do not believe the venue of this conference is a good fit for this work.\n\nI totally disagree with the point that the ICML is not suitable for our paper. The reason is given as follow:\n\n1. This paper focuses on analyzing machine learning algorithms in DCG tasks, making it highly relevant to the topics listed in the ICML call for papers, specifically under \"Theory of Machine Learning\" (including statistical learning theory, bandits, game theory, decision theory, etc.).\n2. ICML accepts many papers with dense theoretical analysis, and the other reviewers have provided relatively lengthy review comments, suggesting a certain level of interest in this paper in the ICML community.  \n3. ICML is an open and diverse community, which is one of the reasons I deeply appreciate it. We hope to uphold this openness. I acknowledge that theoretical researchers are somewhat in the minority within the community, but ICML has always provided opportunities for underrepresented perspectives.", "claims_and_evidence": "see above", "methods_and_evaluation_criteria": "see above", "theoretical_claims": "Several interesting theoretical claims.", "experimental_designs_or_analyses": "no experiments", "relation_to_broader_scientific_literature": "Relations to the more abstract literature. Do not review literature on current compositional representations and methods.", "essential_references_not_discussed": "see above", "other_strengths_and_weaknesses": "see above", "other_comments_or_suggestions": "More illustrations and intuition, connecting the more abstract notions to an actual learning problem.", "questions_for_authors": "See above.", "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": {"ethical_review_concerns": "no"}}, {"review_id": "bQs4x0DRZg", "reviewer": "Reviewer_nkeW", "summary": "In this paper, the authors introduce a statistical framework to address two important research questions that have not been explored in prior work. Specifically, they examine whether a method designed for one DCG problem can be applied to another and identify the statistical properties that indicate a learning algorithm's capacity for knowledge composition", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## More background and examples\n\n### Background:\nWe will include a new section in the Appendix to provide additional background knowledge about **statistical machine learning**. The structure is:\n\n1) Key concepts, including data space, learning algorithms, function space, and the i.i.d. (independent and identically distributed) assumption.  \n2) Generalization  analysis with Rademacher complexity as a example.  \n3) Current applications of generalization bounds .  \n4) extensionto out-of-distribution settings.\n\n### Examples:\n\n**Example for Compositional rule**:  Composition rule is the rule of how the two components are combined. It can have different representation dependent on the data generative process. In image creation, the composition rule can be represented as  ``Draw the contour of a $<$shape$>$ and fill it with $<$color$>$.''. Similarly, for a robotic task, the composition rule can be expressed as “First, complete $<$subtask1$>$, then $<$subtask2$>$.”. The compositional rule can also be non-text representation, as long as it defines how two components are combined.\n\n**Example for inductive bias**: Inductive bias refers to a model's inherent preference for certain compositional rules before it is exposed to any training data for a given task. This bias can be introduced in two primary ways: Model Architecture Design – By carefully structuring the model, we can constrain its outputs to adhere to specific compositional rules. Pretraining & Objective Function – The inductive bias can also be shaped through pretraining strategies or the choice of objective function, either suppressing or reinforcing the model's tendency toward certain compositional behaviors.\n\n**Example for Assumption 5.3**: This assumption requires that the error is bounded. This assumption can be easily satisfied by modifying the original error using a $\\min(\\text{error}, \\text{bound})$ operation. Alternatively, a bounded error measure, such as accuracy, which ranges between 0 and 1, can be used.\n\n**Example for Assumption 5.4**: This assumption ensures that, given all distributions, we can learn how the given components are combined. For example, if provided with images of various shapes and colors, we should be able to understand how shape and color interact to form specific images, such as an image of red triangle. \n\n**More examples** to demonstrate the indications of the theorem will be provided in the next version of paper.\n\n## W & Q\n\n> W1: empirical validation\n\nSee **''Experiments'' of rebuttal to Reviewer  XpR4**\n\n> W2: No examples\n\nSee \"More background and examples\"\n\n> W3: Practical implication\n\nSee Q1. More detail implication will be added in the next version of our paper.\n\n> Q1: Properties of data-centric methods and requirement for data engineering phase?\n\nOur theory suggests that a data-centric approach is fundamental for achieving non-trade-off improvements. It highlights the following key properties of data-centric methods:\n\n1) Data-centric methods should effectively leverage information from the data itself. Injecting human task-specific knowledge into method design—such as using specialized model architectures or loss functions—may hinder the method's ability to learn directly from the data.  \n   \n2) Theory 5.5 further asserts that compatibility between the learning algorithm and the data is crucial. This implies that the learning algorithm should achieve uniform performance across different compositions within the support distribution. For example, if the support distribution includes red triangles and blue rectangles, the model’s performance on red triangles and blue rectangles should be similar.  \n\nRegarding the requirements for the data engineering phase, our theory supports the co-design of both the solution (including network structure and objective function) and data collection. Since the value of $I_{\\mathcal{A},\\beta}(\\tilde{T}=T,P_S)$ in our theory depends on both the learning algorithm and the data, our theory cannot prescribe a universally optimal data development method independent of the specific approach. However, certain data quality requirements, such as the absence of label noise, are absolutely essential.\n\n> Q2: major factors contributing to generalization error\n\nIn the DCG problem, the support distribution provides only a subset of knowledge combinations—for example, a red rectangle and a blue triangle. To generalize effectively, the model must first learn the concepts of colors and shapes and then recombine the learned concepts of \"red\" and \"triangle\" to form the concept of a \"red triangle.\" Based on this property, we identify two major limiting factors: insufficient data and a lack of knowledge composition. Without sufficient data, the model tends to overfit to the small portion of training data, preventing it from learning the correct concepts. Meanwhile, the lack of knowledge composition indicates that the model struggles to recombine learned concepts, limiting its ability to generalize.", "claims_and_evidence": "The theoretical claims in the paper are supported by proofs. However, it would be ideal to include some experimental validation, even in simple toy settings, to further substantiate the findings.", "methods_and_evaluation_criteria": "Not applicable.", "theoretical_claims": "The detailed proofs provided in the appendix were not reviewed, but all the claims presented in the main text were verified, and no issues were found.", "experimental_designs_or_analyses": "There are no experimental designs included. However, the analysis of the generalization bound, accounting for errors from two sources—insufficient data and knowledge composition—was examined. The analysis appears to be correct.", "relation_to_broader_scientific_literature": "In contrast to prior works that focus on DCG problems with specific composition rules, the proposed invariant measure explores the relationships between different composition rules. Additionally, the theorems presented are not confined to any particular learning problem. More importantly, the proposed theoretical framework emphasizes non-tradeoff improvements in DCG problems. This is the first paper to decouple the influence of finite samples and knowledge composition in generalization analysis for out-of-distribution settings. The proposed bound is tractable for various composition rules and establishes a connection between generalization behavior and mutual information.", "essential_references_not_discussed": "Essential references are discussed in detail, along with a thorough explanation of how the proposed framework differs from prior works.", "other_strengths_and_weaknesses": "### Strengths  \n1. The paper addresses two important research questions in the area of DCG, and the proposed framework offers unique insights.  \n2. The paper is well-written, particularly the clear distinction between prior works and the current study. This effectively highlights the uniqueness of the proposed framework.  \n3. The analysis and theoretical framework presented in the paper will contribute to the development of better methods and provide a strong theoretical foundation for future research in this area.  \n\n### Weaknesses  \n1. There is a lack of experimental support or analysis, even in synthetic scenarios.  \n2. While the paper is generally well-written, it would be easier for readers to grasp the key ideas if the authors provided more intuitive explanations. For example, the paper introduces concepts like red rectangles and blue triangles, as well as Examples 3.2 and 3.3, but similar connections are missing in later sections. It would be beneficial if the authors explained major claims and conclusions from the theoretical study in a similar intuitive manner.  \n3. The practical implications of the proposed framework should be discussed in much more detail than in the current version.", "other_comments_or_suggestions": "diagram (1) in Section 3.3 would benefit from a more detailed description.", "questions_for_authors": "**Questions**  \n1 (Important). In the non-tradeoff scenario, the authors propose keeping the $\\mu$ measure fixed and suggest data-centric approaches as a viable solution. Could the authors clarify how data-centric methods can effectively achieve this? Specifically, what should data-centric approaches focus on? Which aspects of training data development (such as collection, labeling, preparation, reduction, or augmentation) should practitioners prioritize for DCG, and what should be the key objectives during the data engineering phase?\n\n2. Why were insufficient data and lack of knowledge composition considered the major factors contributing to generalization error?", "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": "4HZ643Dd01", "reviewer": "Reviewer_PSGU", "summary": "The paper investigates the statistical mechanisms underlying Distributional Compositional Generalization (DCG), focusing on two key questions: 1) whether methods for one DCG task generalize to others, and 2) what statistical properties determine a learning algorithm’s compositional ability. The authors propose an invariant measure (μ) to unify diverse DCG methods, highlighting data adaptivity as critical for non-trade-off improvements. They derive a generalization bound decoupling IID error and compositional error, linking compositional capacity to mutual information and compatibility between learning algorithms and composition rules. The analysis emphasizes the role of statistical dependencies and algorithmic sensitivity in DCG, offering theoretical insights complementary to prior work.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1: lack empirical validation.\n\nWe present new experimental results to validate the theoretical derivations (**see the \"Experiments\" section in the Rebuttal of Reviewer XpR4 for details**). Below is a summary of our findings:  \n1. We confirm that non-trade-off improvements are strongly correlated with adaptivity of learning algorithms.  \n2. The results demonstrate that our bound is tighter than previous methods, supporting the importance of incorporating information about the learning algorithm and data for tighter bound.\n\n> W2: The reliance on abstract statistical formulations may limit applicability.\n\nThe goal of this paper is to offer a broader perspective on DCG tasks. We fully acknowledge the importance of applying the framework to specific DCG tasks; however, substantial efforts have already been dedicated to this aspect in previous works. Rather than replicating those efforts, our paper seeks to address a gap that has not yet been fully explored. The value of our work should not be assessed in isolation. When considered within the broader context of the research community—where numerous theoretical studies on specific tasks already exist—our work provides a complementary perspective that deepens the overall understanding of DCG tasks.\n\n> W3: Terms like \"knowledge composition\" need clearer definitions.\n\nKnowledge composition refers to a learning algorithm's ability to understand and integrate individual components. Specifically, it reflects the algorithm's performance on DCG tasks when the impact of limited data is eliminated (i.e., given an infinite amount of data). To avoid ambiguity, we plan to replace \"knowledge composition\" with \"component composition\" and provide a clearer explanation.   **If there are other terms that require clarification, we would greatly appreciate your feedback and immedately address them.**\n\n> W4: readers without theoretical background find it difficult to follow\n\nThe more examples and background will be provided. The examples will cover the core concepts and the assumptions. The background will be listed in the Appendix to cover the basic knowledge of the statistic machine learning. **The detail can be seen in the Section \"More examples and background\" of Rebuttal to Reviewer nkeW**.  We hope that these effort can make the non-theoretical background reader more easy to read.\n\n> Q1: Estimate of $\\mu$ or validated in practice? Could this inform method selection for DCG tasks?\n\nThe core value of $\\mu$ measure is to provide the analysis of the trade-off and non-trade-off improvement. We design a synthetic task for verify the trade and non-trade-off improvement (See **W1**). \n\nThis has the following indication for the method selection for DCG:\n1) To improvement the learning algorithm in non-trade-off way, it is counterproductive to impose inductive biases or constraints, such as the group constraint, as this would cause the model to loss the data adaptivity ability. A more effective approach is to design a model that can fully leverage the information in the data. \n\n2) Co-design of the learning algorithm and data engeering is importance, as the non-trade-off improvement replies on a large value of $I_{\\mathcal{A},\\beta}(\\tilde{T}=T,P_S)$. The compatibility between the data the learning algorithm is essential for generalization.\n\nMore detail information can be seen in **Q1 in the response to Reviewer nkeW**\n\n> Q2: Clarify Assumptions ?\n\nAssumption 5.3 requires that the error is bounded. For example, the 1-accuracy, which ranges between 0 and 1, can satisfy the assumption.\n\nAssumption 5.4 requires that the DCG problem is solvable which made the problem meaningful.  Specifically, given all distributions, we can learn how the given components are combined. For example, if provided with images of various shapes and colors, we should be able to understand how shape and color interact to form specific images, such as a the image of red triangle. This assumption guarantees that there **exists** a way to recover these compositional rules from the data.\n\n> Q3: Are there plans to test the theory on synthetic?\n\nSee W1\n\n> Q4: \"composition rule\" (T) for canonical DCG tasks?\n\nComposition rule is the rule of how the two components are combined. It can have different representation dependent on the data generative process. In image creation, the composition rule can be represented as  ``Draw the contour of a $<$shape$>$ and fill it with $<$color$>$.''. Similarly, for a robotic task, the composition rule can be expressed as “First, complete $<$subtask1$>$, then $<$subtask2$>$.”. The compositional rule can also be non-text representation. If the image is generated by a generative model, then the compositional rule can be represented as part of the generative model that focus on the combination of the two components. However, as long as these representation describe a same rule for component composition, we regard them as the different representation of a same composition rule.", "claims_and_evidence": "The claims are supported by theoretical derivations but lack empirical validation.", "methods_and_evaluation_criteria": "The theoretical framework is logically structured, using mutual information and compatibility measures to analyze DCG. However, the absence of empirical benchmarks or synthetic experiments weakens validation. The reliance on abstract statistical formulations may limit applicability to specific DCG tasks without further domain-specific adjustments.", "theoretical_claims": "The proofs for Theorem 4.7 and Theorem 5.5 rely on assumptions (e.g., L-bounded errors, composition rule recoverability in Assumption 5.4) that are plausible but not rigorously justified. The mutual information term \\(I_{\\mathcal{A}}(f_S; T|P_S^{(T)})\\) is central but lacks intuitive interpretation in practical settings.", "experimental_designs_or_analyses": "No experiments are provided to validate the theoretical claims. The analysis remains purely mathematical, leaving open questions about the practical relevance of the proposed measures in real-world DCG tasks.", "relation_to_broader_scientific_literature": "The work extends statistical learning theory to DCG, contrasting with IID-based generalization frameworks. It connects to NFL theorems by addressing task trade-offs but focuses specifically on compositional rules. Comparisons to Ben-David et al.’s domain adaptation bounds highlight novel aspects (algorithmic compatibility), though empirical validation is missing.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths include a novel statistical perspective on DCG and the invariant measure unifying diverse methods. Weaknesses include overly abstract formulations and lack of empirical grounding. Clarity suffers from dense notation and undefined terms.", "other_comments_or_suggestions": "1. Terms like \"knowledge composition\" need clearer definitions.\n2. The organizational structure of the paper needs adjustment, as readers without theoretical background find it difficult to follow.", "questions_for_authors": "1. How might the μ-measure be empirically estimated or validated in practice? Could this inform method selection for DCG tasks?  \n2. Assumption 5.4 requires recovering \\(T\\) from \\(P_E^{(T)}\\). Is this feasible for complex composition rules (e.g., in NLP or robotics)?  \n3. Are there plans to test the theory on synthetic or real-world DCG benchmarks (e.g., SCAN, COGS)?  \n4. Could the \"composition rule\" \\(T\\) be explicitly defined for canonical DCG tasks (e.g., attribute recombination)?", "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:

Meta-review: All reviewers agree that the paper provides theoretical insights to better understand the generalization properties of DCG from statistical perspective. Initially, the reviewers had concern on the empirical support of the claims. The rebuttal was very helpful in clarifying questions raised. Based on the consistent positive reviews and the authors' rebuttal, AC recommends acceptance. Please make sure to include these clarifications as well as the extra results in the final version of the paper.
Decision: Accept (poster)