Initializing Services in Interactive ML Systems for Diverse Users
Avinandan Bose Mihaela Curmei Daniel L. Jiang Jamie Morgenstern Sarah Dean Lillian J. Ratliff Maryam Fazel
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.