Generalization Error Bounds for Two-stage Recommender Systems with Tree Structure
Authors: Jin Zhang
Ze Liu
Defu Lian
Enhong Chen
Venue: NeurIPS 2024 oral (2024)
Keywords: Two-stage Recommender Systems
Recommender Systems
Generalization error bounds
Rademacher complexities
Tree-based Learning
Primary area: learning_theory

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.

Generalization Error Bounds for Two-stage Recommender Systems with Tree Structure
Jin Zhang', Ze Liu', Defu Lian" 1,2,3 Enhong Ch
School of Artificial Intelligence and Data Science, University of Science and Technology of China 2 School of Computer Science and Technology, University of Science and Technology of China State Key Laboratory Cognitive Intelligence, Hefei, Anhui, China {j fjinhhng22, 1z123) @mail www.sstc..... edu. en, {liandefu, cheneh) edu.
Abstract
Two-stage recommender systems play 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 tree structure, which consist of an efficient tree-based retriever and a more precise yet time-consuming ranker. We use the Rademacher complexity establish the generalization upper bound for various tree-based retrievers using beam search, as well as for different ranker models under shifted training distribution. Both theoretical insights and practical experiments real-world datasets indicate that increasing the branches in rese retrievers and harmonizing distributions across stages can enhance the generalization performance of two-stage recommender systems.
Introduction
Recommender systems play a crucial role in many online services, such e-commerce 29 digital streaming 4), and social media (2), influencing consumer behavior, media consumption, and social interaction. needs quickly identify few relevant items from millions 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 the two-stage recommender system. the first stage, computationally efficient retriever preselects a small number of candidates from 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, well-balanced trade-off between efficiency and accuracy is achieved that meets demands of real-world scenarios.
The retrievers are often heterogeneous, popular choices like matrix factorization 15
two-tower 23 recurrent neural networks (3), and so on. recent years, the tree-structured retriever model 8 [29 [7.. which takes advantage of the tree structure, usually combined with a greedy algorithm identify relevant items quickly, has demonstrated commendable performance and efficiency. The ranker typically uses enriched features as input, combined with complex model, to enhance prediction accuracy. The computational costs are generally linear relative the number of items at
deployment 4 [8]
Despite the practical success of two-stage models, particularly those based on tree structures, the- oretical research in this area remains limited. To fill in the gap, we start from the perspective of generalization to investigate the upper bounds of generalization error for these models to promote understanding of their generalization capabilities.
CCoresponding Author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this paper, we decompose the generalization error of two-stage models across each stage. Using Rademacher complexity as 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 tree-based retrievers enhances their ability to generalize.
We establish enror decomposition framework for analyzing generalization errors of two- stage 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 presents the notation and background, Section techniques, and Section 5 provides the conclusion of the paper. Finally, the missing proofs and experimental settings are provided in the appendix.
4 presents the main results and analytical
2 Related Work
2.1 Two-stage Recommender Systems
Two-stage recommender systems with candidate generation followed by ranking have been widely adopted in the industry, including YouTube 23 26), Linkedin (2). Pinterest (6). Some works focus more improving candidate generation, partieularly 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- 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 possibly most related 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 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 -ased two-stage recommender that uses a large language model as ranker to improve performance.
2.2 Theoretical Work
In this subsection, we discuss the theoretical work related to our study, as well as other theories related to two-stage models. [ propose a multi-class, hierarchical data-dependent bound on the generalization eгror 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 to the search method of beam search and provide 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.. [2] theoretically demonstrated that nominator count

---

and training objectives significantly impact two-stage recommender performance and linked two- stage recommenders Mixture-of-Expenr models 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.
Preliminaries
3.1
Notation
We use the following notational conventions: bold lowercase and uppercase letters for vectors and matrices respectively, such and A, and non-bold letters for scalars constants, such as and B. For vectors, ||a||p denotes the lp norm; we drop the subseript for the & norm. For matrix,
Alpp
sup
|| |Ax|1p
|=
denotes matrix norms induced by vector p-norms. We denote the set [1, 2..., m) by [m]. In the defined notation system, m represents the number of users or queries, N denotes the total number of items, and K is the number of items retrieved in the first stage. B indicates the number of children nodes per non-leaf node, while specifies the number of layers in a neural network. The complete set of items is symbolized by V For i [m]) E IR is the embedding vector to represent user, if use sequence embeddings represent the user, denote this with matrix A (+),, and yi E y is the corresponding target item. The function h(x)) E y represents the prediction result for x:.
Following previous traditional notations, in the case of hierarchical classification, the hierarchy of classes (V, E)) is defined in the form of rooted tree, with a root 1 and a parent relationship [V + V where π (v) is the parent of node E V. and E' denotes the set of edges with parent to child orientation. B, (a:) identifies nodes selected at depth & during a beam search for input æ. For each node v E [\ we further define the set of its children
D(v) {o' VVL+); (v') v). The specialized nodes at the leaf level constitute the set of target items. Finally, for each item
in y we define the set of its ancestors (yy defined
(vv) = =VV Uky (V), π (VR,) = =L, 414
= = (D),
1}}. -
3.2 Background
3.2.1
Tree Structure Retriever Model
During the retrieval stage, tree is utilized where each leaf node represents 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
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 instance- item matrix Y E 1 1 A strategy to construct item representations is by leveraging indices of positive instances. For any given item within the item set V, its corresponding representation vector z; is defined through normalization as: matrix Y, encapsulating the relationship between instances and the
v./ll, ll. where the vector y; {0, 1)"H signifies the
i-th column of the instance-to-ite item i. It is possible to refine the item representation by incorporating additional feature information, an enhanced formulation of y, is employed, expressed as y; = Σド= H where f, denotes the feature vector associated with the j-th instance. Besides, some works, like (29), have employed a technique of starting with 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--mann, 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 single item, establishing the leaf nodes. balanced distribution of items among the categories can lead to more even tree structure, a practice widely utilized in applications.
3

---

During inference, the user representation starts from the root node, and the path is continually extended until a leaf node reached, using 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 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 (æ:). If the number of available nodes for selection is less than K, all available nodes are selected. 1 denotes the selected nodes at depth (i + 1) for input æ,
(x) = T (=)
where we denote 7 as the Top-K operator, which selects the top K nodes from the children of nodes in (x)), denoted (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 is a leaf node.
In this extended definition, the children of 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)).
3.2.2 Ranker Model
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 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 (zx), as determined by the ranker, returned as the prediction result, which we denote as h(x).
3.2.3 Generalization Error
In the training of machine learning algorithms, we are constrained 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 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 V loss function L, and distribution over the sample and item space D, then our generalization gap for set of samples and items S = ((1z, m Dy E X, yı E V. on the hypothesis
H is defined to be
1 Σ (h (a:s) -
E [(((M()).)))
Notice how if we can have this value go to 0 with high probability over all sets of samples and for all h E 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. defined to be
1
R.m (H)
E.
sup hEH
ech (axz)
where each are i.i.d. and take the value 1 or -1 each with half probability and (eI,...,Ee, It well known that (21). the magnitude of our loss function bounded above by e, with probability greater than 1 5 for all & E H. we have
Σ ((i v1) S 2Rm (l H) + ov
log (2/8)
( [((h( x), v)1
(2)
Therefore, if we have an upper bound on the Rademacher complexity, we can have an upper bound on the generalization gap.

---

Theory Results
We begin by considering the two-stage error decomposition. Let two-stage denote the two-stage classification error, i.c., P(h(x) # y) Prem retriess and per represent the classification errors caused by the retriever and ranker, respectively. We have the following proposition:
Proposition 4.1. The probability of classification error of the two-stage method can decomposed as follows:
pery -err two-stage retrieve peer (K) (1 pary
retrieve )
where pery retrieve
P(y & B())) and Perr (K) P(h(2)) # y ly E B(x)) with [B(x)) K.
In Proposition 4.1 the total generalization error of two stages is decomposed into two critical components, retrieve and Pert Per retrieve captures the enror when the target item isn't 't included in the retriever model's results, reflecting the probability that the item y doesn't 't appear in the set ((z). perr refers to the error that occurs when the target item y, although present in the retriever's results rank
Pert
(Zx), is not correctly ranked by the ranker model.
Compared a single ranker model for classification tasks, we use Pran (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 perr two-stage
Pert (N) if and only if the retrieval error perr retrieve satisfies the
following inequality:
perr
(N)
rank (K)
perr retrieve
perr (K)
Regarding inequality without increasing the number of retriever results. The other is improve the ranker model while keeping the retriever unchanged, to reduce per 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 generalization bound perspective, revealing their relationship with the actual observed empirical errors.
4 we have two approaches to enhance its validity. One is to reduce per
rerrieve
4.1 Retriever
For the model described in 3.2.1 be a vector representation of a text segment, or an embedding derived from a pre-trained model that includes relevant features (If
represent the user using the vector æ; Rdd which can
sequence embeddings represent the user, denote this with matrix A (.)). We consider different user and target items be independently and identically distributed, denoted as (æ1, v1)..... (æm, Fm) ~ D.
Following previous work (.] consider the following analogous function space induced by the function space F:
(f(z, v)
GJ = (gf (z. X min vEP(N)
(5)
maxkif (an v') B(o,2))) []
where B(y) is the ancestors of node y, B(v, ær) denotes the of candidates during beam search the same level as node v. in particular, if d(v) represents the depth of node u within the tree structure, then B(v, x)) - (x=), maxk denotes the K-th largest element in set, fæx, v) represents the score function between node v and input æ. The specific formulation of the score function will be
discussed in Section 4.I.1
Compared with previous work, we extend the function space to the top-k form, as described in equation (5) observe the following proposition:
Proposition 4.3. For any leaf node y E y and user representation we have
95( v) 2 0 + y E B(x).
5

---

This implies that the probability of classification error is equal to the probability of occurrence of the event gy(2 y)
P(y & B(x:) = P (g. < 0).
(6)
For this event, we can formulate the following theorem about the Rademacher complexity of the function space 97:
Theorem 4.4. Consider a loss function A(x) that is monotonically decreasing, satisfies [[ S 0) S A(x), and is Lipschitz, function with Lipschitz constant Ca and an upper bound B. The following inequality holds with a probability of at least 1 1 8:
m E
2 log (2/6)
peir retrieve
Ags (ar, 9c)) + 40 (95) + BAV m
m
Theorem 4.4 presents general result, considering an abstracted loss function under specific conditions and the Rademacher complexity of the function space. In Section 4.1.II we will present the upper bounds of Rademacher complexity for various specific function spaces. Regarding A(gr). ). it can be related to common loss functions, such as margin-bases loss and cross-entropy. We will discuss the relationship between A(gy) and these commonly used loss functions in the Appendix A
4.1.1 Effect Model Architectures
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 widely used in text retrieval tasks [0]. It calculates scores by taking the dot product of user vectors and node vectors, which can be expressed as follows:
fim (x, v) (x, w.)
where w. is a learnable parameter for node in the tree model. The function space Fin is expressed follows:
Fim = (f (xx w) + (xx, w.)
a.c. ll < Bb, VoEV..
We have the following results:
Theorem 4.5. Suppose Vi E [m]. |xlll Bz, then the Rademacher complexity of 95m can be bounded by
4B T vm
Rm (9mm) 5
where T BN/ B
MLP. We consider the concatenation of the user vector and the node vector as inputs to multilayer perceptron (MLP). This architecture is widely used the network structures of recommender systems g which can be expressed follows:
(x,, v) Wz. 01-1 01.-2 o... oa (æ; w.)
where Wz E TR 1xdz-_1, (æ:; w.) E TR 2d represents the concatenation of the column vectors æ and W. the function a (z) defined:
(x = (Wax) gdex1 Wk E [L [L-1]
The function o is Lipschitz continuous activation function with Lipschitz constant c,, has the property (0)) = and WA E [dd xde-1 represents the weight matrix. For the function space:
ʃ (ær, v) + [mpp(e, v) |/wll2 S Bo, V Ve Wxll S Bi, Vk [4]..
Fmip
(8)
we have the following results:
Theorem 4.6. Suppose Vi [m), ||0:|12 Br, then the Rademacher complexity of IFu can be bounded by
8ch-1 BB (Bo + B.)
Rm (9 5
m

---

Target Attention. As a deep neural network architecture, target attention has achieved competitive performance recommender systems and widely used as score function in tree-structured recommendations 8 29 In contrast to the previous two models, which represent 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 A (6)
i
ia
E Rd
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:
( (2) (W
: Oi a
Wp we 1) R,
where w Rdx3d w E R.x.A, and is activation function. The score function can be expressed as:
fta v) = Smip
(z)
(6)
(1) 2N:; w.
22 ...
where Vjj [N].
W
kEC;
Cj. corresponding to different time windows, each C being mutually exclusive, satisfies the following conditions:
N' Uc, f1.2..... j=1
For the function space:
| 112 1 Bu, V Fu = {f: (x, v) + fa(2,
(9)
[aall S B1, vk E [T]] | ||1 < B2, e E (1,2)
we have the following results:
Theorem 4.7. Suppose Vi [m], vk E [T), l|a (8) S Ba then the Rademacher complexity of 9F.. can be bounded by
4eb-1 (B.T Bo) T,
R.n ( 5
/m
where B = 2 B3 B + B. + Bo Ba).
4.1.2
Insights from Generalization Bound
The theorems 4.5 4.6 and show the effect of three different score models their generalization.
More complex models tend to have higher function space complexity. From a generalization error perspective, this represents tradeoff between function space complexity and empirical error, they often result 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 Omm1))). This implies that the number of samples increases, the eиror 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 term Q(B/BBB 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 flatter structure. In an extreme case, when the number of branches equals the number of items, the tree structure becomes ineffective because requires traversing all items during inference. This leads to the highest computational complexity, as the retriever model degenerates into

---

Effect of Branch Numberon on Recall@20 for Mind
Effect of Branch Number Rocall@20 for Movie
0.190
0.13
Recallazz
Recalig20
0.184
0.11
0.181
0.30
0.178
0.08
Figure 1: Effect of branch number Recall @ 20 for Mind (left) and Movie (right)
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 real-world datasets to study the effects of increasing the number of tree branches. In our experiments, we use the same datasets as work { 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 [ The results are presented in Figure]] [
As we can see, the recall rate increases with the number branches. Similar phenomena can be observed in other studies related to tree models 7
4.2 Ranker
In the context of training data sets S {311 vi).. (mm }m)} independently and identically
distributed according distribution 2, where each æ; Rd and y: {1. f1...., NV. we examine subset of this data, referred to as filtered training data, given by S' {a vi)...... ( C S. We suppose this subset is independently and identically distributed, following the distribution D', where each y E B(xr). The generalization error of ranker per rank. is defined the expected probability of the ranking error under the distribution D'. Specifically, we have
perr I (n(=:)) Be
max f(x, < <0)
jEB(a)
where we use f( to denote the model score of user with respect to item 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 (xx)) that monotonically decreasing, satisfies I(x S < < (xx,, and is a funschit with Lipschitz constant ca and an upper bound Bz. The following inequality holds with a probubility of at least 1 - 6:
function
P'(x, 3)
log (2/5)
peer < (((x.g))D rank
+ Trank + 4c (K + +1)Rm. (IL, + Bay
((r, v)
where IT (F) = (x++ f(x, v) WEYYSER P and P' denote the probability density functions of and D', respectively, and brank Σn (f y.) maxxeB(a)) f()x,j)).
Similar to Theorem 4.4 Theorem 4.8 presents general result. As for the abstracted loss function Σ 4 (zf(x; y1) maxjey f(xx, 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> to denote the restriction of the function space F w.r.t. V, specifically:
Taak we
that Trank Lrank
F
For the score function described in the subsection 4.1.I we have the following theorem:
8

---

Theorem 4.9, Suppose the conditions in Theorems 4.5 IfII, can be bounded as follows:
4.6 and 4.7 hold, the Rademacher complexity
B
Rm (111 (Froda))
vm
where Blin = B, Bmip = 2c 2c B (Bo + Ba), Bio = = Bi Bo).
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 two- stage ranker model degrades due to discrepancies between the inference distribution and training distributions. When the training distribution is aligned with the inference distribution, i.c., using the subset of the training data successfully retrieved by the retriever, the distributional disparities are minimized. This suggests that practice, aligning the training distribution and inference distribution can enhance the model's ' performance.
We conduct experiments real-world datasets verify this. In our experiments, 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 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 T 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.
the ranker performance in fixed
Table 1: Comparison of classification accuracy of the two-stage model.
Dataset
Method
K=40
K=80
K=120
TS
0.6500
0.5970
0.5609
Mind
H-TS
0.6565
0.6026
0.5644
TS
0.3516
0.3457
0.3453
Movie
H-TS
0.3555
0.3500
0.3488
It is worth noting that while aligning the training distribution to the inference distribution eliminates the bias introduced by the distribution differences, reduces the number of training samples available mn 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. must ensure that there are enough training samples to maintain the generalization performance of the model.
5 Conclusion
In summary, our study provides theoretical and empirical investigation into the generalization enror bounds of two-stage recommender systems, particularly emphasizing tree-based retriever models. Our study uses Rademacher complexity 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 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 tree-hased two-stage models and provides theoretical foundation for designing more effective models in two-stage recommender systems.

---

Acknowledgments and Disclosure of Funding
The work was supported by grants from the National Key R&D Program of China (No. (021210111801) and the National Natural Science Foundation of China (No. 62022077).
References
[1] Rohit Babbar, Ioannis Partalas, Eric Gaussier, Massih-Reza Amini, and Cécile Amblard. Learn- ing taxonomy adaptation large-scale classification. The Journal of Machine Learning Research, ((1):3355-33388 2016.
[2] Fedor Borisyuk, Krishnaram Kenthapadi, David Stein, and Bo Zhao. Casmos: A framework for learning candidate selection models over structured queries and documents. In Proceedings of the 22nd ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pages 441-450, 2016.
[3] Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H Chi. Top-k off-policy correction for reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pages 456-464, 2019.
[4] Paul Covington, Jay Adams, and Emre Sargin. Deep neural networks for youtube recommenda- tions. In Proceedings of the 10th ACM conference on recommender systems, pages 191-199, 2016.
[5] Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel- based vector machines. Journal of machine learning research, 2(Dec):265-292 2001.
[6] Chantat Eksombatchai, Pranav Jindal, Jerry Zitao Liu, Yuchen Liu, Rahul Sharma, Charles Sugnet, Mark Ulrich, and Jure Leskovec. Pixie: A system for recommending 3+ billion items 200+ million users in real-time. In Proceedings of the 2018 world wide web conference, pages 1775-1784, 2018
[7] Chao Feng, Wuchao Li, Defu Lian, Zheng Liu, and Enhong Chen. Recommender forest for efficient retrieval. Advances in Neural Information Processing Systems, 35:38912-38924, 2022.
[8] Chao Feng, Defu Lian, Zheng Liu, Xing Xie, Le Wu, and Enhong Chen. Forest-based deep recommender. Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 523 532, 2022.
[9] Yann Guermeur. Sample complexity of classifiers taking values r q. application multi-class svms. Communications in Statistics-Theory and Methods, 39(3)5543-557 2010.
[10] Nilesh Gupta, Patrick Chen, Hsiang-Fu Yu, Cho-Jui Hsieh, and Inderjit Dhillon. Elias: End- to-end learning to index and search in large output spaces. Advances in Neural Information Processing Systems, 15:19798-19809, 2022.
[11] Marjorie G Hahn. Probability in banach spaces: Isoperimetry and processes., 1994.
[12] Jiri Hron, Karl Krauth, Michael Jordan, and Niki Kilbertus. On component interactions in two- stage recommender systems. Advances in neural information processing systems, 34:2744-2757, 2021.
[13] Jiri Hron, Karl Krauth, Michael Jordan, and Niki Kilbertus. Exploration two-stage recom- mender systems. arXiv preprint arXiv:2009.08956 2020.
[14] Amit Kumar Jaiswal. Towards theoretical understanding of two-stage recommender systems. arXiv preprint arXiv:2403.0080) 2024.
[15] Yehuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recom- mender systems. Computer, 42(8):30-37, 2009.
[16] Maksim Lapin, Matthias Hein, and Bernt Schiele. Top-k multiclass svm. Advances in neural information processing systems, 28, 2015.
10

---

[17] Yunwen Lei, Urün Dogan. D Zhou, and Marius Kloft. Generalization error bounds for extreme multi-class classification. CoRR, abs/1706. 098444,4,, 2017.
[18] Jiaqi Ma, Zhe Zhao, Xinyang Yi, Ji Yang, Minmin Chen, Jiaxi Tang, Lichan Hong, and H Chi. Off-policy learning in two-stage recommender systems. In Proceedings of The Web Conference 2020, pages 463 473, 2020.
[19] Andriy Mnih and Russ R Salakhutdinov. Probabilistic matrix factorization. Advances in neural information processing systems, 20, 2007.
[20] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[21] Shai Shalev-Shwariz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[22] John Shawe-Taylor and Nello Cristianini. Kernel methods for pattern analysis. Cambridge university press, 2004.
[23] Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Kumthekar, Zhe Zhao, Li Wei, and Ed Chi. Sampling-bing seaiing-bas--ooooe corrected neural modeling for large corpus item recommendations. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 269-277, 2019.
[24] Hsiang-Fu Yu, Jiong Zhang, Wei-Cheng Chang, Jyun-Yo Yu Jiang, Wei Li, and Cho-Jui Hsich. Pecos: Prediction for enormous and correlated output spaces. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4848 4849, 2022.
[25] Zhenrui Yue, Sara Rabhi, Gabriel de Souza Pereira Moreira, Dong Wang, and Even Oldridge. Llamarec: Two-stage recommendation using large language models for ranking. arXiv preprint arXiv:2311.02089, 2023.
[26] Zhe Zhao, Lichan Hong, Li Wei, Jilin Chen, Aniruddh Nath. Shawn Andrews, Aditee Kumthekar, Maheswaran Sathiamorrthy, Xinyang Yi, and Ed Chi. Recommending what video to watch next: multitask ranking system. In Proceedings of the 13th ACM Conference on Reconmender Systems, pages 43-51, 2019.
[27] Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1059 1068, 2018
[28] Han Zhu, Daqing Chang. Ziru Xu, Pengye Zhang, Xiang Li, Jie He, Han Li, Jian Xu, and Kun Gai. Joint optimization of tree-based index and deep model for recommender systems. Advances in Neural Information Processing Systems, 32, 2019.
[29] Han Zhu, Xiang Li, Pengye Zhang, Guozheng Li, Jie He, Han Li, and Kun Gai. Learning tree-based deep model for recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1079-1088, 2018.

---

A Effect of Loss Functions
In the discussion that follows, we examine in detail 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 either as upper bounds or consistent multiples of the upper bounds of A(gr), ). 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 (zz, y), the loss function we consider is:
Algi) = A min () maxk f (2, ((x v'EB(U,a)
vEP(v)
We show the following functions upper bounds for A(gr): Example (Classical multi-class margin- loss (5). The loss function defined as
margin = (((xx)))
max v'FuEB(u.a)
f (x, f2),
(10)
where l represents a function that is ci C--ipschitz and monotonically decreasing. By defining A as E the margin loss marrgin acts as an upper bound for A(gj):
Algs) S max Emargin-
vEP(w)
Example 2 (Top-K loss (6]). The top-K hinge loss is defined by
max (
K
Cuok {K
(1+ Jol ((+00
0.
E
(1+
(11)
j=1
where for the sake of simplicity, we abbreviate the notation
ful == maxj f(x (x,v') for == f(x,
(12)
v'EB(w..)
By setting A(x) max(0, 10--) .)), it can be observed that
A(g,) max (max(0, 1 f.g] - vEP(y)
max Look veP(y)
Example 3 (Cross entropy defined as
This loss is employed in tree-structured recommender systems and
exp(s(x, v))
L Eoottmax
log
(13)
E( exp (f(æ, v'))
vET(
Adopting the notation from equation
12
and by setting A logg (-), it can be observed that
1 1 exp(f[([ - fo) } exp(So)
1
Algs)
max ve
log2
Σ
logg
exp(ff) + eXP(F(K)
vE
logz(e) (e) Looftmex
B Proof of Results
B.1 Proof of Proposition 4.1
Proof of Proposition 4.1
Using the law of total probability, we have
P(h(x) + v)
P(h(#) + (( & B(x)) P(h(z) F B(x))
P(y & B(x)) + P(h(m)))))))))))))))))(()))))P *
(1 fl
B(x))
P(y & B(x))),
where P(h(x) Yy B(x)) is always 1.
12

---

B.2 Proof of Theorem 4.4
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 - 6:
((a,y)~D (e - 1] x ((aa))DDD [A (x, -
2 1og(2/0)
(A (0i,, 9i)) - 1) + 2Rm ((A-1) - (r) + BAV
m
where R., denotes the empirical Rademacher complexity of (A- 1) or on S. x + A(x) is
Lipschitz function with constant and (AA 1)(0) 0. By lemma C.2 we further have:
Rm (A S Rm (GF).
Plugging this bound into the first inequality yields the desired result:
log (2/0)
P (g)((x,)) <0)
A (gf (æt, 9() + Rc (9F, + BAV
=
B.3 Proof of Theorem 4.5
The proof provided below is motivated by [1. requiring the modification for the max operator. In addition, we have made more detailed estimates of the results and generalize of proof technology.
Lemma B.1. Define the mapping frrom F x y into x V as:
(f. (v, [x,00)) = maxk f fxx,0") v"EB(u.x)
maxk ((x, (
(s(,, (cx,
min mE?f())
f(x,u)-
wEB((a))))
which is similar to the one given by [9] for flat multi-class classificution. Then,
Rm (GF) < 2 Σ
E
sup SEF
Σ
Es (f (xi, v)) +
(V.'')V
toll as =o)
(14)
Ex
sup fEF
Ee eil (ces; 8¹)
Σ
Proof of Lemma B.I
m
Run (9x) Fe
sup
Σ egg (a:, vh)
g m
m
maxx I (xi (ain (1) wEB(D..)
Ex
sup
E; min
f (2),,)-
fEF m
v
13

---

where e; are independent uniform random variables which take value in (-1, +1} and are known Rademacher variables. By construction of c:
Rm (gr) -
Σ
Eg
sup
Σ
4 (f(x,, f (20,, 0'))
(v,
fer
is ( (0,0")
Ee
sup
Σ
seif (xo v)
(u,
sEi uE(-E.
tol (o)
Σ
SElf (2 x')
sup fa (=
sE(-1,1),EF
2
Σ
E.
sup feF
Σ
G (f(( v))
(w.e')EV2
hels (.)))
Σ fo (1))(.0))))
+ E.
sup JEF
where the last equation holds because the fact Rm (FU -J) S (F).
Proof of Theorem 4.5
By definition, f (æ,, v) - (z v') (w ww. 24). lemma B.1 and using
Cauchy-Schwards inequality:
2 m
Rm (9x)
Ee
sup
Wy Wo,
Σ
C
| (VV
2 < - Es
sup
w worlla
Σ
771
|W|s5B
(V.
xte(f.m.:B)] (v,wr)
4Bg
Σ E.
(V.
Using Jensen's 's inequality, and as, Vi,j E (1 cJ,, Ri, = (0, v')) j, E. [eve,] = 0, we get:
2
1/2
4Ba
Rm (9
Ee
m
(V)
2
1/2
4Bg
Σ
Σ
(15)
(:((/R....)=(e.r))
4Bp
(M(rre") B2) 1/2
(w,e')EV2
14

---

We have:
Σ
(M(o,rr))
1/2
Σ n(ow))
lf((,, 07) E 12 Bi, s.t. v' E B(v,,,))) x4)
(
(v,D))EV2
Vm
(min (B4(v)-1, - -1)
(16)
(8)
DEVI
VmBN
v B -1
where (((,,") = Hi 6 ( wi, y/) = (v, )') is the number of set {i : c cJ, Ri, y:) - (v, t')}, which satisfies _(..'') (/())11) = m. (a) use the Cauchy-Schward inequality, (b) holds because for given node v, the alternative nodes r' are in the same layer of u; note that this is based on a B-ary tree structure, (c) holds because
h-2
N B
Σ LE
min (N) 11)
Σ d=1
B (B
1)
where h is the depth of tree, satisfy Bh- N Bh-1 Combining equations (15) and [16), we obtain the following result:
4BoBa BN
Rm (9rm)
mm VB² -1
B.4 Proof of Theorem 4.6
Before we start the analysis, for any vectors v, ur R.d ||l||1 S Bu, notice the following inequality:
sup Σ
us
B, max seld
Eejui
S SEn B max jE(1)xE(-1.1)
se,
(17)
Proof of Theorem 4.6
By lemma B.1
we have
Rm (Frm)) <
Σ
EE
sup
Σ
e (f (2;
(u,
JeFab felf (=)))))))))))
(18)
eff (a) )
+ Ee
sup
Σ
fEFiig
15

---

Using the equation 17 we can get:
Eg
sup
Σ
e (f (x,, v))
Ex
sup
Σ
100. oa (x);; w.))
Wu.( (W. iamn fon(f (m)))))((,.)))
[Wz 12
sup s.jldd u. Wv 1
Σ
se; (10.0--1000-2000.. o (x;;w.))
sup
Σ
86, 10- 00 (#1; w)))
w. (Wa) 1 :e(ff.m.B:)=
<
W2 11 W W
sup
Σ
se, (e,, OL-2 o... or (z);; w.))
s.jEld), w.. Walt
20
sup s.jE|d),., w0
Σ
sc, (ej, (x;;; w.))
20
1- 11 Willi
sup Eg
Σ
E (ej,(z;;))
(0)
jE(2d) tfl f. (v.,o)
Ex
sup WoijE (2]]
Σ
es (ej, (0: wv))
isel f (a) (w,rr)
(19)
where (a) holds since is applied element wise, can bring e inside the function and the use of contraction inequality [II, (b) use equation again as e, Wr-1 is a vector, (c) holds as Ru (F -- F)) 2m (F).
As term of I, using Cauchy-Schie Schwartz inequality and Jensen inequality:
1/2
h <
Ex
Σ
Gat
E.
Σ
G
(20)
1/2
Σ
|
S (n B2) 1/2
Belf (ol.
16

---

As term of 12, we have:
1 E
sup (2
(ej, (0; ww)))
Ci
(a)
icel f. (1)
<
Bo
Σ
(21)
27
<
Bo
Ex
Σ
(6)
Bo (((,an)
where (a) holds since for any given (61, C2, Gm), the value (ej, (0; w.)) fixed independent of (b) use Jensen inequality.
Note that E, yeu Eieff (w..)) fif (æ; 0')] and E, yeu share the same upper bound, combined above equations (88 desired result.
Ene(f.m (o..f.... (mmm::))mmmmm (n,w") f,f (#;; v)
Ful
(1 and 16.. we get
B.5
Proof of Theorem 4.7
Proof of Theorem 4.7
Using the same analytical procedure as in equation
19
we can
E.
sup feFu
Σ
e: ( v))
co( (.a:)))) (w..)))
Ee
sup wo. ( 12 k= sel (c
Σ
6 (W 00 (xx w.))
Se. I. 1.-11 !
k=1 Be
sup +i)d((++))d wx.x
Σ
sc; (ej, (21; 22; 2N: w
N'
<cg 1-11 11
W E.
sup s.E
Σ
se, (ej, (n)
Belf [e(((=)..))=(v.o)))
sup
Σ
se; (eg, wv)
s we
(22)
Based equation
21
obtain
sup s.jE(d)
Σ
se; Wp) $ (.ood)
(23)
17

---

For other terms, we have
E.
sup s.jEdd
Σ
8e, (eg, 2nd)
kels (..
Egg s.jE(d),w
sup
Σ
Sei
Eji
Σ
W a
(8)
kEC.
E
sup &JE(d].w
Σ
es, wik ak
(8)
k
td (..)....))))...
Σ Ex kEC
sup sJEld],w w
Σ
8810 ( 0 (W
w
Ox ; 00
(3)
3 wn; @wp wp; 1)) ( (e).
w
Σ E
sup (eE(d)/'E(3dd]..
kEC.
Σ
set (ey,, ak a o wwi w.: (ee, (1)
(1) (2)
kc (c((/A..))))0000")
(24)
Furthermore, we can get
Eg
sup
Σ
sc; (eg,,
a ;a ( o ww; w. 1) (es,
(1))))))
< E.
sup
Σ
SE, (ey, ala) (es.
(((,,)
(25)
+ E,
sup
Σ
sti a
(1) o (ww) (es, eg.
(es) (1)
Ae(f.A,,B))
+ E.
sup
Σ
eej. (e.. (1)) sei wo)
se(l.A..p)=(u..))))
1 + In + Iz.
As terms of 4, we have
Σ
sci (e(ess (ey, (0))
a
eej (5,.at) (c), (
Σ
sc, sc.ee.ppie.
((,))))))))((
Σ
Tr(ejeJ.PP!))
Tr
ejey
T
Σ
86; p(t)
Σ
s(ip
egeg
GolsAA ((v.)))
18

---

where p!
(1) ( ak a
Then, get
Σ
se, (ey,ayt (
(er,ak
11 E
sup +JE
ho (.
E.
sup
ejezi
sc, ((
+JE(d)
< E2
Σ
F
Σ
p(0)
S
V ((o,o') Ba.
Relf.A A;:1):
As terms of 12, use the same analysis technique as for I1, we can get
1 = E.
sup <.E
Σ
8e (e
( c w.
(es) a(t)
xc(f.A..)==(..r)
Eg
sup
Σ
s6, ee
Wg: ( (1))
Cg. (e.. (1))
Ao(fiAr
E.
sup J'
ejey 3 T
Σ
se, P(1)
BBBB
As terms of 13, we have
13 E,
sup
Σ
se; (ey, we)
(ej. (i)
Ao.f) (w,ar)
E.
sup
(ej;, w.)
ej:
Σ
se; (t)
J
isels (o,)))
E,
Σ
e:ak (i)
Bo (( B3-
Combined equations 22
and use N |Cnl = T we have
Eg
sup
Σ
(f (wi v))
feFu oo wh =w,
(26)
ch 11 Willi
(2)
( (2) || (B² + B + BoBa) T + Bo) /iiwwwy
Note that
Eg
sup
Σ
of (at 0²)
feJu iself tte(f.a..)) (w.,))
19

---

and
E
sup feFu
Σ
ff (a,,
share the same upper bound, combined lemma
B.1 equations
26 and 16 we get the desired result.
B.6 Proof of Theorem 4.8
perr
rank
K)
(a)t
max jEB(z) f(xr
0
f(xr < 0
P (2xx,,)) y)
B( I (122
max jEB(a)
P(ar,
(27)
P'(x, (1
+ (m,g)) [
(
P(æ,
where define
py(x,y) = min y'E)(
(f(æ,y) J (x.
Let F = [(xx + (a, v) F), By lemma
C,3 with probability at least - 8, for all f E F:
2 log (2/5)
[p v)) - + (ps (a v.)) + 2m F) + B
Since I(u < 0) < 4uu) ) for all u E R, and given the Lipschitz continuity of 4, we can write:
m
log (2/6)
E [1 [) E (py v)) S m
(ps (2t, vi)) 4co Rm + Boy m
(28)
(F) can be upper-bounded follows:
1
(s (202 - max I ( NEB(a;)
Rm
E
sup JEF
i=1
1
E max (f (ax, vi)
E
sup
eif (wts vi)
+ E
sup
m
FEF
JEF i=1
w vEB(xs)
1=1
Now we bound the first term above. Observe that
sup
ei (ati, yi)
= - E
sup
eif (ari,) v) 1 1
fEr
m
fET
jm
wEY
sup
4f (x 8) 1y1=
(29)
m
FEF
yEy
8i
1
E
sup
of (z,, v)
fet
where s; = 22 19.1 - 1. Since e E 1-1, +1}, we have that e and e, admit the same distribution and, for any V. each of the terms of the right-hand side can be bounded as follows:
E
sup fEF
fif (wi, v)
+ 2
km
1
1
(30)
E
sup JEF
E:sif (zi, v)
+
E
sup JEF
f (0t v)
2m
2m
t=1
t=1
< Rim (1I)
20

---

Thus, we can write 1 E we first apply lemma C.5
rer which yields that
fer Ei= of (o,, (2), - NRm (II( To bound the second term,
k (F)),
sup EF
E
max vEB(a,)
f (xi 3)
S Σ
Rm
j=1
where we use By (2:)) denote the j-th elements in ((x;)) and
Rm (Fx)
-
1
E
SU
Σ
es (zi By (2::))
m.
1
E
sup |EF
f,f (as v) (()(()))) - y)
vEy
==1
< NR
(IT)
where the last inequality holds due to equations and 330
Combined equations 27
28 and above equations, we get the desired results.
B.7 Proof of Theorem 4.9
Using the same analysis applied to equation 15
we can derive the following results:
Ex
sup eE
Σ
es (s (c: v))
< BoBaVm.
i=1
Using the same analysis applied to equation
19
we can derive the following results:
m
E.
sup IEF
Σ 4 (f (z,, (x;,, v))
< 20 (Bo + B.)ym.
Using the same analysis applied to equation 26
we can derive the following results:
m Σ
Ee
sup JEFUNEY i=1
e, (f (z; v))
$ 00 1 Wall
(B. BBBo + BoBa) T Ba) vm.
C Auxiliary Lemmas
Lemma C.1. For matrix A and B, vector v. have
ABB S || || olo
where we denoted | ooc as ||||,x, mar((a
Proof of lemma C.1
We have
Br Bulle
|| |A
A
|B
Be/lo0 I
|A]
[B] ||
Lemma C.2 (Theorem 4.15 (iv) in (2)). Let F be classes of real functions. A
R +
R is
Lipschitz with constant I. and satisfies A()) then
R4 S (F).
21

---

Lemma C.3 (Theorem 26.5 in (2I)). If the magnitude of our loss function is bounded above by with probability greater than for all h E 'H, we have
2 Blog(2/0)
B( v)1 e (h (2:) vi) S 2R (eo H, ev
n
where o H (e(h(x),,)) (x, E X x E H3.
Lemma C.4 (Contraction lemma, lemma 26.9 in 12II). For each i E [m], let di R R be namely for all a,
Lipschitz
we have (0i(a) di(3) S ppa - B). For a I let Φ ()) denote the vector (ø1 (a1)..... 2m (mm)). Let &o A (Φ(a) a E A}. Then,
function, Lipschitz,unntion,
Rm S pR
Fi be hypothesis sets, 1 12 1, and let G {max {hi...., hi} h2 E Fiii {.). Then, for any sample S of size m, the empirical Rademacher complexity of 9 can be upper bounded as follows:
Lemma C.5 Lemmma 9.1 in (20)). Let FI....,FI
Rm (9) S Σ Rm (F)).
D Experiments
We conduct experiments on real-world datasets to validate the effectiveness of the proposed method and theoretical insights. All experiments were conducted on Linux server equipped with a 3.00 GHz Intel CPU, 300 GB of main memory, and NVIDIA 20/30 series GPUs.
Table 2: Statistics of Datasets
Dataset
#User
#ltem
#Interaction
Density
Mind
36,281
7.129
5. 610, 960
2.16%
Movie
69,878
10,677
10, 000, 054
1.34%
D.1 Datasets
We evaluate the two-stage models with two real-world recommendation datasets, which can be downloaded from the P The datasets are Moviel 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 more than 15 items. The overall information of datasets is summarized Table
D.2 Settings
In each dataset, we randomly choose 10% users as validation users. 10% users as test users, and we use 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, 2, 2, 2, 10, 10, 20, 20] (sum up to 69; if the length of behavior history less than 69, pad the absence by zero) interactions. For data both validation users and test users, we regard the first half as context and others as ground truth.
all the left users training users. Following 29 28
In the experiment on the effect branch number, reported in Figure I we used a structure similar to the TDM model (29). except that we increased the number of tree branches and replaced the loss used 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 learning rate of 1.0c-3 with exponential decay. For different branch numbers,
22

---

we conduct 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 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 (77 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 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 subset containing only items successfully retrieved by the retriever. We use precision as 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.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
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 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 be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
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 retriever model with high recall rate.
Guidelines:
The answer NA means that the paper has 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 separate "I "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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
24

---

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

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We have provided links to the publicly available data and submitted a ZIP file containing the experimental code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ https/ccpppblligggddeeeeeeeeeeee Cotee//ddeeeebmmmcia ssi onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide detailed experimental settings in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
We reported the best results within the adjustable parameter range for each
method.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provided a description of the platform and hardware used for the experi- ments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https///hh/////oorr..../////////
Answer: [Yes]
Justification:
We adhere to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper presents work whose goal is to advance the field Machine Learning. There many potential societal consequences of 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 why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess 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 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 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
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?
Question:
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 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 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.
28

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.papersstt
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 not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not 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 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 used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing 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 contribu- tion of the paper involves human subjects, then much detail as possible should be included 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.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based 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 crowdsoureing nor research with human subjects.
29

---

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.
30


Reviews:
[{"review_id": "WMPIK1PPAB", "reviewer": "Reviewer_pcvU", "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.", "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?\n\nWhile 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": "NA", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The paper provides a comprehensive theoretical analysis of the generalization error bounds for two-stage recommender systems with a tree structure. This is an important contribution, as previous theoretical research in this area has been limited.\n\nThe paper analyzes the generalization upper bounds for various tree-based retriever models using beam search, including linear models, multilayer perceptrons, and target attention models. This provides valuable insights into the learnability and generalization capabilities of these widely used retriever models.\n\nThe paper analyzes the generalization upper bounds for ranker models under shifted training distributions. This is an important consideration, as the data distribution during inference can often differ from the training distribution in real-world recommender systems. The theoretical and empirical findings on harmonizing distributions across stages are valuable insights.\n\nThe theoretical insights and guidelines derived in this paper can inform the design and development of more robust and generalizable two-stage recommender systems, with significant implications for a wide range of industries and applications. The analytical techniques and the established error decomposition framework can serve as a foundation for future research in this domain.", "weaknesses": "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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition of our work and the opportunity to address the concerns raised in your review. We value your insightful feedback and would like to share our thoughts in response.\n\n**Response to Questions 1:**\n\n\n> **Questions 1:** 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?\n\nThanks for your question. We fully agree that exploring retriever architectures beyond tree-based models could provide a more comprehensive understanding of two-stage recommender systems. This is a promising and broad area of research. In this work, we chose to begin with an analysis of the generalization bounds for tree-based retriever models, which are commonly used in current two-stage models, with the hope of contributing to research in this broader area. We will continue to work in this direction to advance and refine research in this area in the future.\n\n**Response to Questions 2:**\n\n\n> **Questions 2:** 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?\n\nThanks again for your question. We also share the same view that efficiency and scalability are key considerations in practical recommender systems.\n\nIn terms of efficiency, specifically computational complexity and inference latency, which are critical concerns in practical recommender systems, our work points to the impact of the number of branches on the performance of tree-based models. While the generalization-related conclusions may not directly correlate with efficiency, we highlight that increasing the number of branches in the tree can improve model performance, but also increases the computational complexity and inference latency of the retriever. 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. At this point, the retriever model essentially degenerates into a ranker model, which is more precise yet more time-consuming. The number of branches can thus be viewed as a tradeoff between performance and efficiency.\n\nIn terms of scalability, the two improvement strategies derived from our theoretical analysis, increasing the number of tree branches and adjusting the training distribution of the ranker, are feasible in practice across different models. Although the conclusions may vary depending on the specific network architecture, these strategies can still provide valuable guidance for model design.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "14WEsAkJne", "reviewer": "Reviewer_1EMB", "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.", "questions": "See weaknessnes.", "limitations": "NA.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper has a clear motivation, aiming to analyze the generalization bounds of two-stage tree-structured recommender systems. The writing is clear and understandable.\n2. Two-stage recommender systems are indeed one of the mainstream structures in the current field of recommender systems, especially in industry. However, there has been a lack of theoretical guarantees and guidance for such systems. This paper effectively highlights the issues related to the number of branches in tree structures and the training data for rankers, which is innovative and high-quality.\n3. The paper theoretically studies the relationship between the generalization of tree-structured Retrievers and the number of branches, as well as the relationship between the generalization of rankers and the difference between their training data distribution and the Retriever's predicted distribution. These conclusions are reasonable and align with empirical knowledge.\n4. The experimental results nicely validate the theoretical findings, making the paper cohesive and solid.", "weaknesses": "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.\n2. 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?\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition of our work and providing the constructive comments. We will try our best to address your concerns with planned revisions based on your valuable feedback.\n\n**Response to Weakness 1:**\n\nThank you for your detailed feedback. Our analysis of tree-structured models indeed draws inspiration from previous work, particularly in the context of hierarchical multi-class classification[1]. Our contribution, in addition to the main difference of extending the analysis to the Beam Search algorithm, also provides a more refined estimate specifically tailored to the tree model. Specifically, we use the mapping $c(f, \\boldsymbol{x}, y)=\\left(\\boldsymbol{v}, \\boldsymbol{v}^{\\prime}\\right)$, which establishes a correspondence between a sample point $(x,y)$ and both the target node and the Top-K scoring nodes along the search path within the tree. This mapping allows us to partition the $m$ sample points into several disjoint sets $ \\lbrace (x_i,y_i): c\\left(f, \\boldsymbol{x}_i, y_i\\right)=\\left(\\boldsymbol{v}, \\boldsymbol{v}^{\\prime}\\right) \\rbrace $, each corresponding to different node pairs in the tree. Unlike prior work[1],  the proof of Theorem 1 in [1], where a trivial upper bound of $m$ is used for the size of these sets, we provide individual estimates for each set’s size. By combining these estimates, we derive a tighter overall result, leading to a key conclusion that increasing the number of branches helps to reduce the generalization error—an insight not directly captured in [1].\n\nRegarding Rademacher complexity, our model introduces an additional tree structure, distinguishing it from traditional linear models and MLPs. Our analytical approach involves separating the traditional scoring model from the tree structure component, corresponding to the term $\\mathcal{T}$ in the upper bound of the Rademacher complexity in our analysis. This reduction maps the problem to the scoring function space of traditional models, making existing analysis techniques applicable. We appreciate your comments regarding our references, and we will ensure that these works are properly cited in future revisions.\n\n[1] Rohit Babbar et al. Learning taxonomy adaptation in large-scale classification. JMLR, 17(1):3350–3386, 2016.\n\n**Response to Weakness 2:**\n\nThank you for your observation. We will include experimental results in the revised manuscript to demonstrate the ranker model's performance at different recall rates.\n\nIn our experiments, we varied the number of items retrieved by the model to adjust the recall rate. With $ K=40 $ fixed during inference, from Tables 1 and 2, it can be observed that the ranker model's performance significantly declined when the recall rate was as low as 7.5\\% due to insufficient training data. However, when the recall rate exceeded 10.7\\%, the model consistently showed improvement.\n\nThe improvement in the ranker model's performance depends on sufficient training data and alignment with the target distribution.  It can be observed that once the recall rate reaches a sufficient threshold, further increases in the recall rate actually cause the performance of the trained ranker model in the two-stage classification process to gradually decline, approaching the performance of the ranker model trained on the original distribution, i.e., the complete dataset. This decline occurs because the training data distribution starts to deviate from the target distribution. The most optimal setting may be to keep the number of retrieved items consistent between training and inference, provided the recall rate is relatively high in this scenario.\nExperimental results show that limited data initially hinders performance, but as data and alignment improve, performance increases. However, excessive data leads to misalignment and a subsequent performance decline, consistent with theoretical predictions. For a quantitative result in theory, if we use a sampling method to estimate the error between distributions, defined as \n$err_{\\mathcal{D}} := \\mathbb{E} _{ (\\boldsymbol{x}, y) \\sim \\mathcal{D}}|1-\\frac{P'(\\boldsymbol{x}, y)}{P(\\boldsymbol{x}, y)} | $, we have\n\n$$\nerr_{\\mathcal{D}} \\approx \\frac{1}{m}\\sum_{i=1}^m \\mathbb{I}[y_i \\notin \\mathcal{B}(x_i)] + \\left(\\frac{1}{m^\\prime} - \\frac{1}{m}\\right) \\sum_{i=1}^m \\mathbb{I}[y_i \\in \\mathcal{B}(x_i)] ,\n$$\nand if we aim to achieve an $ \\epsilon $ error between the generalization error and the empirical error with probability $1-\\delta $, the estimated number of training samples required can be expressed as:\n\n$$\nm \\geq \\left(\\frac{4 c_{\\Phi} N(K+1) B_{\\text{model}} + B_{\\Phi} \\sqrt{2 \\log (2 / \\delta)}}{\\epsilon - {err}_{\\mathcal{D}}}\\right)^2.\n$$\nBy further comparing this estimate with the total number of samples, we can estimate the required recall rate. It is worth noting such an estimate is typically conservative, and we still recommend using the results from the experiments.\n\n**Table 1: Model Performance on the Mind Dataset**\n\n| Recall | Accuracy | Improvement (Above 0.6500) |\n| ----------- | -------- | ----------------------------------- |\n| 16.1%       | 0.6717   | Yes                                 |\n| 25.0%       | 0.6844   | Yes                                 |\n| 36.2%       | 0.6685   | Yes                                 |\n| 49.1%       | 0.6550   | Yes                                 |\n\n**Table 2: Model Performance on the Movie Dataset**\n\n| Recall | Accuracy | Improvement (Above 0.3516) |\n| ----------- | -------- | ----------------------------------- |\n| 7.5%        | 0.2581   | No                                  |\n| 10.7%       | 0.3548   | Yes                                 |\n| 17.4%       | 0.3562   | Yes                                 |\n| 24.6%       | 0.3547   | Yes                                 |\n\n\n**Response to Weakness 3:**\n\nThank you for identifying the typos. We will correct these issues and ensure consistency in formatting throughout the manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o8DJXGgUa9", "reviewer": "Reviewer_homr", "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", "questions": "None", "limitations": "Although limitations are mentioned in theoretical result discussion, the authors are encouraged to create a separate \"Limitations\" section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses a common structure used in recommender systems, i.e., the two-stage model. It is also used in other machine learning tasks, demonstrating broader impact.\n2. The analysis of generalization errors in two-stage models fills a gap in the existing literature, which has predominantly focused on efficiency-related issues such as convergence rates. This paper enhances the understanding of this model.\n3. The authors investigate the impact of different scoring models on the tree retriever model. They demonstrate that different model structures result in varying levels of generalization errors. This experimental validation inspired by the theoretical analysis further supports the findings.", "weaknesses": "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.\n2. Please provide more detailed explanations of \"Harmonized distribution\" and \"Harmonized model\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your recognition of our work and providing the valuable suggestions and constructive comments.\n\n**Response to Weakness 1:**\n\n> **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.\n\nThanks for your suggestion. Due to space limitations, we initially decided to organize the paper as it is. In future revisions, we will consider creating a separate \"Experiments\" section to better organize the content. Additionally, we will include a list of notations to enhance readability and understanding of the paper.\n\n**Response to Weakness 2:**\n\n> **Weakness 2:** Please provide more detailed explanations of \"Harmonized distribution\" and \"Harmonized model\".\n\nThanks for your comment. In our work, the \"Harmonized distribution\" arises within the context of the ranker model. During model inference, the ranker model deals with a distribution of data that has been filtered by the retriever. We name the distribution of successfully retrieved data the \"Harmonized distribution,\" denoted as $\\mathcal{D^\\prime}$ in the paper. This distribution is harmonized with the retriever model, and its importance lies in the fact that the accuracy of the ranker in this stage is directly influenced by this data distribution.\n\nThe term \"Harmonized model\" in our work refers to a two-stage model where the ranker model is trained on the Harmonized distribution. Unlike typical two-stage models that are trained independently, the Harmonized model eliminates the additional bias caused by different target data distributions, leading to better overall performance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ggEhZCz32j", "reviewer": "Reviewer_g6F7", "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.", "questions": "Can the authors comment on the potential limitations of the derived generalization upper bounds?", "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.", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper studies a timely topic. The two-stage recommender systems are widely adopted in industry and achieve remarkable empirical performance in balancing the computational efficiency and recommendation accuracy yet lack theoretical understanding on why it works so well. It fills in this gap and provides a nice attempt for this topic.    \n\nThe derived generalization upper bounds are meaningful, revealing valuable insights. The derived generalization upper bounds indicate that optimizing the design choice of two-stage recommender systems. For example, increasing the branches in tree-based retrievers and harmonizing distributions across stages can enhance the generalization performance of two-stage recommender systems.   \n\nTheoretical findings are aligned with empirical experiments on real-world datasets. This further demonstrates that the generalization upper bounds are useful and powerful.  \n\nThe generalization upper bounds are technically nontrivial and the proof idea looks general and systematic. They nicely characterize the impact of various design choices of two-stage recommender systems on the generalization performance. They have a high potential to inspire the generalization analysis of other variants of two-stage recommender systems.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your high recognition of our work, and are eager to share our thoughts with you.\n\n**Response to Questions 1:**\n\n> **Questions 1:** Can the authors comment on the potential limitations of the derived generalization upper bounds?\n\nThank you for your question. While the derived generalization bounds offer valuable insights, they come with some limitations. The tradeoff between model complexity and computational efficiency is a key consideration, as more complex models can lead to higher computational costs despite improved generalization. In addition, aligning the training distribution with the inference distribution reduces distributional bias, but also reduces the number of training samples, which may weaken the generalization guarantee. Thus, in practical applications, there is a need for careful management of these tradeoffs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (oral)