Machine Learning from Human Comparative Judgments
summary
Shows that using UCB with LIL confidence bounds yields a fixed‑confidence best‑item algorithm whose sample cost is roughly sum_i Δ_i^{-2}·log log(Δ_i^{-2}) (no extra factor of n), far better than non‑adaptive n·Δ^{-2}·log(n/δ). Reduces pairwise comparisons to scores via the Borda reduction, then adds a sparse Borda algorithm that exploits sparse informative duels to cut worst‑case n^2 sample cost down to order n in simulations. Implements and simulates the algorithms and reports practical constants.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 0:32Application
- 2:11Notation
- 4:41Empirical Means
- 6:37Nonadaptive
- 9:04Adaptive
- 16:06Upper Confidence Bound
- 17:36Analysis
- 19:55Simulation
- 21:35Comparative judgments
- 25:48Examples
- 30:44Adaptive to Sparsity
related talks
46mEliciting and Enforcing Subjective Individual Fairness
43mMetric Learning for Individual Fairness
44mParsimonious Learning-Augmented Algorithms
42mRethinking AI Alignment and Evaluation under Heterogeneous Preferences
23mComparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
01h 14mMachine Learning For Algorithm Design
40mApproximation Algorithms for Optimization under Uncertainty
53mGroups and Individuals in Fairness and Probability