Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms

Thank you for your feedback. We comment first on “weaknesses”.

1. There are indeed other problems for which Pareto-optimal algorithms are brittle. Examples include 1-MAX search [19], [38] which is a much simpler version of one-way trading, online bidding [6], [23] and searching for a hidden target in the infinite line [4]. We believe there may be several other problems in this class; for example, given the connections between one-way trading and online knapsack demonstrated in [16], it is quite likely that knapsack also suffers from brittleness, in the maximum-density prediction setting studied very recently in [A], but this remains to be proven. More broadly, we aim to bring attention to the fact that Pareto-optimality treats the prediction error in an “all-or-nothing” fashion (perfect vs adversarial predictions) which may not always yield an appropriate measure of performance. Concerning the adaptive algorithm please see our response to Question 1 below.

2. In regards to applying the model to settings beyond single-valued predictions, please refer to Point 2 in the global response. As we explain, while the model is indeed more amenable to single predictions, it can be applied to more complex prediction settings. Specifying the user-based profile can indeed be challenging for certain problems. But we also believe that for problems such as one-way trading, and online financial optimization problems, more broadly, a user-based profile makes sense: e.g., a trader may be satisfied with a linear-like degradation of performance, based on historical data from stock exchanges.

3. Designing a threshold function for the profile setting is non-trivial, and does not follow straightforwardly from known approaches. Please refer to Point 3 in our global response.

Below we respond to questions:

1. The adaptive setting of Section 5 stems from observing that the design and analysis of SOTA algorithms are heavily tied to worst-case sequences, yet a natural question is to ask: can we design Pareto-optimal algorithms that improve upon the SOTA if the input diverges from the worst-case one? We believe this is a natural question that falls into the analysis beyond the worst-case. It is also related to your observation about the analysis being tied to worst-case sequences: we show that it does not need to, and we can indeed go beyond. To solve this problem, we applied some techniques we developed for the profile setting: namely, when analyzing constraints $[\beta]$, we argue that replacing the inequality with an equality allows us to analytically solve the fundamental differential equation, which differs from previous analysis techniques of threshold algorithms. Thus, we believe this setting is not disconnected from the profile setting of Section 4. We also believe that one can combine the two approaches, and obtain an adaptive, profile-based algorithm, in order to circumvent the unavoidable brittleness. This is done as follows, in rough terms: For the decreasing part of the profile (rates smaller than the prediction), the algorithm behaves similarly to lines 6-9 of Alg. 2, by replacing $r$ with the individual ratios $t_i$. For the increasing part of the profile, we would like to exchange as much as possible at each rate, subject to the profile. This can be accomplished, at a high level, using an approach along the lines of Appendix C, but with some additional technical modifications due to the presence of multiple ratios $t_i$ instead of a single one.

In regards to contract scheduling, we demonstrate how to analytically find a schedule that simultaneously optimizes the robustness and the consistency according to a given linear profile. More precisely, we present a 4-robust schedule (best-possible) that also has optimal consistency according to this profile. This demonstrates that the model applies to other problems. Contract scheduling is an important problem in AI that has been studied in learning-augmented settings [7],[B]. Moreover, it has clear connections to other problems such as online-bidding [6,23] and searching on the line [4]. We are very confident that our approach will carry over to these problems, which, likewise, suffer from brittleness.

2. You are correct in that there may exist several algorithms that respect a given profile, say $F$, and one would like to define further criteria to choose a good one. One way to accomplish this is to use our offline algorithm so as to find the best-possible extension $G$ of $F$, as stated in Remark 4.1, and in the discussion at the end of Section 3, starting at line 185. Intuitively, this extension $G$ describes a profile that has the same “shape” as $F$, but defines much better performance ratios than $F$, for all rate values. This means that if $F$ is feasible, then we can obtain an algorithm that not only respects $F$, but also $G$ (hence will perform even better, and “optimally” in the sense of respecting the "lowest" profile that has the shape of $F$). One could impose other criteria, e.g., insist that $w_{l+1} =1$ as you suggest.

3. Yes, the definition can be extended as follows. Let $O$ be an online problem (say cost minimization). Let $\hat{p}$ denote a prediction, $\eta$ the metric that defines the prediction error, and let $r$ denote the robustness requirement. We say that $O$ is brittle with respect to $\hat{p}$ if for every Pareto-optimal algorithm PO and every $\epsilon > 0$, there exists a sequence $\sigma$ such that $\eta(\sigma,\hat{p}) \leq \epsilon$, and ${cost}(PO,\sigma)\geq r \cdot cost(OPT,\sigma) -\delta$, where $\delta$ can be infinitesimally small.

4. Correct, thank you for catching the typo.

[A] M. Danashveramoli et al: Competitive Algorithms for Online Knapsack with Succinct Predictions, arXiv:2406.18752

[B] S. Angelopoulos et al. “Contract Scheduling with Distributional and Multiple Advice”, arXiv:2404.12485

Thank you for your feedback. Below we respond to “weaknesses”.

1. In regards to the prediction being tied to single values, please see Point 2 in the global response. As we explain, while the model is indeed more amenable to single predictions, it can apply to more complex prediction settings.

In regards to the error, specifically, there is a variety of problems and prediction settings for which the worst-case prediction error is bounded, with or without any further assumptions. An example where no additional assumptions are needed includes online problems with frequency-type predictions, e.g., bin packing [8], or knapsack [A]. In our problem, the prediction error is bounded from above by $M$, by the assumption that $M$ is the maximum exchange rate. But this is a standard assumption in the context of trading problems, not only in the standard competitive analysis of one-way trading [19] (without this assumption, no algorithm has bounded competitive ratio), but also in the state-of-the-art learning-augmented algorithm [38]. The bound helps compare our algorithm to that of [38]; however, it is not strictly needed in the definition of the profile, since the profile can be defined even if the error is unbounded. Hence, having an upper bound on the prediction error may be helpful, but is not a requirement in our model.

[A] Im, Sungjin, et al. "Online knapsack with frequency predictions." NeuRIPS (2021): 2733-2743.

2. In general, the analysis of profile-based algorithms need not rely on knowing the structure of worst-case sequences, in the same way that competitive analysis in the standard setting (without any predictions) need not rely on such knowledge. Knowing this structure may help the analysis, but is not a prerequisite. For instance, our analysis of contract scheduling (appendix) does not use “worst-case” instances, it applies instead to any given instance. In addition, we believe that one-way trading remains a challenging problem in our setting even when knowing the structure of worst-case instances, because there are several conflicting objectives in trade-off relation, which is reflected in the complexity of the algorithms and their analysis.

3. We address this issue in Point 3 of the global response, which we also include below. Designing a threshold function for the profile setting is non-trivial, and does not follow straightforwardly from known approaches. For instance, if one tried a “myopic” approach that considered each interval individually (and obtained a threshold function for each such interval), then the overall function would fail. This is because when transitioning to a new interval, the algorithm would not have made enough profit to be competitive in this new interval. This adds complications which we address as explained in Section 4 (lines 245-254) and in lines 9-14 of Algorithm 1: informally, we need to “flatten” a portion of the threshold function of each interval appropriately. As a result, the obtained function is quite complex, and combines exponential functions, plateaus and discontinuities, as illustrated in Figure 3 (appendix).

4. For the experiments, we chose a relatively simple profile in order to be able to compare our algorithms to the known Pareto-optimal algorithms in a very clear and meaningful manner . However, we agree with your suggestion, and in Point 1 of the global response and the accompanying PDF, we describe the performance of our algorithm on a more complex profile, which demonstrates that the algorithm indeed performs as predicted by the theoretical results.

5. Here, we meant that this is a novelty in regards to one-way trading, and online financial optimization problems, more broadly. We will clarify this point, and add references to [9] and other related works.

Thank you for your feedback. In regards to weaknesses/questions, our responses are below.

1. We address this issue in Point 2 of the global response, which we also include below for convenience.

The concept of a profile is inherently applicable, and at the very least, to the class of online problems with a single-valued prediction. In this work, we focused on two well-known problems from this class. The first and main problem is one-way trading, which was chosen because it is one of the main online financial optimization problems and an error-based analysis for such problems is obviously paramount (but missing in the state of the art). In addition, the problem has very close connections to other important online problems, notably online knapsack [16], [41]. The second application is contract scheduling, because it is a well-known problem from AI with close connections to other important problems such as online bidding [6], [23], as well as searching for a hidden target [4], both of which suffer from brittleness. The concepts and techniques we introduced should be readily applicable to such related problems, but due to space limitations and the complexity of approaches, we had to make a selection.

There are two additional points we would like to further emphasize. The first is that single-valued predictions constitute a very rich class of learning-augmented algorithms. Beyond the works cited above, many other studies fall in this class including ski rental and rent-or-buy problems [36], [39], scheduling [A], secretary problems [10] and bin packing [A], to mention only a few representative works. Such predictions are also very useful in the context of succinct predictions, e.g., as studied explicitly in the recent work [D].

The second point is that the prediction need not necessarily be single-valued for our profile-based analysis to be applicable. For example, the prediction may be a vector of values, as e.g., in scheduling [26] or bin packing [8], then the concept of profile still applies since the error is defined by a distance norm between the predicted and the actual vector. Our model can also be applicable in a multiple prediction setting, in which the algorithm is given a set of several predictions, and its consistency is evaluated at the best-possible prediction in this set. More concretely, we believe that one could combine our analysis of one-way trading with the multiple advice setting of [B], and our analysis of contract scheduling with the multiple advice setting of [C]. Of course, we expect any technical results to be more challenging.

Nevertheless, we agree that our profile model, as is, is not immediately applicable to all learning-augmented settings, e.g., when predictions appear dynamically. This is a topic of future work, and we will emphasize this in the introduction and the conclusions.

[A] K. Anand et al. "A regression approach to learning-augmented online algorithms." NeuRIPS 34 (2021): 30504-30517.

[B] K. Anand et al. "Online algorithms with multiple predictions". ICML 2022, 582-598.

[C] S. Angelopoulos et al. “Contract Scheduling with Distributional and Multiple Advice”, arXiv:2404.12485

[D] M. Danashveramoli et al: "Competitive Algorithms for Online Knapsack with Succinct Predictions", arXiv:2406.18752

2. Yes this is a typo. The correct expression is $w_{A,i}=w_{A,i-1} + x_i$, where $x_i$ is the amount traded on the $i$-th rate. I.e., $w_{A,i}$ is the sum of the amounts exchanged up to and including the $i$-th request.

Thank you for your feedback. Please allow us first to comment on the “weaknesses”.

1. For the experiments, we chose a relatively simple profile in order to be able to compare our algorithms to the known Pareto-optimal one, in a very clear and meaningful manner. Nevertheless, we agree with your suggestion, and in Point 1 of the global response and the accompanying PDF, we describe the performance of our algorithm on a more complex profile, which demonstrates that the algorithm indeed performs as predicted by the theoretical results even on more complex profiles.

2. There are indeed practical uses for determining feasibility in an offline fashion. Specifically, let $F$ denote the given profile, then we can use the offline algorithm combined with binary search, so as to find the best-possible extension $G$ of $F$, as stated in Remark 4.1, and in the discussion at the end of Section 3, starting at line 185. Intuitively, this extension $G$ describes a profile that has the same overall “shape” as $F$, but defines much better performance ratios than $F$ for all rate values. This means that if $F$ is feasible, then we can obtain an online algorithm that not only respects $F$, but also $G$ (hence will perform even better).

Below, please see our response to the questions:

1. We are not aware of any such characterizations in the literature, not only for Pareto-optimal algorithms, but also for the standard competitive analysis of this problem. Our adaptive algorithm of Section 5 aims to address this concern: if the sequence is not pathological, then we show that we can perform much better than the known Pareto-optimal algorithms (while maintaining Pareto-optimality). But nothing formal is known about the “likelihood” that a sequence severely degrades the performance of such algorithms. An additional complication is that Pareto-optimality is a generalization of competitive analysis, and thus it is intrinsically bound to worst-case analysis.

2. This is due to Remark 2.1: Any optimal algorithm only trades at rates which are local maxima, hence the function $\phi$ must be increasing for the algorithm to be optimal. Furthermore, $\phi$ needs to be invertible, in order to determine utilization and thus the exchanges made at each rate, hence it needs to be increasing.

Thank you for the suggestion, it is not immediately clear to us to which figure you refer, and whether you mean that certain figure ratios should be more legible, but we will do so.