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

We greatly appreciate your high recognition of our work, and are eager to share our thoughts with you.

Response to Questions 1:

Questions 1: Can the authors comment on the potential limitations of the derived generalization upper bounds?

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

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.

Response to Weakness 1:

Thank 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].

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

[1] Rohit Babbar et al. Learning taxonomy adaptation in large-scale classification. JMLR, 17(1):3350–3386, 2016.

Response to Weakness 2:

Thank you for your observation. We will include experimental results in the revised manuscript to demonstrate the ranker model's performance at different recall rates.

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

The 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. Experimental 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 $err_{\mathcal{D}} := \mathbb{E} _{ (\boldsymbol{x}, y) \sim \mathcal{D}}|1-\frac{P'(\boldsymbol{x}, y)}{P(\boldsymbol{x}, y)} |$, we have

$$err_{\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)] ,$$

and 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:

$$m \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.$$

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

Table 1: Model Performance on the Mind Dataset

Table 2: Model Performance on the Movie Dataset

Response to Weakness 3:

Thank you for identifying the typos. We will correct these issues and ensure consistency in formatting throughout the manuscript.

Thank you for your recognition of our work and providing the valuable suggestions and constructive comments.

Response to Weakness 1:

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.

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

Response to Weakness 2:

Weakness 2: Please provide more detailed explanations of "Harmonized distribution" and "Harmonized model".

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

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

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.

Response to Questions 1:

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?

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

Response to Questions 2:

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?

Thanks again for your question. We also share the same view that efficiency and scalability are key considerations in practical recommender systems.

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

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