Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms
Authors: Alex Elenter
Spyros Angelopoulos
Christoph Dürr
Yanni LEFKI
Venue: NeurIPS 2024 poster (2024)
Keywords: Learning-augmented algorithms
online algorithms
competitive analysis
one-way trading
Pareto-optimality
Primary area: optimization

Abstract: The study of online algorithms with machine-learned predictions has gained considerable prominence in recent years. One of the common objectives in the design and analysis of such algorithms is to attain (Pareto) optimal tradeoffs between the {\em consistency} of the algorithm, i.e., its performance assuming perfect predictions, and its {\em robustness}, i.e., the performance of the algorithm under adversarial predictions. In this work, we demonstrate that this optimization criterion can be extremely brittle, in that the performance of Pareto-optimal algorithms may degrade dramatically even in the presence of imperceptive prediction error. To remedy this drawback, we propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a {\em user-specified profile}. This allows us to regulate the performance of the algorithm as a function of the prediction error, while simultaneously
maintaining the analytical notion of consistency/robustness tradeoffs, adapted to the profile setting. We apply this new approach to a well-studied online problem, namely the {\em one-way trading} problem. For this problem, we further address another limitation of the state-of-the-art Pareto-optimal algorithms, namely the fact that they are tailored to worst-case, and extremely pessimistic inputs. We propose a new Pareto-optimal algorithm that leverages any deviation from the worst-case input to its benefit, and introduce a new metric that allows us to compare any two Pareto-optimal algorithms via a {\em dominance} relation.

Overcoming Brittleness in Pareto-Optimal Learning-Augmenteed Algorithms
Alex Elenter
Spyros Angelopoulos International Laboratory on Learning Systems
Sorbonne University, CNRS, LIP6
4 place Jussieu Paris, France 75005
Montreal, Canada, and Sorbonne University, CNRS, LIP6
al aalexeleetter@@maill com
Paris, France 75005
spyros . angelopoulossllipp
Christoph Dürr Sorbonne University, CNRS, LIP6 4 place Jussieu Paris, France 75005
Yanni Lefki"
Institut Polytechnique de Paris
Rte de Saclay
Palaiseau, 91120, France
chriistoph.durrdl..ppp
yanni. Defniiiiffi@mmmiil..... com
Abstract
The study online algorithms with machine- predictions has gained consid- erable prominence in recent years. One of the common objectives in the design and analysis of such algorithms is to attain (Pareto) optimal tradeoffs between the con- sistency of the algorithm, i.e., its performance assuming perfect predictions, and its robustness, i.e., the performance the algorithm under adversarial predictions. this work, we demonstrate that this optimization criterion can be extremely brittle, in that the performance of Pareto-optimal algorithms may degrade dramatically even in the presence of imperceptive prediction error. To remedy this drawback, we propose a new framework in which the smoothness in the performance the algorithm is enforced by means of user-specified profile. This allows us regulate the performance of the algorithm as a function of the prediction error, while simultaneously maintaining the analytical notion of consistency/rooustness tradeoffs, adapted to the profile setting. We apply this new approach to a well- studied online problem, namely the one-way trading problem. For this problem, further address another limitation of the state-of-the-ar Pareto-optimal algorithms, namely the fact that they tailored to worst-case, and extremely pessimistic inputs. We propose a new Pareto-optimal algorithm that leverages any deviation from the worst-case input to its benefit, and introduce new metric that allows to compare any two Pareto-optimal algorithms via a dominance relation.
Introduction
The field of aurmning-uugmentee online algorithms has witnessed remarkable growth in recent years, starting with the seminal works of Lykouris and Vassilvitskii [31] and Purohit al. [36]. The focus, in this field, is on improving the algorithmic performance by leveraging some inherently imperfect prediction on the online input. This is contrast the standard framework of competitive analysis [15], in which the algorithm has no access to any information about the future, and the analysis based on adversarial inputs tailored to the myopic nature of the algorithm.
Research done while at LIP6, Sorboonne University.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Learning-augee augmented online algorithms are typically analyzed with respect to three performance metrics. The first the consistency of the algorithm. namely its competitive ratio assuming that the prediction is error-free. The second is the robustness, that is, the competitive ratio assuming that the prediction is adversarial, and is thus generated by a malicious oracle. A third consideration is the degradation of the competitive ratio as function of the prediction error; here, the notion of smoothness captures the requirement that the competitive ratio smoothly interpolates between the two extremes, namely the consistency and the robustness.
As expected, not all three objectives can be simultaneously optimized. Many works have thus focused on the trade-off between consistency and robustness. Algorithms with optimal tradeoffs are often called Pareto- Pareto-optimal since their performance lies on the Pareto front of the two extreme metrics. Examples of problems studied in the Pareto setting include online conversion problems [38, 29], searching for a hidden target [4], ski rental [39. 6). online covering [14] metrical task systems [17], energy-minimizatio scheduling [28], scheduling [7. 5] and online state exploration [23].
Pareto-based analysis is attractive for several reasons. First, it fully characterizes the performance of the algorithm on the extreme scenarios, with respect to the reliability of the prediction. In addition, it provides mathematically clean formulation of the desired objectives, which is often quite challenging even for seemingly simple online problems. However, as we will discuss, this type of analysis may very well suffer from brittlenes,, in that the performance ratio of any Pareto-optimal algorithm may be as high as its robustness, even if the prediction is near-perfect. This has an important implication for the algorithm designer: namely, in many realistic situations, a Pareto-optimal algorithm may perform even worse than the best competitive algorithm with no predictions.
To illustrate this drawback, as well as our proposed methodology for counteracting it, will use the well-known one-way trading problem, which is one of the fundamental formulations for online financial transactions. In this problem, decision maker must convert a unit in a given currency, say USD, to a different currency, say EUR, by performing exchanges over an unknown horizon. Specifically, prior to each transaction, the algorithm is informed about the current exchange rate, and must irrevocably exchange a fraction of its USD budget to EUR, according to the rate in question. This problem has served as a proving ground for the competitive analysis of more involved settings such as two-way trading and portfolio optimization; see Chapter 14 in [15] and the survey [35]. In addition, it has connections to other problems such as fractional knapsack [16] and sponsored auctions [41]. Optimal competitive ratios, in the standard framework, were first obtained in [19]. An elegant Pareto-optimal algorithm for maximum-rate prediction was given in [38], based on the concept of an online threshold function. However, [38] does not take into consideration the prediction error other than at the two extreme values. In contrast, the interplay between the prediction error across the entire spectrum and the performance of the algorithm is at the heart of our study.
1.1 Contribution
Our first result (Theorem 3.1) establishes the brittleness of all Parcto-optimal algorithms for one-way trading. To remedy this undesirable situation, in Section 3 we introduce the novel concept of performance profile F, chosen by the end user. Informally, F maps the prediction error to an upper bound on the desired performance ratio of the algorithm. This concept is motivated by practical considerations in everyday applications. E.g., in financial markets, a trader may choose a customized profile based on historical stock exchange data, and how accurate past predictions have proven.
Naturally, not every profile may be feasible, in that there may not exist an online algorithm whose performance abides with it. Our next main result is an algorithm that decides whether a given profile is feasible (Theorem 3.2). Note that this is an offfine problem, however, our algorithm also yields an online strategy, if F is indeed feasible. This further allows us obtain an online algorithm that not only abides with a feasible profile F, but also with the "best" possible profile that has a shape similar to that of F' (Remark 4... We formalize this intuitive notion based the concept of the best vertical translation of F. We thus obtain a generalization of the concept of consistency (which is brittle) to the consistency according to profile F, which is inherently non-brittle by virtue of the profile definition.
In Section 5, we address another limitation of the known Pareto-optimal algorithms for one-way trading. Specifically, we note that the algorithm of [38] is tailored to worst-case inputs in which the exchange rates increase continuously until a certain point, then drop to the lowest rate. Again from practical standpoint, such a worst-case scenario never arises in real markets. Motivated by

---

the concept of the lenient adversary of [19] (in the standard, no- vo-prediction setting), we present and analyze an adaptive, Pareto-optimal algorithm that leverages any deviation from the worst-case sequence to its benefit. To formally quantify the performance gain, we introduce an additional metric that captures the profit of the algorithm on all exchange rates that are at least as high as the predicted maximum rate, and allows us to compare any two Pareto-optimal algorithms via dominance relation. Another novelty of our algorithm, in the context of the problem at hand, is that does not require the prediction to be given ahead of time, instead the prediction can be revealed during its execution (Remark 1. This is a clearly desirable algorithmic feature, that has been achieved in other online problems, e.g.. [9].
In Section we give an experimental evaluation of all our algorithms, over both real data (Bitcoin exchange rates) and synthetic data, which validates the theoretical results and quantifies the obtained performance improvements. We emphasize that our framework can be readily applicable to other Saamiin--uugmente problems, in particular those which suffer from brittleness. We discuss another well-known application from AI, namely contract scheduling [7] in Section
In terms of techniques, our algorithms and analysis are based on the concept of threshold function which carefully guides the actions of the algorithm. While online threshold algorithms have been used in previous studies, including one-way trading [41, 40, 38, 29]. the settings we study pose novel challenges. For the profile- based setting, the design of the function must take into consideration all the constraints induced by the profile. To this end, we use an iterative approach that considers the constraints incrementally, until they are all satisfied. For the adaptive setting. the threshold function must change dynamically, according to the revealed sequence. This is unlike the standard Pareto setting, in which a static function suffices.
While our framework is directly applicable to single-valued predictions, it can also be applied to more complex settings in which the prediction is vector of values. This is because the concept of the profile still applies, since the error is defined by a distance norm between the predicted and the actual vector.
1.2 Related Work
There has been a significant body of recent work on online algorithms with predictions, see, e.g..
settings, e.g.. paging [31, 22], metrical task systems [9, 17], rent-or buy problems [36, 6, 20, 39, 3), packing and covering [14, 8, 21], scheduling [26, 28, 11, 18, 25], matching [27, 10, 24), graph optimization [1, 2, 12, 13), and many others. This is only a partial list; for a comprehensive summary of the existing literature, we refer the reader to the online repository [30]. As discussed earlier, many works have focused exclusively on consistency/robusteee
the surveys [34, 33]. Several problems have been studied in
tradeoffs, without an explicit error-based analysis, e.g. [38. 29, 39, 14, 17, 28, 7, 23, I]. Incorporating smoothness in regards to the prediction error is a challenging task, both in terms of modeling and analysis. For instance, [13, 1] studied online combinatorial optimization problems in which the performance of the online degrades as a function of a distance measure between the predicted and the actual solution. Our work differs from such studies that the dependency on the prediction error user specific, and can change according to the application setting, while still maintaining the concepts of consistency and robustness.
Preliminaries
In the one- way trading problem, the input o is a sequence of exchange rates, where p: denotes the i-th rate in the sequence. The trader has starting budget equal to 1. We follow the standard assumption that p; E [1, M). where M represents an upper bound on the rates that is known in advance. Once p; is revealed, the trader must decide the amount be exchanged to the secondary currency, which cannot exceed her current budget. We consider the general setting in which the horizon n is not known ahead of time. The problem formulation also assumes that the trader is notified once the last rate is revealed, and is thus obliged to exchange all of its remaining fund at rate Pn.
An algorithm A decides the fractional exchanges upon revealing of Pt, a function of the previous i rates, i.e., the sequence o [1,, i 1]. We denote by A(a) the profit of A on o, i.e., the total amount that A has produced after the last exchange. We denote by p maxie(1.N) Ps the maximum rate in and by (pT(o) the profit of the optimal offline strategy, hence OPT(O) p The competitive
3

---

ratio of A is thus defined as CR(A) = sup, A(a) For given a, we refer to the ratio OPT(r)/A(o) as the performance ratio of A on a. The optimal competitive ratio, denoted by r* is (log M), and more precisely, it equal the root of the equation r* In -=1 [19].
OFT(a)
Given algorithm A, denote by (a)) and sA,((0), the budger used by A and its accrued profit right before pj is revealed, respectively. We refer to wA,((o) as the utilization of A. Formally, for every sequence 0, and every algorithm A, we have WA, W Ac-1 Ii, where x; is the amount traded on the i-th rate, that is, WA, , is the total amount exchanged up to and including the i-th request.
We also have that s, Σj=1 P5 wy)) with 81 = O. For simplicity, may omit the input or the algorithm A when it is clear from context. For example, we will denote by p the maximum rate in a.
The above definitions assume the standard setting in which the algorithm has no information on the input. In regards to algorithm has an imperfect prediction P on . We define formally, the consistency and the robustness P. of algorithm A as c(A) =t A(a) and r(A) sup, SuPpe[L.M] A(7] Pe respectively. An algorithm A with prediction ý is Pareto-optimal if, for any given r, it has robustness most r; and has the smallest possible consistency, which we will denote by c(r).
settings, we consider the model of [38] in which the
Remark 2.1. It suffices to consider only sequences in which the exchange rates increase up to certain point, then drop to 1 [19]. Moreover, for any competitively optimal algorithm, the worst-case inputs are such in which the exchange rates increase continuously, i.e., by infinitesimal amounts.
3 Brittleness of Pareto-Optimal Algorithms and Performance Profiles
We first define formally the concept of brittleness.
Definition 3.1. Let P denote a maximum-rate prediction for p", We say that is brittle for any Pareto-optimal strategy A of robustness and consistency c(r). and for every 0, there exists with p PCl I c, for which (a
A(a) r.
The definition deems a prediction to be brittle if there exist sequences for which the slightest prediction error forces every Pareto-Optimal strategy to have a performance that equal to its robustness.
Theorem 3.1 (Appendix A). The maximum-rai prediction is brittle for one-way trading.
Theorem 3.1 shows that Pareto-optimality is very "fragile" metric for comparing strategies with max-rate prediction. To remedy this drawback, we introduce the new concept of a profile.
Definition 3.2. Let P be partition of [M] to intervals, i.c., P U'_ [gt. 4++1), with aı 1 and @++ = .M, and let P be maximum-rate prediction. A profile function F P - R is step function that maps each interval in P t, E RRt,, and which satisfies the following conditions. There exists i E [1, I] such that: (i) f111 2 t. for all i < i and 4,41 2 t4, for all 2 i, and (ii) P [4t 1:+1).
The profile function allows the end user impose requirement on the performance of the algorithm, as expressed in the following definition.
Definition 3.3. We say that an online strategy A respects given profile F :U'=a (++1) R+ for all input sequences a for which p. E [yis (1+1), it holds that OrT(a) < F((g. 1)))). A(Ø)
Informally, a profile F' reflects a desired worst-case performance of an algorithm, assuming that the actual but unknown maximum rate in the input sequence is in the interval [g,, 9++1). Thus, the profile represents the desired upper bound the performance of an algorithm. as a function of the prediction error. Unlike Pareto-optimality which only cares about performance at extremes, the relation between performance and prediction error becomes definable across the entire spectrum of error. The definition also reflects the expectation that the algorithm performs best when the prediction is error-free, and its performance degrades monotonically as a function of the error.
We illustrate the above concepts using the profile depicted in Figure 1a. Here, the profile consists of I 6 intervals, where the first 3 intervals correspond to the decreasing part of the profile and the

---

performance ratio
f
66
1920
46
12
maximum rate
reastrum
01
97
(a) A profile function F with six intervals.
(b) Pareto profile
Figure Illustration of profile functions.
last to the increasing part of the profile. Note that the interval [4a, q4) contains the prediction ý and belongs in both the decreasing and the increasing parts. Note also that the profile allows define an asymmetric dependency on the prediction error. This is a very useful property in applications such as one-way trading. For example, trader may want to more cautious if the market will perform worse in the future, than better in the future, relative to what has been predicted.
Figure 1 depicts different profile in which the performance ratio must be most for any error, unless the prediction is error-free, in which case the performance ratio has to be at most b2 < t1. Such profile yields Pareto-optimality, if
and lo2 c(r).
are interested profiles F that are feasible, the sense there exists an online algorithm that respects F, The following is one of our main results, whose proof will follow from Theorem 4.1 and Corollary 4.1, as we will show in Section
Theorem 3.2. Given profile F defined over intervals, there exists an algorithm for deciding whether F is feasible that runs in time Ol).. Furthermore, if F is feasible, there exists an online algorithm that respects F.
Given our algorithm that decides the feasibility of a profile, we can also answer a more general question. Suppose that F infeasible, but we would like, nevertheless, to be able to respect profile F' that is "similar" to F. Conversely, if F is feasible, then we know we can likely do even better, for example, we would like follow profile F" that similar F, but maps some intervals to smaller ratios. The following definition formalizes this intuitive objective.
Definition 3.4. Let F of F as the vertical transformation of F, in which, for every interval [gt, q(+1) P it holds that Ga Gaa, ())1)) = a F(g., 9.+1)).
R+ denote profile. Given a RR, we define the extension Ge
We can generalize the concepts of consistency and robustness relative to profile F as follows, recalling that f E [g;, qt+1).
Definition 3.5. Given profile F for prediction ý, and robustness r, say that algorithm A is r-robust and c-consistent according to F, there exists an extension G, of for which: (i) for every interval, we have Gallgi, 9++1) < r: (ii) Go q++1) S c; and (iii A respects Ga.
Remark 3.1. The smoothness of a profile is related to the number of intervals, 1. The larger the 1, the smoother the performance an algorithm which respects the profile.
Profile-Based Algorithms
In this section, present algorithm which decides whether given profile F is feasible not. Note that this an offline, decision problem, which we will denote by FEASIBLE(F)). In addition, F is feasible, we also provide an online algorithm that respects F.
Our algorithms are inspired by the class of threshold algorithms (OTA), introduced in [41]. these algorithms, a threshold function & guides the decision about the amount to be exchanged when
5

---

Algorithm 1 Algorithm PROFILE for FEASIBLE (F); also an online strategy if F is feasible
Input: F Ul= 196, 96411)) - R+ Denote F((9)96+1)) by t.
1: w1 f 0, 56
2: for i E 1...../d..
......dd. do
3:
Pi 6 (8 (8+ wi)
4:
if p 2 q: then
5:
Wi+1 e1
Pi-I
+ W;
(1;-((2)
if w E w))
6:
(,(w)
5 (p: etr(w-m)) +1
if w [wi, w(+1)
7:
x 8
1u+t $ (1) dt
8:
else
w/ t- (: (all--arie wig: +1)
9:
19 1)
8' 8 qi (w)
ws)
W1+1
2 In
2, 1111-w])-1 + iy
9:11
1 1 (w)
if w E [1, ws)
12:
(www) + (1e (s' + w!) - 1) clo((ww0) +1 if w E [w/, Ws+1)
13:
w! w/ + s' + Ju (t(t) dt
14:
15:
if W141 > then return F is infeasible else return F is feasible and output 4b
new rate is revealed. Specifically, & maps utilization to reservation rates. Here, utilization value w E [0, 1] represents the fractional amount exchanged so far by the online algorithm, whereas the reservation rate, p. is the minimum rate in [1, M) at which the algorithm will make an exchange. At each point a new rate p; is revealed, the algorithm updates its utilization by setting W;+1 = ① (px). if p. > @ (w:), otherwise Wi+1 w,. In both cases, exchanges an amount equal to w1+1 w; rate Pt- The function & must be increasing, and its codomain must include [1, M).
The main challenge posed in our setting is to guarantee the varying performance ratios globally, i... for all intervals and not just locally for a given interval. Thus, we need a global approach that takes into account the entirety of the profile, and in particular the transitions between consecutive intervals. We will thus design a function so as to satisfy I set of constraints, where each set of constraints applies to a specific interval. Define 5; .o 4(u)du, with š1 O. We seek function & and values 0 = wi S ... S w1+1 < 1 such that the following constraints are satisfied for all i E [1,4].
((3) 8, + Se Φ(t) dt + -
[3]
v3 E [w,, W(+1):
S t4.
[w]+1]
① (ww+1) = 9(+1- w/ S w1+1 < 1.
[u]
Constraint [.8] expresses the requirement on the performance ratio F(q;, 1)) that is imposed by the profile. Note that here s; is the minimum profit of an OTA at the point it reaches utilization wi-
This follows from Remark 2. Constraint [w,-1] allows us to obtain the partition of the utilization levels induced by the profile. Moreover, such constraint is needed for constraint [3] to correctly represent the performance ratio indicated by the profile. Constraint [u] establishes that the utilization levels defined are increasing and that they do not exceed the unit budget available to the algorithm.
The following lemma follows straightforwardly from the above discussion.
Lemma 4.1. F is feasible if and only if there exist & and wi,-.., W1+1 that satisfy the above sets of constraints, for all [1.7].
Algorithm 1, which we call PROFILE, shows how to obtain the threshold function O along with the utilization values Wl,... W1+1, assuming that F is feasible. This is formally stated in Theorem 4.1. We emphasize that the theorem proves an even stronger statement; namely, if not feasible, then PROFILE correctly outputs its infcasibility. That is, the algorithm fully solves FEASIBLE(F).

---

Theorem 4.1 (Appendix B). A profile F admits an online strategy which respects F if and only if PROFILE terminates with value 1141 S
Furthermore, if F is feasible, then PROFILE directly provides an online algorithm that respects F:: Corollary 4.1. If F is feasible, then the threshold function D returned by PROFILE defines an OTA which respects F.
Remark 4.1. For a profile F, we can use binary search in combination with PROFILE, in order to find the minimum a E Rt, such that G. extends F and G. feasible, according to Definition 3.4.
We give some intuition about PROFILE, and how we obtain + and the values wi, for all i. The algorithm computes Φ incrementally: namely, in iteration it obtains new function Φ that aims to satisfy the sets of constraints for the intervals UR [yk. 9k+1), and computes a value for w as well as an updated value for wy. In each iteration i, the algorithm guarantees that an OTA based on b respects the profile on all sequences whose maximum rate is in [L. gi+1) (provided that this is indeed feasible) and, furthermore, that the utilization at the end of iteration i, namely W;+1 is as small as possible. This is crucial, since it allows us to decide FEASIBLE(F)) F)) based on the final value of w1+1-
The algorithm makes a distinction between two types of updates. The first type occurs in the increasing part of the profile, i.e., when 4 < 4--1. This is a relatively simpler case, because the algorithm has already guaranteed a smaller ratio in the previous interval. Hence the algorithm can afford to wait until it sees a rate that exceeds the reservation rate P; (line 5-7). The second type occurs in the decreasing part of the profile (lines 9-14). This is intuitively harder case, because on every new interval the algorithm must do even better than in the previous intervals. That is. when observing a rate equal to qı the algorithm now needs to perform at a ratio t, < f4-1, hence it should have made a bigger profit. To this end, we need first to increase w; (lines 9 and 13) then extend Φ;-1 to account for interval i (line 12). The precise amount by which we increase is guided by the requirement that the algorithm must have performance ratio f; for the worst-case sequence of increasing rates up to qi-
An Adaptive Pareto-Optimal Algorithm
In this section we study another generalization of Pareto-optimality. The starting observation is that the Pareto-optimal OTA of [38] is tailored to worst-case scenarios. Namely, the threshold function in [38] is static, i.e., determined prior to the execution of the algorithm, and tailored to a sequence of continuously increasing exchange rates that may suddenly drop to 1. However, in practice, such sequences never occur in real markets. We show how to obtain an algorithm that is not only Pareto-optimal, but also leverages deviations from the worst-case sequence to its benefit.
Our setting is further motivated by [19], who studied the basic setting of standard competitive analysis without predictions. Their solution is based on threat-based policies, i.e., algorithms that exchange at each point in time the minimum required amount so as to guarantee the optimal competitive ratio. In setting in which the algorithm has access
this section, instead, we consider the to max-rate prediction p. Our algorithm uses an adaptive threshold policy, in which the threshold function is updated every time a deviation from the worst-case input is observed. We follow this approach since OTAs are typically more versatile than threat-based policies, and can apply to more complex problems and settings, such as several variants of the knapsack problem, e.g. [40].
In nutshell, we seek Pareto-optimal algorithm that is not only optimal over worst-case sequences, but also over all other sequences. To describe this formally, we first define some concepts. Let ý be a max-rate prediction for an input a of increasing rates, and define ā as the suffix of a comprised of rates at least as high as p. (in the event that is the empty sequence, our problem reduces to standard Pareto optimality). Let ő Pı..... Pm: and 8 (,,, σ denote the profit made by an online algorithm on o after its exchange over rate P.. for any E [1, m), Let also s(A, or) denote the vector (A, o)) : E m).. We say that algorithm A dominates another algorithm B on input or, if s(A, .)) is lexicographically no smaller than s(B,a) a)..
Informally, s(A, .) is the vector of profits that A has made so far, for each rate that is at least as high as the predicted maximum rate. The lexicographic ordering assigns priority to profits made at exchange rates close to, but larger than the prediction. We now state our main result.
Theorem 5.1 (Appendix C). For any robustness requirement r, ADA-PO is Pareto-optimal and dominates every other Pareto-optimal algorithm, every possible sequence o.
7

---

Note that the algorithm of [38] is dominant only for sequences in which the exchange rates increase continuously up some p" 2 p. then drop to For those and all other sequences, our algorithm dominates that of [38]. Note also that a dominant r-robust algorithm is a Pareto-optimal algorithm.
Algorithm 2 ADA-PO (adaptive Pareto-optimal)
Input: E IR, [] 1: w <- 0, s 0.p" 1-1
2: for p; E do
3:
if p; > p" then
4:
pº - p;
5:
if S p then
Wi+1 ----(e---ppp)
6:
1)
7:
8 - s + Pi (wi+11 w)
8:
s 11+1
9:
else
10:
if r. (s + - pa + w0
M then
11:
Wi+1 t
12:
else
13:
Wi+1 + w²
14:
Pi (wi+1 w)
15:
w 4 W,+1
ADA-PO consists of two phases. The first phase (lines 5-9) consists of revealed rates strictly smaller than p. In this phase, the algorithm exchanges the minimum amounts so as to guarantee r-robustness (i.e., it makes threat-based decisions). Here, adaptivity allows the algorithm to reserve its budget for the second phase. The second phase (lines 11-15) consists of revealed rates at least as high as p. This is the challenging part, since need to ensure simultaneously dominance and r-robustness, but these two objectives are in a trade-off relation. Here, adaptivity allows us to exchange more money at each revealed rate without sacrificing robustness.
Suppose that p; is revealed the second phase (i.e., Ps 2 p). To achieve simultaneously the robustness and the dominance, need to find continuous increasing & whose domain is [wi+1, 1], along with a value for Wi+1- To this end, we solve the optimization problem O, described below.
Here, constraint [3] is for guaranteeing r-robustness; and constraint [M] and [u] guarantee that + well-defined as threshold function. Maximizing maximizes the amount exchanged rate pt. which is essential for dominance. In Appendix C we give further details, and we show that O, has
optimal solution w equal to the root of the equation wt = In F[sct1-ppeee powwtt" (p. (pt-1)-1)
--1
which is used in line 13 of ADA-PO.
max
(0))
subj. to
2(3) 8: + ps (w -w; + 1 ((t) + +1-
[3]
vB E [w, 1):
[M]
((1) 2 M,
[u]
w, S w 1.
Remark 5.1. ADA-PO, unlike the known static OTAs, does not require a prediction ý ahead of time; the prediction be revealed during its execution instead, since it is only used in the second phase. This can be very useful in practice, e.g., the trader obtains information "on-the-fly""
Experimental evaluation
We present experimental results for both the profile-based algorithm PROFiLE (Algorithm 1) and the adaptive Pareto-optimal algorithm ADA-PO (Algorithm 2). We compare our algorithms to the state of the art Pareto-optimal algorithm of [38], which we denote by PO.

---

Profile setting. We use profile F thht consists of three intervals [q: = 1. 929), (42; Qs) and [gs. = M). where M 100. The profile defined in terms of the prediction p. by choosing Q2 = 0.9p and 4 (larger than, but close to the optimal competitive ratio r*). Here, F([ (e)) = 12 < r the smallest value such that F is feasible. To find 12, we use binary search in [1. in combination with PROFILEE and note that this depends on p. F is depicted in Figure 2a. Intuitively, r corresponds to the robustness, whereas f2 is the performance ratio if the input o is such that p E [0.9p, 1.1ş), i.e. if p is "close" to p². The length of [92, q3), which is equal to 0.2p, reflects how much the user trusts the prediction.
23 1. In addition, F is such that F((1.122) 422) = 41 F[[23: q4]) = L3 = r, where
Figure 2b depicts the performance of PROFILE, and PO with robustness on the worst case sequences of maximum rate p", as function of p Recall that such sequence is of the form I.....p', pp, p", 1, with infinitesimal increments up to p". simulated using step equal to 0.01. We denote this sequence by oz.. We choose P u.a.r. [1, M] (Ú = 67.8 in Figure 2b). We observe that PO exhibits high brittleness if p" is very close, but smaller than P. namely has performance ratio of which validates Theorem 3. In contrast, PROFILE guarantees a performance ratio equal to l2 the entire interval [0, 90, 1.1 as required by F, thus tolerating a prediction error high as 10%, while remaining r-robust for all errors. This validates Theorem 4.1, As expected, PO has better ratio if p* = 6 (from the definition of Pareto optimality).
To further quantify the performance difference between the two algorithms, we evaluated both algorithms on 100 randomly defined worst-case sequences. Each sequence oy is obtained by sampling P u.a.r. in [1, MM, and for such p. by randomly picking p¹ E [0.9p, 1.1p]. the significant prediction error for the user. Figure 2c depicts the relative performance difference of the two algorithms for each ox as a function of the prediction error. We observe that if p* < p. then PROFILE improves upon PO by 20% to 50%, whereas if p > p. PROFILE is inferior by only 10% to 20%. The average improvement we report, taken over the 100 ratios is 22%. We conclude that while both algorithms guarantee robustness r, PROFILE is not only smooth around the prediction, but also performs better on the average, which supports the benefits from using a profile.
In addition, we performed experiments over sequences obtained from real trading data, using the profile F' as above. We used exchange rates from Bitcoin (BTC) to USD; specifically, we used a list of the last 1000 daily exchange rates (finishing on May 20, 2024), defining as the prediction á the maximum rate in the first 200 rates, and running the algorithm on a sequence consisting of the last 800 rates. Figure 2d depicts the performance ratios of PROFILE and PO, where each point in the plot corresponds to the maximum rate observed so far: these are the only rates at which the algorithms make exchanges. We observe that PO continues to suffer from brittleness, whereas PROFILE still exhibits smooth degradation in the interval [0.9p, 1.1
In Appendix E we report an additional experiment on the average performance over BTC sequences. The key takeaway from all experiments on both synthetic and real sequences is that PROFILE performs much better if p* < p. and at the same time it is only slightly worse, if p' > p. This behavior is due to the smoothness enforced around the prediction, as guaranteed by the profile.
daptive setting. Since, by definition, PO and ADA-PO PO perform the same over worst-case sequences, we focus sequences from BTC rates. Based on list of the last 1000 daily BTC rates, obtain a prediction ş and the sequence, as in our profile-based experiments above. Figure 2e plots the performance ratio function of the currently observed maximum rate in the sequence. For every such rate that exceeds p. ADA-PO outperforms PO, which validates Theorem 5.1. This comes at an unavoidable increase in brittleness, as expected, and illustrates the tradeoff between smoothness and dominance. We expect ADA-PO to be the algorithm of choice when the prediction is conservative, or when P is not given the trader ahead of time, but is rather revealed at some point in the sequence.
7 Discussion
Our profile-based framework can apply to many other problems augmented with ML predictions, and not specific to one-way trading. To illustrate this, in Appendix D we analyze another application in the context of contract scheduling, which is a classic problem from resource- resource-bounded reasoning in AI, and which, likewise, suffers from brittleness. Our work is the first towards understanding the power and limitations of imperfect ML predictions in competitive financial optimization beyond extreme values of the prediction error. The techniques introduced will help address problems such as two-way trading and portfolio optimization, which have not yet been studied in learning augmented

---

Fadlo
62
T1A2 1950
6-2 1.18
M
92
8e
reEe
(a) Profile F.
(b) Perf. ratio of PROFILE on 0 s. (c) Average performance improve ment d
".
PO
performance rato
perforancc rati
80
M
max rate
max rate
(d) PROFILE performance ratio BTC.
(e) ADA-PO performance ratio on BTC.
Figure 2: Summary of the experimental results.
settings. Other potential applications include several well-known variants knapsack problems, where online threshold algorithms are commonly used, especially learning-augmente settings [16, 40]. Last, it would be interesting to study dynamic settings, in which the predictions are obtained the sequence is revealed to the algorithm.
8 Acknowledgements
This work was funded by the project PREDICTIONS, grant ANR-23-CE48-0010 from the French National Research Agency (ANR). The first author acknowledges the support of AANI (Agencia Nacional de Investigacion e Innovacion).
References
[1] Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re. Online facility location with multiple advice. In Advances Neural Information Processing Systems, NeurIPS 2021, pages 4661-4673, 2021.
[2] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. Online algorithms with multiple predictions. In International Conference on Machine Learning. ICML, volume 162 of Proceedings of Machine Learning Research, pages 582-598. PMLR, 2022.
[3] Keerti Anand, Rong Ge, and Debmalya Panigrahi. Customizing MI predictions for online algorithms. Proceedings of the 37th International Conference on Machine Learning, ICMI., volume 119 of Proceedings of Machine Learning Research, pages 303-313. PMLR, 2020.
[4] Spyros Angelopoulos. Online search with a hint. Inf. Comput., 295 B):105091, 2023.
[5] Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr, and Bertrand Simon. Contract scheduling with distributional and multiple advice. Proceedings of the 33rd International Joint Conference Artificial Intelligence (IJCAI), 2024. arXiv:2404.12885.
10

---

[6] Spyros Angelopoulos, Christoph Dür, Shendan Jin, Shahin Kamali, and Marc P. Renault. Online computation with untrusted advice. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPlcs, pages 52:1-52:15 Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[7] Spyros Angelopoulos and Shahin Kamali. Contract scheduling with predictions. J. Artif. Intell. Res., 77:395 2023.
[8] Spyros Angelopoulos, Shahin Kamali, and Kimia Shadkami. Online bin packing with predic- tions. Journal of Artificial Intelligence Research, 78:1111-1144 2023.
[9] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. ACM Trans. Algorithmss 19(2):991119:344 2023.
[10] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advic.. Discret. Optim., 48(Part 2):100778, 2023.
[11] Yossi Azar, Stefano Leonardi, and Noam Touitou. Flow time scheduling with uncertain processing time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 1070-1080. ACM, 2021.
[12] Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Online graph algorithms with predictions. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 35-66. SIAM, 2022.
[13] Yossi Azar, Debmalya Panigrahi, and Noam Touitou. Discrete-smoothness in online algorithms with predictions. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS, 2023.
[14) Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning augmented algorithms. Advances in Neural Information Processing Systems, 33:20083-20094, 2020.
[15] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 1998.
[16] Ying Cao, Bo Sun, and Danny H.K. Tsang. Optimal online algorithms for one-way trading and online knapsack problems: A unified competitive analysis. In 2020 59th IEEE Conference on Decision and Control (CDC), pages 1064-1069, 2020.
[17] Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness- consisseeecycsssnnnc tradeoff's for Seaming--uugmente metrical task systems. In AISTATS, volume 206 of Proceedings of Machine Learning Research, pages 9377-9399. PMLR, 2023.
(18) Franziska Eherle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, and Bertrand Simon. Speed-robust scheduling: sand, bricks, and rocks. Math. Program., 1099 2023.
[19] Ran El-Yaniv, Amos Fiat, Richard M Karp, and Gordon Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 30(1):101-139, 2001.
[20] Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In Proceedings of the 36th International Conference on Machine Learning. ICML, volume 97 of Proceedings of Machine Learning Research, pages 2319-2327. PMLR, 2019.
[21] Elena Grigorescu, Young- Loung-Sanuue Lin, Sandeep Silwal, Maoyuan Song, and Samson Zhou. Learning- augmented algorithms for online linear and semidefinite programming. In Advances in Neural Information Processing Systems 35: Annual Conference Neural Information Processing Systems 2022, NeurlPS 2022, 2022.
[22] Sungjin Im, Ravi Kumar, Aditya Petety, and Manish Purohit. Parsimonious Saarnnng-uugment caching. International Conference on Machine Learning, ICMI. volume 162 of Proceedings of Machine Learning Research, pages 9588-9600 PMLR, 2022.
11

---

[23] Sungjin Im, Benjamin Moseley, Chenyang Xu, and Ruilong Zhang. Online state exploration: Competitive worst case and 14172 of Lecture Notes in Computer Science, pages 333-348. Springer, 2023.
algorithms. In ECML/KDD (4), volume
[24] Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang. Online selection problems against constrained adversary. In Proceedings of the 38th International Conference on Machine Learning, ICML,, volume 139 of Proceedings of Machine Learning Research, pages 5002-5012.
PMLR, 2021.
[25] Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalis- tic predictions to schedule jobs with online precedence constraints. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 18563-18583, PMLR, 2023.
[26] Silvio Lattanzi, Thomas Lavastida. Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
[27] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu. Learnable and instance- robust predictions for online matching, flows and load balancing. In 29th Annual European Symposium on Algorithms, ESA), volume 204 of L/Plcs, pages 59:1-59:17, 2021.
[28] Russell Lee, Jessica Maghakian, Mohammad H. Hajiesmaili, Jian Li, Ramesh K. Sitaraman, and Zhenhua Liu. Online peak- pware energy scheduling with untrusted advice. In e-Energy, pages 107-123. ACM, 2021.
[29] Russell Lee, Bo Sun, Mohammad Hajiesmaili, and John C. S. Lui. Online search with pre- dictions: Pareto-optimal algorithm and its applications in energy markets. In e-Energy, pages 50-71. ACM, 2024.
[30] Alexander Lindermayr and Nicole Megow. Repository of works on algorithms with predictions. nttps://an halpr/llgooiii/o tetrrtttttaaat withhhssshhhhhhhe wwwh--reeihhhceceoo conniitiiiin....i. gi github. io, 2023. Accessed: 2023-12-01.
[31] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.
J. ACM, 68:4):24: 2021.
[32] Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In 11th Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of LIPIcs, pages 14:1-14:18. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[33] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, pages 646-662. Cambridge University Press, 2020.
[34] Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. Commun. ACM, 65(7):33-35, 2022.
[35] Esther Mohr, lftikhar Ahmad, and Günter Schmidt. Online algorithms for conversion problems: a survey. Surveys in Operations Research and Management Science, 19(2):87-104, 2014.
[36] Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML predic- tions. In Advances in Neural Information Processing Systems, volume 31, pages 9661-9670, 2018.
[37] Stuart J. Russell and Shlomo Zilberstein. Composing real-time systems. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), pages 212-217, 1991.
[38] Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. Pareto- optimal learning-augmentee algorithms for online conversion problems. Advances in Neural Information Processing Systems, 34: 10339-10350, 2021.
[39] Alexander Wei and Fred Zhang. Optimal robustness-consistan trade-offs for learning- augmented online algorithms. In Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS), 2020.
12

---

[40] Lin Yang, Ali Zeynali, Mohammad H Hajiesmaili, Ramesh K Sitaraman, and Don Towsley. Competitive algorithms for online multidimensional knapsack problems. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(3):1-30, 2021.
[41] Yunhong Zhou, Deeparnab Chakrabarty, and Rajan Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In Proceedings of the 17th international conference world wide web, pages 1243- 1244, 2008.
13

---

Appendix
A Details from Section 3
Proof of Theorem 3.1. Let A Pareto-optimal algorithm of robustness r, and consistency c(r). We will show that for any fixed 0, there exists sequence and a prediction á such that n = p Pol S and A satisfies Definition 3.1. Since is Pareto-optimal, there exists a non-empty set of sequences E.,, such that for all 0e Ec, if A is given as prediction Po.. then
Pc. = c(r).
A(o.)
As shown in [19] we can assume, without loss of generality, that every de is increasing, i.e., it is of the form 0g Pi.....PPe Pr_ with p; > Pj. for all i < j. and Pt. > Pk- We define E to be the co-domain of the following function, f:
f: De + such that f(o.) = = de
if Pr. pkl Sc otherwise.
(A.1)
pI...., Pk. Pr.
c.
Given Σ, let n = |o|| 1, and let z,, be the fraction exchanged by A. Since A is r-robust, it needs to account for the scenario in which the adversary chooses to drop all rates to I after exchanging at the rate Pa- Thus, Zn must satisfy
Pn
S
Sn + Pn In + -11- En - Wp
or equivalently,
In 2 Pn r. (sn 1 Wpr
(A.2)
T (Pn 1)
Define be the RHS of (A.2) Suppose first, that there exists sequence E. for which A exchanges Fa = w. this case, if A is given a prediction ý = Pa. then for the the sequence or = [ n] have that p0 ps. S e, and:
Pz- A(o,)
Pn
8n + Pa w
w
W/
and the proof complete in this case.
It thus remains to consider the case that for all E Σ, In. > Let Fn+1 be the amount exchanged by at rate p We define an online algorithm A', whose statement is given Algorithm 3. Intuitively, while the rate is below Pa, A' makes the same decisions as A. If the rate is between p and p A' exchanges w. If the rate is precisely PT A' exchanges In plus what A did not exchange on rates which were between p exceed pa. We will show that A' has robustness at most r and consistency c such that cN < c(r). which contradicts that A is Pareto-optimal.
and p Finally, A'' makes the same decisions A for all rates that
We first show that A' is r-robust. Let an input sequence and ý a prediction given to A', we will show that p. < A(o'). If p < p ---6, then has A' made the same decisions A, hence remains r-robust. y < p < p. then by definition of w, A' is guaranteed to be r-robust. Last, if p., 2 p. then A' achieves strictly better profit than A.
remains show that A' has consistency strictly smaller than c(r). To this end, it suffices show that: (i) for all 0. E Σ, it holds that OPT(a.)
A'(a.) < c(r), and that (ii) for all o' & E, it holds that OpT(ae) < c(r), assuming that both A and A' are given prediction X P Allos)
To show (i), note that for a' E Ee it holds that OrT(f(a')) Al(oo))
c(r), due to A exchanging In
and A' exchanging In = w. If f(a') = o' (first case in (A.1)) then OFt(a') < c(r). Otherwise, Alo')
(second case in (A.1)) A(o') A(J(o')) hence the same result holds. To show (ii), observe that
A'(a') > A(a") due to A exchanging Vn > and A' exchanging In w. Hence, by the definition of E., we have
14

---

Algorithm 3 Statement of the online algorithm A'
Input: Algorithm A, P,
p" =1, e +-
2: for each rate p; in the imput sequence do
3: if p, > p- then
4:
p pp
5:
if Pr <ーpーc then
6:
Exchange the same amount as A
7:
else ý < pr < P then
8:
Exchange
9:
e - e + 02 w
else if p; = p then
11:
Exchange Zin +
else
13:
Exchange the same amount as A
OpT(OE) A'(o.)
OPT(Oe) A(o,)
< <(rr),
which concludes the proof.
B Details from Section 4
In this section, show how to compute the function & used in PROFILE (Algorithm 1), for deciding whether a profile is feasible. Recall that we seek a function and values 0 = w1 S ... S W1+1 S that satisfy the following sets of constraints.
((3) + S ((1) di 1 -
[3]
v/ E [wa, wi+1):
S4
[w;+1] [u]
$ ((w++1) 9i+1 wy S wi+1 <
for each rate interval [g;, 4.+1).
As explained in Section 4, our algorithm builds function & and values w; in an iterative way. That
is, it processes each set of constraints iteratively, and each step [1, [] it builds function $ and computes values w....., 0yy+1 which satisfy the sets of constraints for all intervals [gi, 4+11) with S j. Each function $ and the new values Wi...., Wy+1 are function of 4 and the previous values Wi...., W'+11
We explain iteration of this process. Suppose that the algorithm is step where it has computed $ and values wi,..., Wy as to satisfy the sets of constraints for the intervals [gi, (+11 with i < j. Constraint [3] requires us guarantee ratio of at least tú for every sequence whose maximum rate is in [ ). We derive a function which achieves a ratio equal to tú for such sequences. The equality sought, instead of the inequality, in order minimize utilization. Intuitively, enforcing ratio smaller than lú would force the algorithm to exchange more money to achieve bigger profit.
Thus the following constraint
((B) 85 + JS, (tt) dt
vB
[w. Wj+1):
tt
B
from which we can obtain the differential equation:
+ Φ- Ly-
(B.1)
which is separable first order differential equation. We can hence find the unique solution
((3) C' : +1.
15

---

We then apply constraint [5], for an arbitrary 3 E [wg, wy+1), so to find the value of the constant C, which yields
(B) (t, (5j + wy) 1) (5)(())))
(B.2)
The obtained function is the unique solution to such equation. We denote Pj = (s3 + wj).
We then use constraint [wy+1] find an expression for Wy+1;
1 In
4j+1
wj+1 tj Pj
wi
(B.3)
Note that ((wy) = Pj- There are two cases to be analyzed.
First, if Pj > qj. then we can define Φ as follows:
{ Φ )))((w) (t, (5y +1 -w) e)-eer(0-w)
if w E [1,
(w)
+1 if [ug, W(+1);
where wj+1 defined in (B.3). We say that we extend the previous Φ This scenario materializes when the algorithm has achieved profit 8j, which allows not exchange while observing rates in [ijee py] and still remain t, t,-competitive. This occurs when tj > f1-1, hence it occurs for the increasing part of the profile.
On the other hand, P3 < qz if < 1111. If this case occurs, the algorithm has not obtained a sufficient profit to be t--ompetiiive when presented with the sequence which continuously increases from to qj. which is the worst-case sequence as stated in Remark 2.1. As we will show in the proof of Theorem 4.1 wy is the least utilization that can be spent to satisfy every set of constraints (gk- (k+1) with & < j. To enforce a ratio of ły and still minimize utilization, the algorithm must exchange bigger amount when rate zj is revealed, since exchanging more at lower rate would lead to larger utilization. To guarantee a ratio of ij for the continuous increasing sequence, the algorithm W where w/ is obtained from:
should trade amount equal w/
Uj
wi w/ bj
8, + qj (w')
and leads to
w/ = Uj tj (8) wi + 1)
t (gg - 1)
We now wish to extend function 1 obtained in the previous iteration, so as to satisfy all constraints for interval [gj 95+1). Let s = Sj + 93 (u/) w,). which is the profit obtained by the OTA in the worst case where the maximum rate q5- We may express this problem by new set of constraints, which are:
((3) 8 Ir ((t) dt +
[3]
vB E [w', m1+1):
Stj,
[wy+1] [u]
((w)+1) = 41+1, w/y < Wi+t S 1.
Note that this set of constraints the same the ones we started with, but sy was replaced by s' and wy by w/. Hence, the & and wi+1 which satisfy the constraints and minimize w/+11 are:
(B8 = (1/ (0')
- 1) e e (B-w))- +
(B.4)
Wj+1 1 4: (s' +1 111-w() w!) - + w/y
1
li+1
(B.5)
We can now proceed with the proof for Theorem 4.1.
16

---

Proof of Theorem 4.1. As stated in Remark 2.1, every online strategy will exchange on rates which are best-seen so far. We can hence state every strategy as an OTA. suffices then prove the following: There exists OTA which respects F if and only if PROFIL. terminates with value W141 1.
Let F be a performance profile. The if direction follows directly from the design of PROFILE. It suffices observe that the obtained function & can be used the threshold function for an OTA which respects the profile F.
To prove the only if direction, will prove that every we obtained by PROFILE is the least utilization needed to satisfy all sets constraints for intervals 14,. 9k+11) for & < In other words, we will prove that if A is OTA, which respects F, defined by o. and where wy...., W/41 the respective utilization levels reached by A when observing rates 91..... 91+1, ie: (w qi for each i E [I,..., 1 1], then w, S w.. This statement follows, once again, from the design of PROFILE. By replacing the inequality constraint in [3] by equality, exactly the one demanded by the profile, hence reserving budget for futures rates. PROFILE obtains a function 4 which enforces, for each i [1, |] and for each o [9t. (++1) the equation:
manage achieve ratio which is
4.-
or (4) (u)du + (4)
We conclude that PROFILE minimizes utilization while satisfying every set of constraints, thus proving the theorem.
Figure illustrates PROFILE. Here we observe that for the increasing part of the profile, @; with i E [4, the vertical "jumps" reflect the less stringent requirement in the increasing part (we can afford to reserve our budget for later). For the decreasing part of the profile, 4 with E [1,3] extends Φ;-1 with an exponential function starting at w/ > wyy (line 9 in the statement) where o (w,)) = +.-1(w)) which is reflected in the presence of straight lines in Figure
extends Φ;-1 with exponential function starting at w, where (w,)) 2;- i Here
reservation mis
64
93
utlization
Figure 3: An illustration of PROFILE. Here the profile F is follows: F(1, 20) 7.F([20, 35)) 5.
F(33, 50)) = 3, [[50, 70]) 3.5, and F(70, 100]) =
17

---

C Details from Section
In this section, detail the calculations that lead to the value w;+1. which is the maximum an online algorithm can spend on rate p; while ensuring r-robustness.
The aforementioned w++1 is the solution to the following optimization problem:
max subj. to
(0,)
( 8; + Pi (w wi) S 2(1) dt +1
[3]
v8 E [w. 1):
[M]
(1) 2 M, ii S w 1
[u]
From constraint [.8], we do the same analysis as in B to find +(33 = Cee + 1. Once again, to find the constant C' we use constraint [6] for an arbitrary value B E [W++1, 1}, which leads to:
+ (3) = (r (s; + 1 pan, + w (p. - 1)) 1) e. c0-00-011) (00-111) +1.
We then use constraint [M] obtain an upper bound on w;+1:
(r- (s; + p. + wi+1 (p: - 1)) 1) (1-wwrr)) +12 M,
which leads to:
Wi+1 S 51--11
1
M
r(8; + pew; + wi+ (p: - -1) 1)
Thus the largest value of wi+1 is the root of the equation
M
06+1 1 In
r(s; + paw; u (p: - 1)
which can be solved using numerical methods. Let be the reservation rate for utilization W;+1 then
P -= + (wi+1) = r- (ss + p:u;; + W:+1 (p: - 1)).
pf > M, then the algorithm has achieved a sufficient profit to guarantee r-robustness independently of future rates. Hence, to maximize W;+1, we can safely set it to 1. However, if < M, then constraint [M]] was saturated, and the algorithm will achieve performance ratio of for every sequence which grows continuously from until rate p" E M.. Moreover, for every sequence whose maximum rate p* E (ps,P) the algorithm will have a performance ratio smaller than r.
As explained Appendix using constraint [3] with an equality allows us to guarantee a performance ratio of minimizing utilization. Observe that to maximize Wi+1 we need minimize the left-over budget to remain r-robust in the future. We can hence conclude that Wi+1 wy is indeed the largest amount of money we can exchange at rate pt and remain r-robust.
We will next provide the proof for Theorem 5.1.
Proof of Theorem 5.1. We prove that ADA-PO is Pareto-Optimal and dominates every other Pareto-Optimal algorithm on any sequence a.
First, we will prove that ADA-PO is Pareto Optiiml Let r be a robustness requirement, and c(r) the respective consistency. To start with, we prove that ADA-PO is r-robust. Consider first the (easy) case where p" < K then ADA- PO assures performance ratio of r using the threat-based approach.
Consider then the (harder) case in which p" p. Let p; be the first rate above á and w;+1, 4 be the respective solution to problem O,, We must prove that no matter how the sequence continues ADA-PO achieves performance ratio of at least r. ( (w(+1) 2 M then a performance ratio of r is guaranteed, due 544++1-0144 < r, from constraint [3]. Suppose then (;(wi-1) M, then by constraints [M] and [u] we know that wi+1 1. When the next rate Pc+1 > pt revealed the same analysis can be applicd. We thus obtain non-decreasing sequence of reservation rates (p
M
18

---

for j > i. For each rate, problem O2 is solved. Note that the feasibility of problem O with rate pa implies the feasibility of the problem O with the next rate as shown by the next analysis. Namely, solution, and if p; (p:--)), then w = 4 (p.). e = - is as well. Furthermore, both cases lead to a performance ratio of at least r in case the next rate equals and is the last rate. We hence conclude, that either one of the reservation rates is greater or equal than M or ADA-PO successfully achieves a performance ratio of r for each rate (w,, < 1 was a solution for each problem). We conclude then that ADA-PO is r-robust.
p: S (p:--1) then w w. D2 2 -
We will now prove that AD is c(onsssntttt We must prove that for every error-free sequence the performance ratio is most c(r). Let A' be any Pareto-Optimal algorithm. When observing rates below ÿ. ADA-PO follows the threat-based policy, hence for every error-free sequence, its budget is least the same A' when a rate equal to á is exhibited. Then by solving the optimization problem, ADA-PO exchanges the most it can in order to remain r-robust, larger amount would make the problem infeasible. In other words, there would not exist a function & satisfying the constraints, and the continuously increasing function from P to M will lead to a performance ratio bigger than т. Hence, no other algorithm could achieve a better profit. We conclude that ADA-PO is c(rr-cconistent.
We finally prove that ADA-PO dominates A'. By the previous analysis, when observing the first rate above the prediction, ADA-PO has budget at least the budget than A'. As ADA-PO exchanges the most it can to remain r-robust, it will obtain a next utilization which is equal or smaller than A', hence achieving a better profit, because A' exchanged the same or less at lower rates. If A' has behaved the same as ADA-PO, then this process repeats for every following rate. We conclude then that ADA-PO dominates performs equally A'.
Remark C.1. To conclude we offer an intuitive explanation of dominance. the maximum rate of the sequence is below the prediction, then ADA-PO's profit will be smaller equal than any other Pareto-Optimal algorithm. Its profit will be equal if the sequence is a continuously increasing one. Moreover, for the first rate equal greater than the prediction, its profit will be greater or equal than any other Pareto-Optimal algorithm. By definition of dominance, while observing rates above the prediction, either the two profits will be equal, ADA-PO's profit is larger, unless the Parcto-Optimal algorithm attained a smaller profit at an earlier rate.
D Profile-based contract scheduling
In this section, we discuss another application of our profile-based framework of Section 3. Specifi- cally, we focus on another well-known optimization problem that has been studied under learning- augmented settings, namely contract scheduling. In its standard variant, the problem consists of finding an increasing sequence X = (z,) which minimizes the acceleration ratio, formally defined as
T
acc(X) = sup T T)
(D.1)
where ((X,T) denotes the largest contract completed by T in X, namely
((X,))=max = max (..-
x. T).
1=0
Contract scheduling is a classic problem that has been studied under several settings. In its simplest variant stated above, the optimal acceleration ratio equal to 4 [37], but many more complex settings have been studied in the literature; see [7] and references therein. In this section we are interested in the learning augmented setting introduced in [7] which there is prediction 7 on the interruption time T. The prediction error is defined as 17 IT r/. In this context, the consistency c( c(X) of schedule X is defined as
c(X) ((X,T)'
whereas its robustness is defined as
T r(X) sup
T21 {(X,T)
19

---

ie.. the worst-case performance of X. assuming adversarial interruptions. Since the latter occur arbitrarily close the completion time of any contract, we obtain an equivalent interpretation the robustness as
Ej= 2j
r(X) sup 421
T4-1
In [7] it was shown that the optimal consistency of 4-robust schedule is equal to 2. However, as proven [5], any such schedule suffers from brittleness. Namely, for any >> O, there exists prediction and an actual interruption time T such that [ - and any 4-robust and 2-consistent schedule satisfies ((X,7) T) < -s
In the remainder of this section will show how use our framework of profile-based performance so as to remedy this drawback. For definiteness, and to illustrate the application of the techniques, we consider the requirement that the performance of the schedule degrades linearly as a function of the prediction error. Namely, suppose that we require that f(X, T) == (X/(X,7 T) be respect profile Fg. where the latter is defined as symmetric, bilinear function that is decreasing for T I т, and increasing for T 2 т. with slope o, as illustrated in Figure 4. This profile is chosen by the schedule designer, and the angle & captures the "smoothness" which the schedule required to degrade as function of the prediction error.
Figure 4: An illustration of the profile Fg.
More specifically, for a given prediction t, and profile Fs as above, we are interested in finding the best extension of Fs such that there exists a 4-robust schedule that respects the extension. We can thus define the analytical concept consistency according to F& as
T
CF. == sup inf
X respects Fg.
[(X,7)
The following theorem states our main result.
Theorem D.1. Given a profile F& and a prediction 7 on an interruption time, we can compute a 4-robust schedule that respects Fg and has optimal consistency according to F.g.
Proof. We will assume that X if of the form (X2') This is not limiting assumption, discussed in [5], and its purpose is to simplify the calculations. Since any 4-robust schedule is the above form [5], it will suffice to compute À that satisfies the constraints of our problem, and the result will follow.
Recall that S(X, T) denotes the function T/((X, By definition, for every i E N, f(X, T) is a linear, increasing function of T' function in the interval 4 = [Tk,Te [22 12*+1], with smallest value equal 2, and largest value equal
With the above observation in mind, for a given, fixed X, let l: such that 7 E Ta+1, i.e., we have that {(X, 7) A Define [1 to be such that = aTı, and note that by construction, is function A. Moreover
TTk
ax2
f(X, T)
2a,
(D.2)
X2
A2
A2k
which implies that suffices to compute o, then À must be chosen so that 2(log(2a)), where {x) denotes the fractional part of x.
20

---

In order to minimize f, subject to X respecting the profile, À must be chosen such that one of the two cases occur, which we analyze separately.
Case The profile F has unique intersection point with f at = т, and moreover F(Tx +c) = 4, for infinitesimally small 0. This situation is illustrated in Figure 5, For this case arise, and for the schedule to be consistent with F, it must be that
π tan
4-2 2
2
2a
Φ)
(D.3)
2
Tk+1 Tk
Tk
It must then be that f(X, + r-Tx
4, hence
4 - p(1 1
20, where
tan ④
Solving the above equality for minimizes by means of (D.2). We obtain that
(VP 16 p+ 4) and f(X, 7) 2a, a a=
subject to the condition (D.3).
T)
4
Time
T
Tg-1
Figure 5: An illustration Case 1.
Case 2. This occurs if the condition in Case does not apply. The profile Fs is such that
F(Tx + = F(Tx+1 c). for infinitesimally small 6 >> 0. This situation is illustrated in Figure
For this case to arise, and for the schedule to respect F& it must be that Ths = 3/2. this case, we obtain that
3 r hence
T T 4 where tan Ø
f(X,T) =
tan
We observe that in both cases in the analysis of Theorem D.I we obtain that f E (2, 4]. as a function of and d. This result makes intuitively sense, since X is 4-robust, and the smallest consistency is equal to 2 (when á > 0).
E Further experimental analysis
To further quantify the performance difference between the two algorithms, PROFILE and PO, performed additional experiments. Specifically, we used a list of the last 20,000 ninute-exchange rates of BTC to USD, so as to create 20 different sequences, each with its own prediction, using the same method as in Fig 2c. For each sequence, we computed the average improvement over PO for rates the interval of interest [0.9ý, 1.1 Figure 7 depicts this average for each of the 20 sequences. We observe that for the sequences in which PROFILE outperforms PO (12 out of 20), the improvement ranges from roughly 15% to 30%, whereas outperforms PROFILE out of 20 sequences, by factor that is most 10%, roughly.
21

---

T)
4
Time
T.
Tx-1
Figure 6: An illustration Case 2.
relative impravement
11
15
sequence
Figure 7: Average ratio improvement of PROFILE over PO
F
Computational setup
The experiments are reproducible on any standard computer, and do not require any memory or computational power beyond the standard requirements. They run typically within few milliseconds.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We provide full theoretical results and all proofs, as well as an experimental evaluation over real and synthetic data.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: ADA-PO exhibits unavoidable brittleness, since it is a Pareto-optimal algo- rithm. Our profile definition for one-way trading is not continuous, but nevertheless can approximate any continuous function for sufficiently large 1. The O()) complexity of PROFILE reflects this fact.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
23

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The proofs of all theorems and statements are provided in the technical appendix. All assumptions are stated in the statements
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: The code and data are provided in the supplemental material. We also provided README file that explains how execute and reproduce the code.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
24

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We used Bitcoin exchange rates from Binance, which are publicly available, and fully explained how precisely it was obtained.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips. cc/ mublic/guides/CCe Sorordeeubisssiooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /nips. wttpcc/pccppppccccccceooocc gtt////dde/////// /CodeSubmissa wwt.SSummiiioon.. wwwiisssinnioiiiiieeee asionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: For sequences from real data, we explain how predictions are generated by observing some prefix of the unknown input. For synthetic data, prediction chosen randomly, as specified in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the
the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification:
We do not believe that an error bar provides further insight to the results
obtained.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
25

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: The experiments reproducible any computer with the experimental setting described in the README file. See Section F.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ete:://neuuppee httppp.c.ppubulle cc/public/Etht www.ihhhhiiiiiieeeeeeeenne
Answer: [Yes]
Justification:
We abide by the code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction)
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our work studies foundational issues in the analysis of learning augmented algorithms. However, we briefly discuss how the proposed methods can be applicd online financial optimization.
Guidelines:
26

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
The only data used is obtained from publicly available datasets, namely Binance.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
27

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The code is provided along with its documentation, the README file.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
28

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
29


Reviews:
[{"review_id": "yyKdGyPyjc", "reviewer": "Reviewer_f8Kk", "summary": "In the context of learning augmented algorithms, two widely used metrics are robustness (i.e: the performance when the prediction is adversarially chosen) and consistency (i.e: the performance when the prediction is perfect). \n\nThis work analyzes the interplay between these two metrics in the one way trading problem with imperfect predictions. In particular, it starts by showing that Pareto-optimal algorithms, that is, algorithms that for a given robustness upper bound r achieve the smallest possible consistency c(r), are dramatically sensitive to small prediction errors. Specifically, the authors show that any prediction error guarantees the existence of an input sequence for which the performance ratio reaches its robustness, a behavior denominated ‘britleness’. This implies that the competitive ratio of any Pareto-Optimal algorithm is either its consistency (if the prediction is indeed perfect) or its worse possible performance, suggesting that Pareto-Optimality might not be a sensible algorithm design criteria. \n\nIn light of this result, this work puts forward the notion of profiles, which maps rate prediction intervals to desired competitive ratios, allowing for the performance of algorithms to degrade smoothly with respect to prediction errors. *V*iewing this, the a*u*thors present an a*l*gorithm that establishes the *f*easibility of a profile in an offline fashion and yields an online procedure that, in the feasible case, satisfies the enforced performance constraints. \n\nLastly, the authors propose an adaptive algorithm that is not designed to handle worst-case predictions but leverages the deviations from the predicted exchange rate to navigate the robustness and consistency tradeoff.", "questions": "- Is there a way to characterize the likelihood of the sequences that severely degrade the performance of Pareto-Optimal algorithms ? If those sequences are very unlikely then Pareto-Optimality might not be that fragile a criteria.\n\n- Why is the function \\phi increasing ? That is, why do larger utilizations necessarily map to larger reservation rates ? (Is it only under the assumption that rates are increasing and then drop to 1?)\n\nMinor comment: Fix figure ratios.", "limitations": "- N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written.\n\n- The theoretical results (brittleness of Pareto-Optimality,  feasibility determination of profile-following and correctness of online algorithm for profile following) are relevant and sound. \n\n- The analysis technique used to determine the feasibility and solve the profile-based one-way trading problem seems novel. In particular, the constraints associated to a profile can be written as a set of linear differential differential equation whose solution yields a profile-following exchange strategy.\n\n- The authors provide intuition regarding the PROFILE algorithm, in particular, on the behavior of the threshold function $\\phi$ with respect to transitions in the desired performance ratio.", "weaknesses": "- The experimental setting might be limited. Specifically, the profile used for evaluation if fairly simple, with only three intervals, two of which map to the worse possible ratio.\n\n- Is there any practical use of determining feasibility if it's in an offline fashion ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Please allow us first to comment on the “weaknesses”.\n\n**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. \n\n**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). \n\nBelow, please see our response to the questions:\n\n**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. \n\n**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. \n\nThank 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "czjE5vTKrO", "reviewer": "Reviewer_jsKn", "summary": "The paper considers the learning-augmented one-way trading problem. In the problem, we are given a starting budget equal to 1 and a sequence of exchange rates $p_1,...,p_n \\in [1,M]$ arriving online. When each $p_i$ arrives, we need to. decide the amount to be exchanged to the secondary currency. Our goal is to maximize the total profit under the given budget. In the learning-augmented setting, the algorithm can access an imperfect prediction $\\hat{p}$ of the largest rate.\n\nThe authors first show that Pareto-optimality is very fragile for comparing online trading algorithms and then motivates a new metric called performance profile. This new metric incorporates the structural information of instances, rather than a simple comparison based on consistency-robustness values. They further develop an online algorithm that can satisfy the given performance profile (if it is feasible). The authors also discuss another generalization of  Pareto-optimality and provide empirical evaluations of the proposed algorithms in the end.", "questions": "See the weakness above.", "limitations": "I didn't see any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The brittleness issue considered in the paper is well-motivated. Actually, this is a highly significant concern in the field of learning-augmented algorithms. Previous efforts mainly focused on achieving smoothness in ratios by defining new error metrics, while this paper takes a novel approach by introducing the concept of profiles to tackle this issue.\n\n- Both theoretical analysis and experimental evaluation are provided in the paper.", "weaknesses": "- The main weakness of this work is that the concept of performance profile may be hard to extend to other online problems, which makes this work less interesting. It would be better if the authors could demonstrate the applicability of this technique to a wider range of problems.\n\n- In Line 131, I didn't see why $w_{A,i}=\\sum_{j=1}^{i-1}w_{A,j}$. Is this a typo?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. In regards to weaknesses/questions, our responses are below.\n\n**1**. We address this issue in *Point 2* of the *global response*, which we also include below for convenience.\n\nThe 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. \n\nThere 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]. \n\nThe 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.\n\nNevertheless, 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. \n\n[A] K. Anand et al. \"A regression approach to learning-augmented online algorithms.\" NeuRIPS 34 (2021): 30504-30517.\n\n[B] K. Anand et al. \"Online algorithms with multiple predictions\". ICML 2022, 582-598.\n\n[C] S. Angelopoulos et al. “Contract Scheduling with Distributional and Multiple Advice”, arXiv:2404.12485 \n\n[D] M. Danashveramoli et al: \"Competitive Algorithms for Online Knapsack with Succinct Predictions\", arXiv:2406.18752 \n\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4YR91SuRKb", "reviewer": "Reviewer_9nZL", "summary": "The authors consider learning-augmented algorithms for the one-way trading problem. In this problem, we are given a budget of 1 and a sequence of exchanges rates between 1 and M that are revealed in an online manner. Whenever an exchange rate is revealed, we have to decide whether to exchange a fraction of our remaining budget at this rate or not. The goal is to maximize the overall profit. In the learning-augmented setting, we are additionally given a prediction on the maximum exchange rate, which is equivalent to predicting the optimum, as an optimal solution will exchange the complete budget at the maximum rate. Usually, learning-augmented algorithms are analyzed using consistency, the competitive ratio for a perfectly accurate prediction, and robustness, the worst-case competitive ratio for any input. For the one-way trading problem, a pareto optimal algorithm w.r.t. consistency and robustness is already known from previous works.\n\nThe main point of the paper is to address two weaknesses of such pareto-optimal algorithms and analyses via consistency and robustness in general. The first weakness is called *brittleness* and describes prediction models were even a wrong prediction that is arbitrarily close to the correct value leads to any pareto-optimal algorithm having a competitive ratio matching the robustness. This means that only completely perfect predictions allow for an improved performance. The authors prove that maximum rate predictions for the one-way trading problem are brittle and address the brittleness by proposing an analysis via *profiles*, a generalization of consistency and robustness. A $profile$ partitions the range of possible maximum exchange rates into intervals and, for each interval, defines a target competitive ratio. The interval that contains the predicted maximum exchange rate has the best target competitive ratio and the ratio degrades for intervals that are farther away. An algorithm respects the profile if it always achieves the target competitive ratio of the interval that contains the actual maximum exchange rate. As a main contribution, the paper gives a constructive algorithm that decides whether there exists an algorithm that respects a given profile. \n\nThe second weakness of pareto-optimal algorithms is that such algorithms are often tailored to worst-case instances w.r.t. the consistency and robustness tradeoff. To address this, the authors give a pareto-optimal algorithm that dominates all other pareto-optimal algorithms in the sense that it does not perform worse than any other pareto-optimal algorithm on instances where the actual maximum exchange rate is larger than the predicted optimal exchange rate.", "questions": "-", "limitations": "In my opinion, all limitations have been properly addressed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper identifies and addresses two reasonable and realistic potential drawbacks of pareto-optimal learning-augmented algorithms. Since the framework of learning-augmented algorithms is ultimately a tool to analyze algorithms beyond the worst-case, the proposed generalizations that extend the ability to do just that are certainly of interest to the community. \n\n* The authors give a proof of concept that profile-based algorithms are indeed possible by introducing such algorithms for the one-way trading problem (and contract scheduling in the appendix). It is a nice idea to consider the offline problem of deciding whether a given profile is feasible or not. I am not completely convinced that this idea also works for problems of a different flavor (see weaknesses), but at the very least it inspires future work to settle this question, which already is an important contribution.\n\n* The paper is well-written, the problem statement is properly motivated, and the results are presented clearly and concisely.", "weaknesses": "* The definition of profiles seems to be tailored to predictions models where only a single value is predicted. For more complex predictions, one could define profiles w.r.t. the prediction error. However, specifying a profile upfront would not always be possible as the range for the predictions error often depends on the unknown online input. Even for the maximum exchange rate predictions, the specification of a profile requires knowledge of the maximum exchange rate M.\n\n* As one of the main technical contributions, the authors give an algorithm that decides whether a given profile is feasible. This algorithm heavily relies on the simple characterization of worst-case instances as given in Remark 2.1. For many other online problems, no such simple characterization of worst-case instances are known. This could limit the impact of the proposed analysis framework via profiles as deciding whether a profile is feasible is likely more difficult (or even not possible) for problems without such a simple worst-case characterization.\n\n* I am not an expert regarding the literature on the one-way exchange problem. However, the paper does not seem to introduce too many new algorithmic ideas. Instead, the algorithmic contributions of the paper seem like a very natural extension of known ideas. In particular, Algorithm 1 seems to be the canonical way of extending threshold-based algorithms to profiles. \n\n* Regarding the experiments, it would be interesting to also see results for different profiles. The used profile is quite similar to the consistency and robustness cases. While this makes the comparison to the pareto-optimal algorithm more fair, it would be interesting to see results for profiles that emulate a smooth error dependency. \n\n* Minor comment: Line 86: I do not think that not having access to the prediction ahead of time is a novelty. In the context of online algorithms there are several examples where the predictions also are revealed over time. One example would be reference [9].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. Below we respond to “weaknesses”.\n\n**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.\n\nIn 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. \n  \n[A] Im, Sungjin, et al. \"Online knapsack with frequency predictions.\" NeuRIPS (2021): 2733-2743.\n\n**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. \n\n**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). \n\n**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.\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5J1dGmeJex", "reviewer": "Reviewer_czee", "summary": "In the burgeoning field of learning-augmented online algorithms, the ideal case is to design an algorithm that achieves a competitive ratio (CR) as a function of prediction errors, without knowing the prediction error in advance. To tackle this problem, many existing works focus on two extreme metrics: consistency (i.e., the CR when the prediction error is zero) and robustness (i.e., the worst CR over all prediction errors). These works aim to derive algorithms that achieve the Pareto-optimal trade-off between consistency and robustness.\n\nThis paper introduces and studies the concept of brittleness in Pareto-optimal learning-augmented algorithms, highlighting that the CR of Pareto-optimal algorithms may sharply degrade to the robustness guarantee with only a small prediction error. Specifically, the work formally defines and demonstrates the brittleness of the max-rate prediction in the one-way trading problem. To overcome this brittleness, it extends the consistency to a concept of consistency by profile F, which specifies the target CR over different prediction errors. A profile-based algorithm is proposed to check the feasibility of the consistency by profile F and find the online algorithm if feasible algorithms exist to attain it.    \n\nFinally, the paper presents an adaptive algorithm that can improve the performance of Pareto-optimal algorithms for particular instances. However, this algorithm also suffers from brittleness.", "questions": "- Can you explain how Section 5 (adaptive brittle algorithm for one-way trading) is connected to the theme of the paper (overcoming brittleness in learning-augmented algorithms)? How significant are the results for contract scheduling in the appendix, and can these results be used to validate the generalizability of the proposed concepts and approaches?\n  \n- For a given user profile, there may exist multiple algorithms that can ensure such a profile; however, these algorithms may exhibit different instance-dependent performances. Can you make some formal statements on how to select the profile-based algorithm in practice? It seems the algorithm making $\\omega_{l+1} = 1$ can be a good candidate algorithm.\n\n- The definition of brittleness (in Definition 3.1) is specific to the maximum rate prediction of one-way trading. Can this be a more general definition for the brittleness of learning-augmented algorithms?\n\n- in line 216 page 5, should the integral in $\\tilde{s}_i = \\int_1^{w_i}\\Phi(u)du$ start from $0$?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper formalizes the brittleness issues in Pareto-optimal algorithms for the one-way trading problem. This helps to better understand the limitations of existing works in learning-augmented algorithms, which is particularly important for practical applications where perfect predictions are nearly impossible.   \n\n- The concept of consistency by profile is a natural yet useful extension of the classic consistency. The proposed algorithm, which can quickly identify feasibility and find a feasible online strategy, is an interesting extension of classic threshold algorithms.", "weaknesses": "-  The paper focuses solely on the brittleness issues for the one-way trading problem. It is unclear whether many other problems exhibit similar brittleness and whether profile-based algorithms can also be designed to address such brittleness. The paper mentions the contract scheduling problem in the appendix, which deserves more formal treatment. In contrast, the paper uses an entire section (Section 5) to propose an adaptive Pareto-optimal algorithm (which is still brittle) for one-way trading, which deviates from the central topic of overcoming brittleness in learning-augmented algorithms.\n\n- The concept of consistency by profile is relatively easier to define for single-value predictions, raising the question of whether this concept would generalize when considering multiple predictions. Specifying the profile may also be challenging for users.\n\n\n- The algorithmic techniques used to design profile-based algorithms seem similar to existing approaches, which involve designing thresholds to maintain the target consistency profile while being prepared for the worst-case scenario if exchange rates drop to 1. The complexity arises from maintaining consistency over the user-specified profile instead of a single perfect prediction point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We comment first on “weaknesses”. \n\n**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.\n\n**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.\n\n**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*.\n\nBelow we respond to questions:\n\n**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.\n\nIn 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. \n\n**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.\n\n**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.\n\n**4**. Correct, thank you for catching the typo.\n\n[A] M. Danashveramoli et al: Competitive Algorithms for Online Knapsack with Succinct Predictions, arXiv:2406.18752 \n\n[B] S. Angelopoulos et al. “Contract Scheduling with Distributional and Multiple Advice”, arXiv:2404.12485", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We respond to some points brought up in the reviews.

**1**. **Experimental evaluation on complex profiles**.  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. Namely, the profile of Fig 2(a) in the submission captures the consistency/robustness tradeoff, the smoothness around the prediction, but also allows for an average-improvement evaluation as in Fig. 2(c), which becomes a much more subjective task for more complex profiles. Nevertheless, we agree with the suggestion of some reviewers, and in the accompanying PDF we consider a more complex profile, shown in Fig. 1. Fig. 2 in the PDF depicts the performance of PROFILE relative to the SOTA Pareto-Optimal algorithm PO. We observe again that PO has high brittleness if $p^*$ is close to, but smaller than $\hat{p}$, whereas PROFILE has a much smoother overall performance that respects the profile of Fig. 1 and again validates Theorem 3.1.

**2**. **Prediction types**. 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 a multiple advice setting, such as the one studied in [B] (with static predictions), 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 


**3**. **Challenges in the design and analysis**. 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” 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).

Meta-review: This manuscript identifies and studies the brittleness problem in the usual Pareto-optimal learning algorithms, through the example of one-way trading. Specifically, it is shown that all Pareto-optimal algorithms (i.e. achieving the best competitive ratio with a perfect prediction, while maintaining a prescribed worst-case competitive ratio for possibly bad predictions) are brittle in the sense that the competitive ratio becomes the worst even if the prediction is very accurate (but not perfect). Two approaches are proposed to remedy this brittleness: 1) a profile-based approach is proposed to allow for different competitive ratios on different intervals, and an efficient algorithm is developed to tell if any given profile is achievable; 2) an adaptive Pareto-optimal algorithm is developed whose performance depends on the distance to the worst input sequence. 

The identification of the brittleness of Pareto-optimal algorithms is significant in practical economic applications. The proposed ideas to remedy this drawback are also sound, and practically applicable supported by the numerical experiments. This manuscript is unanimously appreciated by the reviewers, and I'll happily recommend acceptance.
Decision: Accept (poster)