Generalization Error Bounds for Two-stage Recommender Systems with Tree Structure

Authors: jin  zhang
ze  liu
defu  lian
enhong  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:47:31

Abstract: Two-stage recommender systems play a crucial role in efficiently identifying relevant items and personalizing recommendations from a vast array of options. This paper, based on an error decomposition framework, analyzes the generalization error for two-stage recommender systems with a tree structure, which consist of an efficient tree-based retriever and a more precise yet time-consuming ranker. We use the Rademacher complexity to establish the generalization upper bound for various tree-based retrievers using beam search, as well as for different ranker models under a shifted training distribution. Both theoretical insights and practical experiments on real-world datasets indicate that increasing the branches in tree-based retrievers and harmonizing distributions across stages can enhance the generalization performance of two-stage recommender systems.

Main paper: 
 introduction: 
 Recommender systems play a crucial role in many online services, such as e-commerce [29] , digital streaming [4] , and social media [2] , influencing consumer behavior, media consumption, and social interaction. It needs to quickly identify a few relevant items from millions or billions of options, and personalize to the dynamic needs of large numbers of users with low response latency. A widely adopted solution to this problem is the two-stage recommender system. In the first stage, a computationally efficient retriever preselects a small number of candidates from a large pool. In the second stage, a slower but more accurate ranker narrows down and reorders these candidates before presenting them to the user. In this way, a well-balanced trade-off between efficiency and accuracy is achieved that meets the demands of real-world scenarios.The retrievers are often heterogeneous, popular choices like matrix factorization [15, 19] , two-tower [23] , recurrent neural networks [3] , and so on. In recent years, the tree-structured retriever model [8, 29, 28, 7] , which takes advantage of the tree structure, usually combined with a greedy algorithm to identify relevant items quickly, has demonstrated commendable performance and efficiency. The ranker typically uses enriched features as input, combined with a complex model, to enhance prediction accuracy. The computational costs are generally linear relative to the number of items at deployment [4, 18] .Despite the practical success of two-stage models, particularly those based on tree structures, theoretical research in this area remains limited. To fill in the gap, we start from the perspective of generalization error to investigate the upper bounds of generalization error for these models to promote understanding of their generalization capabilities.In this paper, we decompose the generalization error of two-stage models across each stage. Using Rademacher complexity as a methodological tool, our analysis encompasses a range of models prevalent in two-stage methods. This includes tree-structured retriever models employing beam search, such as linear model, multilayer perceptron, and target attention model. Besides, we give generalization error bound for ranker models under shifted training distributions. The theoretical results show that tree models with increased branches and rankers trained on harmonized distributions can improve generalization performance, and we validate these findings on real-world datasets.To summarize, the main contributions of this work are summarized as follows:• We are the first to analyze the learnability of tree-based retriever models in recommender systems and prove the generalization upper bound for various tree-based retrievers using beam search. Both theoretical insights and practical experiments confirm that expanding the number of branches in tree-based retrievers enhances their ability to generalize. • We establish an error decomposition framework for analyzing generalization errors of twostage recommender systems and theoretically derive the optimized training objectives for the ranker models within this framework. • We prove the generalization upper bounds for different ranker models under shifted training distribution, highlighting the significant impact of disparities between training and inference data distributions on generalization errors. Theoretical and empirical findings indicate that harmonizing distributions across stages enhances the overall generalization performance of two-stage recommender systems.The remainder of this paper is organized as follows: Section 2 provides an overview of related work, Section 3 presents the notation and background, Section 4 presents the main results and analytical techniques, and Section 5 provides the conclusion of the paper. Finally, the missing proofs and experimental settings are provided in the appendix.2 Related WorkCauchy-Schwartz inequality:Rm (G F ) ≤ 2 m E ϵ   sup ∥W ∥2≤B (v,v ′ )∈V 2 w v -w v ′ , i:c(f,xi,yi)=(v,v ′ ) ϵ i x i   ≤ 2 m E ϵ   sup ∥W ∥2≤B (v,v ′ )∈V 2 ∥w v -w v ′ ∥ 2 i:c(f,xi,yi)=(v,v ′ ) ϵ i x i 2   ≤ 4B 0 m (v,v ′ )∈V 2 E ϵ   i:c(f,xi,yi)=(v,v ′ ) ϵ i x i 2   .Using Jensen's inequality, and as, ∀i,EQUATION)We have:EQUATIONwhereEQUATIONa) use the Cauchy-Schwartz inequality, (b) holds because for a given node v, the alternative nodes v ′ are in the same layer of v; note that this is based on a B-ary tree structure, (c) holds becausev∈V \⊥ min B d(v)-1 , N -1 = h-2 d=1 B d-1 (B d-1 -1) + N (N -1) ≤ N 2 B 2 B 2 -1 ,where h is the depth of tree, satisfyB h-2 < N ≤ B h-1 .Combining equations ( 15) and ( 16), we obtain the following result:Rm (G Flin ) ≤ 4B 0 B x √ m BN √ B 2 -1 .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes] Justification: The main claims in the abstract and introduction accurately summarize the key contributions and findings of the paper, and they align with the theoretical and experimental results presented. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
two-stage recommender systems: 
 Two-stage recommender systems with candidate generation followed by ranking have been widely adopted in the industry, including YouTube [4, 23, 26] , Linkedin [2] , Pinterest [6] . Some works focus more on improving candidate generation, particularly under tree structures. TDM [29] efficiently manages candidate retrieval in large-scale systems using a hierarchical tree-index strategy. JTM [28] improves on TDM by jointly optimizing the tree index structure and the user node preference prediction model. DeFoRec [8] extends the loss function used in TDM from a binary probability to a multi-class softmax loss. Other works, like [18] , study off-policy learning for two-stage recommender systems, where the goal is to learn a good recommendation policy from the typically abundant logged data. This approach is possibly most related to our work in the ranker component. The main proposal of [18] is to modify the training objective by adding importance weights based on the ranker's probability of recommending each item. With adjustments facilitating gradient descent optimization, the authors show empirical improvements compared to a system trained without importance weighting. [13] propose a modification of naive bandit method deployment in two-stage recommenders that improves results by sharing inferred statistics between ranker and nominators with minimal computational overhead. [25] aims to provide an LLM-based two-stage recommender that uses a large language model as a ranker to improve performance.In this subsection, we discuss the theoretical work related to our study, as well as other theories related to two-stage models. [1] propose a multi-class, hierarchical data-dependent bound on the generalization error of classifiers deployed in large-scale taxonomies to explain several empirical results related to the performance of hierarchical classifiers. Our analysis of tree structure models is inspired by this work. We extend it to the search method of beam search and provide a more refined estimate for the tree model. [17] investigates generalization error bounds for extreme multi-class classification with minimal dependence on the class set by using multi-class Gaussian complexity to construct bounds for multi-class problem. [12] theoretically demonstrated that nominator count and training objectives significantly impact two-stage recommender performance and linked twostage recommenders to Mixture-of-Experts models to show performance improvements by allowing nominators to specialize. [14] quantitatively assesses the asymptotic convergence properties of the two-tower model applied in two-stage recommenders toward an optimal recommender system.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We have stated the applicability of the proposed method in the theoretical result discussion part, noting that it relies on a retriever model with a high recall rate. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
notation: 
 We use the following notational conventions: bold lowercase and uppercase letters for vectors and matrices respectively, such as a and A, and non-bold letters for scalars or constants, such as c and B. Following previous traditional notations, in the case of hierarchical classification, the hierarchy of classes (V, E) is defined in the form of a rooted tree, with a root ⊥ and a parent relationship π : V \{⊥} → V where π(v) is the parent of node v ∈ V \{⊥}, and E denotes the set of edges with parent to child orientation. B k (x) identifies nodes selected at depth k during a beam search for input x.For each node v ∈ V \{⊥}, we further define the set of its childrenD(v) = {v ′ ∈ V \{⊥}; π (v ′ ) = v}.The specialized nodes at the leaf level constitute the set of target items. Finally, for each item y in Y we define the set of its ancestors P(y) defined asP(y) ={v 1 , . . . , v ky : v 1 = π(y), π v ky =⊥, v l+1 = π (v l ) , ∀ l ∈ {1, . . . , k y -1}}.During the retrieval stage, a tree is utilized where each leaf node represents an item. Additionally, each node in the tree has a learnable parameter vector that has the same dimensionality as the user vector. The architecture of the tree is generally determined by hierarchical clustering techniques, as shown in the studies by [29, 24] .When constructing the tree, we first need to obtain the initial item representations, which can be accomplished through various methods. The item representations can be represented by the instanceitem matrix Y ∈ {0, 1} m×N . A strategy to construct item representations is by leveraging indices of positive instances. For any given item i within the item set Y, its corresponding representation vector z i is defined through normalization as: z i = y i /∥y i ∥, where the vector y i ∈ {0, 1} m signifies the i-th column of the instance-to-item matrix Y , encapsulating the relationship between instances and the item i. It is possible to refine the item representation by incorporating additional feature information, an enhanced formulation of y i is employed, expressed as y i = m j=1 Y ji f j , where f j denotes the feature vector associated with the j-th instance. Besides, some works, like [29] , have employed a technique of starting with a randomly initialized tree structure aligned with item categories. The learned parameters of the leaf nodes are subsequently utilized as new initial representations for the items.After acquiring item representations, we repeatedly apply clustering algorithms, such as k-means, to form the complete tree structure. In the initial phase, all items are aggregated at the root. These items are then clustered into B categories, creating the root's child nodes. This procedure is recursively performed in each child node until each category is reduced to a single item, establishing the leaf nodes. A balanced distribution of items among the categories can lead to a more even tree structure, a practice widely utilized in applications.During inference, the user representation x starts from the root node, and the path is continually extended until a leaf node is reached, using a beam search based on the model score between the user representation and the node parameter vector. Specifically, assuming a beam size of K, we maintain at most K paths during the inference process. Initially, the user representation selects the top K nodes with the highest model scores from the children of the root node, denoted as B 1 (x). If the number of available nodes for selection is less than K, all available nodes are selected. B i+1 (x) denotes the selected nodes at depth (i + 1) for an input x,B i+1 (x) = T K c∈D(Bi(x)) f (x, c), where we denote T K as the Top-K operator, which selects the top K nodes from the children of nodes in B i (x), denoted as D(B i (x)) based on the highest score f (x, c). To avoid the problem of leaf nodes lacking children during the inference process, we extend the definition of D(v), D(v) = {v}, if v is a leaf node. In this extended definition, the children of a leaf node are considered to be the leaf node itself. The set of K leaf nodes ultimately selected by this process is denoted by B(x).The retriever models and the ranker models are often trained independently using logged feedback data (e.g., user clicks or dwell time) generated by previous versions of the recommender system. Compared to retriever models, ranker models may utilize more contextual information to better represent the user, leading to more accurate predictions. For simplicity, in this work, we assume that both the retriever and ranker models have the same input (e.g., user interaction history sequence).The key difference is that the retriever uses a tree-structured greedy model to retrieve a subset from a large item pool, while the ranker predicts scores for each item within this subset B(x). Finally, the item with the highest score from B(x), as determined by the ranker, is returned as the prediction result, which we denote as h(x).In the training of machine learning algorithms, we are constrained to a finite dataset for learning. Nevertheless, the resulting function must generalize effectively beyond the training sample. Thus, ensuring high probability guarantees for the difference between the loss on the training sample and the loss on the test population is of paramount importance. Generalization bounds aim to constrain this loss difference.Mathematically, if we have a hypothesis class H, sample space X , item space Y, loss function ℓ, and distribution over the sample and item space D, then our generalization gap for a set of samples and items S = {(x i , y i )} m i=1 , x i ∈ X , y i ∈ Y, on the hypothesis h ∈ H is defined to beEQUATIONNotice how if we can have this value go to 0 with high probability over all sets of samples and for all h ∈ H, then we can be confident that minimizing the empirical loss will not impact our generalization.One tool that can be used to upper bound the generalization gap is the Rademacher complexity. The Rademacher complexity of a hypothesis class H is defined to beRm (H) = 1 m E ϵ sup h∈H m i=1 ϵ i h (x i ) ,where each ϵ i are i.i.d. and take the value 1 or -1 each with half probability and ϵ = (ϵ 1 , . . . , ϵ m ). It is well known that [21] , if the magnitude of our loss function is bounded above by c, with probability greater than 1 -δ for all h ∈ H, we haveEQUATIONTherefore, if we have an upper bound on the Rademacher complexity, we can have an upper bound on the generalization gap.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
theory results: 
 We begin by considering the two-stage error decomposition. Let P err two-stage denote the two-stage classification error, i.e., P (h(x) ̸ = y) . P err retrieve and P err rank represent the classification errors caused by the retriever and ranker, respectively. We have the following proposition: Proposition 4.1. The probability of a classification error of the two-stage method can be decomposed as follows:P err two-stage = P err retrieve + P err rank (K) (1 -P err retrieve ),where P err retrieve = P (y / ∈ B(x)) and P err rank(K) = P (h(x) ̸ = y | y ∈ B(x)) with |B(x)| = K.In Proposition 4.1, the total generalization error of two stages is decomposed into two critical components, P err retrieve and P err rank . P err retrieve captures the error when the target item isn't included in the retriever model's results, reflecting the probability that the item y doesn't appear in the set B(x). P err rank refers to the error that occurs when the target item y, although present in the retriever's results B(x), is not correctly ranked by the ranker model.Compared to a single ranker model for classification tasks, we use P err rank (N ) to denote the classification error, where N emphasizes that the ranker model is used for an N -class task, we have the following corollary: Corollary 4.2. The error P err two-stage ≤ P err rank (N ) if and only if the retrieval error P err retrieve satisfies the following inequality:EQUATIONRegarding inequality (4), we have two approaches to enhance its validity. One is to reduce P err retrieve without increasing the number of retriever results. The other is to improve the ranker model while keeping the retriever unchanged, to reduce P err rank and thus increasing the threshold on the right side of the inequality. Furthermore, by Property 4.1, both approaches will lead to lower two-stage classification error. In the following subsections, we will analyze these two errors separately from a generalization bound perspective, revealing their relationship with the actual observed empirical errors.For the model described in Sec.3.2.1, we represent the user using the vector x i ∈ R d , which can be a vector representation of a text segment, or an embedding derived from a pre-trained model that includes relevant features (If we use sequence embeddings to represent the user, we denote this with a matrix A (i) ). We consider different user and target items to be independently and identically distributed, denoted as (x 1 , y 1 ), . . . , (x m , y m ) ∼ D.Following previous work [1] , we consider the following analogous function space induced by the function space F:EQUATIONwhere P(y) is the ancestors of node y, B(v, x) denotes the set of candidates during beam search at the same level as node v, in particular, if d(v) represents the depth of node v within the tree structure, then B(v, x) = D(B d(v)-1 (x)), max K denotes the K-th largest element in a set, f (x, v) represents the score function between node v and input x. The specific formulation of the score function will be discussed in Section 4.1.1.Compared with previous work, we extend the function space to the top-k form, as described in equation ( 5), we can observe the following proposition: Proposition 4.3. For any leaf node y ∈ Y and user representation x, we haveg f (x, y) ≥ 0 ⇔ y ∈ B(x).This implies that the probability of classification error is equal to the probability of occurrence of the event g f (x, y) < 0:EQUATIONFor this event, we can formulate the following theorem about the Rademacher complexity of the function space G F : Theorem 4.4. Consider a loss function A(x) that is monotonically decreasing, satisfies I(x ≤ 0) ≤ A(x), and is a Lipschitz function with Lipschitz constant c A and an upper bound B A . The following inequality holds with a probability of at least 1 -δ:P err retrieve ≤ 1 m m i=1 A (g f (x i , y i )) + 4c A Rm (G F ) + B A 2 log (2/δ) m .Theorem 4.4 presents a general result, considering an abstracted loss function under specific conditions and the Rademacher complexity of the function space. In Section 4.1.1, we will present the upper bounds of Rademacher complexity for various specific function spaces. Regarding A(g f ), it can be related to common loss functions, such as margin-based loss and cross-entropy. We will discuss the relationship between A(g f ) and these commonly used loss functions in the Appendix A.In this part, we discuss several common score models and provide upper bounds on their Rademacher complexity.Linear Model. One such model is the linear model, which is widely used in text retrieval tasks [24, 10] . It calculates scores by taking the dot product of user vectors and node vectors, which can be expressed as follows:f lin (x, v) = ⟨x, w v ⟩ ,where w v is a learnable parameter for node v in the tree model. The function space F lin is expressed as follows: EQUATION(G Flin ) ≤ 4B 0 B x √ m T ,whereT = BN / √ B 2 -1.MLP. We consider the concatenation of the user vector and the node vector as inputs to a multilayer perceptron (MLP). This architecture is widely used in the network structures of recommender systems [8] , which can be expressed as follows:f mlp (x, v) = W L • σ L-1 • σ L-2 • . . . • σ 1 (x; w v ) ,whereW L ∈ R 1×d L-1 , (x; w v ) ∈ R 2drepresents the concatenation of the column vectors x and w v , the function σ k (x) is defined:σ k (x) = σ (W k x) ∈ R d k ×1 , ∀k ∈ [L -1].The function σ is a Lipschitz continuous activation function with a Lipschitz constant c σ , has the property σ(0) = 0 and W k ∈ R d k ×d k-1 represents the weight matrix. For the function space:EQUATIONwe have the following results: Theorem 4.6. Suppose ∀i ∈ [m], ∥x i ∥ 2 ≤ B x , then the Rademacher complexity of G Fmlp can be bounded byRm (G Fmlp ) ≤ 8c L-1 σ B L 1 • (B 0 + B x ) √ m T .Target Attention. As a deep neural network architecture, target attention has achieved competitive performance in recommender systems and is widely used as a score function in tree-structured recommendations [8, 29] . In contrast to the previous two models, which represent a user as a single embedding vector, the model characterizes the user representation by a history sequence of items they have interacted with. In this context, we denote the matrix of item embedding vectors that the i-th user has interacted with as A (i) ,EQUATIONT ] ∈ R d×T , where we consider the last T recorded item interaction histories. The model uses a two-layer fully connected network to compute weights for node vectors and user-history item vectors, which can be expressed as:w (i) k = σ W (2) w σ W (1) w a (i) k ; a (i) k ⊙ w v ; w v ∈ R,whereEQUATIONw ∈ R 1×h , and σ is activation function. The score function can be expressed as:f ta (x i , v) = f mlp z (i) 1 ; z (i) 2 ; ...; z (i) N ′ ; w v , where ∀j ∈ [N ′ ], z (i) j = k∈Cj w (i) k a (i) k ,C j , corresponding to different time windows, each C j being mutually exclusive, satisfies the following conditions:N ′ j=1 C j = {1, 2, . . . , T }.For the function space:EQUATIONwe have the following results:EQUATIONk ∥ 2 ≤ B a , then the Rademacher complexity of G Fta can be bounded byRm (G Fta ) ≤ 4c L-1 σ B L 1 (B w T + B 0 ) √ m T ,whereB w = c 2 σ B 2 2 B 2 a + B 2 a B 0 + B 0 B a .The theorems 4.5, 4.6, and 4.7, show the effect of three different score models on their generalization. More complex models tend to have higher function space complexity. From a generalization error perspective, this represents a tradeoff between function space complexity and empirical error, as they often result in lower empirical errors. We can see that, similar to most generalization conclusions derived from Rademacher complexity, the order of the number of sample points m is O(m -1/2 ). This implies that as the number of samples increases, the error rate can be effectively controlled by the empirical error, resulting in a performance on the test set that is as satisfactory as on the training set.Besides, the theoretical results reveal a relationship between model generalization capabilities with tree structure retrievers. Specifically, the generalization bound includes a term O(B/ √ B 2 -1), where B represents the number of branches, suggesting that a tree with a larger number of child nodes (branches) tends to exhibit enhanced generalization performance. Intuitively, a tree with more branches will have a flatter structure. In an extreme case, when the number of branches equals the number of items, the tree structure becomes ineffective because it requires traversing all items during inference. This leads to the highest computational complexity, as the retriever model degenerates into a ranker model that processes the entire item pool. Thus, the number of branches of a tree structure represents, to some extent, a tradeoff between efficiency and performance.We conduct experiments on real-world datasets to study the effects of increasing the number of tree branches. In our experiments, we use the same datasets as work [8] , specifically Mind and Movie. We adopt an improved TDM model [8] as the retriever model architecture and use recall as the evaluation metric, since in the retrieval stage, the focus is on whether the target item is successfully retrieved. A more detailed description of the experimental setup can be found in Appendix D. The results are presented in Figure 1 . As we can see, the recall rate increases with the number of branches. Similar phenomena can be observed in other studies related to tree models [7] .In the context of training data sets S = {(x 1 , y 1 ), . . . , (x m , y m )} independently and identically distributed according to distribution D, where each x i ∈ R d and y i ∈ {1, . . . , N }, we examine a subset of this data, referred to as filtered training data, given byS ′ = {(x ′ 1 , y ′ 1 ), . . . , (x ′ m ′ , y ′ m ′ )} ⊂ S.We suppose this subset is independently and identically distributed, following the distribution D ′ , where each y ′ i ∈ B(x ′ i ). The generalization error of ranker P err rank , is defined as the expected probability of the ranking error under the distribution D ′ . Specifically, we haveP err rank = E (x,y)∼D ′ I f (x, y) -max j∈B(x) f (x, j) < 0 ,where we use f (x, j) to denote the model score of user x with respect to item j in this subsection.To establish a relationship between the expected generalization error on distribution D ′ and the empirical error measured on training data distribution D, we have the following theorem: Theorem 4.8. Consider a loss function Φ(x) that is monotonically decreasing, satisfies I(x ≤ 0) ≤ Φ(x), and is a Lipschitz function with Lipschitz constant c Φ and an upper bound B Φ . The following inequality holds with a probability of at least 1 -δ:P err rank ≤ E (x,y)∼D 1 - P ′ (x, y) P (x, y) + lrank + 4c Φ N (K + 1) Rm (Π 1 (F)) + B Φ 2 log (2/δ) m ,where Π 1 (F) = {x → f (x, y) : y ∈ Y, f ∈ F} P and P ′ denote the probability density functions of D and D ′ , respectively, and lrank = 1m m i=1 Φ(f (x i , y i ) -max j∈B(x) f (x i , j)).Similar to Theorem 4.4, Theorem 4.8 presents a general result. As for the abstracted loss function lrank , we can see that lrank≤ lrank = 1 m m i=1 Φ(f (x i , y i ) -max j∈Y f (x i , j)), where the latter, margin-based loss, is commonly used in training. This can also be extended to other common loss functions, as discussed similarly in the Appendix A. As for the Rademacher complexity of the function space, to maintain consistency with the previous subsection, we introduce the notation F Y to denote the restriction of the function space F w.r.t. Y, specifically:F Y = {f (x, v) ∈ F : v ∈ Y} ⊂ F.For the score function described in the subsection 4.1.1, we have the following theorem: Theorem 4.9. Suppose the conditions in Theorems 4.5, 4.6, and 4.7 hold, the Rademacher complexity of Π 1 (F Y ) can be bounded as follows:Rm (Π 1 (F Y model )) ≤ B model √ m ,whereB lin = B 0 B x , B mlp = 2c L-1 σ B L 1 • (B 0 + B x ), B ta = c L-1 σ B L 1 (B w T + B 0 ).Besides, compared to traditional generalization bounds, Theorem 4.8 includes an additional error term induced by distributional disparities. It shows that the generalization performance of the twostage ranker model degrades due to discrepancies between the inference distribution and training distributions. When the training distribution is aligned with the inference distribution, i.e., using the subset of the training data successfully retrieved by the retriever, the distributional disparities are minimized. This suggests that in practice, aligning the training distribution and inference distribution can enhance the model's performance.We conduct experiments on real-world datasets to verify this. In our experiments, we use the improved TDM [8] as the retriever, and the DIN model [27] , which uses the target attention structure, as the ranker. We investigate the effect of the training data distribution on the ranker performance in a fixed retriever two-stage setup. The ranker model is trained in two ways: using the original training data and using a subset of training data successfully retrieved by the retriever model. A more detailed description of the experimental setup can be found in the Appendix D. We evaluate the overall classification accuracy of the two-stage model. The results are presented in Table 1 . We compared the top-1 classification accuracy (i.e., Precsion@1) of rankings produced by the ranker with different numbers of retrieval items for two methods. We can see that the Harmonized Two Stage Model (H-TS) improves performance over the original Two Stage Model (TS) on these datasets. It is worth noting that while aligning the training distribution to the inference distribution eliminates the bias introduced by the distribution differences, it reduces the number of training samples available m ′ relative to the original number of samples m. This reduction means that the upper bound of the generalization guarantee is also somewhat weakened. Consequently, the effectiveness of this adjustment method depends on the presence of a high recall retriever model. In our experiments, we found that a recall rate of more than 10% is typically required to see an improvement effect. It must ensure that there are enough training samples to maintain the generalization performance of the model. 
conclusion: 
 In summary, our study provides a theoretical and empirical investigation into the generalization error bounds of two-stage recommender systems, particularly emphasizing tree-based retriever models. Our study uses Rademacher complexity to analyze the generalization capabilities of several commonly used models in two-stage recommender systems, highlighting how tree models with increased branches and ranker models trained on shifted distributions can affect generalization performance.The theoretical results show that as the number of branches in the tree increases, the model tends to exhibit improved generalization capabilities, effectively balancing efficiency and accuracy. In the presence of a high recall retriever model, using a harmonized distributions to train the ranker will improve performance. Furthermore, our experimental validation on real-world datasets with advanced models for both retriever and ranker stages corroborates the theoretical insights. This study deepens the understanding of generalization in tree-based two-stage models and provides a theoretical foundation for designing more effective models in two-stage recommender systems. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The research involves only publicly available datasets and standard models, posing no significant misuse risks, thus no specific safeguards were necessary.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have cited the relevant papers and provided links to download the data.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [NA]Justification: The paper does not introduce any new assets, thus documentation for such is not applicable.Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: This paper does not involve crowdsourcing or research with human subjects, thus the inclusion of participant instructions, screenshots, and compensation details is not applicable.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: This paper does not involve research with human subjects.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In the discussion that follows, we examine in detail a variety of widely used loss functions, including margin-based, top-k, and soft-max losses. The critical focus of this discussion is to establish that these loss functions act either as upper bounds or as consistent multiples of the upper bounds of A(g f ).This perspective is to confirm the easy applicability of our theoretical results to these commonly used loss functions.In the Theorem 4.4, for a single data point (x, y), the loss function we consider is:A(g f ) = A min v∈P(y) (f (x, v) -max K v ′ ∈B(v,x) f (x, v ′ )) .We show the following functions are upper bounds for A(g f ):Example 1 (Classical multi-class margin-based loss [5] ). The loss function is defined asEQUATIONwhere ℓ represents a function that is c l -Lipschitz and monotonically decreasing. By defining A as ℓ, the margin loss ℓ margin acts as an upper bound for A(g f ):A(g f ) ≤ max v∈P(y) ℓ margin .Example 2 (Top-K loss [16] ). The top-K hinge loss is defined byEQUATIONwhere for the sake of simplicity, we abbreviate the notationEQUATIONBy setting A(x) = max(0, 1 -x), it can be observed thatA(g f ) = max v∈P(y) (max(0, 1 + f [K] -f v )) ≤ max v∈P(y) ℓ topk .Example 3 (Cross entropy [8] ). This loss is employed in tree-structured recommender systems and is defined asEQUATION)Adopting the notation from equation (12) , and by setting A = -log 2 σ(•), it can be observed that Proof of Theorem 4.4. Exploiting the fact that A dominates the 0/1 loss and using the Rademacher data-dependent generalization bound presented in lemma C.3, we have with at least 1 -δ:A(g f ) = max v∈P(y) -log 2 1 1 + exp(f [K] -f v ) ≤ v∈P(y) -log 2 exp(f v ) exp(f v ) + exp(f [K] ) ≤ log 2 (e) • ℓ sof tmax .E (x,y)∼D I g f (x,y)≤0 -1 ≤ E (x,y)∼D [A • g f (x, y) -1] ≤ 1 m m i=1 (A (g f (x i , y i )) -1) + 2 Rm ((A -1) • G F ) + B A 2 log(2/δ) m ,where Rm denotes the empirical Rademacher complexity of (A -1) • G F on S. As x → A(x) is a Lipschitz function with constant c A and (A -1)(0) = 0. By lemma C.2 we further have:Rm ((A -1) • G F ) ≤ 2c A Rm (G F ) .Plugging this bound into the first inequality yields the desired result:P (g f (x, y) < 0) ≤ 1 m m i=1 A (g f (x i , y i )) + 4c A Rm (G F , S) + B A 2 log (2/δ) m .The proof provided below is motivated by [1] , requiring the modification for the max K operator. In addition, we have made more detailed estimates of the results and generalize of proof technology.Lemma B.1. Define the mapping c from F × X × Y into V × V as:c(f, x, y) = (v, v ′ ) ⇒ f (x, v ′ ) = max K v ′′ ∈B(v,x) f (x, v ′′ ) ∧ f (x, v) -f (x, v ′ ) = min u∈P(y) f (x, u) -max K u ′ ∈B(u,x) f (x, u ′ ) ,which is similar to the one given by [9] for flat multi-class classification. Then,EQUATION)Proof of Lemma B.1.F ) = E ϵ sup g f ∈G F 1 m m i=1 ϵ i g f (x i , y i ) = E ϵ sup f ∈F 1 m m i=1 ϵ i min v∈P(yi) f (x i , v) -max K v ′ ∈B(v,x) f (x i , v ′ ) ,where ϵ i s are independent uniform random variables which take value in {-1, +1} and are known as Rademacher variables. By construction of c :Rm (G F ) ≤ 1 m (v,v ′ )∈V 2 E ϵ   sup f ∈F i:c(f,xi,yi)=(v,v ′ ) ϵ i (f (x i , v) -f (x i , v ′ ))   ≤ 1 m (v,v ′ )∈V 2 E ϵ sup s∈{-1,1},f ∈F i:c(f,xi,yi)=(v,v ′ ) sϵ i f (x i , v) + sup s∈{-1,1},f ∈F i:c(f,xi,yi)=(v,v ′ ) sϵ i f (x i , v ′ ) = 2 m (v,v ′ )∈V 2 E ϵ   sup f ∈F i:c(f,xi,yi)=(v,v ′ ) ϵ i (f (x i , v))   + E ϵ   sup f ∈F i:c(f,xi,yi)=(v,v ′ ) ϵ i f (x i , v ′ )   ,where the last equation holds because the fact Rm (F ∪ -F) ≤ 2 Rm (F).Proof of Theorem 4.5. By definition, f(x i , v)-f (x i , v ′ ) = ⟨w v -w v ′ , x i ⟩, lemma B.Before we start the analysis, for any vectors v, u i ∈ R d , ∥v∥ 1 ≤ B v , notice the following inequality:EQUATION)Proof of Theorem 4.6. By lemma B.1, we haveEQUATIONUsing the equation ( 17), we can get:EQUATIONwhere (a) holds since σ is applied element wise, we can bring e ⊤ j inside the function and the use of contraction inequality [11] , (b) use equation (17) again as e ⊤ j W L-1 is a vector, (c) holds as Rm (F ∪ -F) ≤ 2 Rm (F).As term of I 1 , using Cauchy-Schwartz inequality and Jensen inequality:EQUATION)As term of I 2 , we have:EQUATIONwhere (a) holds since for any given (ϵ 1 , ϵ 2 , ..., ϵ m ), the value of ⟨e j , (0; w v )⟩ is fixed independent of i, (b) use Jensen inequality.Note that E ϵ [sup f ∈Fmlp i:c(f,xi,yi)=(v,v ′ ) ϵ i f (x i , v ′ )] and E ϵ [sup f ∈Fmlp i:c(f,xi,yi)=(v,v ′ ) ϵ i f (x i , v)]share the same upper bound, combined above equations ( 18), ( 19), ( 20), (21) , and ( 16), we get the desired result.Proof of Theorem 4.7. Using the same analytical procedure as in equation ( 19), we can getEQUATION)Based on equation ( 21), we can obtainEQUATION)For other terms, we haveE ϵ   sup s,j∈[d],zn i:c(f,Ai,yi)=(v,v ′ ) sϵ i ⟨e j , z n ⟩   = E ϵ   sup s,j∈[d],w i:c(f,Ai,yi)=(v,v ′ ) sϵ i e j , k∈Cn w (i) k a (i) k   ≤ k∈Cn E ϵ   sup s,j∈[d],w i:c(f,Ai,yi)=(v,v ′ )sϵ i e j , w(i) k a (i) k   = k∈Cn E ϵ   sup s,j∈[d],w i:c(f,Ai,yi)=(v,v ′ ) sϵ i σ W (2) w σ W (1) w a (i) k ; a (i) k ⊙ w v ; w v e j , a (i) k   ≤ c 2 σ W (1)EQUATIONk ; aEQUATIONFurthermore, we can getE ϵ   sup s,j∈[d],j ′ ∈[3d],w i:c(f,Ai,yi)=(v,v ′ ) sϵ i e j ′ , a (i) k ; a (i) k ⊙ w v ; w v e j , a (i) k   ≤ E ϵ   sup s,j∈[d],j ′ ∈[d] i:c(f,Ai,yi)=(v,v ′ )sϵ i e j ′ , aEQUATION)As terms of I 1 , we havei:c(f,Ai,yi)=(v,v ′ ) sϵ i e j ′ , a (i) k e j , a (i) k = i:c(f,Ai,yi)=(v,v ′ ) sϵ i e ⊤ j ′ P (i) a e j = i:c(f,Ai,yi)=(v,v ′ ) sϵ i Tr(e j e ⊤ j ′ P (i) a ) = Tr   e j e ⊤ j ′   i:c(f,Ai,yi)=(v,v ′ ) sϵ i P (i) a     = e j e ⊤ j ′ , i:c(f,Ai,yi)=(v,v ′ ) sϵ i P (i) a F, whereP (i) a = a (i) k a (i)⊤ k. Then, we can getI 1 = E ϵ   sup s,j∈[d],j ′ ∈[d] i:c(f,Ai,yi)=(v,v ′ ) sϵ i e j ′ , a (i) k e j , a (i) k   = E ϵ   sup s,j∈[d],j ′ ∈[d]e j e ⊤ j ′ ,i:c(f,Ai,yi)=(v,v ′ ) sϵ i P (i) a F   ≤ E ϵ   i:c(f,Ai,yi)=(v,v ′ ) ϵ i P (i) a F   = i:c(f,Ai,yi)=(v,v ′ ) P (i) a 2 F ≤ n (v,v ′ ) B 4 a .As terms of I 2 , use the same analysis technique as for I 1 , we can getI 2 = E ϵ   sup s,j∈[d],j ′ ∈[d],w i:c(f,Ai,yi)=(v,v ′ )sϵ i e j ′ , a(i) k ⊙ w v e j , a (i) k   = E ϵ   sup s,j∈[d],j ′ ∈[d],w i:c(f,Ai,yi)=(v,v ′ ) sϵ i e j ′ ⊙ w v , a (i) k e j , a (i) k   = E ϵ   sup s,j∈[d],j ′ ∈[d],w e j e ⊤ j ′ ⊙ w ⊤ v , i:c(f,Ai,yi)=(v,v ′ ) sϵ i P (i) a F   ≤ n (v,v ′ ) B 4 a B 2 0 .As terms of I 3 , we haveI 3 = E ϵ   sup s,j∈[d],j ′ ∈[d],w i:c(f,Ai,yi)=(v,v ′ ) sϵ i ⟨e j ′ , w v ⟩ e j , a (i) k   = E ϵ   sup s,j∈[d],j ′ ∈[d],w ⟨e j ′ , w v ⟩ e j , i:c(f,Ai,yi)=(v,v ′ ) sϵ i a (i) k   ≤ B 0 E ϵ   i:c(f,Ai,yi)=(v,v ′ ) ϵ i a (i) k 2   ≤ B 0 n (v,v ′ ) B 2 a .Combined equations ( 22), ( 23), ( 24), (25) , and useEQUATIONNote thatE ϵ   sup f ∈Fta i:c(f,xi,yi)=(v,v ′ ) ϵ i f (x i , v ′ )   and E ϵ   sup f ∈Fta i:c(f,xi,yi)=(v,v ′ ) ϵ i f (x i , v)  share the same upper bound, combined lemma B.1, equations (26) , and ( 16), we get the desired result.B.6 Proof of Theorem 4.8EQUATIONwhere we define ρ f (x, y) = miny ′ ∈B(x) (f (x, y) -f (x, y ′ )) . Let F = {(x, y) → ρ f (x, y) : f ∈ F}, By lemma C.3, with probability at least 1 -δ, for all f ∈ F:E [Φ (ρ f (x, y))] ≤ 1 m m i=1 Φ (ρ f (x i , y i )) + 2 Rm (Φ • F) + B Φ 2 log (2/δ) m .Since I(u < 0) ≤ Φ(u) for all u ∈ R, and given the Lipschitz continuity of Φ, we can write:E 1 ρ f (x,y)<0 ≤ E [Φ (ρ f (x, y))] ≤ 1 m m i=1 Φ (ρ f (x i , y i )) + 4c Φ Rm ( F) + B Φ 2 log (2/δ) m .(28) Rm ( F) can be upper-bounded as follows:Rm ( F) = 1 m E ϵ sup f ∈F m i=1 ϵ i f (x i , y i ) -max y∈B(xi) f (x i , y) ≤ 1 m E ϵ sup f ∈F m i=1 ϵ i f (x i , y i ) + 1 m E ϵ sup f ∈F m i=1 ϵ i max y∈B(xi) (f (x i , y)) .Now we bound the first term above. Observe thatEQUATION)where s i = 2 • 1 yi=y -1. Since ϵ i ∈ {-1, +1}, we have that ϵ i and ϵ i s i admit the same distribution and, for any y ∈ Y, each of the terms of the right-hand side can be bounded as follows:EQUATIONThus, we can write1 m E ϵ sup f ∈F m i=1 ϵ i f (x i , y i ) ≤ N Rm (Π 1 (F)).To bound the second term, we first apply lemma C.5 which yields that1 m E ϵ sup f ∈F m i=1 ϵ i max y∈B(xi) f (x i , y) ≤ K j=1 Rm (F j ) ,where we use B j (x i ) denote the j-th elements in B(x i ) andRm (F j ) = 1 m E ϵ sup f ∈F m i=1 ϵ i f (x i , B j (x i )) ≤ 1 m y∈Y E ϵ sup f ∈F m i=1 ϵ i f (x i , y) I(B j (x i ) = y) ≤ N Rm (Π 1 (F)) ,where the last inequality holds due to equations ( 29) and (30).Combined equations ( 27), ( 28) and above equations, we get the desired results.B.7 Proof of Theorem 4.9Using the same analysis applied to equation 15, we can derive the following results:E ϵ sup f ∈Flin,v∈Y m i=1 ϵ i (f (x i , v)) ≤ B 0 B x √ m.Using the same analysis applied to equation 19, we can derive the following results:E ϵ sup f ∈Fmlp,v∈Y m i=1 ϵ i (f (x i , v)) ≤ 2c L-1 σ B L 1 • (B 0 + B x ) √ m.Using the same analysis applied to equation 26, we can derive the following results:E ϵ sup f ∈Fta,v∈Y m i=1 ϵ i (f (x i , v)) ≤ c L-1 σ Π L k=1 ∥W k ∥ 1 c 2 σ W (1) w 1 W (2) w 1 B 2 a + B 2 a B 0 + B 0 B a T + B 0 √ m.Lemma C.1. For matrix A and B, vector v, we have∥ABv∥ ∞ ≤ ∥A∥ ∞ ∥B∥ ∞ ∥v∥ ∞ ,where we denoted ∥A∥ ∞ as ∥A∥ ∞,∞ = max(|a i,j |).Proof of lemma C.1. We have∥ABv∥ ∞ = A Bv ∥Bv∥ ∞ ∞ ∥Bv∥ ∞ ≤ ∥A∥ ∞ ∥Bv∥ ∞ ≤ ∥A∥ ∞ ∥B∥ ∞ ∥v∥ ∞ .Lemma C.2 (Theorem 4.15 (iv) in [22] ). Let F be classes of real functions. If A : R → R is Lipschitz with constant L and satisfies A(0) = 0, thenRℓ (A • F) ≤ 2L Rℓ (F).Lemma C.3 (Theorem 26.5 in [21] ). If the magnitude of our loss function is bounded above by c, with probability greater than 1 -δ for all h ∈ H, we haveE (x,y)∼D [ℓ(h(x), y)] - 1 n n i=1 ℓ (h (x i ) , y i ) ≤ 2 Rn (ℓ • H, S) + c 2 log(2/δ) n , where ℓ • H = {ℓ(h(x), y) | (x, y) ∈ X × Y, h ∈ H}.Lemma C.4 (Contraction lemma, lemma 26.9 in [21] ). For each i ∈ [m], let ϕ i : R → R be a ρ Lipschitz function, namely for all α, β ∈ R we have|ϕ i (α) -ϕ i (β)| ≤ ρ|α -β|. For a ∈ R m let ϕ(a) denote the vector (ϕ 1 (a 1 ) , . . . , ϕ m (y m )). Let ϕ • A = {ϕ(a) : a ∈ A}. Then, Rm (ϕ • A) ≤ ρ Rm (A).Lemma C.5 ( Lemma 9.1 in [20] ). Let F 1 , . . . , F l be l hypothesis sets, l ≥ 1, and let G = {max {h 1 , . . . , h l } :h i ∈ F i , i ∈ [l]}.Then, for any sample S of size m, the empirical Rademacher complexity of G can be upper bounded as follows:R m (G) ≤ l j=1 R m (F j ) .We conduct experiments on real-world datasets to validate the effectiveness of the proposed method and theoretical insights. All experiments were conducted on a Linux server equipped with a 3.00 GHz Intel CPU, 300 GB of main memory, and NVIDIA 20/30 series GPUs. We evaluate the two-stage models with two real-world recommendation datasets, which can be downloaded from the url2 . The datasets are MovieLens 10M (abbreviated as Movie), Microsoft News Dataset (abbreviated as Mind). Following previous work [8, 7] , since some datasets only include rating-based explicit feedback, they should be converted into implicit feedback for inputs. These datasets are pre-processed by filtering the users who interact with no more than 15 items. The overall information of datasets is summarized in Table 2 .In each dataset, we randomly choose 10% users as validation users, 10% users as test users, and all the left users as training users. Following [29, 28] , we use a slide window to split user-item interaction histories into slices of length 70 at most. For training users' data, the first 69 interactions are used for input context and the 70-th item is regarded as the ground truth of prediction. Each of the 10 time windows contains [1, 1, 1, 2, 2, 2, 10, 10, 20, 20] (sum up to 69; if the length of behavior history is less than 69, pad the absence by zero) interactions. For data of both validation users and test users, we regard the first half as context and others as ground truth.In the experiment on the effect of branch number, reported in Figure 1 , we used a structure similar to the TDM model [29] , except that we increased the number of tree branches and replaced the loss used in training with sampled softmax like [8] . We randomly initialize the correspondence between leaf nodes and labels and use a single well-trained tree model as the retriever model. The dimensions of item and node embeddings are both set to 24 across different branch numbers. We use Adam as the optimizer, with a learning rate of 1.0e-3 with exponential decay. For different branch numbers, we conduct a grid search on the hyperparameters, including weight decay and the number of negative samples. Specifically, we explore weight decay values within the range [1e-2, 1e-3, 1e-4, 1e-5], and the number of negative samples ranges from 50 to 200 in increments of 10. For each branch number, we perform a beam search with a beam size of 100 and report the highest recall@20 value achieved during the grid search of hyperparameters.In the experiment on harmonized distribution reported in Table 1 , we analyze the effect of the training data distribution on the performance of the ranker model within the two-stage model. Following the same setup as the previous experiment, we use the same retriever model and the DIN model [27] as the ranker model. In DIN, we replace the original loss function with a sampled softmax loss, sampling 60 negative examples for each loss computation. The embedding dimension of each item is set to 96, the hidden dimensions of the attention units are set to [64, 16] , and the hidden dimensions of the fully connected layers are set to [200, 80, 1] . The retriever model remains fixed throughout the experiment, while the ranker model is trained on different datasets: the original training data and a subset containing only items successfully retrieved by the retriever. We use precision as a metric to save the ranker model that performs best on the validation set during the training process and then evaluate the overall classification accuracy on the test set of the two-stage model.https://drive.google.com/drive/folders/1ahiLmzU7cGRPXf5qGMqtAChte2eYp9gI 


Decision: The paper considers two-stage recommender systems with tree structure. The theoretical work, providing generalization error of the retriever and ranker components, were appreciated by all reviewers. While all reviewers recommended acceptance, some issues were raised (and addressed) in the reviews. Please make sure to incorporate those changes into the final version of the paper.

Reviews: review: paper_summary: paper_summary: This paper analyzes the generalization error of two-stage recommender systems with a tree structure, which consist of an efficient tree-based retriever and a more precise but time-consuming ranker. The authors use Rademacher complexity to establish generalization error upper bounds for various tree-based retrievers using beam search, as well as for different ranker models under a shifted training distribution. The key findings are that increasing the number of branches in tree-based retrievers and harmonizing distributions across stages can enhance the overall generalization performance of two-stage recommender systems, as validated through both theoretical insights and practical experiments.
strength_weakness: strength_weakness: The analysis of tree-based retriever models is comprehensive, but the paper does not explore the generalization properties of other types of retriever architectures, such as deep learning-based models beyond the target attention model. Expanding the analysis to a broader range of retriever models could provide a more holistic understanding of two-stage recommender systems.

The paper primarily focuses on the generalization performance, but does not delve into the computational complexity and inference latency of the proposed two-stage recommender systems. Providing a more comprehensive analysis of the efficiency and scalability aspects would further strengthen the practical relevance of the work.
questions: questions: The analysis of tree-based retriever models is comprehensive, but does the paper explore the generalization properties of other types of retriever architectures, such as deep learning-based models beyond the target attention model? Would expanding the analysis to a broader range of retriever models provide a more holistic understanding of two-stage recommender systems?

While the paper primarily focuses on the generalization performance, does it delve into the computational complexity and inference latency of the proposed two-stage recommender systems? Would providing a more comprehensive analysis of the efficiency and scalability aspects further strengthen the practical relevance of the work?
limitations: limitations: NA
paper_summary: paper_summary: This paper theoretically analyzes the generalization bounds of two-stage recommender systems using Rademacher complexity. It examines the generalization bounds of the tree-structured retriever and the subsequent ranker, respectively. The paper concludes that the more branches a tree-structured retriever has, the tighter the corresponding generalization bound. Additionally, the smaller the discrepancy between the training distribution and the inference distribution of the ranker, the tighter the generalization bound. The authors also conducted experiments to validate their theoretical findings. Overall, this is a solid work, providing convincing theoretical evidence and offering insightful suggestions.
strength_weakness: strength_weakness: 1. The theoretical results regarding the generalization bounds of tree-structured Retrievers are highly similar to the results for hierarchical multi-class classification in reference [1], with the main difference being the consideration of the Beam Search algorithm. Additionally, the analysis of the Rademacher complexity for linear models and MLP models has been previously established. These should be referenced in the main text of the paper.
2. The paper mentions: "In our experiments, we found that a recall rate of more than 10% is typically required to see an improvement effect" in line 271.  Is there a corresponding experimental analysis for this conclusion? For example, how much does the performance of the ranker model improve with different recall rates (i.e., different data volumes)? Moreover, can this conclusion be theoretically justified as well?
3. There are some typos that need to be checked, especially in the use of bold and regular fonts. For instance, the subscript 'c' in the first formula on page 4 is not bolded, and the subscript 'v’' in formula 10 in Appendix A is not bolded.
questions: questions: See weaknessnes.
limitations: limitations: NA.
paper_summary: paper_summary: This paper studies two-stage recommender systems. The authors focus on analyzing the generalization error of the retriever and ranker components within a two-stage recommendation model, specifically examining the Rademacher complexity. The findings are supported by both theoretical analysis and empirical studies
strength_weakness: strength_weakness: 1. Although this paper is generally well-written, I suggest the authors create a separate "Experiments" section and include a list of notations to enhance clarity.
2. Please provide more detailed explanations of "Harmonized distribution" and "Harmonized model".
questions: questions: None
limitations: limitations: Although limitations are mentioned in theoretical result discussion, the authors are encouraged to create a separate "Limitations" section.
paper_summary: paper_summary: This paper presents the first generalization analysis of the learning algorithm driving the two-stage recommender systems. Specifically, it considers a representative two-stage recommender system with a tree structure, which consists of an efficient tree-based retriever and a more precise yet time-consuming ranker. An error decomposition framework is proposed, based on which the Rademacher complexity is applied to derive generalization upper bounds for various tree-based retrievers using beam search, as well as for different ranker models under a shifted training distribution. The upper bounds indicate that increasing the branches in tree-based retrievers and harmonizing distributions across stages can enhance the generalization performance of two-stage recommender systems. Furthermore, this theoretical finding is validated by experiments on real-world datasets.
strength_weakness: strength_weakness: This paper lacks a discussion on the potential limitations of the derived generalization upper bounds. I believe that this would make a good complement to the contribution.
questions: questions: Can the authors comment on the potential limitations of the derived generalization upper bounds?
limitations: limitations: The authors use the Rademacher complexity as a tool for proving the generalization upper bounds. The potential limitations of this work lie in the limitations of the Rademacher complexity tool itself. I do not think it has a negative impact on the contribution of this work.

Comments: title: Thank you for the authors' responses
comment: I appreciate the authors' response. My concerns have been addressed satisfactorily, and I maintain my positive evaluation of this paper.