# Initializing Services in Interactive ML Systems for Diverse Users

arXiv: https://arxiv.org/abs/2312.11846 · HTML: https://mlsanity.com/paper/2312.11846/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 19 Dec 2023.

## Builds on (most cited first, 18 of 18)

- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [An Efficient Framework for Clustered Federated Learning](https://mlsanity.com/paper/2006.04088/) (2020)
- [Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraints](https://mlsanity.com/paper/1910.01991/) (2019)
- [Retiring Adult: New Datasets for Fair Machine Learning](https://mlsanity.com/paper/2108.04884/) (2021)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Three Approaches for Personalization with Applications to Federated Learning](https://mlsanity.com/paper/2002.10619/) (2020)
- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Eigenvalue and Generalized Eigenvalue Problems: Tutorial](https://mlsanity.com/paper/1903.11240/) (2019)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [How Fine-Tuning Allows for Effective Meta-Learning](https://mlsanity.com/paper/2105.02221/) (2021)
- [Group Retention when Using Machine Learning in Sequential Decision Making: the Interplay between User Dynamics and Fairness](https://mlsanity.com/paper/1905.00569/) (2019)
- [Towards Sample-efficient Overparameterized Meta-learning](https://mlsanity.com/paper/2201.06142/) (2022)
- [Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction](https://mlsanity.com/paper/1606.05374/) (2016)
- [Improved Guarantees for k-means++ and k-means++ Parallel](https://mlsanity.com/paper/2010.14487/) (2020)
- [One for All: Simultaneous Metric and Preference Learning over Multiple Users](https://mlsanity.com/paper/2207.03609/) (2022)
- [Learning User Preferences to Incentivize Exploration in the Sharing Economy](https://mlsanity.com/paper/1711.08331/) (2017)
- [Scalable Distributional Robustness in a Class of Non Convex Optimization with Guarantees](https://mlsanity.com/paper/2205.15624/) (2022)
- [Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback](https://mlsanity.com/paper/2207.03091/) (2022)

## Built on by (most cited first, 5 of 5)

- [Personalizing Reinforcement Learning from Human Feedback with Variational Preference Learning](https://mlsanity.com/paper/2408.10075/) (2024)
- [LoRe: Personalizing LLMs via Low-Rank Reward Modeling](https://mlsanity.com/paper/2504.14439/) (2025)
- [Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning](https://mlsanity.com/paper/2406.06856/) (2024)
- [Cold-Start Personalization via Training-Free Priors from Structured World Models](https://mlsanity.com/paper/2602.15012/) (2026)
- [Policy Design for Two-sided Platforms with Participation Dynamics](https://mlsanity.com/paper/2502.01792/) (2025)

## Abstract (arXiv)

This paper investigates ML systems serving a group of users, with multiple models/services, each aimed at specializing to a sub-group of users. We consider settings where upon deploying a set of services, users choose the one minimizing their personal losses and the learner iteratively learns by interacting with diverse users. Prior research shows that the outcomes of learning dynamics, which comprise both the services' adjustments and users' service selections, hinge significantly on the initialization. However, finding good initializations faces two main challenges: (i) Bandit feedback: Typically, data on user preferences are not available before deploying services and observing user behavior; (ii) Suboptimal local solutions: The total loss landscape (i.e., the sum of loss functions across all users and services) is not convex and gradient-based algorithms can get stuck in poor local minima. We address these challenges with a randomized algorithm to adaptively select a minimal set of users for data collection in order to initialize a set of services. Under mild assumptions on the loss functions, we prove that our initialization leads to a total loss within a factor of the globally optimal total loss with complete user preference data, and this factor scales logarithmically in the number of services. This result is a generalization of the well-known k-means++ guarantee to a broad problem class, which is also of independent interest. The theory is complemented by experiments on real as well as semi-synthetic datasets.