Research map / Learning theory and algorithms / Sample complexity
Sampling for Beyond-Worst-Case Online Ranking
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.
Studies online feedback arc set (ranking in tournaments) in a beyond-worst-case model where a sample of nodes is given offline, showing constant-competitive pivot-based algorithms under uniform samples and a sample-correction scheme for non-uniform samples.
Problem
Online feedback arc set in tournaments has an Omega(n) competitive-ratio lower bound in the worst case; the paper asks whether a sample of past data given offline can bypass this bound.
Approach
Adapts the Pivot (Kwiksort) algorithm into an online binary-tree insertion scheme that, given a uniform sample (semi-online model), achieves O(1/λ) competitiveness; for non-uniform samples, an over/under-sampling procedure adds extra sampled nodes whose total variation distance from uniform bounds the extra cost.
Key results
- Theoretical: O(n) competitive ratio for fully online FAS with matching Omega(n) lower bound; with uniform sample of λn nodes, O(1/λ) competitive ratio with matching Ω(1/λ) lower bound.
- Extra sampling model: with arbitrary sampling distribution Q, the algorithm samples at most δ(Q,U) extra vertices in expectation and achieves O(1/(cλ)) competitive ratio with probability at least 1 − e^{-(1-c)^2/2}.
- Experiments on RedditHyperlink: without samples the ratio to offline Pivot exceeds two hundred; with a 0.1% uniform sample it drops to single digits.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a 0.1% uniform sample | Online pivot · RedditHyperlink | objective ratio to offline pivot: more than two hundred -> single digits | Helped |
| add extra samples to the predefined sample | Extra-sampling algorithm · CollegeMsg | objective ratio to offline pivot | Helped |
| discard vertices from the predefined sample according to the algorithm (ablation) | Extra-sampling algorithm · CollegeMsg | objective ratio to offline pivot | Helped |
Surprising findings
- Pure online FAS admits no constant competitive ratio: any randomized algorithm is Ω(n)-competitive in the worst case.
Limitations
- Non-uniform samples require extra sampled vertices whose number scales with the total variation distance from uniform.
- Several proofs are deferred to the full version, so theoretical claims are not fully verified in this text.
- Experiments use only social temporal network datasets, with adversarial orders approximated by heuristics.
Experimental setup
Datasets: CollegeMsg MathOverflow RedditHyperlink
Benchmarks: CollegeMsg MathOverflow RedditHyperlink
Metrics: ratio of algorithm objective (backward edges) to offline Piv
Baselines: offline Pivot algorithm
Builds on: Pivot (Kwiksort) semi-online model of Lattanzi et al. 2021 correlation clustering analysis of Mathieu, Sankur, and Schudy 2010
Closest papers by meaning
- Sample Complexity Bounds for Active Ranking from Multi-wise Comparisons (NeurIPS 2021 · similarity 0.87)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.85)
- Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.85)
- Adaptive Hardness Negative Sampling for Collaborative Filtering (AAAI 2024 · similarity 0.84)
- Online bipartite matching with imperfect advice (ICML 2024 · similarity 0.84)
- Adaptively Learning to Select-Rank in Online Platforms (ICML 2024 · similarity 0.84)
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.