Research map / Learning theory and algorithms / Kernels and regression theory
Generalization Error Bounds for Two-stage Recommender Systems with Tree Structure
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives Rademacher-complexity generalization bounds for tree-based retrievers with beam search and for rankers trained under shifted (harmonized) distributions in two-stage recommender systems, with experiments on Mind and Movie.
Problem
Theoretical understanding of generalization error in two-stage recommender systems with tree-structured retrievers (beam search) and rankers, where training and inference distributions differ across stages.
Approach
Decomposes two-stage classification error into retrieval and ranking errors, extends the hierarchical-classification Rademacher bound to top-K beam-search function classes, and bounds ranker generalization under a distribution shift between filtered training data and the original data, showing that more tree branches and harmonized training distributions help.
Key results
- Recall@20 on Mind and Movie increases with the number of tree branches (2 to 32) in the TDM-style retriever.
- Harmonized two-stage model (H-TS) improves Precision@1 over TS on Mind (e.g., 0.6565 vs 0.6500 at K=40) and Movie (0.3555 vs 0.3516 at K=40).
- Theory gives a retriever bound term O(B/sqrt(B^2-1)) and an O(m^{-1/2}) rate, with ranker bounds including a distribution-discrepancy term.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train the ranker on successfully retrieved training examples instead of the original training data | Two-stage recommender with Improved TDM and DIN · Mind, K=40 | Precision@1: 0.6500 -> 0.6565 | Helped |
| Train the ranker on successfully retrieved training examples instead of the original training data | Two-stage recommender with Improved TDM and DIN · Mind, K=80 | Precision@1: 0.5970 -> 0.6026 | Helped |
| Train the ranker on successfully retrieved training examples instead of the original training data | Two-stage recommender with Improved TDM and DIN · Mind, K=120 | Precision@1: 0.5609 -> 0.5644 | Helped |
| Train the ranker on successfully retrieved training examples instead of the original training data | Two-stage recommender with Improved TDM and DIN · Movie, K=40 | Precision@1: 0.3516 -> 0.3555 | Helped |
| Train the ranker on successfully retrieved training examples instead of the original training data | Two-stage recommender with Improved TDM and DIN · Movie, K=80 | Precision@1: 0.3457 -> 0.3500 | Helped |
| Train the ranker on successfully retrieved training examples instead of the original training data | Two-stage recommender with Improved TDM and DIN · Movie, K=120 | Precision@1: 0.3453 -> 0.3488 | Helped |
| Increase the number of tree branches | Improved TDM tree retriever · Mind | Recall@20 | Helped |
| Increase the number of tree branches | Improved TDM tree retriever · Movie | Recall@20 | Helped |
Surprising findings
- Aligning ranker training data to the retriever's output only helps when retriever recall is high (more than about 10% recall reported), since fewer training samples are available.
Limitations
- Harmonized training only helps when the retriever has high recall; reduces training sample count m'.
- Experiments are limited to two datasets and a single retriever/ranker configuration.
- Bounds are for classification-style error and depend on norm-bounded function classes.
Experimental setup
Datasets: Mind MovieLens 10M (Movie)
Benchmarks: Mind Movie
Metrics: Recall@20 Precision@1
Baselines: TS (original training data ranker)
Builds on: TDM JTM DeFoRec DIN Rademacher complexity generalization bounds for hierarchical classification
Closest papers by meaning
- On Component Interactions in Two-Stage Recommender Systems (NeurIPS 2021 · similarity 0.88)
- Generalization Bounds for Semi-supervised Matrix Completion with Distributional Side Information (AAAI 2026 · similarity 0.85)
- Learning-Efficient Yet Generalizable Collaborative Filtering for Item Recommendation (ICML 2024 · similarity 0.83)
- Echoes in Filter Bubble: Diagnosing and Curing Popularity Bias in Generative Recommender Systems (NeurIPS 2026 · similarity 0.83)
- Tree of Preferences for Diversified Recommendation (NeurIPS 2025 · similarity 0.82)
- Building Higher-Order Abstractions from the Components of Recommender Systems (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.