This paper studies ML systems that interactively learn from users across
multiple subpopulations with heterogeneous data distributions. The primary
objective is to provide specialized services for different user groups while
also predicting user preferences. Once the users select a service based on how
well the service anticipated their preference, the services subsequently adapt
and refine themselves based on the user data they accumulate, resulting in an
iterative, alternating minimization process between users and services
(learning dynamics). Employing such tailored approaches has two main
challenges: (i) Unknown user preferences: Typically, data on user preferences
are unavailable without interaction, and uniform data collection across a large
and diverse user base can be prohibitively expensive. (ii) Suboptimal Local
Solutions: The total loss (sum of loss functions across all users and all
services) landscape is not convex even if the individual losses on a single
service are convex, making it likely for the learning dynamics to get stuck in
local minima. The final outcome of the aforementioned learning dynamics is thus
strongly influenced by the initial set of services offered to users, and is not
guaranteed to be close to the globally optimal outcome. In this work, we
propose a randomized algorithm to adaptively select very few users to collect
preference data from, while simultaneously initializing a set of services. We
prove that under mild assumptions on the loss functions, the expected total
loss achieved by the algorithm right after initialization is within a factor of
the globally optimal total loss with complete user preference data, and this
factor scales only logarithmically in the number of services. Our theory is
complemented by experiments on real as well as semi-synthetic datasets.

该研究旨在研究与用户交互学习的机器学习系统，以提供不同用户群体的专门化服务，并预测用户偏好；通过采用针对性的方法，克服了未知用户偏好和次优本地解决方案的挑战。