Initializing Services in Interactive ML Systems for Diverse Users

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:

We 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. Theoretical Analysis: We sketch the computational complexity of AcQUIre. Each iteration of the loop is examined as follows:

Line 5: Collecting data across a large user base occurs in a distributed network for recommendation systems like Netflix, where queries can be processed in parallel. This step effectively takes O(1) time.

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 example).

Lines 7 and 8: These involve O(1) time updates, as they are performed only on the selected user.

Since 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. Experimental 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.

To 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).

We hope this addresses the reviewer’s concerns and demonstrates the practical efficiency of our method for large-scale recommendation systems.

[1] Bringmann, Karl, and Konstantinos Panagiotou. "Efficient sampling methods for discrete distributions." In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012

[2] https://recoai.net/netflix-recommendation-system-how-it-works/

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:

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:

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.

Multiplicative weights update [1]: Similar to k-means, but each subpopulation can have users choosing different services simultaneously.

Both generalized k-means and the multiplicative weights update guarantee that the total loss reduces over time [1].

In 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:

(A) Faster Convergence: The optimization algorithms converge more quickly with our initialization method compared to other baselines.

(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.

By 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.

Question 2 (Robustness of AcQUIre to violating assumptions): We 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.

Additionally, 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.

[1] Dean, Sarah, et al. "Emergent specialization from participation dynamics and multi-learner retraining." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

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:

1. 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.

2. 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. Theoretical Analysis: We sketch the computational complexity of AcQUIre. Each iteration of the loop is examined as follows:

   Line 5: Collecting data across a large user base occurs in a distributed network for recommendation systems like Netflix, where queries can be processed in parallel. This step effectively takes O(1) time.

   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 example).

   Lines 7 and 8: These involve O(1) time updates, as they are performed only on the selected user.

Since 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. Experimental 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.

To 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).

We hope this addresses the reviewer’s concerns and demonstrates the practical efficiency of our method for large-scale recommendation systems.

3. 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. It 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).

[1] Bringmann, Karl, and Konstantinos Panagiotou. "Efficient sampling methods for discrete distributions." In Automata, Languages, and Programming: 39th International Colloquium, ICALP 2012

[2] https://recoai.net/netflix-recommendation-system-how-it-works/