# Initializing Services in Interactive ML Systems for Diverse Users

Avinandan Bose
University of Washington
<EMAIL_ADDRESS>Mihaela Curmei
University of California Berkeley
<EMAIL_ADDRESS>Daniel L. Jiang
University of Washington
<EMAIL_ADDRESS>Jamie Morgenstern
University of Washington
<EMAIL_ADDRESS>Sarah Dean
Cornell University
<EMAIL_ADDRESS>Lillian J. Ratliff
University of Washington
<EMAIL_ADDRESS>Maryam Fazel
University of Washington
<EMAIL_ADDRESS>
###### Abstract

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.

##  1 Introduction

In various applications including federated learning (Li et al., 2020), crowd-
sourcing (Steinhardt et al., 2016), online recommendation systems (Song et
al., 2014), data about user preferences is acquired through interactions with
multiple users or sources. The primary objective is to leverage this data to
deliver services that cater to the diverse requirements of users. Typically,
these users exhibit heterogeneity in their preferences, and recent approaches
demonstrate the benefits of deploying and updating multiple, more specialized
models versus using one large shared model as a one-size fits all approach;
e.g., for clustered federated learning Mansour et al. (2020); Sattler et al.
(2020); Ghosh et al. (2020) (Dwork et al., 2018), in the context of fair
classifiers (Ustun et al., 2019), and for meta learning (Kong et al., 2020).
And even when a single large model is used, it is often followed by a fine-
tuning step for specialization to a group of users or tasks by retraining part
of the model (Chua et al., 2021; Sun et al., 2021).

In this paper we consider ML systems that interactively learn from users
across multiple subpopulations with heterogeneous data distributions. The aim
is to provide a range of services, each service specialized for a group of
users. These services typically work by trying to predict user preferences,
and the likelihood of any user picking a service from the available candidates
depends on the services’ performance for them. For example,
Meta111https://nickclegg.medium.com/you-and-the-algorithm-it-takes-two-to-
tango-7722b19aa1c2 uses ML to predict user preferences and make personalized
recommendations for its services like Facebook, Instagram, etc. Users decide
whether to join recommended pages, leave likes or other forms of engagement
such as scrolling activity, hours online indicating their level of
satisfaction with the services. Meta would in turn plan which users each of
its platforms is tailored to, and what personalized content is recommended to
users—these decisions by Meta could altogether be modeled as choosing the
parameters of its services.

These services are usually trained through interaction with users. Once a set
of services is launched users select the service that best predicts their
preferences (generally choosing the service that minimizes the particular
user’s performance metric). These services are then subsequently refined based
on data of current users. This sequence of (alternating) decisions by users
and by services (learning dynamics) continues as more data is gathered.
Broadly speaking, such a learning system could include a set of independent
learners (e.g., different service providers) having an incentive to coordinate
for the purpose of initializing their services, or a single learner with
several deployed models (e.g., a company that owns different platforms, or a
multi-model server in certain federated learning setups). This setup has been
studied by Ginart et al. (2021), who discuss the effect of competition between
services on user welfare, and Dean et al. (2022), who discuss the the
stability of equilibria of learning dynamics in such systems.

Our goal is to design a set of services to minimize the total loss, i.e., the
sum of all losses across users. However, we face the following challenges:

  * •

Unknown User Preferences: In practice, the presence of a service often
precedes data collection. Specifically, in contexts like online
recommendations, it is usually not feasible to gather user preference data
without first deploying the service and observing user interactions. This
means that data collection is inherently conditional on the existence of a
service, challenging the conventional “data-first, model-second” paradigm.

  * •

Suboptimal Local Solutions: The total loss (sum of losses across all users and
all services) landscape in these applications is non-convex (jointly in both
sets of variables for users and services) even if the individual user losses
on a single service are convex, making it likely for the learning dynamics to
get stuck in local minima where the total loss can be significantly worse than
the globally minimum loss. Thus, the outcomes of learning dynamics are heavily
affected by initialization.

#### Contributions.

The following summarizes the contributions of this paper.

  * •

In this work, we address these challenges by designing a computationally and
statistically efficient algorithm for initialization of services prior to
learning dynamics. The algorithm works by adaptively selecting very few users
to collect data from (via zeroth order or bandit access to their loss
functions) in order to initialize the set of services.

  * •

We establish an _approximation ratio_ for our algorithm: the expected total
loss achieved by the algorithm right after initialization is within a factor
of the globally optimal total loss in the presence of complete user preference
data, and this factor scales only logarithmically in the number of services
(cf. Section 3).

  * •

When users belong to a set of unknown demographic groups, it is desirable that
the provided services do not result in unfavorable outcomes towards certain
demographics (say based on gender or racial groups). A fair objective would be
to minimize the maximum average loss of users across different groups. We
provide an approximation ratio for our algorithm on the fair objective as
well, that scales only logarithmically in the number of services (cf. Section
3).

  * •

In the context of linear prediction models, we study generalization properties
of the initialized services to users the services have never interacted with
before (cf. Section 4).

  * •

We empirically demonstrate the strengths of our initialization scheme through
experiments on a prediction task based on 2021 US Census data, and online
movie recommendation task based on Movielens10M dataset (cf. Section 5).

#### Notation and Terminology.

For a symmetric matrix $\mathbf{A}$ and any vector $x\in\mathbb{R}^{d}$, we
denote its Mahalanobis norm by
$\|x\|_{\mathbf{A}}=\sqrt{x^{\top}\mathbf{A}x}$. The generalized eigenvalues
for a pair of symmetric matrices $\mathbf{A}$ and $\mathbf{B}$ are denoted by
$\lambda(\mathbf{A},\mathbf{B})$, defined as the solutions of $\lambda$ for
the generalized eigenvalue problems $\mathbf{A}v=\lambda\mathbf{B}v$ (Ghojogh
et al., 2019; Förstner and Moonen, 2003). Specifically we use
$\lambda_{\min}(\mathbf{A},\mathbf{B})$ to denote minimum generalized
eigenvalue for the matrix pair $\mathbf{A},\mathbf{B}$.

The loss for a user $i$ given service $\theta\in\mathbb{R}^{d}$ is denoted by
$\mathcal{L}_{i}(\theta,\phi_{i})$ where $\phi_{i}$ parameterizes the user’s
preference. For a set of users $\mathcal{A}$ (e.g., $\mathcal{A}=[n]$ denotes
a set of $n$ users) and a set of services
$\Theta=\\{\theta_{1},\ldots,\theta_{k}\\}\subset\mathbb{R}^{d}$, the total
loss is defined as
$\mathcal{L}(\Theta,\mathcal{A})=\sum_{i\in\mathcal{A}}\min_{j\in[k]}\mathcal{L}_{i}(\theta_{j},\phi_{i})$.

##  2 Problem Setup

We consider the setting where a provider wants to design $k$ services for $n$
users with unknown diverse preferences, such that each service specializes to
a subgroup of users. Each service typically uses a model parameterized by a
vector $\theta\in\mathbb{R}^{d}$, which predicts users’ preferences. A user is
more likely to use a service that yields higher utility by predicting their
preference more accurately (corresponding to lower prediction loss).

Let the loss incurred by some user $i$ upon choosing some service
parameterized by $\theta\in\mathbb{R}^{d}$ be denoted by
$\mathcal{L}_{i}(\theta,\phi_{i})$. Here $\phi_{i}\in\mathbb{R}^{d}$
represents this user’s unknown preference parameter and
$\mathcal{L}_{i}:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}_{+}$
is an unknown (nonnegative) function governing this user’s loss (which the
provider can only evaluate at a given point; i.e., has zeroth order or bandit
access to this function only, see Section 3 for more details).

For example, in the case of movie recommendations, $\phi_{i}$ could be the
user’s interests across different genres of movies, $\theta$ a set of
recommended movies, and $\mathcal{L}_{i}(\theta,\phi_{i})$ measures user
dissatisfaction, say some function of hours spent online for this user, or a
rating the user left upon using this recommendation. Users can have diverse
preferences and loss geometries. The example in Figure 1 emphasizes that users
not only have distinct preferences, but also experience varying degrees of
dissatisfaction or satisfaction when presented with recommendations not
exactly their preference.

Note that information about $\mathcal{L}_{i}$ and $\phi_{i}$ is obtained _only
upon interacting with the users_ , which we will discuss in Section 3.

Figure 1: Imagine two users who both have a strong preference for action
movies (and both are content if they receive recommendations for this genre).
However, User 1 also enjoys romantic comedies, but dislikes documentaries,
while User 2 has the opposite preference. If User 1 is recommended a
documentary, they will be dissatisfied, whereas User 2 will still remain
content. Consequently, despite their shared fondness for action movies, their
levels of dissatisfaction or satisfaction diverge when they encounter content
from a different genre.

We make the following assumptions about the functional form of
$\mathcal{L}_{i}$, and state several examples of function classes satisfying
these properties.

######  Assumption 1 (Unique Minimizer).

The loss function satisfies the following equivalence:
$\mathcal{L}_{i}(\theta,\phi_{i})=0\ \Longleftrightarrow\ \theta=\phi_{i}$.

This assumption implies that unless all users have identical preferences,
there doesn’t exist a single service parameter $\theta$ that simultaneously
minimizes every user’s loss. Thus providing multiple services (multiple
$\theta$’s) where the users choose the one best for them is strictly better
than one service for all users.

######  Assumption 2 (Approximate Triangle Inequalities).

For a pair of users $i,j$ there exists a finite constant $c_{ij}>0$ such that
for all $\theta\in\mathbb{R}^{d}$ the following hold:

  1. (i)

$c_{ij}\mathcal{L}_{i}(\theta,\phi_{i})\leq\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j})$.

  2. (ii)

$c_{ij}\mathcal{L}_{i}(\phi_{j},\phi_{i})\leq\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{i}(\theta,\phi_{i})$.

Here $c_{ij}$ (equal to $c_{ji}$) captures the alignment between the
preferences and loss geometries of two users. Lower values of $c_{ij}$
indicate less similarity. Item $(i)$ implies that the loss for user $i$ on any
service $\theta\in\mathbb{R}^{d}$ is no worse than (up to a constant factor)
the sum of (a) loss of another user $j$ on using the same service, and (b) the
loss of user $j$ if they were to use user $i$’s preference. The latter term
(b) can be seen as measuring the similarity between the users’ preferences.

For condition $(ii)$ to hold for all $\theta\in\mathbb{R}^{d}$, it must also
hold for the service that minimizes the sum of losses of both users using the
same service. Suppose that users $i$ and $j$ were to exchange preferences.
Then their loss would be no worse than (up to a constant factor) their minimum
total loss, i.e.,

$\mathcal{L}_{i}(\phi_{j},\phi_{i})\leq\frac{1}{c_{ij}}\min_{\theta\in\mathbb{R}^{d}}\left(\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{i}(\theta,\phi_{i})\right).$

Some examples of functions (with corresponding constants) satisfying these
assumptions include the following (see Appendix A for additional examples and
derivations):

  * •

Squared error loss for linear predictors (cf. Section 4).

  * •

The Huber loss on the prediction error:

$\mathcal{L}_{i}(\theta,\phi_{i})=\begin{cases}\frac{1}{2}\|\theta-\phi_{i}\|^{2},&\text{if
}\|\theta-\phi_{i}\|\leq\delta\\\
\delta(\|\theta-\phi_{i}\|-\frac{1}{2}\delta),&\text{otherwise.}\end{cases}$

This loss is used typically in robust estimation tasks. Here $\|\cdot\|$ could
be any norm, and we show $c_{ij}=\frac{1}{3}$.

  * •

The normalized cosine distance:
$\mathcal{L}_{i}(\theta,\phi_{i})=1-\theta^{\top}\phi_{i}$ where
$\|\theta\|_{2}=\|\phi_{i}\|_{2}=1$, with $c_{ij}=\frac{1}{2}$. This is
commonly used as a similarity measure in natural language processing
applications, for example finding similarity between two documents.

  * •

The Mahalanobis distance:
$\mathcal{L}_{i}(\theta,\phi_{i})=\|\theta-\phi_{i}\|_{\Sigma_{i}}$. Different
users can have different $\Sigma_{i}$ capturing their diverse loss variation
(cf. Figure 1), as long as $\Sigma_{i}$ is full rank. Here
$c_{ij}=\min\\{\lambda_{\rm min}(\Sigma_{i},\Sigma_{j}),\lambda_{\rm
min}(\Sigma_{j},\Sigma_{i})\\}$.

  * •

Any distance metric: This naturally follows from triangle inequality, hence
$c_{ij}=1$. (Note that the examples above are also all distances, but when
focusing on their special form we obtain better estimates for the $c_{ij}$.)

Suppose the users have access to $k$ services parameterized by
$\Theta=\\{\theta_{1},\ldots,\theta_{k}\\}\subset\mathbb{R}^{d}$. Then, each
user $i$ selects service $\theta_{l}$ that minimizes their loss, i.e.
$\mathcal{L}_{i}(\Theta,\phi_{i})=\min_{l\in[k]}\mathcal{L}_{i}(\theta_{l},\phi_{i})$.

Our objective is to design $\Theta$, such that the sum of losses across users
and services is minimized. We define the objective as follows:

$\displaystyle\mathcal{L}(\Theta,[n])=\sum_{i\in[n]}\min_{j\in[k]}\mathcal{L}_{i}(\theta_{j},\phi_{i}).$
(1)

######  Definition 2.1.

Define the unknown optimal set of $k$ services that minimizes the objective to
be

$\Theta_{\rm
OPT}:=\operatorname*{\mathrm{argmin}}_{|\Theta|=k}\mathcal{L}(\Theta,[n]).$

Specifically, $\Theta_{\rm OPT}$ defines a “clustering”, meaning a
partitioning of the $n$ users into $k$ clusters. The cluster $\mathcal{B}_{m}$
is the set of all users that prefer the service $\theta_{m}$ among all the
services in the optimal set $\Theta_{\rm OPT}$. In other words,
$\mathcal{B}_{m}$ is defined as the set of all points such that
$\mathcal{B}_{m}=\\{i\in[n]\;|\;\theta_{m}=\operatorname*{arg\,min}_{\theta_{l}\in\Theta_{\rm
OPT}}\mathcal{L}_{i}(\theta_{l},\phi_{i})\\}$. If multiple services are
equally preferred by a subpopulation, the ties are broken arbitrarily. The
resulting set of clusters is denoted by $\mathcal{C}(\Theta_{\rm
OPT})=\\{\mathcal{B}_{1},\ldots,\mathcal{B}_{k}\\}$.

The are several statistical and computational challenges to this problem.

######  Challenge 1.

Since preferences $\\{\phi_{i}\\}_{i\in[n]}$ and loss functions
$\\{\mathcal{L}_{i}\\}_{i\in[n]}$ are unknown, and the provider only has
zeroth order or bandit feedback access, estimating the objective function
$\mathcal{L}(\Theta,[n])$ usually needs a lot of data collected uniformly
across the users. This large amount of data is needed before services can be
deployed, yet as stated earlier, we are in the situation where we have no data
until we deploy services and observe user interactions. Our limited access to
user information (via limited queries) make our setting challenging.

######  Challenge 2.

In addition to the first challenge, the loss function is non-convex and
iterative minimization approaches from a random initialization are susceptible
to getting stuck in arbitrarily poor local optima. Alternatively, computing
the optimal clustering first and then finding the best service for each
cluster would be NP-Hard.

Despite these challenges, in Section 3, we propose an algorithm that is both
statistically and computationally efficient, and admits an approximation ratio
with respect to the _globally optimal value_ , i.e., $\mathcal{L}(\Theta_{\rm
OPT},[n])$.

Algorithm 1 AcQUIre- Adaptively Querying Users for Initialization

1: Input: Set of users $[n]$, number of services $k$.

2: Choose a user $i$ uniformly randomly from $[n]$.

3: Query user $i$’s preference $\phi_{i}$, set the first service
$\Theta_{1}=\phi_{i}$.

4: for $t\in\\{2,\ldots,k\\}$ do

5: User behavior: Collect user losses on existing services $\Theta_{t-1}$ :
{$\mathcal{L}_{i}(\Theta_{t-1},\phi_{i})\\}_{i\in[n]}$.

6: User Selection: Sample $l$ from $[n]$ with probability
$P(l=i)\propto\mathcal{L}_{i}(\Theta_{t-1},\phi_{i})$.

7: New service: Query user $l$’s preference $\phi_{l}$.

8: $\Theta_{t}=\Theta_{t-1}\cup\phi_{l}$.

9: end for

10: Return $\Theta_{k}$

##  3 Algorithm & Main Results

In this section, we present our initialization algorithm with guarantees,
Algorithm 1, and describe how the steps of the algorithm arise naturally in
the interactive systems under consideration. Since collecting preference data
uniformly across all the $n$ users can be prohibitively expensive, our goal is
to get data from a minimal number of users.

Each iteration of the loop in the algorithm adds a service sequentially and
the loop terminates when there are $k$ services, where $k$ is a predetermined
parameter for the algorithm. We focus on the loop (lines 4-8) in Algorithm 1.

Suppose at time $t-1$, the set $\Theta_{t-1}$ is the set of current $t-1$
services. Then, at time step $t$ the following steps take place.

  * •

User behavior (line 5).  Given the list of services $\Theta_{t-1}$ users are
assumed to choose the best service that minimizes user risk. Users report
their losses with respect to the service they choose from the set of existing
services $\\{\mathcal{L}_{i}(\Theta_{t-1},\phi_{i})\\}_{i\in[n]}$. In
practice, this step requires deploying the services and collecting signals of
engagement and utility to determine the loss associated with each user, under
the behavioral assumption that users are rational agents that choose the best
available service. The provider thus needs to measure each user’s loss only in
their single chosen service.

  * •

User selection (line 6)  A new user $l$ is selected with probability
proportional to $\mathcal{L}_{i}(\Theta_{t-1},\phi_{l})$. This ensures that
users that are currently poorly served by existing services are more likely to
be selected.

  * •

New Service (line 7-8). Given a selected user $l$, the algorithm queries the
preference $\phi_{l}$ of the user and centers the new service at that
preference $\theta_{t}=\phi_{l}$. In practice, this step requires acquiring
data about the user in order to learn their preference (this is needed for
only $k$ total users throughout the algorithm). For example, data may be
acquired by incentivizing the selected users, via offering discount coupons or
free premium subscriptions (Hirnschall et al., 2018).

With each iteration the loss of each user is non-increasing; the previous
services remained fixed and a user would switch to a new service only if it
improves quality or equivalently decreases loss. Since at each iteration, a
new service is added, the process terminates after $k$ steps. Since it is
costly to offer and maintain too many different services, we typically have
$k\ll n$.

We now discuss the theoretical properties of the set of services we get at the
termination of Algorithm 1.

######  Theorem 1.

Consider $n$ users with unknown preferences
$\\{\phi_{1},\ldots,\phi_{n}\\}\subset\mathbb{R}^{d}$, and unknown associated
loss functions $\mathcal{L}_{i}(\cdot,\cdot)$ satisfying Assumptions 1 and 2.
Let $\Theta_{\rm OPT}\subset\mathbb{R}^{d}$ be the set of $k$ services
minimizing the total loss and $\mathcal{C}(\Theta_{\rm OPT})$ the resulting
partitioning of users (Definition 2.1). If Algorithm 1 is used to obtain $k$
services $\Theta_{k}$, then the following bound holds:

$\displaystyle\mathbb{E}_{\Theta_{k}}[\mathcal{L}(\Theta_{k},[n])]$
$\displaystyle\leq K_{\rm OPT}(2+\log k)\cdot\mathcal{L}(\Theta_{\rm
OPT},[n]),$

where the expectation is taken over the randomization of the algorithm and
$K_{\rm OPT}$ is equal to

$\max_{\mathcal{B}\in\mathcal{C}(\Theta_{\rm
OPT})}\frac{4}{\min\limits_{j\in\mathcal{B}}\sum\limits_{i\in\mathcal{B}}c_{ij}}\left(\max_{j\in\mathcal{B}}\sum_{i\in\mathcal{B}}\frac{1}{c_{ij}}\right).$
(2)

A detailed proof is presented in Appendix B; we summarize the main ideas here.
The intuition is that a chosen user’s preference is typically a good
representative for other users in its cluster. Thus adding a service
parameterized by the chosen user’s preferences generally reduces the losses of
users in this cluster. Subsequently we are less likely to pick another user
from the same cluster. The $\log k$ factor is due to clusters from which users
were never picked.

A similar proof approach was used by Arthur and Vassilvitskii (2007) in the
context of the $k$-means problem, by sequentially placing centers on known
points sampled with probability proportional to the point’s squared distance
to its closest existing center. A key novelty of our analysis is to capture
the _alignment_ of diverse loss geometries across users in a large class of
functions, specifically understanding how user similarities $c_{ij}$ affect
the approximation ratio.222In addition, as stated earlier, we tackle the lack
of prior information on $\phi_{i}$ and the function form of
$\mathcal{L}_{i}$—this challenge is particular to our setting and does not
arise in related standard problems of clustering ($k$-means, $k$-mediods) or
resource allocation (facility location problems).

#### Key characteristics of $K_{\rm OPT}$:

The following are essential characteristics of the term $K_{\rm OPT}$.

  1. (i)

All terms in $K_{\rm OPT}$ depend on the local clusters in the unknown optimal
clustering $\mathcal{C}(\Theta_{\rm OPT})$.

  2. (ii)

The constant
$\min_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}c_{ij}$
captures the user whose loss geometry is _least similar_ to the average loss
geometry of the cluster they belong to (recall Assumption 2.i).

  3. (iii)

The constant
$\max_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum_{i}\frac{1}{c_{ij}}$
captures the user whose preference is _least similar_ to the optimal service
parameter of the cluster they belong to (recall Assumption 2.ii).

  4. (iv)

Even within a cluster all terms are averages, so a few poorly aligned pairs of
users don’t hurt the bound if the cluster sizes are large.

#### Fair objective.

While minimizing the total loss is beneficial from the provider’s point of
view in keeping users satisfied on average, it is undesirable in human-centric
applications if the provided services result in unfavorable or harmful
outcomes towards some demographic groups.

Suppose the $n$ users come from $m$ unknown different demographic groups ($m$
is typically small, say racial groups, gender). We denote the groups as
$\mathcal{A}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{m}\\}\subset[n]$. The
fairness objective is defined as the maximum average loss suffered by any
group:

$\Phi(\Theta,\mathcal{A})=\max_{i\in[m]}\frac{\mathcal{L}(\Theta,\mathcal{A}_{i})}{|\mathcal{A}_{i}|}.$
(3)

Ghadiri et al. (2021) defined this objective in the context of fair $k$-means
where the points and group identities are known and gave a non-constructive
proof that if a $c-$approximate solution for $k$-means exists, it is $m\cdot
c$-approximate for fair $k$-means. In our setup, where both user preferences
and group identities are unknown, the set of services initialized by Algorithm
1 enjoys guarantees on optimizing the fairness objective as stated below.

######  Theorem 2.

Consider $n$ users with unknown preferences
$\\{\phi_{1},\ldots,\phi_{n}\\}\subset\mathbb{R}^{d}$, and unknown associated
loss functions $\mathcal{L}_{i}(\cdot,\cdot)$ satisfying Assumptions 1 and 2.
Suppose these users belong to $m$ unknown demographic groups
$\mathcal{A}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{m}\\}\subset[n]$. Let
$\Theta_{\rm fair}\subset\mathbb{R}^{d}$ be the set of $k$ services minimizing
the fairness objective $\Phi$ given in (3). If Algorithm 1 is used to obtain
$k$ services $\Theta_{k}$, then the following bound holds:

$\displaystyle\mathbb{E}_{\Theta_{k}}[\Phi(\Theta_{k},\mathcal{A})]\leq m\cdot
K_{\rm
OPT}\cdot\frac{\max_{i\in[m]}|\mathcal{A}_{i}|}{\min_{i\in[m]}|\mathcal{A}_{i}|}\cdot(2+\log
k)\cdot\Phi(\Theta_{\rm fair},\mathcal{A}),$

where the expectation is taken over the randomization of the algorithm and
$K_{\rm OPT}$ is defined in (2).

If the group identities are known a priori to the provider, we can modify
Algorithm 1 to get rid of the factor
$\frac{\max_{i\in[m]}|\mathcal{A}_{i}|}{\min_{i\in[m]}|\mathcal{A}_{i}|}$ in
the approximation ratio, as discussed in Appendix C.

##  4 Generalization in Linear Predictors

In practical settings, a provider would want to design services that not only
keep the subscribed users satisfied but also attract new users to subscribe by
generalizing the services to users it has never interacted with before. Now
instead of considering $n$ users, suppose that each $i\in[N]$ represents a
subpopulation with its own (sub-Gaussian) distribution of features, and the
provider can interact with finite samples $n_{i}$ from these distributions. A
question that arises is whether we can deal with this finite-sample-from-
subpopulations scenario, and how does the number of samples affect the
algorithm’s output to unseen users. In this section, we answer this question
for the special case of linear predictors (i.e., regression loss).

In this section we restrict ourselves to the special case of linear prediction
tasks, where the goal is to accurately predict the score of a user as a linear
function of their features. The score for a user in the $i^{\rm th}$
subpopulation with zero-mean random feature $x\in\mathbb{R}^{d}$ is generated
as $y=\phi_{i}^{\top}x$ where both the true linear regressor
$\phi_{i}\in\mathbb{R}^{d}$ and the feature covariance
$\mathbb{E}_{x}[xx^{\top}]=\Sigma_{i}$ are unknown. Suppose a service uses a
linear regressor $\theta\in\mathbb{R}^{d}$, to predict the score for this user
as $\theta^{\top}x\in\mathbb{R}$. The loss for this subpopulation for this
service is defined as the expected squared error between the predicted and
actual scores, i.e.,
$\mathcal{L}_{i}(\theta,\phi_{i})=\mathbb{E}_{(x,y)}[(\theta^{\top}x-y)^{2}]=\|\theta-\phi_{i}\|^{2}_{\Sigma_{i}}$.

######  Assumption 3.

For subpopulation $i$, features are independent draws from a zero-mean sub-
Gaussian distribution. For a random feature $x\in\mathbb{R}^{d}$ and for any
$u\in\mathbb{R}^{d}$, such that $\|u\|_{\Sigma_{i}}=1$,
$u^{\top}x\in\mathbb{R}$ is sub-Gaussian with variance proxy
$\sigma_{i}^{2}$.333A random variable $x$ is sub-Gaussian with variance proxy
$\sigma^{2}$ if $\mathbb{E}[\exp(\lambda
x)]\leq\exp(\frac{\sigma^{2}\lambda^{2}}{2})\;\forall\lambda\in\mathbb{R}$.

######  Assumption 4.

We assume that the decision to choose between different services happens at a
subpopulation level and not an individual level.

To illustrate Assumption 4, consider the example of a provider that offers
personalized services to schools (subpopulations) such as online library
resources wherein the service provider queries students about the experience.
Each school typically has a considerable number of students, but only a subset
of them may actively respond to such queries. Once a school selects the
service, it is made available to all students, and the provider could
implement a system where students are encouraged to fill out a feedback form
after using their service.

Suppose only $n_{i}$ users from subpopulation $i$ are subscribed to the
services. Thus, upon choosing a service parameterized by
$\theta\in\mathbb{R}^{d}$ the provider observes an empirical loss, which is
given by

$\widehat{\mathcal{L}}_{i}(\theta,\phi_{i})=\frac{1}{n_{i}}\sum_{j\in[n_{i}]}(\theta^{\top}x_{i}^{j}-y_{i}^{j})^{2},$

where $\\{(x_{i}^{j},y_{i}^{j})\\}_{j\in[n_{i}]}$ are private unknown features
and scores of the users. We stress that the service gets to see the value of
the user loss function at the deployed $\theta$ (bandit feedback), but not the
features of each subpopulation.

######  Assumption 5.

The number of users from each subpopulation is greater than the dimension of
the linear predictor, i.e. $n_{i}\geq d$ for all $i\in[N]$.

In this setting, given a set of services parameterized by
$\Theta_{t-1}=\\{\theta_{1},\ldots,\theta_{t-1}\\}$ the Steps 5-6 of Algorithm
1 proceed with these finite sample averages
$\widehat{\mathcal{L}}_{i}(\Theta_{t-1},\phi_{i})=\min_{j\in[t-1]}\widehat{\mathcal{L}}_{i}(\theta_{j},\phi_{i})$.
In Step 7, multiple ways can be adopted by the provider to estimate
$\phi_{i}$. Users can be given incentives to provide a batch of feature score
pairs, or gradient free methods can be used to estimate the optimal solution
to the regression problem. The generalization guarantee of Algorithm 1 to the
total expected loss is stated below.

######  Theorem 3.

Suppose users belong to $N$ subpopulations satisfying Assumptions 3, 4, and 5.
Let $\\{n_{i}\\}_{i\in[N]}$ denote the number of samples per subpopulation.
Let $\Theta_{k}$ be the output of Algorithm 1 using finite sample estimates
$\widehat{\mathcal{L}}_{i}(\cdot,\phi_{i})$ and $\Theta_{\rm OPT}$ be the
optimal solution of the expected loss. Then, for any $\epsilon\in(0,1)$, if
$n_{i}=\Omega(\frac{\sigma_{i}^{4}\sqrt{N}\log{(2/\delta)}}{\epsilon^{2}})$
for all $i\in[N]$, the following inequality holds with probability at least
$1-\delta$:

$\displaystyle\mathbb{E}_{\Theta_{k}}[\mathcal{L}(\Theta_{k},[N])]\leq\frac{1+\epsilon}{1-\epsilon}K_{\rm
OPT}(2+\log k)\mathcal{L}(\Theta_{\rm OPT},[N]),$

where $K_{\rm OPT}$ is as defined in (2) and

$\displaystyle c_{ij}=\frac{1}{2}\min\
\left\\{\lambda_{\mathrm{min}}(\widehat{\Sigma}_{i},\widehat{\Sigma_{j}}),\frac{1}{\lambda_{\mathrm{min}}(\widehat{\Sigma}_{i},\widehat{\Sigma_{j}})}\right\\},$

with

$\widehat{\Sigma}_{i}=\frac{1}{n_{i}}\sum_{l\in[n_{i}]}x_{i}^{l}(x_{i}^{l})^{\top}\quad\text{and}\quad\widehat{\Sigma}_{j}=\frac{1}{n_{j}}\sum_{l\in[n_{j}]}x_{j}^{l}(x_{j}^{l})^{\top}.$

The proof is presented in Appendix D; we provide a brief overview here. We
apply the Chernoff bound to the difference between the empirical loss and
expected loss. Note that $(i)$ even if the same set of services are provided,
the loss minimizing service for the empirical loss may be different from the
expected loss for any subpopulation, and $(ii)$ the optimal set of services
for the total empirical loss and the total expected loss are different.
Handling these carefully, and utilizing Theorem 1 concludes the proof.

######  Remark 1.

Note that $\widehat{\Sigma}_{i}$ is the empirical feature covariance of
subpopulation $i$. The term $c_{ij}$ captures the alignment between two
subpopulation’s loss geometry, and here is equal to half of the _minimum
generalized eigenvalue_ of the empirical feature covariances of the the
respective subpopulations. This quantity is the largest constant satisfying
Assumption 2 (cf. Appendix D).

##  5 Experiments

We empirically demonstrate444All our code is available at
https://anonymous.4open.science/r/InteractiveSystemInitialization-2A33 the
benefits of our algorithm on a commute time prediction task based on 2021 US
Census data555https://www.census.gov/programs-surveys/acs/data.html. and a
semi-synthetic movie recommendation task on the MovieLens10M dataset. In both
the tasks, our algorithm starts without access to any data and our goal is to
evaluate how well the sequential acquisition of data, subsequent learning and
deployment of learnt models performs on the whole dataset.

#### Census Data.

We consider the task of predicting daily work commute times, based on 2021 US
census data from folktables (Ding et al., 2021). We illustrate a potential use
case: the provider is a transport authority offering services in the form of
personalized podcasts. If the duration of service is similar to the commute
time of a user, that user will be able to consume the media while travelling
to work. Hence an accurate prediction of the commute time may be useful in
providing services tailored to the users.

The data set has $n=7025$ subpopulations defined by the intersection of
gender, race and zip code. We use $k$ linear predictors (as services) with
private user features (education, income, transportation mode, age etc). Refer
to Appendix E for a detailed description of data pre-processing. As described
in Section 4 , the user loss is squared prediction error of their commute
time. The features and commute times are unknown a priori to the the provider.
At time step $t\leq k$, suppose there exists a set of services $\Theta_{t-1}$.
The provider observes the losses (squared prediction error as discussed in
Section 4) across different subpopulations
$\\{\widehat{\mathcal{L}}_{i}(\Theta_{t-1},\phi_{i})\\}_{i\in[N]}$. Based on
these observed losses, a subpopulation $l$ is sampled with probability
$\propto\widehat{\mathcal{L}}_{l}(\Theta_{t-1},\phi_{l})$. Upon selecting a
subpopulation the provider surveys the population and acquires relevant data
for it. Subsequently the provider uses the acquired data to estimate the sub-
population preference via ordinary least squares:
$\widehat{\phi}_{l}=\min_{\theta\in\mathbb{R}^{d}}\widehat{\mathcal{L}}_{l}(\theta,\phi_{l})$.
The list of services is updated
$\Theta_{t}=\Theta_{t-1}\cup\widehat{\phi}_{l}$ and the process is repeated
until $k$ services are initialized.

Figure 2: Average loss of different demographics with services initialized by
Algorithm 1. Note that Algorithm 1 has much lower losses as compared to the
baseline for the each of the demographic groups.

#### Evaluation.

We compare our algorithm against the baseline where $k$ subpopulations are
uniformly selected at random and the services initialized as their learnt
regression parameters. The subpopulations belong to the following demographic
groups666These group labels are taken from the publicly available 2021 US
Census data. (i) Based on sex: male or female, (ii) Based on race: White,
Black, American Indian , Alaskan Native, Asian, Pacific Islander, Others. As
shown in Figure 2, Algorithm 1 reduces the average loss for every demographic
group. We also observe a 15-25% and 7-25% improvement on the fair
objective—which is defined in (3)—for sex and racial group demographics,
respectively, as the number of services varies (see Figure 4 in Appendix E for
detailed plots). We emphasize that this result is observed despite the
algorithm not knowing the identity of the demographic groups whilst collecting
data.

Figure 3: Total excess error $\sum_{i\in[N]}\mathcal{L}_{i}(V,V_{i})$, where
$\mathcal{L}_{i}$ is defined in (4), versus the number of services $d$ (i.e.,
the number of recommendation models) for Algorithm 1 versus the uniform
initialization baseline.

#### Movie Recommendations.

We conduct a semi synthetic experiment based on the widely used Movielens10M
data set (Harper and Konstan, 2015) containing 10000054 ratings across 10681
movies by 71567 viewers. We pre-process the data set (cf. Appendix E) and
divide viewers into $N=1000$ subpopulations and retain only the top $m=200$
most watched movies. We compare the performance of Algorithm 1—which
initializes a set of recommendation models where user preferences are unknown
a priori—to a uniform initialization baseline. For subpopulation $i\in[N]$,
let the solution to the following optimization problem denote the unknown user
and item embeddings:

$(U_{i},V_{i})=\operatorname*{arg\,min}_{(U,V)\in\mathbb{R}^{n_{i}\times
d}\times\mathbb{R}^{d\times m}}\|(UV)_{\Omega_{i}}-r_{i}\|_{2}^{2},$

where $r_{i}$ is the true user ratings and $\Omega_{i}$ is the list of movies
rated by the user for subpopulation $i$. User dissatisfaction for a
recommendation model, parameterized by $V\in\mathbb{R}^{d\times m}$, is
captured by the excess error, namely

$\mathcal{L}_{i}(V,V_{i})=\|(U_{i}V)_{\Omega_{i}}-r_{i}\|_{2}^{2}-\|(U_{i}V_{i})_{\Omega_{i}}-r_{i}\|_{2}^{2}.$
(4)

We chose $d=5$ for the experiment. As described for the census experiment,
Algorithm 1 iteratively selects subpopulations with probability proportional
to their current excess error, and then solves the matrix factorization
problem for the selected subpopulation, and adds the learnt item embedding to
the list of services.

As shown in Figure 3, the total excess error achieved by Algorithm 1 is
significantly lower than uniformly sampling users for their preferences. It is
interesting to note that to achieve the same total excess error for five
services initialized by our algorithm, uniform data collection and
initialization would need 30 services.

##  6 Related Work

#### Retention.

User retention in machine learning systems is closely related to the decision
dynamics between the provider and users studied in the single service setting
by Hashimoto et al. (2018) and Zhang et al. (2019), and multiple services
setting by Dean et al. (2022). In settings with multiple sub-populations of
users of different types, the question of retention has been explored in
parallel with the issue of fairness. The final outcome of such dynamics are
heavily influenced by the initial data available to provider and the initial
configuration (or partitioning) of the users across the offered services. Our
work addresses these issue with theoretical guarantees.

#### Multiple Model Specialization.

Our work also considers the inherent heterogeneity in user preferences,
especially prominent in distributed learning settings where data sources are
users’ personal devices. For applications such as recommendation systems and
personalized advertising, the utilization of multiple specialized models can
yield improved predictions and outcomes. Users are often grouped into
clusters, each representing unique interests and preferences. For instance, in
movie recommendation systems, these clusters could represent users interested
in different movie genres, or different combination of features. This approach
has been adopted in recent federated learning formulations such as clustered
federated learning (Sattler et al., 2020; Mansour et al., 2020) and is
integral to the federated learning model of Ghosh et al. (2020), where users
_choose_ models for which to provide updates. This model specialization is
also explored in the mixture of experts literature (see, e.g., Masoudnia and
Ebrahimpour (2014)), which uses multiple ‘expert’ models to enhance accuracy
and robustness, assigning inputs to the most suitable expert based on their
features through a gating mechanism.

#### Clustering.

The $k$-means clustering problem is one of the most commonly encountered
unsupervised learning problems. Given a set of known $n$ points in Euclidean
space, the goal is to partition them into $k$ clusters (each characterized by
a center), such that the sum of square of distances to their closest center is
minimized. Dasgupta (2008) and Aloise et al. (2009) showed that the $k$-means
problem is NP-Hard.

The most popular heuristic for $k$-means is Lloyd’s algorithm (Lloyd, 1982),
often referred to as the "$k$-means algorithm", which proceeds by randomly
initializing $k$ centers and then uses iterative updates to find a locally
optimal $k$-means clustering, which can be arbitrarily bad compared to the
globally optimal clustering. The performance of the $k$-means algorithm relies
crucially on the initialization. Arthur and Vassilvitskii (2007) and Ostrovsky
et al. (2013) proposed an elegant polynomial time algorithm for initializing
centers, known as $k$-means++. Arthur and Vassilvitskii (2007) proved that the
expected cost of the initial clustering obtained by $k$-means++ is at most
$8(2+\log k)$ times the cost of optimal $k$-means clustering and showed a
family of $k$-means instances where the approximation ratio is $2\log k$
showing their analysis is almost tight. Makarychev et al. (2020) improved the
analysis to show an approximation ratio $5(2+\log k)$ and showed a family of
instances with $5\log k$ approximation ratio, thus showing $k$-means++ is
tight.

Our work generalizes the analysis of Arthur and Vassilvitskii (2007) to the
setting where user’s preferences are represented as unknown points and the
loss functions are unknown and not necessarily identical as long they satisfy
Assumptions 1 and 2. Recent works in clustering (Kanungo et al., 2002;
Ahmadian et al., 2019; Lattanzi and Sohler, 2019) provide a constant
approximation ratio, and although they are polynomial time algorithms, these
methods are data inefficient and rely on knowing the points _a priori_.
Finally, another common clustering algorithm is Gaussian mixture models
(GMMs), where each cluster is represented by a Gaussian distribution, thus
clusters themselves can be viewed as ellipsoidal (which is a different goal
from ours even we choose Mahalanobis distances as losses, for us in this case
every point (user) is associated with a different loss geometry).

#### Facility Location Problem.

Our algorithm has some resemblances with the facility location problem where
there are $n$ users, and a provider can set up at most $k$ facilities at one
of $m$ candidate locations. This is also often known as the $k$-medoids
objective (Arora et al., 2016). One of the key differences is the provider can
choose from $m$ predecided locations, compared to our setting where the
optimization space is infinite. However our algorithm initializes only at $k$
of the $n$ user preferences, hence it can be viewed as the candidate locations
simply being the user preferences and thus $m=n$. A typical greedy algorithm
for the $k$-medoids objective proceeds by evaluating the marginal decrement in
total loss for _all possible candidates_ and selects the candidate with
maximal loss reduction. Thus (i) the algorithm would need to know all
$\\{\phi_{1},\ldots,\phi_{n}\\}$ apriori, and (ii) deploy $n$ services to
obtain all $n^{2}$ function evaluations
$\mathcal{L}_{j}(\phi_{i},\phi_{j}),\;\forall i,j\in[n]$. This is infeasible
in applications like online recommendation systems where $n$ is very large and
typically a provider has the capacity to deploy only $k\ll n$ services. Hence
a $k$-medoids like objective will not be reasonable in our setup with
incomplete information.

Bose et al. (2022) studied the case where the provider had prior access to
only $N<n$ users’ utility functions before deploying services and the goal was
to minimize the worst case total (over all $n$ users) loss. However their
results assume they can solve a computationally hard mixed integer program
optimally.

#### Preference Learning.

Given a fixed set of items, Tatli et al. (2022) focus on learning preferences
distributions of users. Canal et al. (2022) extend this to the setting where
the user losses are given by an identical metric, and they learn both
preferences and the metric efficiently. Our setting focuses on the design of
services rather than learning preferences over a fixed set of services, and we
also allow each user to potentially have a different loss geometry; e.g.,
Mahalanobis distances with different matrices (where the sublevel sets of the
loss are ellipsoids with different principal axes and orientations).

##  7 Discussion

It would be interesting to study how strategic user behavior affects the data
acquisition and services’ initialization process. For example, users may
report losses that are higher than their true losses in the hopes of being
selected by the provider. This in turn can lead to a biasing of the service
towards these particular untruthful users. It an interesting line of
questioning centers on the design of algorithm modifications or the design
explicit incentives to help avoid this, for example, by encouraging truthful
reporting and also voluntary participation in the case that the designed
mechanisms (algorithmic or incentive based) lead to users ‘opting out’ of all
services.

On a related note, seemingly benign non-strategic behavior can also lead to
degradation in performance. Specifically, there are many open questions
relating to quantifying the robustness of the proposed initialization
algorithm to noisy observations, perturbations, or outliers in the finite
sample case when the feature distribution is heavy-tailed.

Finally, it is interesting to study the improvement in the total loss not only
after initialization as was done in this paper, but also after running
iterative learning dynamics, alternating service updates and users’ choice
updates. It is known that the total loss will not increase and the iterations
converge to a local minimum of the total loss, but further quantifying this
improvement, as well as other properties of the iterative updates (including
whether they can be carried out in our low-information setting) is left for
future work.

## Acknowledgements

Dean, Fazel, Morgenstern and Ratliff were supported by NSF CCF-AF
2312774/2312775. Additionally, Morgenstern’s work was supported by NSF CCF
2045402. Dean’s research was supported by a gift from Wayfair, a LinkedIn
research award, and NSF OAC 2311521. Ratliff’s research was supported by NSF
CNS 1844729 and Office of Naval Research YIP Award N000142012571. Fazel was
supported in part by awards NSF TRIPODS II 2023166, CCF 2007036, CCF 2212261.

## References

  * Ahmadian et al. (2019) Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward.  Better guarantees for k-means and euclidean k-median by primal-dual algorithms.  _SIAM Journal on Computing_ , 49(4):FOCS17–97, 2019.
  * Aloise et al. (2009) Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat.  Np-hardness of euclidean sum-of-squares clustering.  _Machine learning_ , 75(2):245–248, 2009.
  * Arora et al. (2016) Preeti Arora, Shipra Varshney, et al.  Analysis of k-means and k-medoids algorithm for big data.  _Procedia Computer Science_ , 78:507–512, 2016.
  * Arthur and Vassilvitskii (2007) David Arthur and Sergei Vassilvitskii.  K-means++ the advantages of careful seeding.  In _Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1027–1035, 2007.
  * Bose et al. (2022) Avinandan Bose, Arunesh Sinha, and Tien Mai.  Scalable distributional robustness in a class of non-convex optimization with guarantees.  _Advances in Neural Information Processing Systems_ , 35:13826–13837, 2022.
  * Canal et al. (2022) Gregory Canal, Blake Mason, Ramya Korlakai Vinayak, and Robert Nowak.  One for all: Simultaneous metric and preference learning over multiple users.  _arXiv e-prints_ , pages arXiv–2207, 2022.
  * Chua et al. (2021) Kurtland Chua, Qi Lei, and Jason D. Lee.  How fine-tuning allows for effective meta-learning.  In _Proc. of Advances in Neural Information Processing Systems_ , volume 34, 2021.
  * Dasgupta (2008) Sanjoy Dasgupta.  _The hardness of k-means clustering_.  Department of Computer Science and Engineering, University of California, San Diego, 2008.
  * Dean et al. (2022) Sarah Dean, Mihaela Curmei, Lillian J Ratliff, Jamie Morgenstern, and Maryam Fazel.  Multi-learner risk reduction under endogenous participation dynamics.  _arXiv preprint arXiv:2206.02667_ , 2022.
  * Ding et al. (2021) Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt.  Retiring adult: New datasets for fair machine learning.  _Advances in Neural Information Processing Systems_ , 34:6478–6490, 2021.
  * Dwork et al. (2018) Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Max Leiserson.  Decoupled classifiers for group-fair and efficient machine learning.  In _Conference on fairness, accountability and transparency_ , pages 119–133. PMLR, 2018.
  * Förstner and Moonen (2003) Wolfgang Förstner and Boudewijn Moonen.  A metric for covariance matrices.  _Geodesy-the Challenge of the 3rd Millennium_ , pages 299–309, 2003.
  * Ghadiri et al. (2021) Mehrdad Ghadiri, Samira Samadi, and Santosh Vempala.  Socially fair k-means clustering.  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , pages 438–448, 2021.
  * Ghojogh et al. (2019) Benyamin Ghojogh, Fakhri Karray, and Mark Crowley.  Eigenvalue and generalized eigenvalue problems: Tutorial.  _arXiv preprint arXiv:1903.11240_ , 2019.
  * Ghosh et al. (2020) Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran.  An efficient framework for clustered federated learning.  _Advances in Neural Information Processing Systems_ , 33:19586–19597, 2020.
  * Ginart et al. (2021) Tony Ginart, Eva Zhang, Yongchan Kwon, and James Zou.  Competing ai: How does competition feedback affect machine learning?  In _International Conference on Artificial Intelligence and Statistics_ , pages 1693–1701. PMLR, 2021.
  * Harper and Konstan (2015) F Maxwell Harper and Joseph A Konstan.  The movielens datasets: History and context.  _Acm transactions on interactive intelligent systems (tiis)_ , 5(4):1–19, 2015.
  * Hashimoto et al. (2018) Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang.  Fairness without demographics in repeated loss minimization.  In _International Conference on Machine Learning_ , pages 1929–1938. PMLR, 2018.
  * Hirnschall et al. (2018) Christoph Hirnschall, Adish Singla, Sebastian Tschiatschek, and Andreas Krause.  Learning user preferences to incentivize exploration in the sharing economy.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Honorio and Jaakkola (2014) Jean Honorio and Tommi Jaakkola.  Tight bounds for the expected risk of linear classifiers and pac-bayes finite-sample guarantees.  In _Artificial Intelligence and Statistics_ , pages 384–392. PMLR, 2014.
  * Hug (2020) Nicolas Hug.  Surprise: A python library for recommender systems.  _Journal of Open Source Software_ , 5(52):2174, 2020.  doi: 10.21105/joss.02174.  URL https://doi.org/10.21105/joss.02174.
  * Kanungo et al. (2002) Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu.  A local search approximation algorithm for k-means clustering.  In _Proceedings of the eighteenth annual symposium on Computational geometry_ , pages 10–18, 2002.
  * Kong et al. (2020) Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh.  Meta-learning for mixed linear regression.  In _International Conference on Machine Learning_ , pages 5394–5404. PMLR, 2020.
  * Lattanzi and Sohler (2019) Silvio Lattanzi and Christian Sohler.  A better k-means++ algorithm via local search.  In _International Conference on Machine Learning_ , pages 3662–3671. PMLR, 2019.
  * Li et al. (2020) Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  _IEEE signal processing magazine_ , 37(3):50–60, 2020.
  * Lloyd (1982) Stuart Lloyd.  Least squares quantization in pcm.  _IEEE transactions on information theory_ , 28(2):129–137, 1982.
  * Makarychev et al. (2020) Konstantin Makarychev, Aravind Reddy, and Liren Shan.  Improved guarantees for k-means++ and k-means++ parallel.  _Advances in Neural Information Processing Systems_ , 33:16142–16152, 2020.
  * Mansour et al. (2020) Yishay Mansour, Mehryar Mohri, Jae Ro, and Ananda Theertha Suresh.  Three approaches for personalization with applications to federated learning.  _arXiv preprint arXiv:2002.10619_ , 2020.
  * Masoudnia and Ebrahimpour (2014) Saeed Masoudnia and Reza Ebrahimpour.  Mixture of experts: a literature survey.  _The Artificial Intelligence Review_ , 42(2):275, 2014.
  * Ostrovsky et al. (2013) Rafail Ostrovsky, Yuval Rabani, Leonard J Schulman, and Chaitanya Swamy.  The effectiveness of lloyd-type methods for the k-means problem.  _Journal of the ACM (JACM)_ , 59(6):1–22, 2013.
  * Sattler et al. (2020) Felix Sattler, Klaus-Robert Müller, and Wojciech Samek.  Clustered federated learning: Model-agnostic distributed multitask optimization under privacy constraints.  _IEEE transactions on neural networks and learning systems_ , 32(8):3710–3722, 2020.
  * Song et al. (2014) Linqi Song, Cem Tekin, and Mihaela Van Der Schaar.  Online learning in large-scale contextual recommender systems.  _IEEE Transactions on Services Computing_ , 9(3):433–445, 2014.
  * Steinhardt et al. (2016) Jacob Steinhardt, Gregory Valiant, and Moses Charikar.  Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Sun et al. (2021) Yue Sun, Adhyyan Narang, Ibrahim Gulluk, Samet Oymak, and Maryam Fazel.  Towards sample-efficient overparameterized meta-learning.  In _Proc. of Advances in Neural Information Processing Systems_ , volume 34, 2021.
  * Tatli et al. (2022) Gokcan Tatli, Rob Nowak, and Ramya Korlakai Vinayak.  Learning preference distributions from distance measurements.  In _2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 1–8. IEEE, 2022.
  * Ustun et al. (2019) Berk Ustun, Yang Liu, and David Parkes.  Fairness without harm: Decoupled classifiers with preference guarantees.  In _International Conference on Machine Learning_ , pages 6373–6382. PMLR, 2019.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Zhang et al. (2019) Xueru Zhang, Mohammadmahdi Khaliligarekani, Cem Tekin, and Mingyan Liu.  Group retention when using machine learning in sequential decision making: the interplay between user dynamics and fairness.  _Advances in Neural Information Processing Systems_ , 32, 2019.

##  Appendix A Mappings satisfying Assumptions 1 and 2

In this appendix, we provide more details on examples that satisfy Assumptions
1 and 2. For the squared error loss for linear predictors, we refer the reader
to Lemma 5 for a derivation of $c_{ij}$. The remainder of the example classes
are detailed below.

###  A.1 Huber Loss

Recall that the Huber loss is defined by

$\mathcal{L}_{i}(\theta,\phi_{i})=\begin{cases}\frac{1}{2}\|\theta-\phi_{i}\|^{2}&\text{if
}\|\theta-\phi_{i}\|\leq\delta,\\\
\delta(\|\theta-\phi_{i}\|-\frac{1}{2}\delta)&\text{otherwise}.\end{cases}$

Note that the Huber loss varies quadratically when the error
$\|\theta-\phi_{i}\|\leq\delta$ and linearly otherwise. We will refer to these
as quadratic and linear regime of the Huber loss subsequently.

We divide the derivation into 2 subcases.

Case 1. $\|\theta-\phi_{i}\|\leq 2\delta$. Within Case 1, there are several
subcases to consider. We analyze each one separately.

  * •

At least one of the terms on the right is linear: Under the condition of Case
1, $\mathcal{L}_{i}(\theta,\phi_{i})\leq\frac{3}{2}\delta^{2}$. Note that the
Huber loss is monotonicly increasing in the prediction error. The function
value in the linear in $\|\theta-\phi_{i}\|$ is at least
$\frac{1}{2}\delta^{2}$. Thus, if one of the terms in
$\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j})$ were in
the linear regime, the
$\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j})\geq\frac{1}{2}\delta^{2}$
and
$\frac{1}{3}\mathcal{L}_{i}(\theta,\phi_{i})\leq\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j})$.

  * •

Both terms on the right are quadratic: In this sub-case, it needs to be shown
when both terms of
$\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j})$ are in
the quadratic regime the bound still holds.

By the triangle inequality on norms, we have that

$\displaystyle\|\theta-\phi_{i}\|\leq\|\theta-\phi_{j}\|+\|\phi_{i}-\phi_{j}\|.$

Using the power mean inequality, namely

$a\leq b+c\implies a^{2}\leq 2(b^{2}+c^{2}),$

on the triangle inequality, we deduce the following implication:

$\displaystyle\|\theta-\phi_{i}\|\leq\|\theta-\phi_{j}\|+\|\phi_{i}-\phi_{j}\|\
\implies\
\frac{1}{2}\|\theta-\phi_{i}\|^{2}\leq\|\theta-\phi_{j}\|^{2}+\|\phi_{i}-\phi_{j}\|^{2}.$

If the $\mathcal{L}_{i}(\theta,\phi_{i})$ is quadratic, we have that
$\frac{1}{2}\mathcal{L}_{i}(\theta,\phi_{i})\leq\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j})$.
Now, let $\mathcal{L}_{i}(\theta,\phi_{i})$ be linear. Then, we deduce that

$\displaystyle\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j})=\frac{1}{2}(\|\theta-\phi_{j}\|^{2}+\|\phi_{i}-\phi_{j}\|^{2})\geq\frac{1}{4}\|\theta-\phi_{i}\|^{2}.$

Since the equation $\frac{1}{4}x^{2}-\frac{1}{3}x+\frac{1}{6}=0$ has no real
roots, the expression is always positive. Hence, by substituting
$x=\frac{\|\theta-\phi_{i}\|}{\delta}$, we have that

$\displaystyle\frac{1}{4}\|\theta-\phi_{i}\|^{2}\geq\frac{1}{3}\delta(\|\theta-\phi_{i}\|-\frac{1}{2}\delta)=\frac{1}{3}\mathcal{L}_{i}(\theta,\phi_{i}).$

Therefore, we deduce that

$\frac{1}{3}\mathcal{L}_{i}(\theta,\phi_{i})\leq\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j}).$

Case 2. $\|\theta-\phi_{i}\|>2\delta$. First, observe that

$\displaystyle\frac{1}{3}\mathcal{L}_{i}(\theta,\phi_{i})$
$\displaystyle=\frac{1}{3}\delta(\|\theta-\phi_{i}\|-\frac{1}{2}\delta)$
$\displaystyle=\frac{1}{3}\delta\|\theta-\phi_{i}\|+\frac{1}{6}\delta\|\theta-\phi_{i}\|-\frac{1}{6}\delta\|\theta-\phi_{i}\|-\frac{1}{6}\delta^{2}$
$\displaystyle\leq\frac{1}{3}\delta\|\theta-\phi_{i}\|+\frac{1}{6}\delta\|\theta-\phi_{i}\|-\frac{1}{3}\delta^{2}-\frac{1}{6}\delta^{2}$
$\displaystyle\leq\frac{1}{2}\delta\|\theta-\phi_{i}\|-\frac{1}{2}\delta^{2},$

where the second to last inequality follows from the fact that
$\|\theta-\phi_{i}\|>2\delta$. By the triangle inequality on norms, we have
that

$\displaystyle\|\theta-\phi_{i}\|\leq\|\theta-\phi_{j}\|+\|\phi_{i}-\phi_{j}\|.$

In turn, this implies either $\|\theta-\phi_{j}\|$ or $\|\phi_{i}-\phi_{j}\|$
is greater than $\frac{1}{2}\|\theta-\phi_{i}\|$. Without loss of generality,
assume $\|\theta-\phi_{j}\|\geq\frac{1}{2}\|\theta-\phi_{i}\|\geq\delta$. Thus

$L_{j}(\theta,\phi_{j})=\delta(\|\theta-\phi_{j}\|-\frac{1}{2}\delta)\geq\frac{1}{2}\delta\|\theta-\phi_{i}\|-\frac{1}{2}\delta^{2}\geq\frac{1}{3}\mathcal{L}_{i}(\theta,\phi_{i}).$

Since $\mathcal{L}_{j}(\phi_{i},\phi_{j})\geq 0$, we have that

$\displaystyle\frac{1}{3}\mathcal{L}_{i}(\theta,\phi_{i})\leq\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{j}(\phi_{i},\phi_{j}).$

###  A.2 The normalized cosine distance

Recall that the normalized cosine distance is given by

$\mathcal{L}_{i}(\theta,\phi_{i})=1-\theta^{\top}\phi_{i}\quad\text{where}\quad\|\theta\|_{2}=\|\phi_{i}\|_{2}=1.$

Therefore, we have that

$\displaystyle
1-\theta^{\top}\phi_{i}=\frac{1}{2}(\|\theta\|_{2}^{2}+\|\phi_{i}\|_{2}^{2}-2\theta^{\top}\phi_{i})=\frac{1}{2}\|\theta-\phi\|_{2}^{2}.$

Assumption 2 is satisfied with $c_{ij}=\frac{1}{2}$ by using triangle
inequality followed by power mean inequality.

###  A.3 Mahalanobis distance

Consider the Mahalanobis distance which is defined by

$\mathcal{L}_{i}(\theta,\phi_{i})=\|\theta-\phi_{i}\|_{\Sigma_{i}},$

where $\Sigma_{i}$ is full rank and $c_{ij}=\min\\{\lambda_{\rm
min}(\Sigma_{i},\Sigma_{j}),\frac{1}{\lambda_{\rm
min}(\Sigma_{i},\Sigma_{j})}\\}$. The derivation is similar to proof of Lemma
5.

##  Appendix B Proof of Theorem 1

We note that the parameters of the services initialized by Algorithm 1 are a
subset of the users’ unknown preferences. This allows us to define the notion
of covering.

######  Definition B.1.

Let $\Theta\subset\\{\phi_{1},\ldots,\phi_{n}\\}$ be a set of services. A
cluster $\mathcal{B}\in\mathcal{C}(\Theta_{\rm OPT})$ is said to be covered by
$\Theta$ if there exists $i\in\mathcal{B}$ such that $\phi_{i}\in\Theta$. If
no such $i\in\mathcal{B}$ exists, then the cluster $\mathcal{B}$ is said to be
uncovered.

The proof idea from here on is to show that there exists an approximation
ratio $K_{\rm OPT}$ for the covered clusters, and is shown in Lemma 1 and 2.

######  Lemma 1.

Let $\mathcal{B}\in\mathcal{C}(\Theta_{\rm OPT})$ be an arbitrary cluster in
$\mathcal{C}(\Theta_{\rm OPT})$, and let $\theta\in\mathbb{R}^{d}$ be a
service centered on the preference of a user $j$ chosen uniformly at random
from $[n]$. The expected loss of users in $\mathcal{B}$, conditioned on
$j\in\mathcal{B}$, satisfies

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\\{\theta=\phi_{j}\\},\mathcal{B})\;|\;j\in\mathcal{B}]\leq\left(\max_{j\in\mathcal{B}}\frac{2}{|\mathcal{B}|}\sum_{i}\frac{1}{c_{ij}}\right)\mathcal{L}(\Theta_{\rm
OPT},\mathcal{B}).$

###### Proof.

Since we choose a user from $\mathcal{B}$, the conditional probability that we
choose some fixed $\phi_{j}$ as the parameter for the service is precisely
$P(\theta=\phi_{j}\;|\;\theta\in\mathcal{B})=\frac{1}{|\mathcal{B}|}$. Let
$\mathcal{J}(\mathcal{B})$ denote the best service covering all the points in
$\mathcal{B}$, and then compute

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\\{\theta=\phi_{j}\\},\mathcal{B})\;|\;j\in\mathcal{B}]=\sum_{j\in\mathcal{B}}P(\theta=\phi_{j})\mathcal{L}(\theta,\mathcal{B})=\sum_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\phi_{j},\phi_{i}).$

Using Assumption 2.(ii) with $\theta=\mathcal{J}(\mathcal{B})$, we have that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\\{\theta=\phi_{j}\\},\mathcal{B})\;|\;j\in\mathcal{B}]$
$\displaystyle\leq\sum_{j\in\mathcal{B}}\sum_{i\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\left(\frac{1}{c_{ij}}\left(\mathcal{L}_{j}(\mathcal{J}(\mathcal{B}),\phi_{j})+\mathcal{L}_{i}(\mathcal{J}(\mathcal{B}),\phi_{i})\right)\right),$
$\displaystyle=\sum_{j\in\mathcal{B}}\left(\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\frac{1}{c_{ij}}\right)\mathcal{L}_{j}(\mathcal{J}(\mathcal{B}),\phi_{j})+\sum_{i\in\mathcal{B}}\left(\frac{1}{|\mathcal{B}|}\sum_{j\in\mathcal{B}}\frac{1}{c_{ij}}\right)\mathcal{L}_{i}(\mathcal{J}(\mathcal{B}),\phi_{i}).$

Noting that $c_{ij}=c_{ji}$, by swapping the indices of the second term in the
above summand, the second term is identical to the first term. Therefore, we
deduce that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\\{\theta=\phi_{j}\\},\mathcal{B})\;|\;j\in\mathcal{B}]\leq
2\sum_{j\in\mathcal{B}}\left(\left(\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\frac{1}{c_{ij}}\right)\mathcal{L}_{j}(\mathcal{J}(\mathcal{B}),\phi_{j})\right).$

Now, using the fact that
$\max_{j\in\mathcal{B}}\left(\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\frac{1}{c_{ij}}\right)$
is a uniform upper bound for the multiplier in the above expression, we bring
it outside the summation as a constant. Therefore, we deduce that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\\{\theta=\phi_{j}\\},\mathcal{B})\;|\;j\in\mathcal{B}]\leq\left(\max_{j\in\mathcal{B}}\frac{2}{|\mathcal{B}|}\sum_{i}\frac{1}{c_{ij}}\right)\mathcal{L}(\mathcal{J}(\mathcal{B}),\mathcal{B}),$
(5)

where we have used the fact that
$\mathcal{L}(\mathcal{J}(\mathcal{B}),\mathcal{B})=\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\mathcal{J}(\mathcal{B}),\phi_{i})$.
Since $\mathcal{B}\in\mathcal{C}(\Theta_{\rm OPT})$, the covering
$\mathcal{J(B)}$ is the loss minimizing service among all services in
$\Theta_{\rm OPT}$ for all points in $\mathcal{B}$. Thus, we have that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\\{\theta=\phi_{j}\\},\mathcal{B})\;|\;j\in\mathcal{B}]\leq\left(\max_{j\in\mathcal{B}}\frac{2}{|\mathcal{B}|}\sum_{i}\frac{1}{c_{ij}}\right)\mathcal{L}(\Theta_{\rm
OPT},\mathcal{B}).$

This concludes the proof. ∎

######  Lemma 2.

Let $\mathcal{B}\in\mathcal{C}(\Theta_{\rm OPT})$ be an arbitrary cluster in
$\mathcal{C}(\Theta_{\rm OPT})$, and let $\Theta_{t}\subset\mathbb{R}^{d}$
denote the parameters for a set of preexisting $t$ arbitrary services.
Consider a new clustering $\Theta_{t+1}=\Theta_{t}\cup\theta$ where
$\theta=\phi_{j}$ is a random service centered on user $j\in[n]$ selected with
probability $P(\theta=\phi_{j})\propto\mathcal{L}_{j}(\Theta_{t},\phi_{j})$.
Then, the expected loss of $\mathcal{B}$, conditioned on $j\in\mathcal{B}$,
satisfies

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\Theta_{t}\cup(\theta=\phi_{j}),\mathcal{B})\;|\;j\in\mathcal{B}]\leq\frac{1}{\min_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}c_{ji}}\left(\max_{j\in\mathcal{B}}\frac{2}{|\mathcal{B}|}\sum_{i}\frac{1}{c_{ij}}\right)\mathcal{L}(\Theta_{\rm
OPT},\mathcal{B}).$

###### Proof.

Given that we are choosing a user from $\mathcal{B}$, the conditional
probability that we center the new service on some fixed $\phi_{j}$ is
precisely
$\mathcal{L}(\Theta_{t},\phi_{j})/(\sum_{i\in\mathcal{B}}\mathcal{L}(\Theta_{t},\phi_{i}))$.
After adding $\phi_{j}$ to the list of services, a user $i$ will have loss
$\min\\{\mathcal{L}_{i}(\Theta_{t},\phi_{i}),\mathcal{L}_{i}(\phi_{j},\phi_{i})\\}$.
Therefore we deduce that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\Theta_{t}\cup(\theta=\phi_{j}),\mathcal{B})\;|\;j\in\mathcal{B}]$
$\displaystyle=\sum_{j\in\mathcal{B}}P(\theta=\phi_{j}|\;\theta\in\mathcal{B})\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\Theta_{t}\cup\theta,\phi_{i}),$
(6)
$\displaystyle=\sum_{j\in\mathcal{B}}\frac{\mathcal{L}_{j}(\Theta_{t},\phi_{j})}{\sum_{l\in\mathcal{B}}\mathcal{L}_{l}(\Theta_{t},\phi_{l})}\sum_{i\in\mathcal{B}}\min\\{\mathcal{L}_{i}(\Theta_{t},\phi_{i}),\mathcal{L}_{i}(\phi_{j},\phi_{i})\\}.$

By Assumption 2.$(i)$, for any $\theta\in\mathbb{R}^{d}$ we have that

$\displaystyle
c_{ji}\mathcal{L}_{j}(\theta,\phi_{j})\leq\mathcal{L}_{i}(\theta,\phi_{i})+\mathcal{L}_{i}(\phi_{j},\phi_{i}).$

We utilize the fact that given two functions
$f,g:\Theta\rightarrow\mathbb{R}$, if $f(\theta)\leq
g(\theta)\;\forall\theta\in\Theta$, then
$\min_{\theta\in\Theta}f(\theta)\leq\min_{\theta\in\Theta}g(\theta)$. Hence,
the following implication holds:

$\displaystyle
c_{ji}\min_{\theta\in\Theta}\mathcal{L}_{j}(\theta,\phi_{j})\leq\min_{\theta\in\Theta}\mathcal{L}_{i}(\theta,\phi_{i})+\mathcal{L}_{i}(\phi_{j},\phi_{i})\
\implies\
c_{ji}\mathcal{L}_{j}(\Theta_{t},\phi_{j})\leq\mathcal{L}_{i}(\Theta_{t},\phi_{i})+\mathcal{L}_{i}(\phi_{j},\phi_{i}).$

Summing over all $i\in\mathcal{B}$, we get that

$\displaystyle\mathcal{L}_{j}(\Theta_{t},\phi_{j})\leq\frac{1}{\sum_{i\in\mathcal{B}}c_{ji}}\left(\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\Theta_{t},\phi_{i})+\mathcal{L}_{i}(\phi_{j},\phi_{i})\right)$

Applying this to $\mathcal{L}_{j}(\Theta_{t},\phi_{j})$ on the right hand side
of (6), we have that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\Theta_{t}\cup(\theta=\phi_{j}),\mathcal{B})\;|\;j\in\mathcal{B}]$
$\displaystyle\leq\sum_{j\in\mathcal{B}}\frac{1}{\sum_{i\in\mathcal{B}}c_{ji}}\left(1+\frac{\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\phi_{j},\phi_{i})}{\sum_{l\in\mathcal{B}}\mathcal{L}_{l}(\Theta_{t},\phi_{l})}\right)\sum_{i\in\mathcal{B}}\min\\{\mathcal{L}_{i}(\Theta_{t},\phi_{i}),\mathcal{L}_{i}(\phi_{j},\phi_{i})\\}.$

Since $\min\\{a,b\\}\leq a$, we further deduce that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\Theta_{t}\cup(\theta=\phi_{j}),\mathcal{B})\;|\;j\in\mathcal{B}]$
$\displaystyle\leq\sum_{j\in\mathcal{B}}\frac{1}{\sum_{i\in\mathcal{B}}c_{ji}}\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\phi_{j},\phi_{i})$
$\displaystyle\qquad+\sum_{j\in\mathcal{B}}\frac{1}{\sum_{i\in\mathcal{B}}c_{ji}}\frac{\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\phi_{j},\phi_{i})}{\sum_{l\in\mathcal{B}}\mathcal{L}_{l}(\Theta_{t},\phi_{l})}\sum_{i\in\mathcal{B}}\mathcal{L}(\Theta_{t},\phi_{i}),$
$\displaystyle=\sum_{j\in\mathcal{B}}\frac{2}{\sum_{i\in\mathcal{B}}c_{ij}}\sum_{i\in\mathcal{B}}\mathcal{L}_{i}(\phi_{j},\phi_{i}).$

Now, we use the upper bound
$\frac{1}{\min_{j\in\mathcal{B}}\sum_{i\in\mathcal{B}}c_{ji}}$ for the
multiplier to get

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\Theta_{t}\cup(\theta=\phi_{j}),\mathcal{B})\;|\;j\in\mathcal{B}]\leq\frac{2}{\frac{1}{|\mathcal{B}|}\min_{j\in\mathcal{B}}\sum_{i\in\mathcal{B}}c_{ji}}\sum_{j\in\mathcal{B}}\sum_{i\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\mathcal{L}_{i}(\phi_{j},\phi_{i}).$

Note that
$\sum_{j\in\mathcal{B}}\sum_{i\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\mathcal{L}_{i}(\phi_{j},\phi_{i})$
is essentially the loss on choosing users from $\mathcal{B}$ uniformly
randomly and centering the service on the chosen user. Plugging in the
expression in (5) from the proof of Lemma 1, we have that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\Theta_{t}\cup(\theta=\phi_{j}),\mathcal{B})\;|\;j\in\mathcal{B}]\leq\frac{4}{\min\limits_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum\limits_{i\in\mathcal{B}}c_{ji}}\left(\max_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\frac{1}{c_{ij}}\right)\mathcal{L}(\mathcal{J}(\mathcal{B}),\mathcal{B}).$
(7)

Since $\mathcal{B}\in\mathcal{C}(\Theta_{\rm OPT})$, the covering
$\mathcal{J(B)}$ is the loss minimizing service among all available services
in $\Theta_{\rm OPT}$ for all points in $\mathcal{B}$. Therefore, we deduce
that

$\displaystyle\mathbb{E}_{\theta}[\mathcal{L}(\Theta_{t}\cup(\theta=\phi_{j}),\mathcal{B})\;|\;j\in\mathcal{B}]\leq\frac{4}{\min\limits_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum\limits_{i\in\mathcal{B}}c_{ji}}\left(\max_{j\in\mathcal{B}}\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\frac{1}{c_{ij}}\right)\mathcal{L}(\Theta_{\rm
OPT},\mathcal{B}),$

which concludes the proof. ∎

The following Lemma is an induction relating the losses on covered and
uncovered clusters.

######  Lemma 3.

Let $\Theta_{t}\subset\mathbb{R}^{d}$ denote the parameters of a set of $t$
arbitrary services. Consider $u>0$ _uncovered_ clusters from
$\mathcal{C}(\Theta_{\rm OPT})$, denoted by $\mathcal{U}_{t}$, and let
$\mathcal{H}_{t}$ denote the covered clusters. Suppose we add $v\leq u$ random
services to $\Theta_{t}$, chosen with probability proportional to their
current loss—i.e., $\mathcal{L}(\Theta_{t},\phi_{j})$—and let $\Theta_{t+v}$
denote the the resulting set of services. The following estimate holds:

$\displaystyle\mathbb{E}_{\Theta_{t+v}}[\mathcal{L}(\Theta_{t+v},[n])]\leq\left(\mathbb{E}_{\Theta_{t}}[\mathcal{L}\left(\Theta_{t},\mathcal{H}_{t}\right)]+K_{\rm
OPT}\cdot\mathcal{L}\left(\Theta_{\rm
OPT},\mathcal{U}_{t}\right)\right)\cdot\left(1+S_{v}\right)+\frac{u-v}{u}\cdot\mathbb{E}_{\Theta_{t}}[\mathcal{L}\left(\Theta_{t},\mathcal{U}_{t}\right)],$

where $K_{\rm OPT}$ is as defined in (2) and
$S_{v}=\left(1+\frac{1}{2}+\ldots+\frac{1}{v}\right)$ is the harmonic series.

###### Proof.

Replacing the factor 8 in Lemma 3.3 from (Arthur and Vassilvitskii, 2007) by
$K_{\rm OPT}$ gives us the desired result.

∎

With the preceding technical lemmas, we are now ready to prove the main
theorem which we restate for convenience. See 1

###### Proof.

Consider $t=1$, and $\mathcal{B}\in\mathcal{C}(\Theta_{\rm OPT})$, the cluster
in which the first chosen user belongs. Applying Lemma 3 with $v=u=k-1$ and
the fact that $\mathcal{B}$ is the only covered cluster, we have that

$\displaystyle\mathbb{E}_{\Theta_{k}}[\mathcal{L}(\Theta_{k},[n])]\leq\left(\mathbb{E}_{\Theta_{1}}[\mathcal{L}\left(\Theta_{1},\mathcal{B}\right)]+K_{\rm
OPT}\cdot\mathcal{L}\left(\Theta_{\rm
OPT},[n]-\mathcal{B}\right)\right)\cdot\left(1+S_{k-1}\right).$

Observe that

$\displaystyle\mathbb{E}_{\Theta_{1}}[\mathcal{L}\left(\Theta_{1},\mathcal{B}\right)]$
$\displaystyle\leq K_{\rm OPT}\cdot\mathcal{L}\left(\Theta_{\rm
OPT},\mathcal{B}\right)],$

by Lemma 1. Moreover, we have that

$\mathcal{L}\left(\Theta_{\rm
OPT},[n]-\mathcal{B}\right)=\mathcal{L}\left(\Theta_{\rm
OPT},[n]\right)-\mathcal{L}\left(\Theta_{\rm OPT},\mathcal{B}\right).$

Using these two expression and noting $S_{k-1}\leq 1+\log k$, we get the
stated result. ∎

##  Appendix C Fair Initialization

See 2

###### Proof.

For any $\Theta\subset\mathbb{R}^{d}$, we have that

$\displaystyle\Phi(\Theta,\mathcal{A})$
$\displaystyle=\max_{i\in[m]}\frac{\mathcal{L}(\Theta,\mathcal{A}_{i})}{|\mathcal{A}_{i}|}\leq\frac{1}{\min_{i\in[m]}|\mathcal{A}_{i}|}\sum_{i\in[m]}\mathcal{L}(\Theta,\mathcal{A}_{i})=\frac{1}{\min_{i\in[m]}|\mathcal{A}_{i}|}\mathcal{L}(\Theta,[n]).$

This implies for $\Theta_{k}$ the output of Algorithm 1, we have that

$\displaystyle\mathbb{E}_{\Theta_{k}}[\Phi(\Theta_{k},\mathcal{A})]\leq\frac{1}{\min_{i\in[m]}|\mathcal{A}_{i}|}\mathbb{E}_{\Theta_{k}}[\mathcal{L}(\Theta_{k},[n])].$

Hence, we have that

$\displaystyle\mathcal{L}(\Theta_{\rm fair},[n])$
$\displaystyle=\sum_{i\in[m]}\mathcal{L}(\Theta_{\rm
fair},\mathcal{A}_{i})\leq\max_{i\in[m]}|\mathcal{A}_{i}|\sum_{i\in[m]}\max_{i\in[m]}\frac{\mathcal{L}(\Theta_{\rm
fair},\mathcal{A}_{i})}{|\mathcal{A}_{i}|}=\max_{i\in[m]}|\mathcal{A}_{i}|m\cdot\Phi(\Theta_{\rm
fair},\mathcal{A}).$

Now, since $\Theta_{\rm OPT}$ is the minimizer of $\mathcal{L}(\cdot,[n])$ and
$\Theta_{\rm fair}$ the minimizer of $\Phi(\cdot,\mathcal{A})$, we have that

$\displaystyle\mathcal{L}(\Theta_{\rm OPT},[n])$
$\displaystyle\leq\max_{i\in[m]}|\mathcal{A}_{i}|m\cdot\Phi(\Theta_{\rm
fair},\mathcal{A})$
$\displaystyle\leq\max_{i\in[m]}|\mathcal{A}_{i}|m\cdot\mathbb{E}_{\Theta_{k}}[\Phi(\Theta_{k},\mathcal{A})]$
$\displaystyle\leq\frac{\max_{i\in[m]}|\mathcal{A}_{i}|}{\min_{i\in[m]}|\mathcal{A}_{i}|}m\cdot\mathbb{E}_{\Theta_{k}}[\mathcal{L}(\Theta_{k},[n])].$

Using Theorem 1 for the guarantee on $\Theta_{k}$, we conclude the proof. ∎

###  C.1 What if User Demographic Identities are known?

We assume the scenario when the user demographic identities are known _a
priori_. Let $\gamma:[n]\rightarrow\mathcal{A}$ be a mapping, which maps a
user $i$ to its demographic group $\gamma(i)$, and let $|\gamma(i)|$ denote
the size of the demographic group user $i$ belongs to.

We define the weighted total loss (where each users’ loss is divided by its
group size) as:

$\displaystyle\mathcal{G}(\Theta,[n])$
$\displaystyle=\sum_{i\in[n]}\frac{\mathcal{L}_{i}(\Theta,\phi_{i})}{|\gamma(i)|}=\sum_{i\in[m]}\frac{\mathcal{L}(\Theta,\mathcal{A}_{i})}{|\mathcal{A}_{i}|}.$

Note that this can also be interpreted as the sum of average losses across
different demographic groups.

We introduce Algorithm 2 with a couple of changes from Algorithm 1.

  * •

Instead of uniformly picking a user at random, we are picking a user $i$ with
probability proportional to $\frac{1}{|\gamma(i)|}$. This is equivalent to
saying, the probability of the first user being in some group
$\mathcal{A}_{j}\in\mathcal{A}$ is

$\frac{\sum_{i\in\mathcal{A}_{j}}\frac{1}{|\gamma(i)|}}{\sum_{j\in[m]}\sum_{i\in\mathcal{A}_{j}}\frac{1}{|\gamma(i)|}}=\frac{1}{m}.$

That is, the first user is equally likely to belong to one of the $m$ groups.

  * •

A user $i$ at any time step $t$ is selected with probability proportional to
$\mathcal{L}_{i}(\Theta_{t-1},\phi_{i})/|\gamma(i)|$. This implies that a user
from some group $\mathcal{A}_{j}\in\mathcal{A}$ is likely to be picked with
probability proportional to the average demographic loss—i.e.,

$\sum_{i\in\mathcal{A}_{j}}\mathcal{L}_{i}(\Theta_{t-1},\phi_{i})/|\gamma(i)|=\frac{\mathcal{L}(\Theta_{t-1},\mathcal{A}_{j})}{|\mathcal{A}_{j}|}.$

We first state the approximation ratio of Algorithm 2 on the objective
$\mathcal{G}(\Theta,[n])$.

######  Lemma 4.

Consider $n$ users with unknown preferences
$\\{\phi_{1},\ldots,\phi_{n}\\}\subset\mathbb{R}^{d}$, and unknown associated
loss functions $\mathcal{L}_{i}(\cdot,\cdot)$ satisfying Assumptions 1 and 2.
Let $\Theta_{\rm scaled}\subset\mathbb{R}^{d}$ be the set of $k$ services
minimizing the total loss and $\mathcal{C}(\Theta_{\rm scaled})$ the resulting
partitioning of users. If Algorithm 2 is used to obtain $k$ services
$\Theta_{k}$, then the following bound holds:

$\displaystyle\mathbb{E}_{\Theta_{k}}[\mathcal{G}(\Theta_{k},[n])]$
$\displaystyle\leq K_{\rm fair}(2+\log k)\cdot\mathcal{G}(\Theta_{\rm
scaled},[n]),$

where the expectation is taken over the randomization of the algorithm and
$K_{\rm fair}$ is equal to

$\max_{\mathcal{B}\in\mathcal{C}(\Theta_{\rm
scaled})}\frac{4}{\min\limits_{j\in\mathcal{B}}\sum\limits_{i\in\mathcal{B}}\frac{c_{ij}}{|\gamma(i)|}}\left(\max_{j\in\mathcal{B}}\sum_{i\in\mathcal{B}}\frac{1}{c_{ij}|\gamma(i)|}\right).$
(8)

The proof is similar as Theorem 1, with the introduction of
$\frac{1}{|\gamma(i)|}$’s when deriving Lemma 1 and 2.

Algorithm 2 Fair AcQUIre- Fair Adaptively Querying Users for Initialization

1: Input: Set of users $[n]$, number of services $k$, Demographic groups
$\mathcal{A}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{m}\\}$, Map users to
demographic groups $\gamma:[n]\rightarrow\mathcal{A}$

2: Choose a user $i$ uniformly randomly from $[n]$ with probability
$\propto\frac{1}{|\gamma(i)|}$.

3: Query user $i$’s preference $\phi_{i}$, set the first service
$\Theta_{1}=\phi_{i}$.

4: for $t\in\\{2,\ldots,k\\}$ do

5: User behavior: Collect user losses on existing services $\Theta_{t-1}$ :
{$\mathcal{L}_{i}(\Theta_{t-1},\phi_{i})\\}_{i\in[n]}$.

6: User Selection: Sample $l$ from $[n]$ with probability
$P(l=i)\propto\mathcal{L}_{i}(\Theta_{t-1},\phi_{i})/|\gamma(i)|$.

7: New service: Query user $l$’s preference $\phi_{l}$.

8: $\Theta_{t}=\Theta_{t-1}\cup\phi_{l}$.

9: end for

10: Return $\Theta_{k}$

######  Theorem 4.

Consider $n$ users with unknown preferences
$\\{\phi_{1},\ldots,\phi_{n}\\}\subset\mathbb{R}^{d}$, and unknown associated
loss functions $\mathcal{L}_{i}(\cdot,\cdot)$ satisfying Assumptions 1 and 2.
Suppose these users belong to $m$ demographic groups
$\mathcal{A}=\\{\mathcal{A}_{1},\ldots,\mathcal{A}_{m}\\}\subset[n]$. Let
$\Theta_{\rm fair}\subset\mathbb{R}^{d}$ be the set of $k$ services minimizing
the fairness objective $\Phi$ given in (3). If Algorithm 2 is used to obtain
$k$ services $\Theta_{k}$, then the following bound holds:

$\displaystyle\mathbb{E}_{\Theta_{k}}[\Phi(\Theta_{k},\mathcal{A})]\leq
mK_{\rm fair}(2+\log k)\cdot\Phi(\Theta_{\rm fair},\mathcal{A}),$

where the expectation is taken over the randomization of the algorithm and
$K_{\rm fair}$ is defined in (8).

###### Proof.

For any $\Theta\subset\mathbb{R}^{d}$, we have that

$\displaystyle\Phi(\Theta,\mathcal{A})$
$\displaystyle=\max_{i\in[m]}\frac{\mathcal{L}(\Theta,\mathcal{A}_{i})}{|\mathcal{A}_{i}|}\leq\sum_{i\in[m]}\frac{\mathcal{L}(\Theta,\mathcal{A}_{i})}{|\mathcal{A}_{i}|}=\mathcal{G}(\Theta,[n]).$

For $\Theta_{k}$—namely the output of Algorithm 1—the above expression implies
that

$\displaystyle\mathbb{E}_{\Theta_{k}}[\Phi(\Theta_{k},\mathcal{A})]\leq\mathbb{E}_{\Theta_{k}}[\mathcal{G}(\Theta_{k},[n])].$

We also have that

$\displaystyle\mathcal{G}(\Theta_{\rm fair},[n])$
$\displaystyle=\sum_{i\in[m]}\frac{\mathcal{L}(\Theta_{\rm
fair},\mathcal{A}_{i})}{|\mathcal{A}_{i}|}\leq\sum_{i\in[m]}\max_{i\in[m]}\frac{\mathcal{L}(\Theta_{\rm
fair},\mathcal{A}_{i})}{|\mathcal{A}_{i}|}=m\cdot\Phi(\Theta_{\rm
fair},\mathcal{A}).$

Let $\Theta_{\rm scaled}$ be the minimizer of $\mathcal{G}(\cdot,[n])$ and
$\Theta_{\rm fair}$ be the minimizer of $\Phi(\cdot,\mathcal{A})$. Then, we
have that

$\displaystyle\mathcal{G}(\Theta_{\rm scaled},[n])\leq\mathcal{G}(\Theta_{\rm
fair},[n])\leq m\cdot\Phi(\Theta_{\rm fair},\mathcal{A})\leq
m\cdot\mathbb{E}_{\Theta_{k}}[\Phi(\Theta_{k},\mathcal{A})]\leq
m\cdot\mathbb{E}_{\Theta_{k}}[\mathcal{G}(\Theta_{k},[n])].$

Now using Lemma 4 for the guarantee on $\Theta_{k}$ for
$\mathcal{G}(\cdot,[n])$, we conclude the proof. ∎

######  Remark 2.

If all $c_{ij}$’s are identically equal to some $c>0$, $K_{\rm
fair}=\frac{4}{c^{2}}$ and the approximation ratio of Algorithm 2 for the fair
objective is $4m(2+\log k)/c^{2}$. Meanwhile, Algorithm 1 would have an
approximation ratio

$4m\cdot\frac{\max_{i\in[m]}|\mathcal{A}_{i}|}{\min_{i\in[m]}|\mathcal{A}_{i}|}\cdot\frac{(2+\log
k)}{c^{2}}.$

##  Appendix D Proof of Theorem 3

Let the empirical loss—which is a finite sample average regression loss—be
denoted

$\widehat{\mathcal{L}}_{i}(\theta,\phi_{i})=\frac{1}{n_{i}}\sum_{j\in[n_{i}]}(\theta^{\top}x_{i}^{j}-y_{i}^{j})^{2},$

where $\\{(x_{i}^{j},y_{i}^{j})\\}_{j\in[n_{i}]}$ are private unknown features
and scores of the users, respectively.

######  Lemma 5.

Under Assumptions 3 and 5, each subpopulation empirical loss
$\widehat{\mathcal{L}}_{i}$ satisfies Assumption 1 and Assumption 2 with

$\displaystyle
c_{ij}=\frac{1}{2}\lambda_{\mathrm{min}}\left(\frac{\sum_{l\in[n_{i}]}x_{i}^{l}(x_{i}^{l})^{\top}}{n_{i}},\frac{\sum_{l\in[n_{j}]}x_{j}^{l}(x_{j}^{l})^{\top}}{n_{j}}\right).$

###### Proof.

Fix a subpopulation index $i$. We start by showing $\widehat{\mathcal{L}}_{i}$
satisfies Assumption 1. We use the following result: if $p\leq d$ random
vectors in $\mathbb{R}^{d}$ are independently drawn from a distribution that
is absolutely continuous with respect to the Lebesgue measure, then they are
almost surely linearly independent. By Assumption 5, applying this result to
our scenario, if we draw $n_{i}\geq d$ features independently from a sub-
Gaussian distribution to form a feature matrix
$\mathbf{X}_{i}\in\mathbb{R}^{n_{i}\times d}$, then it is almost surely full
column rank.

Therefore, we compute $\phi_{i}=\mathbf{X}_{i}^{\dagger}y_{i}$ since
$\mathbf{X}_{i}^{\dagger}\mathbf{X}_{i}=\mathbf{I}_{p}$ when $\mathbf{X}_{i}$
is full column rank. The subpopulation $i$’s empirical loss is compactly
written as
$\widehat{\mathcal{L}}_{i}(\theta,\phi_{i})=\|\theta-\phi_{i}\|_{\mathbf{A}_{i}}^{2}$,
where
$\mathbf{A}_{i}=\frac{1}{n_{i}}\sum_{l\in[n_{i}]}x_{i}^{l}(x_{i}^{l})^{\top}$.
Thus $\widehat{\mathcal{L}}_{i}(\theta,\phi_{i})$ satisfies Assumption 1.

We now show that $\widehat{\mathcal{L}}_{i}$ satisfies Assumption 2 with
$c_{ij}=\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})$. To this
end, we find the largest $c\in\mathbb{R}_{+}$ such that
$c(u^{\top}\mathbf{A}_{i}u)\leq u^{\top}\mathbf{A}_{j}u$ and
$c(u^{\top}\mathbf{A}_{j}u)\leq u^{\top}\mathbf{A}_{i}u$ for all
$u\in\mathbb{R}^{d}$.

Rearranging the inequality, this problem is the same as finding the largest
$c\in\mathbb{R}_{+}$ such that

$u^{\top}(\mathbf{A}_{i}-c\mathbf{A}_{j})u\geq
0\quad\text{and}\quad\mathbf{A}_{j}-c\mathbf{A}_{i})u\geq 0\quad\forall\
u\in\mathbb{R}^{d},$

or equivalently,

$\mathbf{A}_{i}-c\mathbf{A}_{j}\succeq
0\quad\text{and}\quad\mathbf{A}_{j}-c\mathbf{A}_{i}\succeq 0.$

Therefore, finding such a constant $c$ is easily reformulated as the following
optimization problem:

$\displaystyle\max\\{c~{}|\ \mathbf{A}_{i}-c\mathbf{A}_{j}\succeq
0,\mathbf{A}_{j}-c\mathbf{A}_{i}\succeq
0\\}=\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j}).$

There are two key tools we use to finish the argument.

  * •

For any $u\in\mathbb{R}^{d}$,
$\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})\|u\|_{\mathbf{A}_{i}}^{2}\leq\|u\|_{\mathbf{A}_{j}}^{2}$.

  * •

For any norm triangle inequality gives us
$\|\theta-\phi_{i}\|\leq\|\theta-\phi_{j}\|+\|\phi_{i}-\phi_{j}\|$. Then we
use power mean inequality, i.e. $a\leq b+c\implies a^{2}\leq 2(b^{2}+c^{2})$.

The following shows Assumption 2.$(i)$ holds with
$c_{ij}=\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})$:

$\displaystyle\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})\widehat{\mathcal{L}}_{i}(\theta,\phi_{i})$
$\displaystyle=\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})\|\theta-\phi_{i}\|_{\mathbf{A}_{i}}^{2}$
$\displaystyle\leq\frac{1}{2}\|\theta-\phi_{i}\|_{\mathbf{A}_{j}}^{2}$
$\displaystyle\leq\|\theta-\phi_{j}\|^{2}_{\mathbf{A}_{j}}+\|\phi_{i}-\phi_{j}\|^{2}_{\mathbf{A}_{j}}$
$\displaystyle=\widehat{\mathcal{L}}_{j}(\theta,\phi_{j})+\widehat{\mathcal{L}}_{j}(\phi_{i},\phi_{j}).$

Analogously, the following shows Assumption 2.$(ii)$ holds with
$c_{ij}=\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})$:

$\displaystyle\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})\widehat{\mathcal{L}}_{i}(\phi_{j},\phi_{i})$
$\displaystyle=\frac{1}{2}\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})\|\phi_{j}-\phi_{i}\|_{\mathbf{A}_{i}}^{2}$
$\displaystyle\leq\lambda_{\rm\min}(\mathbf{A}_{i},\mathbf{A}_{j})\left(\|\theta-\phi_{j}\|_{\mathbf{A}_{i}}^{2}+\|\theta-\phi_{i}\|_{\mathbf{A}_{i}}^{2}\right)$
$\displaystyle\leq\|\theta-\phi_{j}\|_{\mathbf{A}_{j}}^{2}+\|\theta-\phi_{i}\|^{2}_{\mathbf{A}_{i}}$
$\displaystyle=\mathcal{L}_{j}(\theta,\phi_{j})+\mathcal{L}_{i}(\theta,\phi_{i}).$

This concludes the proof. ∎

With the preceding technical lemma in place, we now are ready to prove Theorem
3. See 3

###### Proof.

Lemma 5 gives us that the subpopulation $i$’s empirical loss for a regressor
$\theta\in\mathbb{R}^{d}$ can be written as
$\|\theta-\phi_{i}\|^{2}_{\mathbf{A}_{i}}$. This is a random quantity since
$\mathbf{A}_{i}$ is a sample average covariance of randomly chosen features.
We analyse this term next.

For a random feature $x\in\mathbb{R}^{d}$ in subpopulation $i$, given a fixed
center $\theta\in\mathbb{R}^{d}$, the term
$\frac{(\theta-\phi_{i})^{\top}x}{\|\theta-\phi_{i}\|_{\Sigma_{i}}}$ is sub-
Gaussian with variance proxy $\sigma_{i}^{2}$ by Assumption 3. The square of a
sub-Gaussian random variable,
$\frac{(\theta-\phi_{i})^{\top}xx^{\top}(\theta-\phi_{i})}{\|\theta-\phi_{i}\|^{2}_{\Sigma_{i}}}$
is sub-exponential777A random variable $x$ is subexponential with parameters
$(v^{2},\alpha)$ if $\mathbb{E}[\exp(\lambda
x)]\leq\exp(\frac{\nu^{2}\lambda^{2}}{2})\;\forall|\lambda|\leq\frac{1}{\alpha}$.
with parameters $\nu_{i}^{2}=32\sigma_{i}^{4},\alpha_{i}=4\sigma_{i}^{2}$ (see
(Honorio and Jaakkola, 2014, Appendix B)).

Since subpopulation $i$’s empirical loss is an average of $n_{i}$ samples, the
empirical loss $\|\theta-\phi_{i}\|^{2}_{\mathbf{A}_{i}}$ is a subexponential
variable with parameters
$\frac{\nu_{i}^{2}}{n_{i}}\|\theta-\phi_{i}\|^{4}_{\Sigma_{i}},\frac{\alpha_{i}}{\sqrt{n_{i}}}\|\theta-\phi_{i}\|^{2}_{\Sigma_{i}}$.
This is because the variance of sample average scales as
$\frac{1}{\sqrt{n_{i}}}$, and the constant
$\|\theta-\phi_{i}\|^{2}_{\Sigma_{i}}$ scales the subexponential parameters
appropriately.

Now, given a set of $k$ arbitrary services
$\Theta=\\{\theta_{1},\ldots,\theta_{k}\\}\subset\mathbb{R}^{d}$, let
$\theta_{\gamma(i)}\in\Theta$ be an arbitrary service chosen by subpopulation
$i$. The sum of empirical losses on based on such choices is also
subexponential with parameters
$\nu^{2}=\sum_{i\in[N]}\frac{\nu_{i}^{2}}{n_{i}}\|\theta-\phi_{i}\|^{4}_{\Sigma_{i}}$
and
$\alpha=\max_{i\in[N]}\frac{\alpha_{i}}{\sqrt{n_{i}}}\|\theta-\phi_{i}\|^{2}_{\Sigma_{i}}$.
Using Chernoff bound (Vershynin, 2018), we have that

$\displaystyle
P\left\\{|\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\mathbf{A}_{i}}-\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\Sigma_{i}}|\right\\}\geq
t]\leq 2\exp\left(-\frac{t^{2}}{2\nu^{2}}\right)\quad\text{where}\ 0\leq
t\leq\frac{\nu^{2}}{\alpha}.$ (9)

Note that the probability bound is is increasing in $\nu$, we thus take an
upper bound on $\nu^{2}$ to upper bound this probability:

$\displaystyle\nu^{2}$
$\displaystyle=\sum_{i\in[N]}\frac{\nu_{i}^{2}}{n_{i}}\|\theta-\phi_{i}\|^{4}_{\Sigma_{i}}=32\sum_{i\in[N]}\frac{\sigma_{i}^{4}}{n_{i}}\|\theta_{\gamma(i)}-\phi_{i}\|^{4}_{\Sigma_{i}}\leq
32\left(\sum_{i\in[N]}\frac{\sigma_{i}^{8}}{n_{i}^{2}}\right)^{\frac{1}{2}}\left(\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{8}_{\Sigma_{i}}\right)^{\frac{1}{2}},$

where the last inequality follows from Cauchy-Schwarz. Further, noticing that
$\sum_{i\in n}a_{i}^{4}\leq(\sum_{i\in n}a_{i}^{2})^{2}$, and applying it for
the last term twice, we deduce that

$\displaystyle\nu^{2}\leq
32\left(\sum_{i\in[N]}\frac{\sigma_{i}^{8}}{n_{i}^{2}}\right)^{\frac{1}{2}}\left(\sum_{i\in[n]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\Sigma_{i}}\right)^{2}.$

Choosing
$t=\epsilon\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\Sigma_{i}}$ in
(9), where
$0\leq\epsilon\leq\mathcal{O}(\min_{i\in[N]}\frac{\sigma_{i}^{2}}{\sqrt{n_{i}}})$,
we have that

$\displaystyle
P\left[|\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\mathbf{A}_{i}}-\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\Sigma_{i}}|\geq\epsilon\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\Sigma_{i}}\right]$
$\displaystyle\qquad\geq
2\exp{\left(-\frac{\epsilon^{2}}{64}\left({\sum_{i\in[N]}\frac{\sigma_{i}^{8}}{n_{i}^{2}}}\right)^{-1/2}\right)}.$

With high probability, at least
$1-2\exp{\left(-\frac{\epsilon^{2}}{64}\left({\sum_{i\in[N]}\frac{\sigma_{i}^{8}}{n_{i}^{2}}}\right)^{-1/2}\right)}$,
for all $\Theta\subset\mathbb{R}^{d}$, we have that

$\displaystyle(1-\epsilon)\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\Sigma_{i}}\leq\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\mathbf{A}_{i}}\leq(1+\epsilon)\sum_{i\in[N]}\|\theta_{\gamma(i)}-\phi_{i}\|^{2}_{\Sigma_{i}}.$

The rest of the proof is deterministic, thus it is assumed everything follows
with probability at least
$1-2\exp{\left(-\frac{\epsilon^{2}}{64}\left({\sum_{i\in[N]}\frac{\sigma_{i}^{8}}{n_{i}^{2}}}\right)^{-1/2}\right)}$.
Define $\Theta^{N}=\Theta\times\cdots\times\Theta$—i.e., Cartesian product of
the set $\Theta$ $N$-times. Given two functions
$f,g:\Theta^{N}\rightarrow\mathbb{R}$, if $f(\theta)\leq g(\theta)$ for all
$\theta\in\Theta^{N}$, then
$\min_{\theta\in\Theta^{N}}f(\theta)\leq\min_{\theta\in\Theta^{N}}g(\theta)$.
Therefore, we deduce that

$\displaystyle(1-\epsilon)\sum_{i\in[N]}\min_{j\in[k]}\|\theta_{j}-\phi_{i}\|^{2}_{\Sigma_{i}}$
$\displaystyle\leq\sum_{i\in[N]}\min_{j\in[k]}\|\theta_{j}-\phi_{i}\|^{2}_{\mathbf{A}_{i}}\leq(1+\epsilon)\sum_{i\in[N]}\min_{j\in[k]}\|\theta_{j}-\phi_{i}\|^{2}_{\Sigma_{i}}.$
(10)

Hence, given the same set of services $\Theta$, the total empirical loss can
be bounded with respect to the total expected loss as follows:

$\displaystyle(1-\epsilon)\mathcal{L}(\Theta,[N])\leq\widehat{\mathcal{L}}(\Theta,[N])\leq(1+\epsilon)\mathcal{L}(\Theta,[N]).$

Recall $\Theta_{\rm OPT}$ denotes the optimal solution for the total expected
loss and let $\widehat{\Theta}_{\rm OPT}$ denote the optimal solution for the
total empirical loss. Let $\Theta_{k}$ be the output of Algorithm 1 on finite
samples per subpopulations. Using the first inequality of (10), we have that

$\displaystyle(1-\epsilon)\mathbb{E}_{\Theta_{k}}[\mathcal{L}(\Theta_{k},[N])]\leq\mathbb{E}_{\Theta_{k}}[\widehat{\mathcal{L}}(\Theta_{k},[N])].$
(11)

Also, noting that $\widehat{\Theta}_{\rm OPT}$ is the minimizer for
$\widehat{\mathcal{L}}(\Theta,[N])$ and using the second inequality of (10),
we get that

$\displaystyle\widehat{\mathcal{L}}(\widehat{\Theta}_{\rm
OPT},[N])\leq\widehat{\mathcal{L}}(\Theta_{\rm
OPT},\Phi)\leq(1+\epsilon)\mathcal{L}(\Theta_{\rm OPT},\Phi).$ (12)

Now combining (11) and (12) with Theorem 1, we get the desired result—i.e.,

$\displaystyle\mathbb{E}_{\Theta_{k}}[\mathcal{L}(\Theta_{k},[N])]\leq\frac{1+\epsilon}{1-\epsilon}K_{\rm
OPT}(2+\log k)\cdot\mathcal{L}(\Theta_{\rm OPT},[N]).$

Setting
$\delta=1-2\exp{\left(-\frac{\epsilon^{2}}{64}\left({\sum_{i\in[N]}\frac{\sigma_{i}^{8}}{n_{i}^{2}}}\right)^{-1/2}\right)}$,
we get that
$n_{i}=\Omega(\frac{\sigma_{i}^{4}\sqrt{N}\log{(2/\delta)}}{\epsilon^{2}})$.
This concludes the proof.

∎

Figure 4: Fair objective improvement for AcQUIre over the baseline across
different demographics. We observe that there is atleast 15% improvement
across sex demographics for a wide range of number of services. For racial
demographics the improvement is 7-26%.

Figure 5: Average losses across different demographic groups for Fair AcQUIre
(left,middle). Percentage improvement over baseline (right). We observe that
Fair AcQUIre reduces disparity across different groups compared to the
baseline.  Figure 6: Average Total Loss across different baselines. We observe
that while the greedy algorithm does when the number of services is small, its
performance starts degrading as the number of services grows. This is beacuse
the greedy algorithm is susceptible to pick outliers. AcQUIre beats both the
baselines across a large range of number of services.

##  Appendix E Experiment Details

#### Census Dataset.

The categorical features (schooling, marital status, migration status,
citizenship) were first converted to one hot vectors and the continuous
features (age, income) were scaled appropriately for better conditioning. We
performed singular value decomposition on the features and retained the top
ten components. The scores were taken as the log transform of the daily
commute time in minutes. To form subpopulations, we split users based on their
Public Use Microdata Area codes (zip code) and ensure each subpopulation
belongs to one of the demographic groups considered. The percentage
improvements of our algorithm are plotted in Figure 4.

We also run Fair AcQUIre (Algorithm 2) on the Census experiment where the
demographic identities are known to the provider. As a baseline we used a
weighted sampling of users where the weights are inversely proportional to the
demographic sizes. This baseline ensures the expected number of users sampled
per demographic is equal. The results are reported in Figure 5.

#### Additional Baseline.

We consider an additional baseline for initialization process. The greedy
algorithm at every iteration picks the user with the largest loss, queries the
picked user’s preference and sets the new service to this preference. We find
that while the algorithm performs well when the number of services $k$ is
small, however as $k$ increases the uniform sampling starts performing better
than greedy (see Figure 6). This is because a greedy algorithm is susceptible
to pick outliers, particularly when $k\ll n$ and these outliers don’t
generalize well to the average population.

#### Movie Recommendation Dataset.

We use Surprise (a Python toolkit (Hug, 2020)) to perform our experiments. We
split the total 10 million ratings into top (a) 200 movies, and (b) all other
movies. We use the inbuilt nonnegative matrix factorization function of
Surprise on (b) to get user and item embeddings. We cluster the users into
1000 subpopulations by running $k$-means on the obtained user embeddings we
get. We evaluate algorithms for this experiment on the held out set (a) of the
top 200 movies.