Weaknesses

1. Although the paper provides a mathematical analysis for the proposed online objective, the objective itself appears relatively straightforward, as it primarily combines a standard loss function with retraining costs.

We disagree with the statement that the objective is straightforward. The objective described by Eqn. 1 is not a standard loss function with retraining costs. The loss function described in Eqn.1 is parameterized by a binary vector $\boldsymbol{\theta}$ that is subject to some constraints. This doesn't resemble any standard setup. If the reviewer is instead referring to the training loss used to obtain the parameters of the Gaussian r.v. in Eqn. 13, it is true that a standard loss is being used, but this is only a small part of our methodology, and cannot be characterized as the objective of our method. This would overlook the second part of our methodology, described in Section 4.2, which is central to our method and is how we form our prediction $\boldsymbol{\theta}$.

2. The performance improvements demonstrated in the evaluation are modest compared to traditional methods that rely on distribution shift signals for retraining, raising questions about the practical advantage of the proposed approach.

We disagree with the statement that the improvements over distribution shift methods are modest. On average, in Table 1, the distribution shift methods are $23\%$ worse than ours, (or ours is $17\%$ better on average). This is a significant improvement, especially considering that they are on average $31\%$ worse than the oracle, and the oracle is $20\%$ better on average. We can include these summary statistics to better highlight the improvement of our method over these baselines.

Moreover, the experimental setting that we chose is beneficial to the distribution shift methods, as we stop the evaluation at a cost-to-performance ratio where the oracle finds that no retraining should be done. Since the distribution shift methods are entirely agnostic to any cost considerations, settings with a very high cost of retraining would be catastrophic to use. This can be easily inferred by extrapolating the results of the distribution shift methods in the top figure of Figure 2 (the green and red lines).

3. Few sentences in the related works need a bit of clarification, for example "Since the signal is designed to adapt a model rather than trigger a full retraining, these methods are not appropriate as retraining signals." I think "as" should replaces with "for" but I could be wrong

Yes, thank you for pointing this out. It is phrased a little awkwardly. We will rewrite line 101 from: Since the signal is designed to adapt a model rather than trigger a full retraining, these methods are not appropriate as retraining signals. to: Since the signal for these methods is designed to adapt a model rather than trigger a full retraining, they are not appropriate to be used as full retraining signals.

4. Why the results seems incremental when compare the proposed method with the traditional method even though the paper considers high training cost?

This is related to our previous response regarding the performance of distribution shift methods. We deliberately avoided scenarios with excessively high costs, where the cost-aware methods would easily determine that no retraining is necessary, while the distribution shift methods would have a very poor performance.

Methods

1. Bayesian model: ablations with/without feature $z$

Experimentally, we saw that without the shift feature $z$, the results were on average $5-10\%$ worse, with some datasets being more affected than others (the electricity and the synthetic datasets were mostly unaffected). We can include this as an ablation study.

2. XGBoost justification - use for tasks involving text

Better suited models could be used for each specific dataset, but we decided to keep a single model in these experiments for simplicity. We chose a tree-based algorithm since they can handle different datatypes.

3. Why choose between 188 models for iWildCam? What happens if you don’t?

This experiment was designed to highlight that the setup does not assume any particular model $f$ to be consistently used, and to illustrate a scenario where the training cost is not restricted to the training of a single model. The procedure to obtain $f$ is actually outside of our framework; it is part of what defines the dataset in our setting. We could have also chosen a single model, which would have resulted in lower accuracy values.

4. Details on dataset construction

Thank you for pointing this out. We will include additional details in Appendix A.6.

5. Section A.8.1 advertises something different from what it delivers

That is true. It is slightly misleading, and we will change the title of the section to BETA APPROXIMATION VS NORMAL.

6. Theoretical claims - errors in Proof of Prop. 3.1

Thank you very much for taking the time to verify our result. Yes, there is double counting in 33. The summand should be offset by a minus 1 in the first two terms to avoid this. The second mistake you pointed out in (44) is also related to this missing offset. The added terms should start at $s=t^*_{r+1}+1$ and not at $s=t^*_{r+1}$. We will fix these errors. This doesn't affect the final result.

Weaknesses

7. Not a realistic setting.

If a practitioner has no flexibility on when/if to retrain the model due to some operational/organizational/procedural reasons, it is true that our algorithm is not applicable, since there is no retraining problem. However, we believe that this is a rare case and that the problem we are addressing is ubiquitous in industrial settings. Many practitioners do have this flexibility and are actually faced with the problem of deciding when to retrain their model. Indeed, we were motivated to formulate this problem due to collaborations with several industry partners who have live, deployed models, and must make this exact decision.

Many companies collect data in real-time, and their interest is to forecast something based on this most recent data. That is the case for companies that operate recommender systems, perform manufacturing control (e.g., detecting faults), or employ fraud detection systems, for example.

The cost of retraining is indeed usually related to external costs (i.e., not computation), but this is precisely what we are trying to tackle in this work. While quantifying these costs can be challenging, these types of risk assessments and quantification are actually made all the time, and are inherently considered when a decision to retrain is being made. Financial transaction companies running fraud detection systems do estimate the potential financial cost that could be incurred if a newly deployed model performed poorly.

The contribution of our work is to provide a formal framework for practitioners to incorporate cost estimates into retraining decisions. It asks them to provide a direct specification of what amount of accuracy gain is worth this holistic cost of retraining, at a given time step. Our formulation has the considerable advantage of enabling this explicit quantification. This formulation is the most interpretable and therefore useful for setting this problem and making decisions.

8. A common problem in modeling under distribution shift over time is how much past data to train on. Here, this problem is not part of the formulation

This is a valid point and could be an interesting extension to our formulation. Rather than just deciding whether to retrain, we could choose to retrain on varying amounts of samples, adding another dimension to our prediction space. Instead of only the timestep index and model index, we would now have multiple models to choose from.

Comments

9. Discussions about scaling laws seem unrelated to the paper.

The organization of this paragraph made it seem like the scaling law applies to the distribution shift scenario, which, as the reviewer pointed out, is not the case. It belongs to the section where we describe the performance of a given model remaining constant (i.e., no distribution shift). We will reorganize this paragraph by moving the scaling law discussion before the discussion about distribution shift.

10. Other typos

Thank you for bringing these to our attention. We will correct them.

Claims and Evidence

1. Beta r.v. motivation:

We agree that there could be a better motivation for the Beta distribution and will add sentences to improve the flow. Our choice to use a Beta distribution was motivated by the facts that 1) Beta distributions are appropriate (and a common choice) for continuous r.v.s defined over a finite interval; and 2) the empirical accuracies can be interpreted as sum of Bernoulli outcomes and the Beta is the conjugate prior. Moreover, the model performs well empirically, and we conducted some experiments with a Gaussian-based alternative that can be seen in Appendix A.8.1, where we can see that the Beta model slightly outperformed. We recognize that this is a modeling choice and the framework could be applied with other distributions.

2. Future performance forecaster is trained first and then used for derivation in Section 4.2

Yes, we train the forecaster on some available training data collected at some past timesteps (the offline data, denoted $\mathcal{I}^{offline}$ in Section 3.1). We incorporate a modeling assumption that the predictive relationships learned during this offline period also exist in the operational period, allowing us to forecast performance in future timesteps.

3. Are rules in Section 4.2 derived from RL algorithm?

No, these rules are not directly derived from the RL formulation. Section A.11 aims to clarify and highlight the connection between our approach and an offline RL formulation, though it is not a perfect match. To make this clearer, we will rename the appendix "Connection to an Offline RL Formulation." Since the problem is closely related to offline RL, we found it important to emphasize these connections. However, the addressed task is not ideal for RL, as discussed in the main text, which is also reflected in the performance of a basic offline RL baseline in Table 7.

Weaknesses

4. Additional discussion to explain the connection to continual learning

There is a connection between the "when to retrain" problem and continual learning and we will add more text to discuss. The main difference lies in how cost is incorporated in the problem formulation and whether the setting allows for future planning. In particular, continual learning approaches do not ever delay updates due to cost considerations. For example, in a when-to-retrain scenario, I might decide to hold off from retraining in period 7, because I only have budget to retrain one more time, and if I retrain in the next window in period 8, it will give me better performance for periods 9-11. In continual learning, the primary goal is typically to maintain performance, sometimes while trying to reduce the number of gradient updates. In contrast, our when-to-retrain formulation is abstracting away the training procedure and focuses more on cost considerations. Here, cost is not limited to gradient updates. It is a parameter set by the practitioner which will influence the algorithm’s behavior, as the algorithm explicitly considers the cost trade-off when deciding whether to retrain.

Moreover, our algorithm does not aim to optimize how models are retrained/updated under distribution shift, which is a core focus of continual learning. In fact, continual learning techniques could be combined with our algorithm to balance the decision of whether to apply an update. Even if continual learning mechanisms indicate that gradient updates should be applied to adapt to distribution shift, our approach could deem that it would still be better to wait due to other training cost considerations.

As suggested, we will add a more detailed explanation of the connections and differences between our problem and the field of continual learning, incorporating these key points.

5. Theoretical analysis: does it apply to datasets with arbitrary distributions

Yes, in theory, the result in Eqn. 7 does not impose any structure on the dataset distributions, so it is the case that it would apply to datasets with arbitrary distributions. It is also the case for Appendix A.11. However, since the result relies on bounding the performance gap of two models trained on subsequent datasets $\mathcal{D_i}$ and $\mathcal{D_{i+1}}$, evaluated on dataset $\mathcal{D_t}$, it will likely be related to a function of the distributions of these datasets. We will add a comment to this effect as suggested. This is exemplified in Appendix A.5, where we present examples illustrating how the performance quantities $pe_{i,t}$ can be characterized for a simple Gaussian model. In this example, the bound is indeed a function of the dataset characteristics, i.e., its size $|\mathcal{D}|$, variance $\sigma$ and dimensionality $d$.

Methods

1. Types of non-stationarities: approach is more suited for slowly changing environments rather than abruptly changing ones

That is a good point. It is true that the best scenario for our approach is a slowly changing environment, and that abrupt changes would be harder for our model to handle. We will clarify the scope of our paper by adding a comment to the effect that our model is mostly adapted to gradual performance changes in the limitations section and state that abrupt changes in performance remain an open problem.

That being said, the combination of probabilistic forecasting and a risk-averse decision algorithm in our method provides some defence against abrupt changes in the environment. Since our approach does not rely solely on pointwise estimates but also produces probabilistic estimates through mean and variance predictors, a failure in capturing sudden changes will result in high-variance estimates for past models. Due to our risk-averse design, the model would be biased toward frequent retraining to avoid catastrophic performance drops. We believe unexpected performance rises are less likely than sudden drops, which is why our approach is designed this way.

2. Forecasting procedure: choice of the feature vector

There are certainly various designs of input features that could be more informative. However, we aimed to keep our approach simple, as we are in some ways introducing a new problem setting. Our priority was to ensure broad applicability across settings, rather than focusing on more complex feature combinations that might yield better performance but reduce generalizability.

3. Forecasting procedure: inability to detect concept drift

The point about concept drift is an important one. We agree that it is crucial for the model to identify concept drift, and in fact, our model is capable of capturing pure concept drift where $p(Y_1|X_1) \neq p(Y_2|X_2)$ with $p(X_1) = p(X_2)$. In short, the presence of concept drift will be reflected for a model $f_0$ that was trained on dataset $D_0 (X_0, Y_0)$ in the shift of performance on the dataset $X_1, Y_1$ versus the performance on the dataset $X_2, Y_2$. Even if the dataset shift feature stays constant, since we also feed the time index as input, our model can pick up this trend. The performance will be a decreasing function of $t$ and that can be captured in the model.

This is an important point worth highlighting. We will add a comment in the text about the model's capability to capture concept drift and also include the possibility of designing more informative input features as a future direction.

4. Dependence on past predictions: prediction of future values also depends on the previous choices of retraining or not the model

This is an excellent point. It is true that retraining decisions influence the online dataset $\mathcal{I}^{online}$, which in turn affects the prediction algorithm. This effect is, in fact, ignored by our algorithm. Empirically, we do see that this is not a problem as we observe a good performance. However, it would be a good research direction to investigate strategies to allow for more non-optimal decisions to provide training data for the prediction algorithm in other decision regions.

We will add the following comment to highlight this fact by adding in line 259: "As constructed, past decisions influence the dataset $\mathcal{I}^{online}$ available for the next iteration, but this effect is ignored by the algorithm. Empirically, we find that the algorithm performs well despite this. One direction worth investigating is the incorporation of random decisions to allow the predictor to learn over a broader region of actions and responses."

5. Simplifications: linear model for prediction, beta distributions. Do these limit the applicability to more general and complex scenarios?

While our approach uses simple components, we do not consider it limits the applicability of the approach to complex scenarios. Indeed, the iWildCam experiment represents a reasonably complex setting, with distribution shift, and 188 architectures of different natures.

Given the nature of the retraining problem, where data is scarce and potentially noisy, a linear regression model with variance estimation is a suitable choice, especially when only 10-20 samples are available for learning. Furthermore, since this is a relatively new problem formulation, we found it appropriate to introduce a simple yet robust method that can be applied across various settings. That being said, the limited modeling complexity of the chosen method may indeed restrict the model's expressiveness, and exploring more complex algorithms in the future would be valuable.

Regarding the Beta assumption, it is a common distribution for modeling continuous random variables over a finite interval. Please see our response to point 1 of Reviewer 1 for more discussion.