When to retrain a machine learning model

Thank you for the review of the paper. We will update a revised version of the paper before the end of the rebuttal with the changes and suggestions.

Missing essential related work (uncertainty estimation/quantification)

Uncertainty quantification methods estimate the probability of error for individual samples given a model $f$ with the goal to assess the risk of specific predictions ($P(f(x)=y|x)$). In contrast, our approach forecasts the model's overall future performance (e.g. accuracy) of known and unknown models to determine optimal retraining points, with the goal to minimize total costs by balancing inference errors and retraining cost. We do not consider the uncertainty of model predictions in our framework. Therefore, the cited work could not be used as baselines, and are not closely related to our problem. We agree that making that difference clear in the text is important, so as suggested we will clarify the difference with this line of work and add in the text: `` This forecasting problem can seem similar to the problem of uncertainty quantification [1][2], but we are targeting average performance of unknown models, not the probability of error of a given model at a given input $P(f(x)=y|x)$.

Strict assumptions

( We assume the reviewer meant line 247 Eq.8 ). This is a misunderstanding and we will add the word ``conditionally'' to clarify, i.e., the random variables $A_{i,j}$ are conditionally independent of one another given the distributional parameters $\alpha$ and $\beta$. We do not make that assumption and the reviewer is correct to state that it would be an unrealistic assumption to make. Line 247 assumes that the target variables $A_{i,j}$ conditioned on the parameters are independent of one another. This is not the same as stating that the $A_{i,j}$ are IID. The equations states that the dependencies between the variables $A_{i,j}$ and $A_{k,l}$ are captured by the dependencies between the parameters $\alpha(x_{i,j}),\beta(x_{i,j})$ and $\alpha(x_{k,l}),\beta(x_{k,l})$. Specifically, we do not make the assumption that $P(A_{i,j}, A_{k,l}) = P(A_{i,j})P(A_{k,l})$.

Limited experiments.

We have made a typo in the table detailing our experiment. The iWild dataset is actually a 100-class classification task with 224x224 resolution images and 1 categorical feature, and is of reasonable size. The purpose of adding this dataset was to ensure that we did indeed present a realistic large-scale experiment, as we recognized, alongside the reviewer, that such experiments are important to assess the practicality of the work. We have corrected this typo in the Appendix, and we hope that this addresses concerns about the practicality of the method. We are also working towards adding an additional dataset from the same family as the iWild dataset which will add before the end of the rebuttal period if time permits.

(Minor) Relation to life-long learning and transfer learning

We group life-long learning and transfer learning with the fields of adaptive learning and online learning that we mentioned in our text. These represent similar alternative approaches to the general problem of using machine learning models in production and addressing the inevitable distribution shift. We agree that, in principle, they could constitute a sensible solution, as the reviewer suggested. The main reason we view these methods as not directly applicable is that they generally focus only on optimizing performance without considering the full cost of modifying a model. This approach is sensible in some settings where updates are not too costly; for example, companies do update their recommender systems every day with incremental learning methods. However, in other settings (safety-critical or with regulatory issues), the cost of changing or modifying a model in production can go beyond the number of gradient updates or sample complexity. For example, costs associated with deployment and risk assessment of a fraud detection model will be incurred no matter how small the update to the model is.

If we were to address this by integrating these baselines and applying a flat cost each time one of the models is modified, it would be unfair to them, as it would be completely orthogonal to the intended use of these algorithms.

To clarify, we will modify the text in line 62 to include those additional related fields: ``Other related areas are online or adaptive learning (Hoi et al., 2021) and life-long learning which updates models with a continuous stream of data through gradual gradient updates, and transfer learning which adapts model from one distribution to another. However, this differs from our problem, as it focuses on maximizing performance while abstracting the practical retraining costs involved in production deployment. In practice, the cost of retraining can go beyond the number of gradient updates or sample complexity, as discussed above.''

Do datasets $D_j$ include all previous datasets?

In our experiments, no, they do not. For the iWild experiment, we do some overlapping so the dataset $D_j$ contains half of the dataset $D_{j-1}$. We describe the construction of the datasets in Appendix 8.4 and will clarify that point.

$C(\theta)$ sometimes has sub-index alpha, sometimes not.

In some places, we have omitted the $\alpha$ to lighten the notation. We will add it to be more consistent as suggested.

What is "w".

$w$ is the number of timesteps in the offline data and is defined in the problem setting line 141.

Clarifying $\mu$

How we use $\mu$ is described in the methodology in line 267``Maximizing the likelihood w.r.t. to the mean parameters $\mu_{\phi}$ then becomes a standard mean square error objective. Once these parameters are learned, we can recover the corresponding $\alpha,\beta$ parameters to obtain our predictive distribution;'' . We will add the explicit connection between the mean and variance parameter and the $\alpha, \beta$ parameters of a Beta distribution in the text.

Bolded values in Table 2

Bolded values are the lowest cost, as stated in the table 1 description line 380; ``The bolded entries represent the best, and the underlined entries indicate the second best'' . We can repeat this in the caption of Table 2 as well.

Please, revise the "$*$ denotes statistical significance ...

We will modify the text following that suggestion.

Conclusions could be extended

the conclusion was indeed cut a little short because of space constraint, we will make space and extend it to integrate additional limitations and future work.

Other typos and suggestions

Thank you for pointing those out, we will correct them and integrate the suggestions.

Flaw in results (Figure 3)

The range of the tested alpha value is set per dataset, from $\alpha=0 , \dots, \alpha_{max}$. $\alpha_{max}$ is set following the procedure detailed in the experiment section, line 354: ``The upper bound, $\alpha_{max}$, is determined by the $\alpha$ value at which the oracle reaches 0 retrains''. For that specific dataset, that value was $\alpha_{max} = 0.1$.

To clarify this, we will change the label axis of the figure to reach $\alpha_{max}$ instead of $0.1$ and add the explicit $\alpha_{max}$ value per dataset in Table 4.

Missing oracle

We initially omitted the oracle because there were too many lines, making the plot difficult to read. We will add it for completeness and increase the size of the plots to improve readability.

UPF not defined

This is a mistake, UPF stands for uncertainty performance forecaster. We will add the following when we describe our method in line 234; ``Since this is infeasible, we propose to 1) model these future values as random variables and learn their distributions; and 2) base our decisions on the predicted distributions to construct our method, the Uncertainty-Performance Forecaster (UPF).''

Undefined $x_{i,j}$, ..

Thank you for pointing those out, we will add explicit definition of $X,Y$ and $x_{i,j}, y_{i,j}$ in the revised version. We agree that our notation was confusing, we used the bolded $x_{i,j}$ to differentiate from $x_{i,j}$ but this is confusing, we replaced it for another different notation $r$ altogether.

Why PE is presented in matrix notation

That is right, we changed it to a scalar notation as proposed.

How does $g(t, I_<t)$ depend on $t$ apart from $I_<t$?

This notation was to highlight the information you have each time you make a decision, i.e. whatever past information you have access to paired with the current time you are. It is true that $t$ can simply be included in $I$.

$g_{\phi}$ is not defined but directly mentioned in Section 4.

$\phi$ is introduced as the parameters of our algorithm. To make this explicit, we will modify line 232 from ``A retraining decision algorithm must specify the decision functions $g_{\phi}(t, I<t)$ used to build the decision vector $\theta$ '' to ''A retraining decision algorithm must specify the decision functions $g_{\phi}(t, I<t)$ (where $\phi$ contains the parameters of the algorithm) used to build the decision vector $\theta$ ''

Notation issue with $PE$ and $A$

Thank you for pointing these out, we will correct those typos.

Condition in Eq. 8

Yes, to make this explicit we modified the notation in the revised version.

Mutual independency proof (9)

Eq 9 assumes that the distribution of the target variables $A_{i,j}$ conditioned on the parameters is IID. We will make this assumption explicit in the text by modifying line 247:``Given the parameters $\alpha, \beta$, we model the random variables to be independent of each other;''

$x_i,j$ is used here for something different than in (1) $a_{ij}$ is not defined. What is it? A realization of $A_{i,j}$? please be explicit.

As state previously, the bolded $x_{i,j}$ are different than the $x_{i,j}$ in 1). We modified it by using an other symbol to make the distinction clearer. $a_{i,j}$ are defined as observation in line 257, we modified this line to; ``From the offline data, we have access to observations of $a_{i,j}\sim A_{i,j}$ ''

Beta approximation

The approximation is pretty close. We included results without the Beta approximation in the Appendix.

Constant variance assumption

In practice it is probably not constant, this is a modeling choice we made as we have access to a limited amount of training data. We will clarify that this is modeling choice by changing line 267 to : ``As we have access to a limited quantity of data, we make the modeling choice of parameterizing the variance as a constant $\sigma_{\phi}(x_{i,j} ) = \sigma_{\phi}$ ''

Footnote 2 must be in the main text.

We will move it in the main text and add additional clarification in the appendix.

the notation of $P(A_i,j)$ is not clear

$P(A_{i,j})$ is the distribution over the bounded performance metric. $Beta$ denotes the pdf of the Beta distribution, we will clarify this in the text.

Shouldn't it be that T in the sum becomes "t"?

Eq. 14 describes the random variable that we are aiming to predict, so it includes value that are bigger than $t$.

misleading that "we only incur the performance cost of the old model", because we also incur in the future cost for the decisions we will make.

It was in the context of the decision at a single step $t$. Either we incur the cost the performance of the new model + the cost of retraining, or we incur the cost of performance of the old model.

Undefined $W$ (19)

This is a typo that we have corrected.

Missing comparison with online learning

The key practical considerations missing from the online learning formulation make the problems that online learning methods tackle fundamentally different. Online learning (and related fields) aims to minimize updates to a model to optimize performance, while we focus on assessing whether an update is worth its cost.

Therefore, we cannot make meaningful comparisons to these methods. The reviewer’s question, ``How can we compare retraining cost (of the whole model) with incremental updates in online learning?'' reflects the problem. In our view, updating any model (even with small updates) incurs a flat cost (e.g., deployment, risk assessment, human resources) that should be considered.

We could present an experiment applying a flat cost to each update in an online learning method, but this would be misleading, as these methods were not designed for this scenario.

Instead, we could integrate this mechanism into our framework, where new models $f_t$ can be obtained without retraining from scratch. This is why we note in line 161: ``The datasets and trained models can be formed and obtained through any means depending on the task at hand; for example, $f_1$ could be fine-tuned from $f_0$ and $\mathcal{D}_1$ could contain $\mathcal{D}_0$.''

We could extend our framework to account for varying retraining costs by considering different models ($f^{(1)}_t, f^{(2)}_t, \dots$) with associated costs based on the number of updates applied. For example, $f^{(1)}_t$ could be a full retrain, while $f^{(2)}_t$ could represent a cheaper model fine-tuned from $f_{t-1}$. This is an avenue worth exploring, but would constitute a substantial research endeavour that is beyond the scope of our current work.

Finally, offline RL can be more easily integrated into our framework, so we have provided results on sensible baselines as suggested by the reviewer.

Proposition 3.1 results

This is a great suggestion. Of course the tightness of the bound is dependent on how well we can bound the performance gap $L$, but we can provide results with some rough estimates of this quantity to provide a sense of how tight this result is and how it is meant to be used. We will provide such results in the appendix of the revised version. The bound is meant to be used as a first test to determine if someone should even consider retraining their model. If the problem is indeed worth solving, as is the case in the experiments we presented, the bound will not be particularly tight.

Lack of complexity comparison

We agree that providing explicit training complexity figures of the baselines would strengthen the presentation. We will add this in the revised version.

Comparison with offline RL baselines

We agree that providing a state-of-the-art offline RL baseline would indeed strengthen this point. However, we are faced with some technical issues when implementing them. For example, COMBO (Yu et al., 2021), which could be viewed as a state-of-the-art offline RL baseline, has more than six hyperparameters to set, and the architecture and training procedure are far too complex for a dataset of only 30 sample points: ``We train an ensemble of 7 such dynamics models ... pick the best 5 models based on the validation ... set that contains 1000 transitions in the offline dataset D. ... we randomly pick one dynamics model from the best 5 models ... 4-layer feedforward neural network with 200 hidden units...''(Yu et al., 2021). In order to implement that baseline, we would have to make numerous ad-hoc adjustments to fit the smaller dataset, which may ultimately lead to a solution that diverges significantly from the intended approach. If time permits, we will add such a baseline within the rebuttal period.

As an alternative, to provide quantitative proof of offline RL methods as requested, we will present a more dated offline RL method (Michail et al., 2003) that is better suited to our setting, as it consists of linear models applied to basis functions. While it still suffers from the listed drawbacks of offline RL, its methodology does not explicitly rely on large validation sets.

Yu, A. Kumar, R. Rafailov, A. Rajeswaran, S. Levine, and C. Finn, “Combo: Conservative offline model-based policy optimization,” in Neural Information Processing Systems, 2021.

Michail G. Lagoudakis and Ronald E. Parr. Least-squares policy iteration. J. Mach. Learn. Res., 4: 1107–1149, 2003

Figure 2 as best case scenario

Figure 2 is not the best case; it is fairly consistent with the exception of the low-cost point at $\alpha=0$ on a single dataset mentioned by the reviewer (we believe the reviewer is referring to the EpicGames dataset in Figure 6). We will add the oracle to these plots as requested, which will show that this is not a cherry-picked result but rather a consistent result across datasets and $\alpha$ values. We will also expand the appendix section to discuss this outlying result.

We thank the reviewer for their thorough review and comments. The suggested changes and comments are excellent and significantly improved the presentation of our work. We will update a revised version of the paper before the end of the rebuttal with the changes and suggestions.

Focus on classification

While it is true that our experiments showcase only classification tasks, the methodology is not actually tied to the specific case of classification. The only constraint on the type of task that our proposed method can handle as-is is that its performance is measured by a bounded metric as we stated in our text on line 274; ``As stated, this parameterization is appropriate for bounded losses''. This is not exclusive to classification. For example, normalized metrics such as the mean absolute percentage error (MAPE) or the normalized mean absolute error (nMAE), which are suitable for regression, could be used as is.

We also agree that our empirical evaluation focuses on classification and should be made clear in the presentation, so we will modify the abstract to reflect this limitation of our work:

''To address this, we present a principled formulation of the retraining problem and propose an uncertainty-based method that makes decisions by continually forecasting the evolution of model performance evaluated with a bounded metric. Our experiments addressing classification tasks show that the method consistently outperforms existing baselines on 7 datasets. We thoroughly assess its robustness to mis-specified cost trade-off.''

Moreover, extending our method to non-bounded losses, such as RMSE, could be done by swapping our Beta parameterization for a truncated Gaussian or log-Gaussian distribution.

We allude to this on line 274: ``As stated, this parameterization is appropriate for bounded losses. Other distributions can be used to model different loss domains if needed''.

However, we agree that this was vague. We will provide a concrete example of how to extend our method to a non-bounded regression metric, such as RMSE, in the appendix to clarify this point.

It is not clear how, for example, the solution deals with "1) very limited information"

In the context of machine learning, we consider that a dataset consisting of less than 100 datapoints, (around 30 in our experiment) would be classified under ''very limited information''. The provided results in the appendix is even more limited, as it uses around 3 points for the offline training phase. The fact that our solution deals with ``very limited information'' is reflected in our method design in three ways: 1) We incorporate maximum structural knowledge of the problem into our methodology; 2) we use lightweight inference modules, such as logistic regression; and 3) we integrate uncertainty into our model and opt for a risk-averse policy to balance the limited amount of information. We appreciate that this is an important point to illustrate, so we will add an extension of this section of the appendix by covering a wider range of cardinality of available information and modify the text to highlight that point.

In particular we will make the following changes; line 85: ''We propose a novel retraining decision procedure based on performance forecasting. Our proposed algorithm is robust and outperforms existing baselines. It requires minimal performance data by fully leveraging the problem structure, employing compact regression models, and balancing the uncertainty caused by data scarcity through an uncertainty-informed decision process.'' as well as in line 268: ``Maximizing the likelihood w.r.t. to the mean parameters then becomes a standard mean square error objective. Given the expectation of operating in a very low-data regime, we rely on simple inference models, such as linear regression.''

Assumption that ''difficulty of the task remains constant''

We were referring to the fact that under distribution shift ($p_t \neq p_{t+1}$), it is possible that the difficulty of the task itself could fluctuate. This means that even with a constant number of samples $N$, constant cost of retraining $c$ and cost of error $e$, the performance of each newly trained model $f_t$, i.e., $E_{D_t \sim p_t} [\ell( f_t(X) ,Y)]$ could change. The CARA formulation implicitly assumes that this stays constant, meaning that if you were to always retrain, you would always maintain the same performance in expectation. We will clarify that point by modifying the text at line 168; ``We do not assume that the difficulty of the task remains constant, i.e., we do not assume that $PE_{t,t} = PE_{t+1,t+1}$''.

Thank you for the review of the paper. We will update a revised version of the paper before the end of the rebuttal with the changes and suggestions.

Limited evaluation of the proposed approach

We presented results on 7 datasets (2 synthetic and 5 real) with 6 baselines (3 variants from CARA and 3 detection shift baselines). Seven datasets is a reasonable number for assessing performance and is within the norm for strong evaluation. While 6 benchmarking baselines may seem low, this is to be expected as this problem has been largely understudied in the literature (as pointed out by all reviewers). It is therefore to be expected that fewer relevant works are available. The reviewer pointed out three works they believe constitute relevant and important benchmarks that should have been included. We explain below why these are not appropriate baselines. For these reasons, we do not agree that our evaluation and experimental section is limited.

Missed connections to several relevant research streams (active testing and label-free performance estimation).

Some aspects of our problem do have connections to the field of active testing and label-free performance estimation, which we will discuss and add to our extended related work section. However, there are fundamental differences in the problem formulation that makes these methods at best tangentially related, and definitely unsuitable to be used as baselines.

To restate, our method has two components: a) the performance forecaster module; and b) the retraining decision module.

Active testing, label-free estimation, and the cited works are unsuitable for two reasons:

1. These methods are only related to the performance forecasting component of our method. They do not provide a mechanism to produce retraining decisions.

2. Even if we were to disregard the first point (which is critical since the goal is to make retraining decisions), and consider the proposed baselines as a replacement for the first component of our method, they still would not be suitable. For most of the performances that we need to forecast, we do not assume access to the underlying datasets, nor the future models.

   To illustrate the second point, we now discuss each of the proposed baselines.

The cited work [1] considers the problem of estimating the shifted label distribution of a target distribution that undergoes label shift from a source distribution, given samples from the source distribution $(X_s, Y_s) \sim P_s$, label-free samples from the target distribution $X_t \sim P_t(X)$, a trained model on $P_s$, $\hat{f}$, and the assumption that the conditional distribution remains constant $(P(Y_s|X_s) = P(Y_t|X_t))$. Ignoring the fact that this last assumption is already disqualifying for our retraining setting on its own, we also do not have access to most of the models $\hat{f}$ or input data samples $x$.
The cited work [3] relies on assumptions similar to those in [1] but aims to predict the performance on the target distribution instead of the target distribution itself.

The other cited work [2] makes fewer assumptions on the target distribution and [2] also produces uncertainty quantification of its prediction. However, [2] also assumes that it has access to input samples and the trained model to perform the prediction.

In summary, we do not see how active testing or label-free performance estimation methods could be used as baselines in our work. Not only do they not include a retraining decision module, but the assumptions that are commonly adopted prevent them from even being used in the forecasting stage. If the reviewer can provide more details concerning how to circumvent these issues, we would be happy to integrate them as additional baselines, as we do believe that more baselines would strengthen the work.

Missing dedicated dataset

We agree that the proposed dataset [4] would be a good dataset for us to include and if time permits, we will include preliminary results before the end of the rebuttal period. However, it is not correct that ``WILD-time benchmark [4] was designed for the very task the authors address''. The WILD-time benchmark dataset was introduced for benchmarking robustness to temporal distribution shift, not for the retraining problem.

How does the method demonstrate the claim “have access to only a few examples”?

This is reflected in our method design in three ways: 1) We incorporate maximum structural knowledge of the problem into our methodology; 2) we use lightweight inference modules, such as logistic regression; and 3) we integrate uncertainty into our model and opt for a risk-averse policy.

To make this clearer, we will make the following changes; line 85: ``We propose a novel retraining decision procedure based on performance forecasting. Our proposed algorithm is robust and outperforms existing baselines. It requires minimal performance data by fully leveraging the problem structure, employing compact regression models, and balancing the uncertainty caused by data scarcity through an uncertainty-informed decision process.'' as well as in line 268:`Maximizing the likelihood w.r.t. to the mean parameters then becomes a standard mean square error objective. Given the expectation of operating in a very low-data regime, we rely on simple inference models, such as linear regression.''

Could you provide experimental results showing performance with varying amounts of data?

We present experimental results for varying amounts of data, including an even smaller dataset in Appendix 8.8: Low Training Data. Additionally, we will supplement these results with further experiments to explore the effect of a the size of the offline training dataset.

Focus on retraining vs adaptation

The paper does not focus on completely retraining. There is no constraint on how the ''retrained'' model $f_t$ is obtained. It can be obtained through fine-tuning from a previous model $f_{t-1}$, adapted, trained from scratch, or any other procedure. We have made that comment explicit in footnote 1 on page 3; ``The datasets and trained models can be formed and obtained through any means depending on the task at hand; for example, $f_1$ could be fine-tuned from $f_0$ and $\mathcal{D}_1$ could contain $\mathcal{D}_0$.'' We will move the footnote to the main body of text to clarify that point. To showcase this flexibility, we have presented in our iWildCam experiment a setting where instead of retraining from scratch, we fine-tune pretrained models and select from different architectural choices (See lines 367-377).
Our method can integrate adaption methods as-is.

Shouldn't the cost of the offline training phase also be incorporated? Maybe a discussion on how incorporating offline training might affect the method's performance is helpful.

That is a good point and was also requested by another reviewer. We will add a timing table to compare the training complexity of the offline training of the different methods in an updated version before the end of the rebuttal period.

Does the performance predictor suffer from distribution shifts and therefore affect the method's performance?

It depends on the nature of the shift and its impact on overall performance. The role of the performance forecaster is to capture and predict the impact of this shift on the performance, so distribution shift is expected and is not, in itself, bad for your proposed approach. If the distribution shift were to be too sudden, unpredictable, and result in sudden and dramatic variation of performance, then yes, the performance forecaster would be negatively impacted. But in this case, so would any retraining method. The hope is that in practice, the distribution shift is gradual and has a somewhat predictable overall impact on performance, which can then be forecasted with reasonable accuracy. To illustrate this point, see Figure 1 of the paper. The fact that the accuracy of a model decreases as time advances (see any line of the same color that tracks the performance of a given model across time) indicates that there is indeed a distribution shift; otherwise, the performance would stay constant. However, in that figure, you can see that this rate of decrease is more or less regular, and is similar across different models (the rate of decrease of model $f_1$ that was trained on $\mathcal{D}_1$ is similar to that of model $f_2$ that was trained on a more recent dataset $\mathcal{D}_2$). In such a case, the performance forecaster would not be negatively impacted by this type of distribution shift.

Thank you for the review of the paper. We will update a revised version of the paper before the end of the rebuttal with the changes and suggestions.

Unstated assumptions

In relation to the forecasting of the performance module, the underlying assumption is that the future performance of models follows some trend that can be forecasted. In short, the assumption is that the performance of a model trained at time $t$ has some temporal autocorrelation with the performance of a model trained at another time $t+1$, and that the performance of a model evaluated at time $j$ has some temporal autocorrelation with the same model evaluated at another time $j+1$. this assumption was not clearly outlined, and we agree that adding it would strengthen the presentation.

We will add the following text in Section 4, line 324: ``To make perfect decisions, we would need future performance values. This is infeasible; however, we assume that there is an underlying temporal autocorrelation between the performance of different models trained at different times, which we aim to exploit to build a predictive model. We therefore propose to 1) ...''

Predictor's performance effect on the final result and Performance requirement

This is a great suggestion. We can certainly provide more insights into the performance of the predictor. This will also provide empirical results to comment on the performance requirement of our model as requested. Later this week, we will add a dedicated section in the appendix showing the average RMSE of the predicted mean performance in relation to the overall performance of the algorithm.

Related work

Thank you for the references; we will add a discussion on the relation of our setting to the change point detection problem. In order to transform the changepoint detection problem from Li et al. 2021 to the retraining problem we are considering, we would need to add a cost for adaptation, a cost for accuracy loss, and then introduce an optimization problem to find the best beta value to achieve the optimal number of adaptations. The Li et al. 2021 paper does suggest that the temperature parameter (beta) can be set by the user: ``people can choose different $\beta$ for a specific environment, with a trade-off between adaptation speed and the erased amount of information.''. However, since that beta parameter does not have a specific physical or practical meaning, it is unclear ahead of time exactly how the choice of a particular value is going to lead to different rates of adaptation. Moreover, in our setting, we do not know what this optimal rate of adaptation (retraining frequency) is. Finding this optimal retaining frequency is one of the major difficulties of the retraining problem. Therefore, we would need to develop a mechanism to relate this beta parameter to our alpha parameter which has physical meaning --- it is the cost ratio of retraining over performance. For these reasons, adding the method by Li et al. (2021) as a baseline would require us to design this additional missing component. The retraining cost is not a new dimension of the problem; it is an essential component of the problem itself, and without it, a sensible retraining decision algorithm cannot be defined.

Could you quantify what you mean by "a few examples"

In practice, the number of models stored along with their recorded performance is likely very limited. This is why throughout the work we assume that the number of datapoints available for training is on the order of 10, and refer to this setting as: “have access to only a few examples”. Accordingly, we set the experiment parameters to stay in that low-data regime. By setting the number of offline steps to $w=7$, we collect the performance of $7$ models evaluated on each of $7$ timesteps. Therefore, the total size of the offline data is $|\mathcal{M}_{<0}| = \frac{7 \times 6}{2} = 21$ examples.

To clarify in the text, we add the following in the description of the offline and online data, in Section 3.1 Offline and Online Data, line 179:

``We assume that we have access to all the datasets and trained models during the offline period. In practice, the number of models and datasets is typically limited to only a few (around 10 to 20 at most), which is why we characterize this problem as being in a low-data regime.'' and will add explicit $|\mathcal{M}_{<0}|$ values in our table detailing the experiments.