Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of estimating the change in the performance of commercial ML APIs (ML as a service) as the models are updated over time (experiments are for 2020 vs 2021). It formalizes the problem as estimating the change in the confusion matrix over time. The main theoretical contribution is an adaptive sampling method to more efficiently estimate this shift. Interesting empirical results on various ML APIs are provided in the paper, showing the relevance of the problem and the effectiveness of the proposed method.
main_review: **Originality and significance**: To the best of my knowledge, this is the first work to systematically investigate the shift in the performance of commercial ML APIs. With the popularity of these services on the rise, it is important to study various aspects of the models, including the variations of the performance over time. The proposed sampling method is also novel and can be used in similar settings where model queries are expensive. The paper aims to minimize the Frobenius norm of the error in estimating the confusion matrix of classifiers, while keeping the sample complexity close to the optimal allocation strategy (in hindsight). The proposed algorithm asymptotically approaches the optimal allocation decay rate of 1/N. The empirical studies suggest that the proposed method can be an order of magnitude more sample efficient compared to random sampling.

**Quality and clarity**: The paper is well written and motivates the problem with case studies and examples. The algorithms and theorems are clearly stated. I did not check the proofs in the appendix.

Some limitations of the work:
- The method (as described in the paper) only applies to classification settings.
- Although not a strict requirement, the experimental analysis of the sampling method benefits from a rough estimate of the “difficulty” of each example before it is evaluated by the ML API . This “difficulty” is calculated by using a separate (client-side) cheap model. This goes against one of the main appeals of ML APIs that try to minimize client-side evaluation setup (think installing TF runtime, etc). There are no ablation studies on the quantified role of using such client side models.
- The experiments could be improved by comparison to baselines other than random sampling. Though this might not be possible with updated APIs.

Note: I was a reviewer to an earlier version of this work. Compared to the previous version, (1) the writing of the paper is improved in parts, (2) there is a more clear discussion of related work, and (3) the dataset is being publicly released.
summary_of_the_review: This work opens a discussion around the problem of estimating the performance shift in commercial ML APIs (for classification). The paper defines a metric for the performance shift of such APIs (via the confusion matrix), and presents a method to achieve near optimal sampling rates.

The theoretical contributions of the paper are small but non-trivial. The experimental analysis is detailed and interesting, but could benefit from further ablation studies on the effect of the client-side difficulty gauge model. The problem is of interest to the ML community and the release of the annotated dataset used in this work would be useful to the community.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: API shifts are common in several deployed machine learning models. This work proposes an efficient way to measure shifts in the confusion matrices of ML models using limited number of API calls. 
main_review: The problem addressed is important and the method seems to yield good results in practise in comparison to random sampling. 

Once concern is its unclear why this problem cannot leverage some of the existing work on stratified sampling (based on explanation at the end of section 1) with the aim to reduce the variance of the estimator? Could you please elaborate on this. After all, the goal is to estimate elements of the confusion matrix. 

Based on section 3.3, does MASA yield an optimal allocation of API calls?
summary_of_the_review: API shift is an important problem that needs to be addressed in order to operationalising AI. This work proposes a way to assess these shifts using limited number of API calls and has a lot of practical importance. Most deployed ML models are also priced in a manner wherein each API calls has an associated cost and thus performing API shift assessment using limited calls is quite important even from a pricing stand point.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Authors show that ML models behind publicly available APIs change and these changes cause result changes for input datasets.
Authors track the changes through confusion matrix differences. They propose an efficient algorithm they call MASA to evaluate the changes in results with reduced number of queries. Their algorithm achieves better estimates given the same budget than uniform sampling.
main_review: Strengths:
- Tackles important practical problem of the result differences from ML APIs
- Presents accuracy change results from a number of actual ML APIs from leading providers
- Authors created a novel algorithm (MASA) to efficiently detect and evaluate result differences for ML APIs. 
- Authors demonstrate that MASA significantly outperforms baseline algorithms.

Weaknesses:
- Accuracy changes from actual ML APIs is limited in scope. Only few systems were analyzed and only for two dates (spring 2020 and spring 2021). It would be interesting and important to track both more systems and more time points
- Unclear how confusion matrixes were used for speech recognition task, which presumably has a very large number of "classes". I am guessing authors treated speech recognition problem as classification problem for evaluation. However, there are no details on this. It would be good if this was explained and info provided.
- As authors noted, confusion matrix difference is a good measure as a result drift only for certain (classification-like) APIs. It would be good to see how to deal with non-classification APIs.
- Authors suggest that the differences seen in confusion matrix provide useful insights into how API results changed and why they changed. There is little substantiation of usefulness of how the API results changed. I.e. is confusion matrix difference really the best we can do to show how the API results changed? Regarding "why" the results changed, the authors provide guesses, but it seems to me that we cannot really know based on the results. If we cannot determine the "why", this should be stated. If we can, then it would be good to see what can be determined and how. 

Minor typo:
Page 7: diffident - should be different.
summary_of_the_review: I think that the problem of ML API result shift is real and important. I believe authors made interesting and useful contribution in evaluating such shifts. Although the paper has some weaknesses, I would recommend accepting it.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: A method to estimate the confusion matrix of a black-box classifier, using as few samples as possible. The paper is focused around one use case: tracking changes in ML APIs, considering that such changes may go unannounced.
main_review: Strengths
- The use case is one that is not often studied, yet is important both from a business accountability perspective (assessing the trustworthiness of a commercial ML API) and ethics perspective (providing information to society about hidden dangers in commercial ML APIs, which are difficult to track because of the algorithmic intransparency that is a common problem in the tech industry)
- Algorithm is uncomplicated to implement, and provides clear improvement over naive sampling methods
- Collected dataset on API shifts is novel, and is a major contribution of the work if released to the public

Weaknesses
- The idea of difficulty levels (K) is not well-developed. There are a couple of places where I was expecting more details: (1) some experiments use K=2 while others use K=3, what is the justification for doing so?; (2) I was expecting an ablation study comparing MASA with K=1 vs MASA with K>1. As the paper stands, it is unclear just how much of MASA's performance improvement over uniform and stratified sampling is due to K, versus the uncertainty-based sample selection.

Other suggestions for improvement
- Being able to measure the uncertainty in each partition, and use that uncertainty to inform sample selection, is the key idea that makes MASA perform better than uniform or stratified sampling. Given the importance of this idea, it would be better to explain this via an intuitive figure. As a suggestion, the authors could visualize how a partition in which the ML API classifies all data points with the same class (whether right or wrong) will have low uncertainty, while the opposite gives high uncertainty.
summary_of_the_review: The paper makes atypical but important contributions to ML ethics. Although the proposed algorithm is not groundbreaking from a technical perspective, it does contribute significantly towards measuring and tracking changes in black-box APIs, and I think it is of high value to society. I am concerned that the idea of difficulty levels (K) is not fully developed, but I lean towards acceptance.
review_title: null

Meta-review: The paper studies real world ML APIs' performance shifts due to API updates/retraining and proposes a framework to efficiently estimate those shifts.  The problem is very important and the presented approach definitely novel. My concern is about limited novelty of the theoretical analysis and weak experimental evaluation (just two dates, limited number of systems tested, small number of ablations). As of now the paper looks like an interesting but unfinished proposal. Looking forward to the discussion between the authors and the reviewers to address the concerns.

In the rebuttal, the authors have addressed reviewers' comments, in particular by adding additional experiments that strengthen the paper. All the reviewers recommend the paper to be accepted. It is suggested that in the camera-ready version the authors will add additional details regarding the experiments, as some of the reviewers mentioned.
Decision: Accept (Poster)