Research map / Learning theory and algorithms / Prediction and decision losses
Initializing Services in Interactive ML Systems for Diverse Users
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.
Proposes AcQUIre, a randomized k-means++-style algorithm that adaptively queries a small set of users to initialize multiple services under bandit feedback, with a logarithmic-in-services approximation guarantee.
Problem
Initializing k services for n users with diverse preferences in interactive ML systems, where preference data is unavailable before deployment (bandit feedback) and the total loss landscape is nonconvex with poor local minima.
Approach
Generalizes k-means++ seeding to general loss families satisfying approximate triangle inequalities: sample new services from users with probability proportional to their current loss under existing services, querying only k users' preferences, yielding an instance-dependent (2+log k) approximation to the global optimum with full information.
Key results
- AcQUIre and Fair AcQUIre are consistently the two best baselines on the Census task across user selection strategies, averaged over 500 seeds.
- Theory: expected total loss after initialization is at most K_OPT(2+log k) times the globally optimal loss with complete user preference data.
- Runtime: AcQUIre handles 1 billion users in about 300 seconds, while greedy and epsilon-greedy take over 10^5 seconds even for 10 million users.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| select users with probability proportional to their current loss rather than using the other tested selection strategies | AcQUIre · Census travel-time prediction and MovieLens10M recommendation | average loss / average excess error | Helped |
| select users with probability proportional to their current loss rather than using the other tested selection strategies | AcQUIre · MovieLens10M recommendation | average excess error | Helped |
| use greedy selection instead of AcQUIre | Census travel-time prediction · Census data, k < 10 | average loss | Mixed |
| use random sampling instead of greedy or epsilon-greedy selection | Census travel-time prediction · Census data, larger k | average loss | Helped |
| use greedy selection instead of AcQUIre | MovieLens10M recommendation · MovieLens10M | average excess error | Mixed |
| use epsilon-greedy selection instead of greedy selection | MovieLens10M recommendation · MovieLens10M | average excess error | Helped |
| initialize services with AcQUIre rather than another tested initialization strategy | Generalized k-means and multiplicative weights update · Census data and MovieLens10M | final total loss | Helped |
| initialize services with AcQUIre rather than another tested initialization strategy | Generalized k-means and multiplicative weights update · Census data and MovieLens10M | convergence speed | Helped |
| use AcQUIre rather than greedy or epsilon-greedy initialization | Census data runtime · Census data | runtime: 300 sec vs >10^5 sec | Helped |
Surprising findings
- Greedy and epsilon-greedy selection perform well for small k but become myopic as k grows, where random sampling outperforms them.
Limitations
- Analysis assumes noiseless losses; robustness to noise, perturbations, or outliers is not established for finite-sample case.
- Finite-sample guarantee for linear predictors requires heavy-tailed-free sub-Gaussian features and n_i >= d per subpopulation.
- Movie recommendation experiment is semi-synthetic.
Experimental setup
Datasets: 2021 US Census (folktables) MovieLens10M
Benchmarks: 2021 US Census commute time prediction (folktables) MovieLens10M semi-synthetic movie recommendation
Metrics: average loss worst-demographic average loss average excess error runtime
Baselines: Random Greedy Epsilon Greedy Balanced Random Balanced Greedy Balanced Epsilon Greedy
Builds on: k-means++ Lloyd's algorithm generalized k-means multiplicative weights update
Closest papers by meaning
- Learning from Streaming Data when Users Choose (ICML 2024 · similarity 0.86)
- HYDRA: Model Factorization Framework for Black-Box LLM Personalization (NeurIPS 2024 · similarity 0.83)
- MultiScale Contextual Bandits for Long Term Objectives (NeurIPS 2025 · similarity 0.83)
- Self-Consuming Generative Models with Co-Evolving Human Preferences (NeurIPS 2026 · similarity 0.82)
- Adaptively Learning to Select-Rank in Online Platforms (ICML 2024 · similarity 0.82)
- Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF (ICLR 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.