Initializing Services in Interactive ML Systems for Diverse Users
Authors: Avinandan Bose
Mihaela Curmei
Daniel L. Jiang
Jamie Heather Morgenstern
Sarah Dean
Lillian J. Ratliff
Maryam Fazel
Venue: NeurIPS 2024 poster (2024)
Keywords: Algorithm design for multi-service ML systems
initialization
clustering
approximation ratio
preference learning
Primary area: active_learning
TL;DR: We study the problem of initializing multiple services for a provider catering to a user base with diverse preferences, developing algorithms with approximation ratio guarantees on average and worst case losses.

Abstract: This paper investigates ML systems serving a group of users, with multiple models/services, each aimed at specializing to a sub-group of users. We consider settings where upon deploying a set of services, users choose the one minimizing their personal losses and the learner iteratively learns by interacting with diverse users. Prior research shows that the outcomes of learning dynamics, which comprise both the services' adjustments and users' service selections, hinge significantly on the initial conditions. However, finding good initial conditions faces two main challenges: (i) \emph{Bandit feedback:} Typically, data on user preferences are not available before deploying services 
and observing user behavior; (ii) \emph{Suboptimal local solutions:} The total loss landscape (i.e., the sum of loss functions across all users and services) is not convex and gradient-based algorithms can get stuck in poor local minima.

We address these challenges with a randomized algorithm to adaptively select a minimal set of users for data collection in order to initialize a set of services. Under mild assumptions on the loss functions, we prove that our initialization leads to a total loss within a factor of the \textit{globally optimal total loss,with complete user preference data}, and this factor scales logarithmically in the number of services. This result is a generalization of the well-known $k$-means++ guarantee to a broad problem class which is also of independent interest.
The theory is complemented by experiments on real as well as semi-synthetic datasets.

Initializing Services in Interactive ML Systems for Diverse Users
Avinandan Bose University of Washington avibose @csss www.ss.aiinnoooedii
Mihaela Curmei University of California Berkeley mcurmei @ berkeley.edu
Daniel L. Jiang
University of Washington danji @ cs. wwwhington.c...
Jamie Morgenstern
Sarah Dean
Lillian J. Ratliff
University of Washington
Cornell University sdean @ cornell.edu
University of Washington ratliffl uww.eu
jamiemmt@cs. sumniemnt@ess.wsshnnnoon.ee
Maryam Fazel
University of Washington mfazel @ uw.edu
Abstract
This paper investigates ML systems serving group of users, with multiple mod- els/services, each aimed at specializing to a sub-group of users. We consider settings where upon deploying set of services, users choose the minimiz- ing their personal losses and the learner iteratively learns by interacting with diverse users. Prior research shows that the outcomes of learning dynamics, which comprise both the services' adjustments and users' service selections, hinge signifi- cantly on the initial conditions. However, finding good initial conditions faces two main challenges: (i) Bandit feedback: Typically, data on user preferences are not available before deploying services and observing user behavior; (ii) Suboptimal local solutions: The total loss landscape (i.e., the sum of loss functions across all users and services) is not convex and gradient-baag based algorithms can get stuck poor local minima.
We address these challenges with randomized algorithm to adaptively select minimal set of users for data collection in order to initialize a set of services. Under mild assumptions
the loss functions, we prove that our initialization leads a total loss within a factor of the globally optimal total loss with complete user preference data, and this factor scales logarithmically in the number of services. This result a generalization of the well-known k-means++ guarantee to a broad problem class, which is also of independent interest. The theory is complemented by experiments on real as well as semi-synthetic datasets.
Introduction
We consider setting where a provider wants to design à services for n with diverse preferences. Each service uses model parameterized by vector E Rdd to predict users' preferences, and users pick service that yields the smallest loss for them. The loss incurred by user i when choosing a service parameterized by is denoted by C, ó.), where Φ; gd parameterizes the user's preference. We want design services by minimizing the sum of all losses; i.c., optimization
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

problem of the form:
minimize 02.0..0 Og Elta
min min be), .............................. L((0x,0)))
This problem formulation is broad and includes the classical k-means clustering problem 28 (where Li are Euclidean distances and the inner 'min' selects the closest among k centroids), mixed-linen regression 42 generalized principal component analysis (GPCA) or subspace clustering M. in addition to our new, motivating problem of designing k services for users, Even if the losses L₁ are convex in 0, this objective generally not convex (even in the special case of the k-means problem).
Our goal is to find a local minimum of this optimization problem with an approximation ratio (a worst-case guarantee the achieved total loss with respect the global optimum) under suitable yet broad assumptions on L. Further, an important limitation in many practical settings is that the provider/designer has only bandit feedback (zeroth-order oracle access) to the loss functions (i.e., the designer doesn't know the function (.)) but can only evaluate its value for some 0 corresponding to the service chosen by the user among the ones deployed), which further complicates solution methods, compared to the classical cases of clustering and facility location problems [10] which typically assume full information.
In this paper, we seek a novel and effective initialization scheme that vastly extends the celebrated k-means++ algorithm and its analysis [5). This scheme should retain the simplicity and ease of implementation of the original algorithm, yet be able to (1) handle general loss families (assumptions on L; are discussed in Section 2) (2) provide tight, detteneedeeendent approximation ratio (details in Section [). and (3) handle realistic information limitations such as access only to (noisy) bandit feedback, in a sample-efficient manner. Next, we describe in more detail the important use case of initialization of services for diverse users in multi-service ML systems (yet as noted above, our main result has other applications as well, and can be of independent interest).
Motivation. In a variety of contexts such as federated learning (27], crowd-sourcing [36 and online recommendation systems (35), data about user preferences is acquired through iterative interactions. This data is then used to improve the model and serve the individual needs of users. Given that users' preferences typically heterogeneous, recent works demonstrate that using multiple specialized models can be more effective than the one-size fiize-lii--ll---- approach of employing a single large shared model, e.g., for clustered federated learning [30) [7], meta learning (25) 71. fine-tuning for specific groups of users or tasks [9] 37]. and in the context of fair classifiers 33). Here we tackle the crucial yet under-explored phase of initializing services in ML systems that learn interactively from diverse users. The initialization process is crucial as it sets the stage for how effectively these systems can adapt and specialize with future user interactions. Once initialized, the services interact with users. who, in turn, choose among services based on their loss, These "learning dynamics" typically lead to the specialization of services to groups of users [2] and [12] shows experimentally that the overall social welfare achieved by the services depends on the initialization of the learning dynamics. We note that in the context of problem ( the learning dynamics in [12] can be seen as updates of an alternating minimization algorithm, iteratively updating users' choices (the inner minimization) and services' parameters (update to each 0,). Our goal is to initialize a set of services to minimize the sum of losses for all users (or equivalently, maximize total welfare), tackling the following challenges:
Bandit loss feedback: In practice, offering a service often precedes data collection. Specifically, in contexts like online recommendations, it is usually not feasible to gather user preference data (knowledge about o; and evaluations of C,(,, Øt) at various different parameter values in problem ( without first deploying the services parameterized by {01,..., 02) ) and observing user interactions. This means that data collection is inherently conditional on the existence of services, challenging the conventional "data-first, model-second" paradigm.
Suboptimal local solutions: Since users select the service with the lowest loss (min(C, (C,(0, (. L.,,,, }
in problem (I)), minimizing over the parameters (01,...,4 0z) leads to nonconvex problem in general, as mentioned earlier. Gradient-base based learning dynamics can 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 of service parameters.
Contributions. The following summarizes the contributions of this paper.

---

We design a computationally and statistically efficient algorithm for initialization of services prior learning dynamics. The algorithm works by adaptively selecting a small number of users to collect data from (via queries of their loss function) in order to initialize the set of services.
We establish an approximation ratio for the designed algorithm: the expected total loss achieved by the algorithm right after initialization is within factor of the globally optimal total loss in the presence of complete user preference data, and this factor scales logarithmically in the number of services. Furthermore this bound is tight, and recovers the known k-means++ approximation ratio as special case (cf. Section 3}.
When users belong to a set of demographic groups, it is desirable that the services do not result in unfavorable outcomes towards certain demographies (e.g.. based on gender or racial groups). One fair objective is to minimize the maximum average loss of users across different groups. We provide approximation ratio for this fair objective that scales logarithmically in the number of services (cf. Section 3).
In the context of linear prediction models, we study the problem of generalizing to users the provider has not interacted with before (cf. Section 4
We empirically demonstrate the strengths of our initialization scheme via experiments on a pre- diction task using 2021 US Census data, and online movie recommendation task using the Movie- lens 1OM dataset (cf. Section
1.1 Related Work
Multiple Model Specialization. In distributed learning, where data sources users' personal devices, utilizing multiple specialized models, where users are grouped into clusters representing interests, can yield improved predictions and outcomes. For instance, in recommendation systems these clusters could represent users interested in different movie genres, or different combination of features (see Appendix [ for concrete example on Netflix recommendation clusters). This approach has been adopted recently in clustered federated learning [44 30 17] and online interactive learning [32,, facility location problems [6], where users choose models/services and for which they provide updates.
Clustering. Multiple model specialization leads to clustering the users into groups and centering a specialized model on each group. We provide a brief review of the k-means clustering problem and establish the connection specialization. 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 partition them into A clusters (each characterized by a center), such that the sum of square of distances to their closest center is minimized. Dasgupta 11 and Aloise et al. 3 showed that the k-means problem is NP-Hard. The most popular heuristic for k-means is Lloyd's algorithm (28), which proceeds by randomly initializing k centers and then uses iterative updates to find 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 (5) and Ostrovsky et al. [33] proposed an elegant polynomial time algorithm for initializing centers, known as k-means++. Arthur and Vassilvitskii [5] proved that the expected cost of the initial clustering obtained by + is at most 8(2 + log k) times the cost of optimal k-means clustering, Our work generalizes the analysis of Arthur and Vassilvitskii (5) to the setting where user's 's preferences are represented as unknown points and the loss functions are unknown with only bandit access, not necessarily identical, and general as long they satisfy Assumptions 2.7 and 2.2 with important examples given in Appendix C
For a detailed discussion on more related works please see Appendix A
Notation and Terminology. For symmetric matrix A and any vector E Rd, we denote its Mahalanobis norm by ||æ||A A Vxr Aar. The generalized eigenvalues for pair of symmetric matrices A and B are denoted by X (A, B), defined as the solutions of X for the generalized eigenvalue problems Av AB [16] D4. Specifically we use Amin (A, B) denote minimum generalized eigenvalue for the matrix pair A, B. The loss for user i given service 0 E Id is denoted by (, Φi) where Φi parameterizes the user's preference. For a set of users A (e.g., A = [x] denotes a set of n users) and set of services θ = (01,..., EieA minje(K) (,),,, 6.).
(a....,,)] 0c) C RRd the total loss is defined as L(,, A) =
3

---

2
Problem Setup
We make the following assumptions about the functional form of C,, and state several examples of function classes satisfying these properties. Note that the designer/provider doesn't I need to know the functional form of Ci, and knowledge about L; is obtained through bandit feedback via observing the scalar values (0, o,) for different 0, where 9 parameterizes the services.
Assumption 2.1 (Unique Minimizer). The loss function satisfies the following equivalence: (, 6.) 0 + di.
This assumption implies that unless all users have identical preference parameters, there doesn't It exist single service parameter 0 that simultaneously minimizes every user's loss. Thus providing multiple services (multiple 0's) where the users choose the one best for them is strictly better than one service for all users.
Assumption 2.2 (Approximate Triangle Inequalities), For pair users i, there exists a finite
constant Cij > 0 such that for all 0 E IRd the following hold:
(i) ci (0, @x) S (B, Φ,) + (o( 0z).
(ii) c,Ci( 0.) < (0, 05) + (.(0 6.).
Here Gt (equal to Cjs) captures the alignment between the preference parameters and loss geometries of two users. Lower values of Gty indicate less similarity. Item (i) implies that the loss for user i on any service E Rd is no worse than (up to constant factor) the sum of (a) loss of another user on using the same service, and (b) the loss of user j if they were to use user i's preference parameter. The latter term (b) can be seen as measuring the similarity between the users' preferences.
For condition (ii) hold for all Rd, it must also hold for the service that minimizes the sum of losses of both users using the same service. Suppose that users and j were to exchange preference parameters. Then their loss would be no worse than (up to a constant factor) their minimum total loss, i.e.
Ci C, 0i) min (0, 6,) + C.(0, DER
Some examples of loss functions and the corresponding constants that satisfy these assumptions include the following (see Appendix for additional examples and derivations):
Squared error loss for linear predictors (ef. Section 4).
The Huber loss on the prediction error:
{ | 0.12 [ bill ()) otherwise.
if 0 -10- 5
C, 6.)
This loss is used typically in robust estimation tasks. Here || could be any norm, and we show
Czy = =1/3.
The normalized cosine distance: (.) 1 HT oi where ||0|]2 |l 1, with ey J.
This is commonly used as a similarity measure in natural language processing applications, for example finding similarity between two documents.
The Mahalanobis distance: L,(0, Φ;) = 10 diIE,, Different users can have differ- ent Σ; capturing their diverse loss variation, as long as E, is full rank. Here Gj
(E, E (E,, E,)}.
Auiin
Any distance metric: This naturally follows from triangle inequality, hence cjj 1.
Any arbitrary function Le(0, de) that is L--Lipschitz and pu-strongly convex in with eyj =
min(H: /t)/ max(L,, Lg).
Objective. Suppose the users have access services parameterized by θ (6, ........ Ox c Rd. Then, each user i selects service OJ that minimizes their loss, i.e. Li(O, 9.) = min (0, dr).
As discussed earlier, our goal is to design O such that the sum of losses across and services is minimized. We define the objective as follows:
L(0, In]) Exen minje(s) L,(0,, 0x) = Exeto C,(9, 6z).
Definition 2.3. Define the unknown optimal set of services that minimizes the objective to be
θorT argmin L(O, [n]).

---

Algorithm AcQUIre- Adaptively Querying Users for Initialization
1: Input: Set of users [n], number of services kt.
2: Choose a user uniformly randomly from in].
3: Query user i's preference 6 set the first service θ = di.-
4: for (2....,k) k} do
5: User behavior: Collect user losses existing services 1,-1 (1)
6: User Selection: Sample I from [n] with probability P(l = i) x (,,,)_,,))) 9t).
7: New service: Query user /'s preference dt.
8: O: = - db..
9: end for
10: Return O₂
Specifically, Gopr defines "clustering", meaning partitioning of the users into k clusters. The cluster Bm is the set of all users that prefer the service 6n among all the services in the optimal set OOpr. In other words, B,, is defined the set of all points such that Bm (i E [m] Om arg g (0, )z))-
3 If multiple services are equally preferred by subpopulation, the ties are broken arbitrarily. The resulting set of clusters is denoted by ((@OPT) = {Bi,... Bx
The are several statistical and computational challenges to this problem.
Challenge 1. Since preferences {ø: jej] and loss functions {Ci are unknown and the provider only has zeroth order or bandit feedback access, estimating the objective function C(O) [nl] usually needs lot of data collected uniformly across the users. This large amount of data is needed before services can be deployed, yet 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) makes our setting challenging.
The loss function is non-convex and iterative minimization approaches from a random initialization are susceptible to getting stuck in arbitrarily poor local optima. This means computing the optimal clustering first and then finding the best service for each cluster is NP-Hard.
Challenge 2.
Challenge 3. We do not assume any data separability conditions, for example user preference parameters are drawn from l well separated distributions. Thus we are unable to exploit underlying structure to reduce sample complexity.
Despite the challenges, in Section 3] we propose an algorithm that is both statistically and computa- tionally efficient, and admits an approximation ratio with respect to the globally optimal value, i.e., [(OOPT, [n]).
3 Algorithm & Main Results
In this section, we present our initialization algorithm with guarantees, Algorithm and describe how the steps of the algorithm arise naturally in the interactive systems under consideration. Since collecting data uniformly across all the n users can prohibitively expensive, our goal is to get data from minimal number of users.
Each iteration of the loop in the algorithm adds service sequentially and the loop terminates when there are k services, where lo is predetermined parameter for the algorithm. We focus on the loop (lines 4-8) in Algorithm
Suppose at time - 1, the set O,-1 is the set of current L - services. Then, at time step t. the following steps take place.
User behavior (line 5). Given the list of services θ users assumed to choose the best service that minimizes user loss. Users report their losses with respect to the service they choose from the set of existing services (L:(O,-1, Φt.) [x)))e])) 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 / is selected with probability proportional to (O di). This ensures that users that are currently poorly served by existing services are more likely to be selected.
5

---

New Service (line 7-8). Given selected user I, the algorithm queries the preference Φi of the user and centers the new service at that preference 8, Φr. practice, this step requires acquiring data about the user in order to learn their preference parameter (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 (21
With each iteration the loss of each user is non-increasing; the previous services remained fixed and user would switch to a new service only if improves quality or equivalently decreases loss. Since at each iteration, 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 < n.
We now discuss the theoretical properties of the set of services we get at the termination of Algo- rithm 1
Theorem 3.1. Consider users with unknown preferences {Øi...., ,,, C. Rd, and associated loss functions Li(:.-) satisfying Assumptions 2.1 and 2.2 with bandit access. Let Oorr C R be the set of le services minimizing the total loss and ((OPT) the resulting partitioning of users (Definition) 2.3 3. If Algorithm iis used to obtain l services O2 then the following bound holds:
Ee, [n])] S KoPT log [(0OPT.[n))
where the expectation is taken over the randomization of the algorithm and KorT is equal to
(maxjer EieB 6g
maxgec(@orr)
Bin
C13 SEB
A detailed proof is presented in Appendix D we summarize the main ideas here. The intuition is that a chosen user's preference parameter is typically a good representative for other users in its cluster. Thus adding 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.
similar proof approach was used by Arthur and Vassilvitskii 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 its closest existing center. A key novelty of our analysis to capture the alignment of diverse loss geometries across users in a large class of functions, specifically understanding how user similarities Ciy affect the approximation ratio
Key characteristics of KOPT: The following are essential characteristics of the term KOPT.
(i) All terms in KoPT depend on the local clusters in the unknown optimal clustering C(0
(ii) The constant minjes [вr Eieg Gij captures the user whose loss geometry is least similar to
the average loss geometry of the cluster they belong to (recall Assumption 2.2 i).
(iii) The constant maxje
[ Σx 1 captures the user whose preference is least similar to the
ezj
optimal service parameter of the cluster they belong to (recall Assumption 2.2 ii).
(iv) Even within cluster all terms are averages, so few poorly aligned pairs of users don't 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 users come from different demographic groups (m is typically small, say racial groups, gender). We denote the groups as A = [Ai...., C [n]. The fairness objective is defined as the maximum average loss suffered by any group:
4 ( A)
max L(O, A.)|A
[E(m]
15 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 a a-pproximate solution for k-means exists, is
In addition, as stated earlier, we tackle the lack of prior information on di and the function form of L, this challenge is particular to our setting and does not arise in related standard problems of clustering (k-means, k k-mediods) or resource allocation (facility location problems).

---

m. c-approximate for fair k-means. For the fairness objective, we slightly modify our algorithm, by simply reweighting the probability select an user by the inverse of the size of their demographic group to result in Fair AcQUIre (Algorithm Zin Appendix
Theorem 3.2. Consider n users with unknown preferences {ch1,..., [ C IR, and associated loss functions C((s,)) satisfying Assumptions 2.7 and 2.2 with bandit access. Suppose these users belong to demographic groups A = {A1,- ..... Am [n]_ Let Otair C R be the set of services minimizing the fairness objective given in (4). If Algorithm the following bound holds:
2 is used to obtain services U₁ then
Be, (0,,, A)] S mKKaar (2 + log k) 40 (( A),
where the expectation is taken over the randomization of the algorithm and Kiair is defined in (10)
4 Generalization in Linear Predictors
In practical settings, 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 [N] represents subpopulation with its own (sub-Gaussian distribution of features, and the provider can interact with finite samples n, from these distributions. A question that arises is whether we can deal with this -eee--aaape---o-uuuooopoeee algorithm's output to unseen users. In this section, we answer this question for the special case of linear predictors (i.e., regression loss).
scenario, and how does the number of samples affect the
In this section we restrict ourselves 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 ht subpopulation with zero-mean random feature r Id is generated as y = o x where both the true linear regressor Φb; RRd and the feature covariance Ex[ | = Σ, are unknown. Suppose service
linear regressor 0 Rd. predict the score for this user 0- ' TR. The loss for this subpopulation for this service is defined as the expected squared error between the predicted and actual scores, i.e., (0, Φ.) = ( [00 x ") |0 l
Assumption 4.1. For subpopulation i, features are independent draws from a zero-mean uub-Gaussian distribution. For a random feature x E Rd and for any u E IRd, such that |ulls, 1, u x E IR is sub-Gaussian with variance proxy of
Assumption 4.2. We assume that the decision to choose between different services happens at subpopulation level and not an individual level.
To illustrate Assumption 4, consider the example of 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 considerable number of students, but only a subset of them may actively respond to such queries. Once a school selects the service, it made available to all students, and the provider could implement system where students are encouraged to fill out a feedback form after using their service.
Suppose only users from subpopulation are subscribed to the services. Thus, upon choosing a service parameterized by 0 E R the provider observes an empirical loss, which is given by
[,(0.))) = म. EmE (8 -
where {(x{, j[[.] are private unknown features and scores of the users. We stress that the service gets the value of the user loss function at the deployed 0 (bandit feedback), but not the features of each subpopulation.
Assumption 4.3. The number of users from each subpopulation is greater than the dimension of the linear predictor, i.e. n; 2 d for all e [N].
In this setting, given a set of services parameterized by 0,-1 = -01,..., 0-11 the Steps 5-6 of Algorithm | proceed with these finite sample averages [, (i) = minze E.(0), (:). In
AA random variable is sub- nab-Gaussian with variance proxy o² if Elexp(Ax)) expl 22(""")) AA E
7

---

223
225
AcCUte
Asoutt
200
200
175
fandom
baaaress fandom
Greasy
175
Greed
Buannod Greal
Epilion Cready
Ealarcst on
smoel Easion Gready
Namber of Service R
Namber of Service
Namber of Servicss (t)
(a) Avg. loss (all Census groups) (b) Avg. loss (worst demographic) (c) Avg. excess error (ML10M task) Figure 1: Fig. la and show the performance of various user selection strategies on the travel time prediction task on the Census data. Notably, our findings reveal that the greedy and epsilon-gree -geedy baselines exhibit strong performance for k < 10. However, as the value of k grows, these strategies prove myopic, with random sampling surpassing their effectiveness. AcQUIre and Fair AcQUIre consistently emerge the two best baselines for both tasks. Fig. presents the average excess emror for the movie recommendation task. Remarkably, the greedy algorithm demonstrates efficacy when is small. Epsilon- greoddy, employing explore-vs-expl tendencies. Nevertheless, AcQUIre continues to be the best baseline for data collection.
approach, successfully overcomes myopic
Step 7, multiple ways can be adopted by the provider to estimate oi. Users can given incentives to provide batch of feature score pairs, gradient free methods can be used to estimate the optimal solution to the regression problem. The generalization guarantee Algorithm to the total expected loss is stated below.
Theorem 4.4. Suppose users belong to N subpopulations satisfying Assumptions' 4.1
4.2 and 4.3
Let (ni]veNN) denote the number of samples per subpopulation. Let O₂ be the output of Algorithm using finite sample estimates Ci(;, (5) and θoPr be the optimal solution of the expected loss. Then, for any (0, 1), if 22( Vt (2/0)) for all E [N], the following inequality holds with probability at least -6:
e²
Be, [e, [ND I KoPT2 log k) ((OPT) [N]), where KoPT is as defined in (3) and Gy = min { Amin (E,, Eg); Amiia E,
with E, 1 ni [fa))) Eg my E Ei (ot)).
The proof is presented in Appendix F we provide a brief overview here. We apply the Chernoff bound 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 of services for the total empirical loss and the total expected loss are different. Handling these carefully, and utilizing Theorem 3.1 concludes the proof.
Remark 4.5. Note that Σg is the empirical feature covariance of subpopulation i. The term Gi captures the alignment between two subpopulation's '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.2 (cf. Appendix F).
5 Experiments
We empirically demonstrate the benefits our algorithm on commute time prediction task based on 2021 US Census data" and semi-synthetic movie recommendation task on the MovieLens 10M dataset. In each task the merti-eervice provider has initially no access data. Our goal is to evaluate the effectiveness of the iterative data collection and service initialization procedure in comparison to established baselines. Below we first describe both the tasks and then discuss the baselines we consider for our evaluation.
Census Data. We consider the task of predicting daily work commute times, based on 2021 US census data from FOLKTABLES [13]. We illustrate a potential use case: the provider is a transport authority offering services in the form of personalized podcasts. 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 the users.
All our code
available at
https: wwwpnnywwwouuuuoooooooo..
MultiSeeee Biieericemittiilizaiaiioo A422
https://www census. wwasuus.goov. hwop/prgraams-.o http:///rrrrrrruuurrrr/////////e

---

The dataset has N = 7025 subpopulations defined by area zip codes. We use k linear predictors (as services) with user features (education, income, transportation mode, age etc). Refer to Appendix [G for details on data pre-processing. The features and commute times are unknown priori to the provider. At time step S k; suppose that the provider offers a set of services parameterized by 0.-1- The provider observes the losses (squared prediction error of their commute times as discussed in Section 4) across different subpopulations (Z.(Or-1, [E(N]- Then the provider selects subpopulation 1 [_V]. to get the user feature and commute time data and then estimates Φi via least squares regression. This selection can be done via our proposed method or one of the baseline strategies discussed later. The provider then centers its next service
Φi and updates the list of offered services θ = 1 1 U Φ1. Note that in this process the provider only observes features and commute times of users in the & selected subpopulations and k & N. In Figure 2 we compare runtimes, and observe that even with billion users, AcQUIre takes 300 sec, whereas the greedy and epsilon greedy methods take 10y sec even for 10 million users. With 5000 services, AcQUIre takes < 900 secs, whereas the runtimes for greedy and epsilon greedy are in the range of 10 secs.
Runtine
litumber servicee K 2000 he di fhood)
AcQUhte
Burtime in secoris (log scele)
Greedy
321
Epsilon Greedy
Rainia
AcQUire
Groccy
Epsilum Greedy
Burtme in
427
Random
12
Number
Number services
Figure 2: Runtimes for AcQUIre and basclines as number of users (N) and services (I) vary.
Movie Recommendations. We conduct semi synthetic experiment based on the widely used Movielens 10M data set [19] containing 10000054 ratings across 10681 movies by 71567 viewers. We hold out the top m 200 movies and pre-process the data set to divide viewers into = 1000 user subpopulations based on similarity of their ratings on the remaining movies (cf. Appendix G Our goal is to evaluate the generalization performance of the baselines to viewers that the provider has never interacted with before. Thus during the service initialization phase, only half of the users in each of the N subpopulations interact with the provider (train set), and we evaluate the performance of the algorithm by the loss incurred by the initialized services data of the other half of the users that no prior interaction with the provider (test set). For subpopulation i E [N], the solution to the following optimization problem denotes the user and item embedding:
(U&, ( = arg min (U.. (U.))) xxxx (U T: 7:) 11
(5)
where r; is the true user ratings and Qtrain is the list of movies rated by the users in subpopulation i. Since r; is a sparse matrix we consider the prediction error only on the movies they rated, i.e. Qurain User loss dissatisfaction for a recommendation model, parameterized by 0 E Rddmm is captured by the excess error, namely
(0, = [| - r.)a 11 II(Uccs 1.)a 11-
(6)
This value typically indicates how unhappy users are with the suggested movies with respect to their preferred movies. The provider initially doesn't know the user ratings. At time step L S k, suppose the provider offers a set of recommendation models O, Users choose the service with the best recommendations and the provider observes the losses across different subpopulations (O,,,, Φ.) Jig Then the provider selects a subpopulation / E [N] to estimate Φi via (5). This selection can be done via our proposed method or one of the baseline strategies discussed below. The provider then centers its next model on ái and updates the list of offered models θ H U di. In this process the provider only observes movie ratings of the users in the selected subpopulations. Once the services are initialized we evaluate the performance on the movies rated in the test set denoted by [02 ).
Baselines. Both our tasks iterate through the steps of observing User Behuvior, User Selection to gather data, designing New Service to update set of offered services. Through our experiments we wish to empirically evaluate different User Selection strategies with respect to AcQUIre (linc

---

6 in Algorithm| 1 The different user selection strategies result in the following baselines: (i)
Random: P(I =) 1/n, (ii) Greedy;
argmax (O, Øz). (ii) Epsilon Greedy: I = a (x) (C, 0.) + ei) where E1...., En denotes zero mean i.idd. noise. Given that the Census Dataset comprises various racial demographic groups of varying sizes (with the smallest group being ten times smaller than the largest group), and considering our interest in the faimess objective ( we explore incorporating these size imbalances into our algorithms. Consequently, we introduce three additional baselines, wherein the selection criteria are scaled by the corresponding group sizes: (iv) Balanced Random, (v) Balanced Greedy, and (vi) Balanced Epsilon Greedy. We benchmark them against Fair AcQUIre (Algorithm 2 which has guarantees as stated in Theorem 3.2
Evaluation: Each algorithm is run for 500 initialization seeds, the averages are reported in Figure [
Runtimes: We compare the runtimes of AcQUIre with the baselines, and study the affect of the number of users (N) and number of services (K) in Figure 2 We find the runtimes of AcQUIre to be of the similar order of magnitude of random initialization, meanwhile performing much better than random, and the much slower greedy and epislon greedy initialization schemes.
Once set of services are initialized, with more user interactions, the provider updates the services on new data to improve the quality (indicated by the reduction in total loss). To evaluate the importance of initialization, we conducted experiments using two different optimization algorithms: (i) Generalized k-means: The services are iteratively updated by training each service on the current group of subpopulations selecting it. After updating the service parameters, the subpopulations reselect their best service. This process repeats until convergence. (ii) Multiplicative weights update [1]] Similar to k-means, but each subpopulation can have users choosing different services simultaneouslly. Both generalized k-means and the multiplicative weights update guarantee that the total loss reduces over time [2].
Impact of Initialization:
In our experiments, we initialize a set of services using AcQUIre and other baseline methods, then let both optimization algorithms run until convergence. We plot the total loss versus the number of iterations (Figure 3). Our results demonstrate that AcQUIre leads to: (1) faster convergence, and (2) lower final loss (initializing with AcQUIre converges to lower losses; other initialization schemes are prone to being stuck in suboptimal local minima). These findings highlight the significance of a robust initialization strategy. By starting with a better initial configuration, the optimization algorithms can more effectively reach higher quality solutions.
SeIe2os SCCrS92 Data
SUPUERONN PROGEAS IC2ERIS PIRI
MMtRECItne MOSTSL (Maedt2/5120)
AcClive
AcOutre
AcOllhe
Ac2lAre
Randor
Rardbm
Randion
kandom
Cready
Gready
Greedy
greedy
Epallor Gready
Ezsiion Cready
Sear Fil
Epalion Creacy
Epakon Grawdy
Barratons
Kordtors
Toratoon
Norations
Figure 3: We study the importance of initialization in both the convergence rate and quality of converged solution of optimization algorithms. We find AcQUIre converges both faster and to a lower total loss across optimization methods (kmeans and multiplicative weights) well as datasets.
6
Conclusion
We study the problem of initializing services for a provider catering to a user base with diverse preferences. We address the challenges of unknown user preferences, only bandit (zeroth-order) feedback from the losses, and the non-convexity of the optimization problem, by proposing an algorithm that designs services by adaptively querying data from a small set of users. We also consider the fairness aspect of such design in human centric applications. Our proposed algorithm has theoretical guarantees on both the average and fair loss objectives. There are open questions relating to quantifying the robustness of the proposed initialization algorithm to noisy observations, perturbations, or outliers the finite sample case when the feature distribution is heavy-tailed, which is a direction for future work.
10

---

Acknowledgements
Dean, Fazel, Morgenstem and Ratliff were supported in part by NSF CCF-AF 2312774/2312775. Additionally, Morgenstem''s s work was supported by NSF CCF 2045402. Dean's 's research was sup- ported by a gift from Wayfair, a Linkedln research award, and NSF OAC 2311 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 2623166, CCF 2007036,
CCF 2212261.

---

References
[1] Generalized principal component analysis (GPCA). IEEE Trans. on Pattern Analysis and Machine Intelligence, (12):1945-113 2005.
[2] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k k-median by primal-dual algorithms. SIAM Journal on Computing, 49 (4):FOCS17-97, 2019. 2019.
[3] Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. Np-hardness of euclidean sumaoe-squares clustering. Machine learning, 75(2):245 248, 2009.
[4] Preeti Arora, Shipra Varshney, et al. Analysis of k-means and k-medoids algorithm for big data. Procedia Computer Science, 78:507-512, 2016.
[5] 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.
[6] Avinandan Bose, Arunesh Sinha, and Tien Mai. Scalable distributional robustness in class of non-convex optimization with guarantees. Advances in Neural Information Processing Systems, 35:13826-13837 2022.
[7] Avinandan Bose, Simon Shaolei Du, and Maryam Fazel. Offline multi-task transfer rl with representational penalization. arXiv preprini arXiv:2402.125700 2024.
[8] Gregory Canal, Blake Mason, Ramya Korlakai Vinayak, and Robert Nowak. One for all: Simultaneous metric and preference learning multiple users. arXiv e-prints, pages arXiv- 2207, 2022.
[9] 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.
[10] Gérard Cornuéjols, George Nemhauser, and Laurence Wolsey. The uncapicitated facility location problem. Technical report, Cornell University Operations Research and Industrial Engineering, 1983.
[11] Sanjoy Dasgupta. The hardness of k-means clustering. Department of Computer Science and Engineering, University of California, San Diego, 2008.
[12] 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.
[13] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt. Retiring adult: New datasets for fair machine learning. Advances in Neural Information Processing Systems, 14:6478-6490. 2021.
[14] Wolfgang Förstner and Boudewijn Moonen. A metric for covariance matrices. Geodesy-the Challenge of the 3rd Millennium, pages 299-309, 2003.
[15] 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.
[16] Benyamin Ghojogh, Fakhri Karray, and Mark Crowley. Eigenvalue and generalized eigenvalue problems: Tutorial. arXiv preprint 19Xiv:1903.11222 2019.
[17] Avishek Ghosh, Jichan Chung, Dong Yin, and Kannan Ramchandran. An efficient framework for clustered federated learning. Advances Neural Information Processing Systems, 33: 19596, 2020.
[18] 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.
12

---

[19] F Maxweel Harper and Joseph A Konstan. The movielens datasets: History and context. Acm transactions on interactive intelligent systems (tiis), 5(4):1-19, 2015.
[20] 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.
[21] 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 Artificial Intelligence, volume 32, 2018.
[22] Jean Honorio and Tommi Jaakkola. Tight bounds for the expected risk of linear classifiers and pac-bayes samite-sample guarantees. In Artificial Intelligence and Statistics, pages 384-392. PMLR, 2014.
[23] Nicolas Hug. Surprise: A python library for recommender systems. Journal Software, 5(52):2174, 2020. doi: 10.21 00.21105/joss.02111 URL httptt:////o.i org 21105/ joss 02174
Journal of Open Source
[24] Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the eighteenth annual symposium on Computational geometry, pages 10-18, 2002.
[25] Weihao Kong, Raghav Somani, Zhao Song, Sham Kakade, and Sewoong Oh. Meta-learning for mixed linear regression. In International Conference Machine Learning, pages 5394 5404. PMLR, 2020.
[26] Silvio Lattanzi and Christian Sohler. A better k-means++ algorithm via local search. In International Conference on Machine Learning, pages 3662-3671. PMLR, 2019.
[27] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning; Chal- lenges, methods, and future directions. IEEE signal processing magazine, 37(3):00-60, 2020.
[28] Stuart Lloyd. Least squares quantization pem. IEEE transactions on information theory, 28 (2):129-133) 1982.
[29] 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.
[30] Yishay Mansour, Mchryar Mohri, Jae Ro, and Ananda Theertha Suresh. Three approaches for personalization with applications federated learning. arXiv preprint arXiv:2002. 10619, 2020.
[31] Saeed Masoudnia and Reza Ebrahimpour. Mixture of experts: a literature survey. The Artificial Intelligence Review, 42(2):275, 2014.
[32] Adhyyan Narang, Omid Sadeghi, Lillian Ratliff, Maryam Fazel, and Jeff Bilmes. On- line submodular+ supermodular (bp) maximization with bandit feedback. arXiv preprint arXiv:2207.0309) 2022.
[33] 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.
[34] 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-377 2020.
[35] Linqi Song, Cem Tekin, and Mihaela Van Der Schaar. Online learning in large-scale contextual recommender systems. IEEE Transactions on Services Computing, 9(3):333 445, 2014.
[36] Jacob Steinhardt, Gregory Valiant, and Moses Charikar. Avoiding imposters and delinquents: Adversarial crowdsourcing and peer prediction. Advances Neural Information Processing Systems, 29, 2016.
13

---

[37] Yue Sun, Adhyyan Narang, Ibrahim Gulluk, Samet Oymak, and Maryam Fazel. Towards sample-efficient overparameterrzzed meta-learning. In Proc. of Advances Neural Information Processing Systems, volume 34, 2021.
[38] Gokcan Tatli, Rob Nowak, and Ramya Korlakai Vinayak. Learning preference distributions from distance measurements. In 2022 58th Anmual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-8. IEEE, 2022.
[39] 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.
[40] Roman Vershynin. High-diimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[41] Xueru Zhang, Mohammadmahdi Khaliligarekanni Cem Tekin, and Mingyan Liu. Group reten- tion when using machine learning in sequential decision making: the interplay between user dynamics and fairness. Advances in Neural Information Processing Systems, 32, 2019.
[42] Kai Zhong, Prateck Jain, and Inderjit S Dhillon. Mixed linear regression with multiple compo- nents. Advances in neural information processing systems, 29, 2016.
14

---

A More Discussion on Related Works
Retention. User retention in machine learning systems is closely related to the decision dynamics between the provider and users studied the single service setting by Hashimoto et al. [20], Zhang et al. [4] and multiple services setting by Dean et al. [2]. Ginart et al. [8] 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. These works typically focus the stability of the dynamics equilibrium. However, the final outcome is heavily influenced by the initial data the provider has and the initial configuration (partitioning) of the users across the offered services. Our work addresses the impact of initialization on the final outcome with theoretical guarantees.
Mixture of Experts. This model specialization is also explored in the mixture of experts literature (see, e.g., (3I). which uses multiple 'expert' models to enhance accuracy and robustness, assigning inputs to the most suitable expert based on their features through gating mechanism.
Clustering. (2 improved the analysis of (5) show an approximation ratio 5(2 + log and showed a family of instances with 5 log kt approximation ratio, thus showing k-means++ is tight. Recent works in clustering [24 2 [66] provide constant approximation ratio, and although they are polynomial time algorithms, these methods are data inefficient and rely on knowing the points
priori.
Facility Location Problem. Our algorithm has some resemblances with the facility location problem where there are users, and provider can set up most & facilities one of m candidate locations (also known as the k-medoids objective [4]. One key difference is the provider can choose from m predecided locations, compared 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 {ōi..... on } apriori, and (ii) deploy n. services to obtain all n²² function evaluations C, (dr, Φ5), Vi,j E [m]. This is infeasible applications like online recommendation systems where n is very large and typically provider has the capacity to deploy only h < n services. Hence a k-medoids like objective will not be reasonable in our setup with incomplete information.
6 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 users) loss. However their results assume they can solve computationally hard mixed integer program optimally.
Preference Learning. Given fixed set of items or services, [8 focus on learning preference
distributions of users. ( 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 the design of services rather than learning preferences over a fixed set of services, and we also allow each user to have different loss function and loss geometry.
B Motivating Example
We conceptualize 'services' broadly, encompassing both sets of independent learners -ucch as various service providers collaborating on initialization-and single learners with multiple models, like companies with diverse platforms or multi-model servers in federated learning settings. This initialization process is further relevant for social planners aiming to facilitate the coordination of service initialization.
Netflix Example. All details are borrowed from the actual working of Netflix (refer https //recoai. wwt./eeeninnnnennnn http://ettllxx--eeccmmmamtatttet -areedddatton-syytttmmmm wwwsss--tttttttt--eeeee how-it-works/ for a detailed description
and more references). The Netflix homepage displays several rows of suggestions. Each row is a collection of movies and the rows are arranged from top to bottom in decreasing order of likelihood that the user will pick movies to watch. The user has complete choice of which row to select a movie to watch from. The different rows are generated by different underlying recommendation models parametrized by O,,..., 0x. Our model abstracts these rows out as services. Netflix maintains K = 1300 such different recommendation models. Users' decision of watching a movie from the available rows of recommendations on the Netflix homepage informs the provider (Netflix) which of
15

---

the rows (parameterized recommendation model) the user prefers most, This let's them finetune their recommendation models.
C Mappings satisfying Assumptions 2.1 and 2.2
In this appendix, provide more details examples that satisfy Assumptions 2.1 and 2.2 For the squared error loss for linear predictors, we refer the reader to Lemma F.T for derivation of Cij- The remainder of the example classes detailed below.
C.1 Huber Loss
Recall that the Huber loss defined by
2110 0111 6(110 - 6ill (0)
if 10 dell - 8, otherwise.
(.)
Note that the Huber loss varies quadratically when the error |0 @ill S 8 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. |10 <bll S 26. 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, (0, 6,) S 3 822 Note that the Huber loss is monotonicly increasing in the prediction error. The function value in the linear ||0 - dell is at least _ Thus, if one of the terms in C, (5) + Ly(0i, were in the linear regime, the (,, Φ5) + Li(os, 6;) 2 102 and [. 6.) I (8, Φ5) + Cy(e., 05).
Both terms the right quadratic: In this sub-case, it needs to be shown when both terms of (0, 0z) + (or, Øÿ) are in the quadratic regime the bound still holds. By the triangle inequality on norms, have that
||0 l < ||e - اilه + l6:; - -0yll-
Using the power mean inequality, namely
b a² 2 + c²),
on the triangle inequality, we deduce the following implication:
||0 - o.1l < ||0 - 6, + ll lill = クタ 110 o.11 110 -- + 11,, -0,11?
If the L,(0, Φ.) is quadratic, we have that Co, (1) be linear. Then, we deduce that
C, Φv) < C,(0, 6z) + (o. Φ3). Now, let
|0: - 2,117 2 - C, Φb) + L, 01) = 1 -1 2
1 | 0111.
Since the equation f=² -fxr +
0 has no real roots, the expression is always positive.
B
Hence, by substituting
11-0:
o.1l we have that
110 11
1 501100
1::1--o111-0 ø.ll ( -
1 -.000 d.).
3
Therefore, we deduce that
C, 6.) 1 (,(),,,)+ (,(0.,0))
16

---

Case 2. 110 -6sll > 26. First, observe that
1
L,(0, 0.)
8(110
2 6)
3
3
5
d:1l + 8110 Øill
0zll
02
6
1
8
6ill + 8110
6ill
82
82
3
8 d:ll 82
where the second to last inequality follows from the fact that |10 - <bll > norms, we have that
26. By the triangle inequality
||0 Φe1l S 1|0 ,
10: dyll.
In turn, this implies either |00 0, || or | Qy is greater than | 110 dell- Without loss of generality,
assume |10 Φill z 1110 oull 2 8. Thus
Ly(0, = 6(100 الوه () z
1 2010 - will - 1 -001-220 2
20, 0.).
Since Li((s,, Φ5) 2 have that
2 (,(dr,
C.2 The normalized cosine distance
Recall that the normalized cosine distance given by
C,(0, 0.)
T o, where ||0|2 |10.12 1.
Therefore, have that
f Φ: = (11011 + 110.11 20 Φ.) 2 01.
Assumption 2.2 is satisfied with Cjj = 1/ by using triangle inequality followed by power mean
inequality.
C.3 Mahalanobis distance
Consider the Mahalanobis distance which is defined by
C, (b) 110 di ||x.; where Σ, is full rank and cty = min Amii (E,, Eg), Amin (2,,,,) }. of Lemmal F1
The derivation is similar to proof
D Proof of Theorem 3.1
We note that the parameters of the services initialized by Algorithm are subset of the users' unknown preferences. This allows us to define the notion of covering.
Definition D.1. Let θ C (di..... dn) a set of services. A cluster B E C(@OrT) is said to be covered by @ if there exists E B such that E O. If no such i B exists, then the cluster B is said to be uncovered.
The proof idea from here on is to show that there exists an approximation ratio Kort for the covered clusters, and is shown in Lemma D.2 and D.3
17

---

Lemma D.2. Let B C(@OPT) be an arbitrary cluster in (( and let f E I&' be service centered on the preference of user chosen uniformly at random from [n]. The expected loss of users in B, conditioned on j E B, satisfies
Bo [o IjEB
mDx jEB
2
Σ Gj
[(OOPT,
B
Proof. Since we choose a user from B, the conditional probability that we choose some fixed Φj B)
as the parameter for the service is precisely P(O = Φj service covering all the points in B, and then compute
= [
Let J (B) denote the best
Eo[c((0 (0](0=)))))) 3)), EEB
-E 20
Σ
Σ
B
jEB
JEB
Using Assumption 2.2 (ii) with 1 = =J(B), have that
1
Eg [o[( = IjeB]
+
B
Ctj
(,(J(B),
(B)
Ctj
B
Cij
JEB
iEB
iEB
JEB
Noting that Ctj Cjs. 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
1 B
E Cij
2(((()))))
Es[ = 23) 1 B
JEB
iEB
Now, using the fact that maxjeB above expression, we bring it outside the summation as a constant. Therefore, we deduce that
Eies cty
is uniform upper bound for the multiplier in the
[B]
Ee[c((0 111000,,,.B0 o,). E
max JEB
Σ
C(J(B).
(7)
B
Ctj
where have used the fact that L(J(B), B) covering J [(3) is the loss minimizing service among all services in θoPT for all points in B, Thus, we have that
Eie
L.
o.). Since B C(@OPT), the
2 B
Eg [C((0= (00,= 4)).B))BB).)))) BjE Bj
max JEB
L(OOPT,
Gj
This concludes the proof.
Lemma D.3. Let C(Oorr) be an arbitrary cluster in C(Horr), and let θ C Rd denote the parameters for set of preexisting t arbitrary services. Consider new clustering O++1 O U where 0 = Øj is a random service centered on user j E [n] selected with probability P(# = 6,) x (,, 6z). Then, the expected loss of B, conditioned on j E B, satisfies
1
Ee[c(O, (0))), ( E
max JEB
Σ Cij
L(OOPT.
minjes [3] EiEB Cji
B
Given that we choosing user from B, the conditional probability that center the new service on some fixed dy is precisely L(O,, () L(O,, o.)). After adding Ø, to the list of services, a user will have loss (in Φi), L,(0,, o.)). Therefore we deduce that
Proof.
Ee[C(O, (0= = Σ P(0 = 651 0 E B) E U0,,))),
JEB
iES
(8)
C, 0 04)
Σ
min( C,(,,, L.(0,,
Eien Li ④1)
JEB
ie8
18

---

By Assumption 2.2 ()), for any A E Rd we have that
cg:L, C.(0, 0e) + Li(0j, (1).
We utilize the fact that given two functions f.g e + R. if f(0) I g(0) v0 E θ then mingee f(0) I mingge g()). Hence, the following implication holds:
Gji min C0, (b) min Li(0, (x) 8ge Summing over all B, we get that
(1)
cr: L,(O,, .i) Li(0i,
BEB
Cj OJ) S
Σ C. 0.) + Li(ds, Ø.)
EieB Cjf
NEB
Applying this to L, x5) on the right hand side of (8), have that
Eies Li(Øj, EieB Li(Or, 0r)
Eo[c(O. U - B) E
1
Σ
min (s),
jEB
Since min(a, (a,00 b} & a, we further deduce that Eg|C(9, U (0 o)).
Eier Cjt
jEB
SEB
Eies Li(()j,
+
Σ
C(0,, 01);
iEB Cji
Eies Li(Or, 01)
jEB
iEB
2
En(0)
ZiEB Ctj
JEB
SEB
Now, we use the upper bound
for the multiplier to get
minyes Lice
()) E
2
ΣΣ jEB iBii
Lilo)
B minjes Eies Oj
Note that Ejes Eies [8 (1b,,, ②.) is essentially the loss on choosing users from B uniformly randomly and centering the service on the chosen user. Plugging in the expression in from the proof of Lemma D.2, we have that
4
Eg[c(O, B) |jEB]
max JEB
((J(B),
(9)
min JEB
B
Σ FEB
Cja
B
iEB
Since B C(QorT), the covering JBB) is the loss minimizing service among all available services θOPT for all points in B. Therefore, we deduce that
Eo|C(O, U Bi
Σ iEB
1 Cij
c(OorT,
min JEB
B
Σ IEB
Cjt
jEB
[B]
which concludes the proof.
The following Lemma is induction relating the losses covered and uncovered clusters.
Lemma D.4. Let O, C Rdd denote the parameters of set of I arbitrary services. Consider u >> 0 uncovered clusters from C(HoPT), denoted by Ur and let H. denote the covered clusters. Suppose we add v S u random services to θ, chosen with probability proportional to their current loss-i.e.. L(O,, -nd let Octv denote the the resulting set of services. The following estimate holds:
Eo [ [rt)]] < (E..I((,,, H.)) + KOPT (OOPT, 24)) (1 S.)
u-C
u
where KOPT is defined in 3 and S,
+ 1 ..... + 2) is the harmonic series.
19

---

Proof. Replacing the factor 8 in Lemma 3.3 from [S] by KOPT gives us the desired result.
With the preceding technical lemmas, we are now ready to prove the main theorem which we restate for convenience.
Theorem 3.1. Consider users with unknown preferences {Øi...., 2n} C R. and associated loss functions Ci(-.-) satisfying Assumptions 2.1 and 2.2 with bandit access. Let θorr C R be the set of k services minimizing the total loss and (PPPT) the resulting partitioning of users (Definition 2.3 If Algorithm is used to obtain lo services Ø₁ then the following bound holds:
Ee,, (C [n])] S (oPT log k) L(0OPT. [n]),
where the expectation is taken over the randomization of the algorithm and KoPT is equal
max
mmxxEB ΣiEB a33
1
(3)
min JEB
Proof. Consider = 1, and B C(OOrT), the cluster in which the first chosen user belongs. Applying Lemma D.4 with u = k and the fact that B is the only covered cluster, we have that
Ee, [0(, [n]]] S (Be, [C (01, BB] + Korr C (Gorr, [n] - -B) (0))-11 + Sk
Observe that
Ee, [C (01, S KOPT [(OPT,
by Lemma D.2
Moreover, we have that
L (OOrT, [n] B) L (0OPT, [n]) L. (0oPr,B).
Using these two expression and noting St-1 S 1 + log k, we get the stated result.
E Fair Initialization
We assume the scenario when the user demographic identities are known priori. Lety: [n] - A be mapping, which maps user i to its demographic group (i), and let In(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:
L.(O,
L(),
g(
(m)
Σ
Σ
hnill
IA
(E(m)
iE(m
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
Instead of uniformly picking a random, picking i with probability proportional to [+0] This is equivalent to saying, the probability of the first user being in some group A₁ E is
EiEA, POOT
1
Ejeial EiEA, HOT
That is, the first user is equally likely to belong to one the m groups. A user i at any time step t is selected with probability proportional to (, (i)). This implies that a user from some group A, E A is likely to be picked with probability proportional to the average demographic loss i.e.,
Σ ((0r-1.00//(0) = L(0,-1,A)) KEA,
AA
20

---

Algorithm 2 Fair AcQUIre- Fair Adaptively Querying Users for Initialization
1: Input: Set of users [n], number of services k, Demographic groups A = [Ai,.... An). Map
users to demographic groups y [n] +
2: Choose a user uniformly randomly from [n] with probability
3: Query user i's preference Φi. set the first service θ di.
4: for / (2....,k) do
5: User behavior: Collect user losses on existing services ① (0)
6: User Selection: Sample I from [n] with probability P(I = i) (0)0--,,0)//h(0
7: New service: Query user l's preference Φ1-
8: O2 = - ÚI.
9: end for
Return Oμ
We first state the approximation ratio of Algorithm 2 on the objective G(O, (n)).
Lemma E.1. Consider n users with unknown preferences {őI...., dn) C Rd, and unknown associated loss functions C.(..)) satisfying Assumptions 2.1 and 2.2 Let O C R2 be the set of k services minimizing the total loss and s(ascaled) the resulting partitioning of users. Algorithm used to obtain services ④y, then the following bound holds:
Ee, [n])] S. Ktain (2 + log k) G(Oscaled: [n]),
where the expectation is taken over the randomization of the algorithm and Kfair is equal to
4
max BEC(Osculed
min jEB
Σ
max JEB
(10)
iEB
EEB
The proof is similar as Theorem 3.1 with the introduction of |x()] D.3
's when deriving Lemma D.2 and
Theorem 3.2. Consider n users with unknown preferences { ,n. C Bd and associated loss functions C.(..) satisfying Assumptions 2.1 and 2.2 with bandit access. Suppose these users belong to m demographic groups A = {AA....., Am nn]. Let Otair C. Rd be the set of services minimizing the fairness objective de given in (4). If Algorithm is used to obtain k services O₁ then the following bound holds:
2.2
Be, ( A)] S mKisir (2 logk) o (O A),
where the expectation is taken over the randomization of the algorithm and Kfair is defined in 10
Proof. For any O Rdd have that
L(O,A.) A4j
L(O,A))
A) = max
(m),
ic/m]
A,
(E(m)
For - the output Algorithm D the above expression implies that
Ee, [ A)] Eo, (g(@), [n])]
We also have that
L(O Pairs A:)
C(O Ad)
G(Omar [m])
Σ
Ai
max <e(m)
[A
m ((riir A).
kE|m]
(EIm]
Let Oscaled be the minimizer of G(:, [rz]) and Otatr be the minimizer of (), Then, we have that
@(Osraten [m]) < ((O [x]) & m ((Otair; A) S m Ee,, (#0 A)) S m Ee, (9(0,, [n])]-
Now using Lemma E. for the guarantee θ₁ for g(:, [n]), conclude the proof.
Remark E.2. If all c.y 's are identically equal to some 0, Kiair = 3 and the approximation ratio of Algorithm 2 for the fair objective is 4m(2 + log k)/c². Meanwhile, Algorithm | would have an approximation ratio
ma
Ag
(2 log k)
4m
min
c2
21

---

F
Proof of Theorem 4.4
Let the empirical loss which is finite sample average regression loss be denoted
(0,
Σ 10 10' -
jE(P)
where {(2) ( v/) b5))senn are private unknown features and scores of the users, respectively.
Lemma F.1. Under Assumptions 4.1 and 4.3 each subpopulation empirical loss E, satisfies Assump-
tion 2. and Assumption 2.2 with
Eiema =((=)) Eieln a3( ( n2
Cjj 2 Amiu
n
Proof. Fix a subpopulation index i. We start by showing 2. satisfies Assumption 2.1 We use the following result: if S. d random vectors in I2d are independently drawn from a distribution that absolutely continuous with respect the Lebesgue measure, then they are almost surely linearly independent. By Assumption 4.3 applying this result to our scenario, if we draw 2 d features independently from a sub- Gaussian distribution to form feature matrix X, E R"ixd then it is almost surely full column rank.
Therefore, we compute o; = X,y: since x(X, = I, when X; is full column rank. The subpopulation i's empirical loss is compactly written (0, 0;) ||0 1 where A, - n. Eieina =
Thus (0, o.) satisfies Assumption 2.1
We now show that É, satisfies Assumption 2.2 with Gı 1 Amin (A,, Aj). To this end, we find the largest E R, such that c(u" T A,u) uuT A' and c(u Aju) S T A,u for all u E Rd.
Rearranging the inequality, this problem is the same as finding the largest E R4 such that u1 (A, cA,)u
and A, cAi)u 2 0 Vu YuERd.
or equivalently.
A; cA ž 0 and A, - A ž 0. Therefore, finding such a constant e is easily reformulated as the following optimization problem: max(cl A; cA, = 0, Aj cA, = 0} Amin (A,, Aÿ).
There are two key tools we use to finish the argument.
For any Rd, Ammi (A,, Ay)llu1,, S ||u]2
For any norm triangle inequality gives us 110 6ill < 00 0 o,1l 11,; -5ill. Then we use
power mean inequality, i.e. a S b c = a² s 2(1 + 2)
The following shows Assumption 2.2 (i) holds with Cij = 2 Ammiu (A,, A;):
1
1
2 Amin A, A C.,,
2 Aminn ( (A,, A, 1)110 12
1
< マ1 110
&ell
110 (0-0, 112, + +110; -3
(0, + [, 0,),
Analogously, the following shows Assumption 2.2 (ti) holds with Czj = j/2 Xumin Aj):
Amin A, Amin (A, ,1oo 2.l13
S Amin (A, A,) (I10 6, + +100 12.)
S 10 o5 05l|,, + 100 $1112.
= (0, o,) + (,
This concludes the proof.
22

---

With the preceding technical lemma in place, we now are ready to prove Theorem 4.4
Theorem 4,4. Suppose users belong to N subpopulations satisfying Assumptions 4.1
4.2 and 4.3
Let (ni)iE[N] denote the number of samples per subpopulation. Let 2y be the output of Algorithm / using finite sample estimates Le(;, 6.) and θOpT be the optimal solution of the expected loss. Then, for any E (0, 1). if nn = 52( VNN log (2/6)) for all E [N) the following inequality holds with probability least -.
Ea [c(O2, ND] 2 _ KoPT(2 log ()O0T). [N]), where KOPT is as defined in and
Cij 1/2 min { Amin (E,, E,), Amin
1 (., } with E, Dranu =f(a)), Eg ny Eienn 2 (x))
Proof. Lemma F11 gives us that the subpopulation i's empirical loss for a regressor E Rd can be written as ||0 Φe 11,, This is random quantity since A; is sample average covariance of randomly chosen features. We analyse this term next.
For random feature x E Rd in subpopulation i, given fixed center 0 E Rd the term
(0 dv
is sub-
| d. 1
Gaussian with variance proxy of by Assumption 4.1 The square of a sub- Gaussian random variable, (0-6.) ax (8-0x) is sub-exponential with parameters v/ 32o |10 -. Il
40, (see [22 [Appendix
B)).
Since subpopulation i's empirical loss is average of nı samples, the empirical loss |00 Φb 1 is subexponential variable with parameters of sample average scales vn. and the constant ||0 d1113, scales the subexponential parameters appropriately.
u2 ||0 dolli. an vmz
||0 dx de This because the variance
nu
Now, given set of k arbitrary services θ = (0I,... 0z} C Rd, let o2(0) E O be an arbitrary service chosen by subpopulation The sum of empirical losses on based on such choices is also
zf subexponential with parameters 2² Eie[N] / 11 dilli,, and = max 7n, 110 d.
Using Chernoff bound 440, we have that
t²
22
P
|10x(0) kE(N)
Σ KE(N)
10x00)
o.113,11
2 S 2exp
(-20²
where 0 55t5
2//
a
(11)
Note that the probability bound is is increasing in v, thus take upper bound on y² to upper bound this probability:
2
110
0i = 32
Σ VE[N]
L 10,000
-111s. S 32
Σ KE[N]
10 - dill
Thi
n
iE[N]
where the last inequality follows from Cauchy-Schwarz. Further, noticing that Eien ot 5 EEen a,) and applying it for the last term twice, we deduce that
1
2²
32
Σ
10
$4 E,
n
NE(N
'A random variable is subexponential with parameters (62, a)) if Elexp(Ax)) S expl (xp(222) 1/AA S
23

---

Choosing
EiE(N) 107(0)) - 2.11..
where 0 <
of [miinee[N]
have that
yuz
P
100 10-(0)
Σ
100 7()
0ill
|0-30 25113,
iE(N]
iE[N]
E N
2
2
exx
64
SEIN
With high probability, at least 1 - cxp (- [Eie(N) a -1/2)
for all θ C R,, we have that
(1 c) Σ [10,0) - 0i113, S
Σ (l)(()) - 0. $ (1 +c) VE[N]
|0,(0) - 3.l... Σ SE[N]
[EIN]
The rest of the proof is deterministic, thus it is assumed everything follows with probability at 11/2
Define ON = θ x ... @iie.. Cartesian product of the set ④ N-times. Given two functions f.g ON - IR, if f(0) S (0) for all 0 E ON then minggex f(0) < mingaee g(0). Therefore, we deduce that
least - 2exp
- [ie[M]]
(1-6) Σ min 10, 0:113. S min 10 0:122 S (1++)) iE[N]
Σ
Σ
min 10, 0,1 (12)
JEI
JEJK
jE(K]
AE[N]
VE[N]
Hence, given the total expected loss as follows:
of services O the total empirical loss can be bounded with respect the
(1-c)C(O,(N) s E(e, S (1)))
Recall OoPT denotes the optimal solution for the total expected loss and let θOPT denote the optimal solution for the total empirical loss. Let O₁ be the output of Algorithm on finite samples per subpopulations. Using the first inequality of 12). we have that
(1 - Ee, [M)] S Ee, Ee, (o [N])..
(13)
Also, noting that θOPT is the minimizer for Z(e, [N]) and using the second inequality of (12) get that
2( [M] < Ž(0Orr, + < (1 + c) +).
(14)
Now combining
13 and with Theorem 3.1 we get the desired result-i.e..
Ee. [c(0x, [N]) < + Kort(2 + log L(OOPT, [N]).
)111)) get that n, 2( 2 log (2/6)) This con-
Setting 1 2exp
(-67 (Eie(N) x
cludes the proof.
G Experiment Details
The categorical features (schooling, marital status, migration status, citizenship) were first converted 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 the demographic groups considered. The percentage improvements of our algorithm are plotted in Figure
Census Dataset.

---

Demagraphics
Demographics
15
Fair Ospection
10
Mumber services (R)
Number of services (K)
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 demographies the improvement 7-26%.
Radial Demographics
(We gloud)
220
can hntlar (Wl ghrad!
2.3
Wandan Nattee (Weithedd
ihus Act.hral
Alskkn Nation (har AuDUinc) Poolss biiree (hepliad leancer thir Aequine
Denogaale
0dlas Shighiest
Other: Am
Feir Oiteetivee
120
120
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.
In Figure 5 we plot the average losses on the individual demographic groups. We benchmark against the weighted random baseline and note that Fair AcQUIre improves not only the fair objective value but the loss for every demographic group.
We use Surprise (a Python toolkit (23] to perform our experi- ments. 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.
Movie Recommendation Dataset.
Ablation: We use a 2 layer Neural Network with ReLU activations that takes as input the user features and outputs their score. We still use the standard squared prediction error. However note that in this modeling scenario, the loss no longer satisfies our assumptions in the parameters of the neural network. Given user's features and true score, since there are no unique minimizers, we run gradient descent to compute local minimizer and then use this trained neural network as a service to predict other user's scores. We run AcQUIre and other baselines under this modeling and report our results in Figure 6. We find that the performance of AcQUIre even when violating assumptions is almost similar to using AcQUTre under modeling which satisfies assumptions.
Additionally, we would like to emphasize that the implementation of our algorithm itself does not rely on these assumptions. only requires the loss values to be observable. Therefore, one can model very complex precision models and only supply the loss values of these models to our algorithm.
25

---

24g lazk swo.rrg 26GACIpRATS SCorSr Datan
FUX Loss Mabkiing SGGARTSC SNG ISensas
Arg LOGG wwl.oli EERATIRRCCS CMMAAORISIONN
275
AICARRE
230
AcOUli
200
Fanden 2011
Delencee for owen 19AC
For dare
125
Oreaiyy (M00
2.20
Crocily
PV11
Eptter (ready
Sha Neveon
Sander
Figure 6: We evaluate the performance of initialization methods when Assumptions 2.1 and 2.2 are violated. "AcQUIre (NN)" refers to using AcQUIre with a Neural Network (NN) to predict scores. This terminology is consistently applied to all other baselines as well. Notably, the performance of AcQUIre doesn't 't degrade when using Neural Network to predict the scores, thereby demonstrating its robustness to violating the assumptions made in the paper.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We abstract out the problem statement, challenges, and novelty in solution ideas the abstract.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we clearly state all the assumptions that the theoretical results rely on. We also briefly discuss open directions which were not covered in this paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
26

---

The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Proof sketches are in the main paper, with full proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We state experimental setup and details, and provide anonymous link to our code base and links to the two publicly available datasets that we used in the experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
27

---

(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Yes, we provide both code link and upload codebase in the supplemental.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.cc.. cwtppbliccguudeeeeeeeecceeceeeee Stael////guddee//dCeSuuuuiiiiii /et////ooeSemeeeee commiissionll ssionPolicy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The focus of the paper is not experimental, but experiments are used to illustrate our algorithmic and theoretical contributions. All details are specified in the experiments section and the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
28

---

7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report number of trials and error bars.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All our experiments can be run personal devices.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:////eeereeeecc///ppbb/////a
Answer: [Yes]
Justification:
We have read the code of ethics and verified we align with
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
29

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: While it is not the main focus of the paper, paper has devoted section that considers the fair version of the total loss, and discusses the fairness aspects of the proposed methods.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairesss considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper is mostly theoretical in nature and poses such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
30

---

Answer: [Yes]
Justification:
We eite the dataset papers.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's ' creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper is theoretical in nature.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects were needed for this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
31

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
32


Reviews:
[{"review_id": "uTDwMqO1ki", "reviewer": "Reviewer_XL2L", "summary": "1) This paper introduces a new algorithm to efficiently initialize a system providing K services to N users (K << N) where user preferences are unknown beforehand and the system iteratively learns about user preferences as the services are recommended, example : netflix movie recommendations. \n\n2) The proposed method has been inspired by the k-means++ algorithm and applies it in a more general setting. Authors also provide theoretical proof that the system initialized in this way will achieve a worst-case loss not exceeding a log multiplier on the optimal loss for this system. \n\n3) AcQUIre and  it's modification to preserve fairness across subpopulations (Fair AcQUIre) are the main algorithms presented in this paper with experiments ablating the effect of different user selection strategies used in AcQUIre\n\n4) Experiments on census dataset and movielens dataset are provided.", "questions": "1) It is unclear how line 7 of the proposed method : \"New service: Query user l’s preference\" would be implemented in a real world setting. In a large scale distributed recommendation system such as netflix where user preferences are being collected on a subset of recommended services in parallel as soon as the system is deployed it's unclear how to get a specific user's preferences so some clarification here would be useful.", "limitations": "There's no negative societal consequences of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) Paper is well-written and authors have done a great job introducing the problem with sufficient notations and related work.\n\n2) The problem introduced is very relevant and encourages future research in this direction.", "weaknesses": "1) In the \"Movie Recommendation\" experiment users are divided into N=1000 subpopulations based on the similarity of their movie ratings and all experiments are then conducted to achieve minimal excess error w.r.t to these subpopulation groups, however in a typical setting where the proposed method might be applied there's no such prior data to group users conveniently so an ablation on user clustering methods prior to applying AcQUIre would further boost it's effectiveness. \n\n2) The size of the datasets are small enough to make the computations practical but the method is actually expensive depending on the choice of K the system needs to get desired loss on the population of N users, so some discussion around this aspect would be useful where authors go deeper in practical deployments of this method is a system like Netflix recommending movies to a billion users.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review, and for finding our problem setup novel with the potential to encourage future research in this direction. We appreciate the thoughtful questions the reviewer asked, and believe that our findings and explanations to these questions will further strengthen our paper. Here are our responses: \n\n1. **Subpopulation grouping (Weakness 1):** We appreciate the reviewer's insight regarding the practical application of our method where prior data for grouping users may not be available. To address this, we have conducted additional experiments to evaluate the dependence of AcQUIre's performance on the quality of grouping. Specifically, we initially form clusters based on prior data, then shuffle x% of the users into incorrect clusters, varying x from 100% (completely random grouping, i.e. no prior data) to 66%, 33%, and 0% (accurate grouping based on prior data). Our results demonstrate  that AcQUIre consistently outperforms the baselines across all values of x (see Figure 1 in attached pdf). Additionally, Figure 1 (right) shows that AcQUIre with different qualities of user grouping outperforms all the baselines with accurate grouping based on prior data. Als0, the performance deterioration as x varies from 0 to 100 is very small, demonstrating AcQUIre’s robustness to accuracy of prior data to form groups. \n\n2. **Time Complexity (Weakness 2):** We appreciate the reviewer’s concern regarding the computational efficiency of our proposed algorithm, AcQUIre. We want to emphasize that despite these concerns, our algorithm is indeed very computationally efficient, even for large-scale settings like Netflix, where recommendations are made to a billion users. Below, we provide a theoretical analysis of the computational complexity of AcQUIre and also back it up with empirical validation.\nTheoretical Analysis: We sketch the computational complexity of AcQUIre. Each iteration of the loop is examined as follows:\n\n      Line 5: Collecting data across a large user base occurs in a distributed network for recommendation systems like Netflix, where \n      queries can be processed in parallel. This step effectively takes O(1) time.\n\n      Line 6: After aggregating the data, a new user can be sampled in O(log⁡N) time with modern multinomial samplers (see [1], just as an \n      example).\n\n      Lines 7 and 8: These involve O(1) time updates, as they are performed only on the selected user.\n\nSince the loop runs K times, the total cost is O(Klog⁡N). The growth in N is logarithmic, while the growth in K is linear. In practical settings like Netflix recommendation systems, K is much smaller than N. For instance, Netflix groups N=200 million users into 1300 recommendation clusters [2]. Just to compare with our baselines, the greedy and epsilon greedy methods are O(KN) because selecting the highest loss needs going over all N users.\nExperimental Validation: To study the effect of number of users N on the runtime, we generate synthetic datasets in d=200 dimensional space with sizes N=10^4, 10^5, 10^6, 10^7, 10^8, 10^9 (1 billion), and report the runtimes for AcQUIre and the baselines in Figure 2 (left) (attached in the pdf) keeping number of services K fixed at 2000. We observe than even with N=1 billion users, AcQUIre finishes running in less than 300 sec (5 minutes), whereas the greedy and epsilon greedy methods take >10^5 sec (~1day) even for N=10 million users.\n\nTo study the effect of the number of services K on the runtime, we generate a dataset with N=5 million users  in d=200 dimensional space  and report the runtimes in Figure 2 (right) as we vary K from 500 to 5000 in steps of 500. We find that even with 5000 services, AcQUIre finishes running in <900 secs (15 minutes), whereas the runtimes for greedy and epsilon greedy are in the range of 10^5 secs (~1-3 days). \n\nWe hope this addresses the reviewer’s concerns and demonstrates the practical efficiency of our method for large-scale recommendation systems.\n\n3. **Querying new user preferences (Question 1):** In a large-scale distributed recommendation system like Netflix, user preferences are collected from initial interactions with the service. When a new set of services is deployed, user preferences can be quickly gathered by prompting users to rate or select their favorite content from a curated list. Additionally, the system can analyze immediate user behaviors, such as search queries, viewing choices, and engagement patterns, to start building a profile. Services like Netflix often also provide incentives such as free first month trial to increase new user engagement during the free trial. As users spend more time watching movies, Netflix gathers more data about their preference. \nIt is realistic that all users will not have high levels of engagement when a set of new services are provided. Our algorithm also works when only a small set of a potentially large subpopulation interacts with the provider. Our results in Section 4 provide confidence bounds on the performance of AcQUIre in this setting (see Theorem 4.4). \n\n[1] Bringmann, Karl, and Konstantinos Panagiotou. \"Efficient sampling methods for discrete distributions.\" In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012\n\n[2] https://recoai.net/netflix-recommendation-system-how-it-works/", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NNLFiY3cYa", "reviewer": "Reviewer_qH2x", "summary": "This paper introduces a novel method for initializing services in interactive machine learning (ML) systems tailored to diverse user preferences. The focus is on scenarios where multiple models or services are deployed, allowing users to choose the one that minimizes their personal losses. The authors highlight two primary challenges in determining optimal initial conditions for these services: the absence of user preference data prior to deployment (bandit feedback) and the presence of non-convex loss landscapes that can lead to suboptimal local solutions. To overcome these challenges, the authors propose a randomized algorithm for service initialization. They provide theoretical guarantees, demonstrating an approximation ratio for the algorithm, and present empirical results that showcase the approach's effectiveness on both real and semi-synthetic datasets.", "questions": "- What is the performance of optimization algorithms after using your proposed initialization method? Have you empirically compared that performance with other existing initialization approaches?\n\n- Could you elaborate on the potential impact of violating the assumptions made about the loss functions? How robust is your algorithm to deviations from these assumptions in practice?", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed adaptive randomized algorithm for service initialization in interactive ML systems is a novel contribution. It extends the well-known K-means++ algorithm to a more complex setting involving diverse user preferences.\n\n- The paper provides strong theoretical guarantees, including tight bounds on total loss and a generalization of the K-means++ guarantee. This adds significant value by ensuring the robustness of the proposed method.\n\n- The empirical results on real and semi-synthetic datasets validate the algorithm's effectiveness in reducing total loss and improving service specialization. The inclusion of fairness considerations further strengthens the practical relevance of the work.", "weaknesses": "- The algorithm relies on specific assumptions about the loss functions (e.g., uniqueness of minimizers, approximate triangle inequalities). These assumptions, although reasonable in many cases, may not hold in all practical applications, potentially limiting the algorithm's applicability.\n\n- The empirical validation, although convincing, is limited to two datasets. Additional experiments on a broader range of datasets and application domains would provide stronger evidence of the method's effectiveness and generalizability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed review, and for finding our tight bounds on a novel setup to be a significant contribution, as well highlighting the practical impacts of our fairness considerations. Below, we hope to address some of the reviewer’s questions:\n\n**Question 1 (Performance of optimization algorithms after initialization):** We thank the reviewer for this question. Once a set of services are initialized, indeed with more user interactions, the provider updates the services on new data to improve the quality (indicated by the reduction in total loss). To evaluate the importance of initialization, we conducted experiments using two different optimization algorithms:\n\n**Generalized k-means:** The services are iteratively updated by training each service on the current group of subpopulations selecting it. After updating the service parameters, the subpopulations reselect their best service. This process repeats until convergence.\n\n**Multiplicative weights update [1]:** Similar to k-means, but each subpopulation can have users choosing different services \n      simultaneously. \n\nBoth generalized k-means and the multiplicative weights update guarantee that the total loss reduces over time [1].\n\nIn our experiments, we initialized a set of services using our proposed initialization scheme, AcQUIre, and other baseline methods. We then let both optimization algorithms run until convergence. We plotted the total loss values as a function of the number of iterations (see Figure 3 in the attached PDF). Our results demonstrate that our initialization method, AcQUIre, leads to:\n\n**(A) Faster Convergence:** The optimization algorithms converge more quickly with our initialization method compared to other baselines. \n\n**(B) Lower Final Loss:** Initializing with our method convergence to lower losses whereas other initialization schemes are prone to being stuck in suboptimal local minimas. These findings highlight the significance of a robust initialization strategy. \n\nBy starting with a better initial configuration, the optimization algorithms can more effectively and efficiently reach higher quality solutions. The reviewer's comments underscore the importance of this aspect, and we believe our empirical comparisons provide strong evidence of the advantages of our proposed method.\n\n**Question 2 (Robustness of AcQUIre to violating assumptions):**\nWe appreciate the reviewer’s attention to the potential impact of violating assumptions underlying our proofs. We conduct a new set of experiments, where we use a 2 layer Neural Network with ReLU activations that takes as input the user features and outputs their score. We still use the standard squared prediction error. However note that in this modeling scenario, the loss no longer satisfies our assumptions in the parameters of the neural network. Given a user’s features and true score, since there are no unique minimizers, we run gradient descent to compute a local minimizer and then use this trained neural network as a service to predict other user’s scores. We run AcQUIre and other baselines under this modeling and report our results in Figure 4 (see attached pdf). We find that the performance of AcQUIre even when violating assumptions is almost similar to using AcQUIre under modeling which satisfies assumptions.  \n\nAdditionally, we would like to emphasize that the implementation of our algorithm itself does not rely on these assumptions. It only requires the loss values to be observable. Therefore, one can model very complex precision models and only supply the loss values of these models to our algorithm.\n\n[1] Dean, Sarah, et al. \"Emergent specialization from participation dynamics and multi-learner retraining.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kZlQLmsQkq", "reviewer": "Reviewer_vEYc", "summary": "The paper introduces a novel method for initializing machine learning services tailored to diverse user preferences. The work addresses the challenges of non-convex optimization and lack of pre-existing user preference data before running a service; the authors propose a randomized algorithm that adaptively selects a minimal set of users for data collection. The approach guarantees a total loss close to the global optimum under mild assumptions and extends the k-means++ algorithm to a broader problem class. The results also are supported by experiments on real and semi-synthetic datasets.", "questions": "Could you provide any data on the time performance of the algorithms in the experimental study?", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors tackle the challenge of service initialization in the context of bandit feedback and non-convex optimization, which has not been extensively studied before. The proposed algorithm is an interesting extension of the k-means++ algorithm, designed to handle general loss families. The analysis of the proposed approach is solid. The theoretical result is supported by experimental study. The paper is well-written and clearly structured.", "weaknesses": "The computational complexity is not well studied, especially in large-scale settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and thoughtful review of our paper. We appreciate your positive comments on both the theoretical and experimental study, as well as finding our paper well-written. Below, we hope to address your concerns regarding the computational complexity of our algorithm:\n\nWe want to emphasize that our algorithm is indeed very computationally efficient, even for large-scale settings like Netflix, where recommendations are made to an order of a billion users. Below, we provide a theoretical analysis of the computational complexity of AcQUIre and also back it up with empirical validation.\nTheoretical Analysis: We sketch the computational complexity of AcQUIre. Each iteration of the loop is examined as follows:\n\nLine 5: Collecting data across a large user base occurs in a distributed network for recommendation systems like Netflix, where \n      queries can be processed in parallel. This step effectively takes O(1) time.\n\nLine 6: After aggregating the data, a new user can be sampled in O(log⁡N) time with modern multinomial samplers (see [1], just as an example).\n\nLines 7 and 8: These involve O(1) time updates, as they are performed only on the selected user.\n\nSince the loop runs K times, the total cost is O(Klog⁡N). The growth in N is logarithmic, while the growth in K is linear. In practical settings like Netflix recommendation systems, K is much smaller than N. For instance, Netflix groups N=200 million users into 1300 recommendation clusters [2]. Just to compare with our baselines, the greedy and epsilon greedy methods are O(KN) because selecting the highest loss needs going over all N users.\nExperimental Validation: To study the effect of number of users N on the runtime, we generate synthetic datasets in d=200 dimensional space with sizes N=10^4, 10^5, 10^6, 10^7, 10^8, 10^9 (1 billion), and report the runtimes for AcQUIre and the baselines in Figure 2 (left) (attached in the pdf) keeping number of services K fixed at 2000. We observe than even with N=1 billion users, AcQUIre finishes running in less than 300 sec (5 minutes), whereas the greedy and epsilon greedy methods take >10^5 sec (~1day) even for N=10 million users.\n\nTo study the effect of the number of services K on the runtime, we generate a dataset with N=5 million users  in d=200 dimensional space  and report the runtimes in Figure 2 (right) as we vary K from 500 to 5000 in steps of 500. We find that even with 5000 services, AcQUIre finishes running in <900 secs (15 minutes), whereas the runtimes for greedy and epsilon greedy are in the range of 10^5 secs (~1-3 days). \n\nWe hope this addresses the reviewer’s concerns and demonstrates the practical efficiency of our method for large-scale recommendation systems.\n\n[1] Bringmann, Karl, and Konstantinos Panagiotou. \"Efficient sampling methods for discrete distributions.\" In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012\n\n[2] https://recoai.net/netflix-recommendation-system-how-it-works/", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all the reviewers for their detailed reviews. We deeply appreciate the questions and insights the reviewer's gave in their reviews. We attach below a set of empirical studies to hopefully answer the questions the reviewers had. Please let us know if we can answer any more questions. Thanks!

Meta-review: The paper gives a new algorithm for an ML system providing K services to N users with service aimed at a sub-group of users. User preferences are unknown beforehand and the system iteratively learns these preferences. The method proposed is inspired by the kmeans++ algorithm. The authors provide a theoretical bound as well as experimental results for their method on cendud dataset and movielens. 

The reviewers unanimously appreciated the contribution of the work. Some questions raised by the reviewers were answered sufficiently in the rebuttal. The revision was quite satisfactory to the reviewers. I am happy to recommend acceptance.
Decision: Accept (poster)