Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
Authors: Bo Sun
Russell Lee
Mohammad Hajiesmaili
Adam Wierman
Danny Tsang
Venue: NeurIPS 2021 Poster (2021)
Keywords: learning-augmented algorithm
robustness
consistency
Pareto-optimality
online conversion problem

Abstract: This paper leverages machine-learned predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions are accurate (i.e., consistency), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve a better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion. 

Pareto-Optimal Learning-Augmented Algorithms for Online Conversion Problems
Bo Sun
Russell Lee CICS, UMass Amherst rcleeêcs. umass. edu
ECE, HKUST
bsunaadconnect. ust.hk
Mohammad Hajiesmaili CICS, UMass Amherst hajiesmailie @cs. seass.edu
Adam Wierman CMS, Caltech
Danny H.K. Tsang ECE, HKUST eetsang@ust.
adam@caatecch.ede
Abstract
This paper leverages machine-leared predictions to design competitive algorithms for online conversion problems with the goal of improving the competitive ratio when predictions accurate (i.e., consistency), while also guaranteeing worst- case competitive ratio regardless of the prediction quality (i.e., robustness). We unify the algorithmic design of both integral and fractional conversion problems, which are also known as the 1-max-search and one-way trading problems, into a class of online threshold-based algorithms (OTA). By incorporating predictions into design of OTA, we achieve the Pareto-optimal trade-off of consistency and robustness, i.e., no online algorithm can achieve better consistency guarantee given for a robustness guarantee. We demonstrate the performance of OTA using numerical experiments on Bitcoin conversion.
Introductions
An online conversion problem aims to convert one asset to another through sequence of exchanges at varying rates in order maximize the terminal wealth in financial markets. With limited information on possible future rates, the core challenge in an online conversion problem is how to balance the return from waiting for possible high rates with the risk that high rates never show up. high profile example of this risk is cryptocurrency markets, e.g., Bitcoin, where high fluctuations up and down make it challenging to optimize exchanges. Two well-known classical online conversion problems are 1-max-seane search [ and one-way trading [8] which can be considered as integral and fractional versions of the online conversion problem that trade the asset as a whole fraction- by- -raction (e.g.. trading stock in lot or shares). Beyond these two problems, number of extensions and variants of online conversion problems have been studied with applications to lookback options [14] online portfolio selection
[3], online bidding (5). and beyond.
Most typically, conversion problems are studied through the lens competitive ratios and the goal is to design online algorithms that minimize the worst-case return ratio of the offline optimal to online algorithm decisions. For example, El-Yaniv al. [8] have shown that optimal online algorithms can be designed to achieve the minimal competitive ratios for both 1-max-search and one-way trading. However, real-world problems, predictions about future conversion rates are increasingly available and the algorithms developed in the literature are not designed to take advantage of such information.
The challenge for using such predictions is that, in one extreme, the additional information an accurate prediction (advice) of future inputs. In this case, the algorithm can confidently use the information improve performance, e.g., However, most commonly, predictions have
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

no guarantees on their accuracy, and if an online algorithm relies on an inaccurate prediction the performance can be even worse than if it had ignored the prediction entirely.
This challenge is driving the emerging area of the leaming-auugmette online algorithm (LOA) design, which seeks to design online algorithms that incorporate untrusted machine-learned predictions in way that leads to near-optimal performance when predictions are accurate but maintains robust performance when predictions are inaccurate. To measure this trade-off, two metrics have emerged, introduced by [5 and [9]: consistency and robustness. Consistency is defined as the competitive ratio when the prediction is accurate, i.e., CR(O), where CR(E) the competitive ratio when the prediction eπror is e. In contrast, robustmess is the worst competitive ratio over any prediction errors, ie., max; (R()). Thus, consistency and robustness provide way to quantify the ability of an algorithm to exploit accurate predictions while ensuring robustness to poor predictions.
In recent years, stream of literature has sought to design robust and consistent LOA for variety of online problems, such as online caching (15), ski-rental [19], and others. The ultimate goal is to develop algorithms that are Pareto-optimal across robustness and consistency, in the sense that for any 7, the LOA achieves the minimal consistency guarantee among all online algorithms that are g-competitive For the ski rental problem, recent works have derived Pareto-optimal algorithms, e.g., [22] but in most cases the question of where the Pareto-boundary of LOA lies is yet to be answered.
In this paper, we focus on the design of LOA for online conversion problems and we seek to answer the following question: Is it possible to design a Pareto Pareto-optimal LOA for the online conversion problem?
Contributions. We show that the answer to the above question is "yes", by designing an online threshold-based algorithm (OTA), and proving that it is Pareto-optimal. particular, we introduce a class of OTA that unifies the algorithmic design of both 1-max-search and one way trading. We then incorporate predictions into OTA by parameterizing the threshold functions based on the predictions. This approach yields bounded consistency and robustness (see Theorem 4.5 and Theorem (.6). Further, we derive lower bounds for pouustness-consstencyy trade-offs and show that our learning- augmented OTA achieves those lower bounds, and is thus Pareto-optimal (see Theorem 5.1 and Theorem 5.2).. Finally, we demonstrate the improvement of the saariing-augmennn online algorithms using numerical experiments based real- wealdworld data tracking Bitcoin prices.
OTA over pure
The technical contributions of this paper are twofold. First, we provide a sufficient condition for OTA with guaranteed generalized competitive ratio.
design and analysis of the learning-augmente This competitive ratio is general in the sense that it not only can yield robustness and consistency guarantees, but can also potentially provide more fine-grained performance guarantees beyond robustness and consistency. Second, we provide a novel way of deriving the lower bound on the trade-off, which may be of use beyond online conversion problems. The key idea is to construct a function that can model all online algorithms under a special family of instances, and the lower bound can be derived from combining the robustness and consistency requirements on this function. This constructive approach to arriving at a lower bound is distinctive.
robustness-consisten
2 Related Work
Online Conversion Problems. The online conversion problem is first introduced by El-Yaniv ? and analyzed under the competitive analysis framework. It aims search for the maximum rate to make conversions from sequence of time-varying rates, which are chosen by an adversary in the worst-case. The subsequent works X 14 have designed competitive algorithms for both integral and continuous versions the online conversion problem and achieved the minimal competitive ratios. Many variants and extensions have also been studied, such as online conversion under interrelated rates (20] or with inventory constraints (23 See [18) for a survey of other variants. In addition, the design and analysis of competitive algorithms for the online conversion problem have been shown to closely relate to those of the online knapsack problems, such as the online 0/1 knapsack with small weights (24 266 and online fractional knapsack (2T] Beyond the worst-case input model, another line of research considers searching for the maximum value from the time-varying rates with some form of prior knowledge. For example, the secretary problem
R assumes that the rates arrive in a uniformly random order and the prophet inequality ( assumes that the rates arrive in the worst-case order but with prior distributions. The prior information in these problems makes the design and analysis of algorithms essentially different from those of online conversion problems.

---

Gearning-augmenter algorithms. The learning augmenned algorithm (LOA) takes advantages of machine learned predictions about the future imput into the design of online algorithms and aims to optimize for better competitive performance with an improved quality of predictions. The concepts of consistency and robustness are first introduced to study the online caching problem in [5]. Then the follow-up work [19] formally shows that there exist trade-offs between consistency and robustness in the ski-rental problem and its variants, and LOA needs to be designed to balance the two criteria unlike the online algorithms just optimized for the competitive ratio. Furthermore, the works [4] and [22] independently prove that the LOA designed in [9] is Pareto-optimal, i.c., given a robustness, no online algorithms can achieve smaller consistency. Also, in [I] and motivated by an energy optimization scenario, the authors develop Pareto-optimal algorithms for an extended version of the ski-rental problem. From the aspect of methodology, the work [4] provides general approach to incorporate the prediction into the online primal-dual algorithm and shows it can be applied to solve multiple online problems. In terms of applications, LOA has been designed for a variety of online problems, such as online caching [15]. ski-rental [19] 22 4 [1, online set cover [4] online
scheduling [19 [10), secretary and online matching [3, metrical task systems (2), etc. However, among those applications, the Pareto-optimality of LOA has only been rigorously shown for the ski-rental problem.
3 Problem statement and a unified algorithm
The online conversion problem. An online conversion problem considers how convert one asset (e.g., dollars) to another (e.g., yens) over trading period [N] == {I....,, N]. At the beginning of step n [NV] an exchange rate (or price), Un announced and a decision maker must immediately determine the amount of dollars, In, to convert and obtains U, yens. The conversion is unidirec- tional, i.e., yens are not allowed to convert back to dollars. The trading horizon N is unknown the decision maker, and if there are any remaining dollars after N - 1 trading steps, all of them will be compulsorily converted to yens at the last price UN. Without loss of generality, the initial asset can be assumed to be 1 dollar, and the goal is to maximize the amount of yens acquired at the end of the trading period. The offline version of the conversion problem can be cast as
maximize 20
Eme[Ny Un:En: subject to ΣmEINy In S1
(1)
If the conversion is only allowed in single transaction, the decision In E 1) is binary variable, and this integral version is called L-max-search (7]. If the asset is allowed to convert fraction- by-fraction over multiple transactions, the decision 2;, E [0, 1] is continuous variable, and this
fractional version is refereed to as one-way trading [8]. Following the literature, we assume the prices {v, ] are bounded, i.e., 2n [], Vn E [N], where L and U are known parameters, and define 0= = U/T as the price fluctuation.
Online hhreshold-based algorithms. Online threshold-based algorithms (OTA) belong to class of reserve-and-gree -reddyyddy algorithms where the idea is to use threshold function to determine the amount of resources that need to be reserved based on resource utilization, and then greedily allocate resources respecting the reservation in each step.
OTA is known to be casy-to-use but hard-to-design due to the difficulties in developing the threshold function. Prior work using OTA has often been problem specific. For example, optimal design of the threshold function in OTA is derived in (21] for one-way trading and in 255 26 for the online knapsack problem, which is closely related to one-way trading.
Here, we unify online algorithms for online conversion problems in an OTA framework in Algorithm [ Algorithm I takes threshold function & as its input, where d(w) [0, 1] + [L, U] is function of resource utilization (i.e., amount of traded dollar) w and d(w) can considered as the reservation price when the utilization is w. The algorithm makes conversions only if the current price v, is at least (x))),,)), where (n-1) = Eiejn-1j F. is the utilization after the previous n - steps of trading. More specifically, the conversion decision F, in each step is determined by solving an optimization problem in Line of Algorithm []] The OTA framework transforms the algorithmic design task in online conversion problems into the design of Φ. and the challenge is to design e such that OTA can have theoretical performance guarantees. To provide two examples, in the following we show how recover the optimal online algorithms for 1 1-max-search search and one- way trading.
3

---

Algorithm Online Threshold-basee algorithm with threshold function & (OTA3))
1: input: threshold function <(-), and initial resource utilization (i.e., traded dollar) w = 0:
2: while price Uy revealed do
puin 1 plu)duu
3: determine resource allocation Zi arg maxx, E.N, Un Satta
4: update the utilization w(() = w(n-1) + Zn.
5: end while
1 I-max-search. In this integral conversion problem, OTA sets the feasible space as X, = {0, 1 and the threshold function constant ((w) Φ E [0, 1], where
also called reservation price.
Then the algorithm simply selects the first price that is at least 4. When the reservation price is designed as 4 = VLU, OTA is exactly the same algorithm as the reservation price policy in (8). which achieves the optimal competitive ratio vB.
One-way trading. OTA sets X, [0. (nn=1)) and & as a continuous and strictly increasing function. The conversion decisions fall into three cases based on the solution of the optimization in
Line 3: (i) if en < ((w(n-1)), make no conversions, i.e., T, = O; (ii) if (1w(1-1)) I Un S ((1), In can be solved based on the first-order optimality condition, i.e., 2n, ((w(-=1) + ).)): and (iii if
Un > ((1), F. 1 - w (n-1) converts all its remaining dollar at the price By setting the threshold
function to (bw) ()) = + (a I, - L.) exp(a" (aww""))))) w), w E [o, 1). OTA achieves the optimal competitive
ratio a² = + ((0 - 1))e), where W() is the Lambert-V W function [21]
4 Robustness and consistency
This paper is focused on the design of leaming-auggmnter online algorithms (LOA) where the online algorithm is given machine-learned prediction P E [Z, U] of the maximum price V = maxng[N] Up the price sequence. In the online conversion problem, suppose V is known a prior, waiting to trade all assets at the price V achieves the maximum profit. Therefore, the maximum price is an appropriate value be predicted and incorporated into the design of the online algorithm. The prediction P is not necessarily accurate and we define g = IV - Pl as the prediction error. Let CR(s) denote the competitive ratio of OTA when the prediction error is e. Our goal is to design an algorithm that is concosiittntt and 7-robust, i.e., an algorithm where 1) 2 CR(O) and 7 2 max, CR(E). We first focus on designing a darning--uumenterr OTA by incorporating predictions into the design of the threshold function ø to achieve bounded robustness and consistency.
4.1 Warmup
To highlight the challenges of algorithm design in this setting, we start by showing that an intuitive use of predictions can result poor robustness consnesss--cssstennyycy. guarantees. Thus, it of essential importance to take advantage of the problem structure in designing the learning- augmented OTA.
To illustrate this, consider the design of the reservation price &p for I-max-search an example. If we blindly use the prediction of the maximum price by setting 6p = P, OTA is indeed offiine optimal when the prediction is accurate, and thus 1-consistent. However, its robustness is the worst possible competitive ratio 0, which is achieved when the prediction is P = U and the actual maximum price is V U e, where + 0. fact, the robustness guarantee approaches 0 with an arbitrarily small prediction error.
Another intuitive design is to set the reservation price linear combination of P and the optimal reservation price for pure online algorithms VLU, i.c., p XVLU + (1 (1-A) P),, where À E [0, 1] called the robustness parameter, indicating the distrust in the prediction. The robustness and consistency of this algorithm is characterized by the following result.
Proposition 4.1. Given E (0, 1), OTA with the reservation price 4p AVLU + (1- X)P 1-max-search is (Av0 + (1 - x)0) -robust and VD-consistent.
Above consistency-robustness result tight in the sense that for a given X, we can construct an instance, under which OTA with the reservation price &p can achieve the robustness and consistency

---

in Proposition 4.1 with arbitrarily small gaps. This result highlights that, while the robustness is a linear combination of the optimal competitive ratio v and 6, the consistency is v0, which yields no improvement over the optimal competitive ratio except for a special case when 0.
4.2 A sufficient condition
Together, the two examples in the previous section highlight some the challenges associated with balancing robustness and consistency in OTA. Given the challenges, we now focus developing general approach for the design and analysis of robust and consistent learning-augmented OTA. To do so, we first generalize the competitive ratio from scalar to vector, where each element corresponds to a competitive ratio over a subset of instances (see Definition 4.2). Since consistency and robustness can be considered as the competitive ratios over the subsets of the predicted instances and the guarantees
other instances, the competitiveness of OTA can be transformed to robustness-consiste (see Lemma 4..) This transformation leads us to characterize general sufficient condition (see Theorem 4.4) on the threshold function of OTA that guarantees generalized competitive ratio over given subsets of instances. Then, combining T.e Lemma (43 gives a general approach for analyzing the consistency and robustness of OTA, which we leverage in the analysis of 1 1-max-search and one trading in the following sections in order to illustrate its applicability.
To begin, let (Z) and (Z) denote the returns of offline optimal and an online algorithm under instance I, respectively. Let P := (Pi,..., -- P1} be partition of the set Ω of all instances.
Definition 4.2 (Generalized competitive ratio). a == (o1....,.x)) .,)) is a generalized competitive ratio over P if oq maxIep, OPT(T)/ /ALG([))GTT)))) is the worst-case ratio over P, Pofor all i (T].
In online conversion problems, let Qpp S Ω be subset, which each instance has a maximum price Thus, if we have a prediction P on the maximum price, it means the instance is predicted to belong to Qp. We can show the consistency and robustness of a -aaningguugmeeeedd OTA by proving its generalized competitive ratio over partition. In particular, given prediction P. OTA is cononsisttnt and y-robust if there exists a partition such that OTA is c-competitive over the subset that contains Qp and c-comettitive for the remaining subsets. Formally we have the following claim.
Lemma 4.3. Given a prediction P E [L. U), and parameters n and y with S 7, OTA for online conversion problems is n-consistent and y-robust there exists a partition P (Pr, P-} with Ω PPP and Q2 C Pay and OTA is (n, competiiive over P.
Building on Lemma 4.3 we now focus on how to design the threshold function & in OTA to ensure a small generalized competitive ratio. To this end, divide the range of price [T. U] into / price M2 U. We partition Ω based on the price segments, i.c., Ω = (Sp))e([Mo.MM ) U .... (Sp)pE(MM Hereafter, we use P; or [M,11.M, to denote the i-th instance subset {Sp)pe[M, I.M,). 1. To ensure different worst-case ratios over different subsets of instances, we consider a piece-wiss threshold function & created by concatenating sequence of functions (db))etf)) where each piece Φ; is designed to guarantee a--competttveeness over P; In particular, divide the feasible region [0, 1] into 1 resource segments
segments [Mo, .M)....,, [M My] with L Mo M1
[8. B1). [31-1, $5]] with 0- = Bn < 31 < < 31 = 1, and (w) E [M;-1- M2), [8-11, 8.). We say Φ; absorbed if 3;-1 3z. The following theorem then provides a sufficient condition for designing the threshold function é in OTA to guarantee generalized competitive ratio.
Theorem 4.4. OTA is a-competitive over {P:) for online conversion problems if == { hejn a piece-wise and right-continuous function, ((1) E {MaJaetn is one of the partition boundaries, and each threshold piece (e(w)) 1Bi-1, (c) [M,11, M,) satisfies one of the following conditions:
Case if M, E <(0), then M, S oz I and B, = 0:
Case II: (0) < M; S @(1), then Φ, is in the form of
vc(w) Mi-1
w E (8,-1,33-1)
(((w) w E 3.)
which consists of a flat segment in [3,-1, 1, 8/-1) and strictly increasing segment (u((w) that satisfies
{ (p((w) < a: [oo d(u)du + Sø (i(luddu + (1 - w)[] Ye E 11)_113))
(3)
(:(3)) = M,
5

---

Case III: M, > 6(1. then M, S az So ((u)du and B = 1.
Theorem is the key to the analysis that follows. In particular, it provides sufficient condition for analyzing the generalized competitive ratio of OTA, which in turn yields bounds on consistency and robustness as highlighted in Lemma 4.3 We show its broad applicability in the subsections that follow by applying in the context of 1- 1-max search and one-way trading.
Further, this approach is general and provides opportunities to derive more fine- fine-grained performance metrics for the Garning-augmenter OTA beyond consistency and robustness. For example, instead of just focusing on the improved competitive ratio when predictions are accurate, we can redefine the consistency as prediction-error dependent metric x(E) == maxe<e CR(e). x(E) characterizes the improved competitive ratio if the actual value is within the neighbourhood of the prediction { + c. Thus, x({) is a more general and fine-grained metric, and 1j and 7y are two extreme points of x<E), i... 77 = x0) and f = k(oo). Given É. we can leverage the competitive ratio to design -conssititt and 7-robust OTA. In particular, given P. OTA is k(E) conssccosttt and y-robust if there exists partition P = (Px(e): P,} with [pe(r-g.P4S) S Pa(e). and OTA is (M)()) coompettiieeee over P.
4.3
1-max search
We now apply the sufficient condition in Theorem 4.4 to the setting of 1-max search. Our goal is to design the reservation price D given a prediction P. To do this, set 17 := 17()) and y == 7A) as
7()) = (11 - x)2 4X0 - (1 - -))]/(2)), and ry()) = 0/>(A),
(4)
where À E [0, 1] is the robustness parameter, and 1j and y are predetermined parameters for designing Pp that represent the consistency and robustness that we target to achieve. In particular, 1 and y are designed as the solution
() = 0/7(), and (A) = (x(
A.
(5)
The first equation is the desired trade-off between robustness and consistency, which will be shown to match the lower bound in Section 5 and thus represents a Pareto-optimal trade-off. The second equation sets 7/ as a linear combination of and y. In this way, as À increases from 0 to 1, 77 increases from the best possible ratio 1 to the optimal competitive ratio v0, and y decreases from the worst possible ratio to vo. Taking 7) and y as inputs. we design the reservation price op as follows:
when P E [T., Ln)) Φp Lmf when P E Ln, Ln), pp ALy + (1 A)PPTT
(6a)
(6b)
when P [Ly,U] pp Iny
(6c)
The following theorem provides robustness and consistency bounds for this algorithm. The result follows from the general sufficient condition for the class of OTA in Section 4.2 Given each reservation price p, the key step of analysis is to determine a proper partition of instances and then analyze the competitive ratio over each subset, in which 2p can satisfy the sufficient condition in one of the cases in Theorem 4.4 Take pp in (6a for an example. We partition [L, U into [L. Ln)) and [L, by letting M₁ = Ln. Since d(0) x(1) = h L1j, op satisfies Case and Case III for Ln) and Ln,, U), respectively. and the corresponding competitive ratios are
& 17 and 02 = U/ = 0/n- = 7. Thus, OTA (1), -)-ooppetiiive over [L., Lạ)) and [Ly, U.. A Additionally, the predicted instance 22 C Ope(L,LL)) and thus OTA is 1y-consistent and 7-robust based on Lemma 4.3
Theorem 4.5. Given À [0, 1]. OTA with the reservation price in Equation 6 for 1-max-search is (A))-robutt and ()))))(()o)))))) -consiseee, where ((A) and ()() are given in Equation
Before moving to the proof is important to give insights into the form of the reservation price (6). It consists of three segments for predictions that are in boundary regions [L, Ln)) and [L,, U] close to price lower and upper bounds, and intermediate region [Ln, Ly). Figure [ Iillustrates the form and compares it with two intuitive designs P P and h p = AVIU + X) which we have shown providing poor robustness and consistency guarantees. Given any reservation price &b E [T. U'). the robustness of OTA max ( (L,,, U/ where T/L and U/ are the worst-case ratios over subsets [L, ④) and [4), UJ. To ensure good robustness, (6a) and (6c) are designed to balance & and U/4

---

10
gergend by 4p P
Pe 2.
(v8.v0)
4p JV
Thoshold frrction e
L-max
Roseratinn price
Consittncy
1.8
wne-way trading
[9. 161
0.1)
10
0.2
0.4
Prediction
Utiization W
Robusiness
Optimal robustness- search (left) and one-way trading (right) with L. and U 10 consistency trade-off'
Figure 1:
Reservation price and threshold function for 1-max- Figure 2:
by just ensuring /-coopetitiveness over the boundary region that contains the prediction. The intuitive design p P neglects this structure, and thus its robustness approaches the worst possible ratio Given accurate prediction P. the consistency of OTA is max L/ L, P/D]. To guarantee good consistency, we must avoid the case that P < 4, leading to the ratio &/ L that cannot be properly bounded. (6b) is designed by enforcing P 4 p. In this way, OTA always makes conversions in the intermediate region and the consistency P/ p. which can be designed to be upper bounded by
The intuitive design 4p = AvLU + (1 A) fails to improve the consistency over v0 since cannot always guarantee P &p in the intermediate region, and thus may make conversions even with an accurate prediction. A full proof of Theorem 4.5 is in Appendix A.4
way trading
Next, we apply the sufficient condition in Theorem 4.4 one-way trading. We also aim design the threshold function based on the prediction P. Here, we set 7 == 7()) and r) :- (A) as
72) + (0 (0- (1 7(1) In 7())
] and ((A) = a" +1 1) a²), (7) -
(A)) 0/
where À E [0. is the robustness parameter and a" is the optimal competitive ratio of one-way trading. Similarly to the design in 1 1-max-search, the two equations in ( determine the desired trade-off between 1) and y, and their desired relationship with X. Again, derive lower bound in Section S showing that this relationship is tight and provides a Pareto-optimal trade-off.
Taking 7/ and y as inputs, we design the threshold function as follows:
w E [0, (3) L+ + (U - L) exp(r(w-1))
T. + (1 T.) exp(nw)
when P E M), Φp(w)=
(8a)
w E [3, 1]
I (7L L.) exp((w)
w E (0,31) w E [5,
Mj
when P [M,U), 6r(w)-
(8b)
I++ (Mi - I.) (oxp(n(w-811)
w E [3,
L + (U -L)exp(1(u) - 1))
w E (82,1)
where B and M solutions of
M = = (nL (n)=)))))((33) My/n = L (U - L) exp(> 1));
(9)
and Mj. 31, 3r and Bg are all functions of P and are determined by
81 1 In M, M, /L,)
7
7-1
M, 1o o(u)du (8) B. + -
17
(10)
P = + (M1 - L)exp(m(32 - -()),
82 1 1+ In pin
The following theorem provides robustness and consistency bounds for this algorithm. Again, the result follows from the general sufficient condition for the class of OTA that we introduce in Section 4.2

---

Compared to 1-max-seardee the additional difficulty of one-way trading lies in the analysis of the competitive ratios over the subsets belonging Case II of the sufficient condition since the threshold
function dp ranging in these subsets needs to satisfy set of differential equations (3) Φ0 in (8) is in
fact designed as the solution of the differential equation (3) with binding inequalities and properly designed boundary conditions (by setting the length of the flat segment of each threshold piece).
Theorem 4.6, Given À E [0, 1], OTA with the threshold fincttin ( for one-way trading is 7(A)- robust and (()) consisteet,, where 7(A) and (()) are given in Equationn (7).
Figure 1 illustrates the function given different predictions. The basic idea behind the design of the threshold function (8) similar to that of 1-max-search. When the prediction in the boundary region P e I, M), the threshold function (8a) (i.e., red curve) is designed to ensure sycompetitiveness over [L. M), and additionally g >>comettitiveeess over [M, U.. In the other extreme when
L + (L7 L) exp(rw), E [0, (1) and Φr(w) = U, w E [3,, 1] (i.e., green curve) since 82 = 31 = and M1 = by solving equation (TO) with P = U. This threshold is -competiieee over [U] and [z, U). When the prediction is in the intermediate region P E [M, U), the threshold function consists of at most four segments. The first and the forth segments when aiming to ensure 7-competitiveness over [L, M1) and (P, These two segments may be absorbed when the prediction is small (M1 S Ty) or large (Py/n 2 U), corresponding 31 = 0 and [92 1. To guarantee a good consistency, a flat segment in w E (1) is designed to convert enough dollar before reaching the price P by enforcing P 2 M1, and an exponential segment with rate n in w E [8), [2] to ensure y-competitiveness over [M Pl. A full proof can be found in Appendix A.5
P P= U, the threshold function (8b) becomes Φp
[0, [1) and
(82, 1] are exponential functions with rate 7
5
Pareto-optimal consistency-robustues trade-off
To this point, we have focused on upper bounds for robustness and consistency. This section provides lower bounds on the robustness-consse consistency trade-offs for both 1 I-max-search and one-way trading and shows the cartta-optimality of our proposed lower bounds on the trade-off between robustness and consistency for online algorithms has proven difficult. The only existing tight lower bounds we are aware of are in the case of deterministic ( and randomized [4] [22 algorithms for the ski-rental problem.
-aggingte algorithms. Note that, obtaining
Theorem 5.1. Any 7-robust deterministic LOA for I-max-search must have consistency 2 0/7. Thus, OTA with the reservation price (6) Pareto-optimal.
Theorem 5.2. If a deterministic LOA for one-way trading is 7-robust, its consistency is at least 7 2 g + (0- - 1) In 8-1 )]. Thus, OTA with the threshold function (8 is Pareto-optimal.
We illustrate the Pareto- Pareto-optimal trade-offs of robustness and consistency for 1 1-max-search and one- way trading in Figure 2 Notice that the Pareto-boundary of one-way trading dominates that of 1 I-max-search since the fractional conversion leaves more flexibility to online decisions in one-way trading, leading to a better lower bound. For both problems, with the improvement of consistency from the optimal competitive ratio (i.e.. v or a") to the best possible ratio 1, the robustness degrades from the optimal competitive ratio to the worst possible ratio 6, This means there is no free lunch in online conversion problems; to achieve a good consistency, robustness must be sacrificed.
We end the section by proving Theorem 5.2 for one-way trading. A proof of Theorem 3.1 is included in Appendix
Proof of Theorem 5.2 To show a lower bound result, we first construct a special family of instances, and then show that for any 7-robust LOA (not necessarily being OTA), their consistency 1) is lower bounded under the special instances.
We focus collection of p-instances (Ip)pe[L,n where p ranges from L to U, where a p-instance is defined as follows.
Definition 5.3 (p-instance). Given p E [L, U] and large N, an instance In := {Ui, UN is called a p-instance v. = L + (n - 1)6, n E [N 1] with 8 = -- and uy =
Notice that, when N + oc, the sequence of prices in I, continuously increases from I. to p. and drops to L in the last step.
8

---

Let g(p) [L. U] + [0. 1] denote conversion function of a deterministic LOA for one-way trading, where g(p) its total amount of converted dollar under the instance Ip before the compulsory conversion in the last step. A key observation is that for large N, executing the instance I is equivalent to first executing Ip (excluding the last step) and then processing p + and L.. Since the conversion decision is unidirectional and deterministic, we must have g(p + 6) 2 g(p), i.e., g(p) is non-decreasing in LL, U]. In addition, the whole dollar must be converted once the maximum price U is observed, i.e., {U) 1.
Under the instance Ip. the offline optimal profit is ( p and the profit of an online algorithm with conversion function g is (I, g J udg(u) + L(1 g()),, where udg(u) the profit of converting dg (u) dollar the price u. The first two terms the cumulative profit before the last step and the last term is from the compulsory conversion.
For any 7-robust online algorithm, the corresponding conversion function must satisfy -ph> p/7, Vp E [L,U], U]. If, additionally, given prediction P 2 7L, no dollar needs to be converted under instances {Ip pE])..... i... g(p) 0, Vp [L,yL), This is because a y-robust online algorithm converts any dollar below the price L we can always design a new algorithm by letting it convert the dollar at the price Y instead. The new online algorithm is still n-robust and achieves a smaller consistency when the prediction is accurate. Thus, given P U 2 In the conversion function of any y-robust online algorithm must satisfy
ALG 2 OPT(I,)/7
ALG = g(>DnL+ ["' udg(u) + L(1 - g())) 2 P. ?"
V [7L.
(11)
By integral by parts, a necessary condition for above robustness constraint (T] to hold is g(p) 2 p/7-L + p- JeL g(u)d(( du. Based on Gronwall's Inequality (see Theorem 1, p.356, [17), we have p-L
s(p) 1/7 - T
1 /" u 7 p p-L 7 7 (u Ly du In p L 7 L' Vp E U..
(12)
7
In addition, to ensure n-consistency when the prediction is P = U, we must ensure ALG 2 OPT(Iu)/m) Combining this constraint with g(U) gives
[ g(u)du S ( 1)U/n.
(13)
By combining equations (12 and (13, the conversion function g(p) of any 7-robust and conosisstttt
online algorithm given P = U must satisfy 1/ In w-L du S l g S (1 - 1)U/n, which
7L-1 0 + (0 1)(1 In 9-1)].
equivalently gives 1) 2 0
Finally, since Theorem 4.6 has shown that OTA with the threshold function (8) can achieve the lower bound in Theorem 5.2 it is Pareto-optimal.
6 Numerical results
We end with a case study on the exchange of Bitcoin (BTC) to USD. This case study is timely since the rapid growth of cryptocurrency has left many traders eager to profit from rising and falling of exchange rates in average-case scenarios, while the uncertainty and volatility of cryptocurrency have made many traders cautious of unforeseeable crashes in corst-case scenarios. Our results answer two questions: (Q1) How does the -atrientee OTA compare to pure online algorithmss with different prediction qualities and drastic exchange rate crashes? (Q2) How should the OTA select the robustness parameter X, and especially, would an online learning algorithm work in practice?
Setup. We use historical BTC prices in USD of years from 2015 to 2020, with exchange rates collected every 5 minutes from the Gemini exchange. We assume one BTC is available for trading during 250 instances of length one week. Since BTC is traded in the unit of satoshi (i.e., 0.00000001 BTC), this problem fits the fractional conversion setting and we apply the LOA for the one-way trading problem the following experiments. We set L and U as the historical minimum and maximum prices over the entire 5 years To generate a prediction P. we simply use the observed maximum
'The focus of this paper is not on the impact of L and U, and thus we simply set them as historical values. In practical trading problems, L and U can be considered as predetermined parameters that represent the stop-loss and take-proc -pofit prices in the exit strategy of the trading process.

---

2.25
2.25
Aconge Camubatiee Profit
Aiguay Algiaar Alg
Migh
Profit Ratio
Profit Ratio
2-
Aig/aois
1.75
1.75
Reget
0.95
1.5
1.5
1.25
1.25
0.3
A0gl
Alg
0.9
0.15
100
200
150
Error Level Group
Crush Probability Group
(a)
(b)
(c)
(d)
Figure 3: Profit ratios of different algorithms with (a) different prediction errors and (b) different
crash probabilities. The evolution of (c) the average cumulative profit and (d) regret of Alg (Aa))
exchange rate of the previous week. To evaluate the impact prediction quality, we adjust the error level between 0.0 to 1.0, where 0.0 indicates perfect predictions and 1.0 indicates unadjusted predictions. To evaluate the performance in worst-case settings, we also introduce a crush probubility q. where the exchange rate of BTC at the last slot will crash to L with probability 9.
We compare the empirical profit ratio of four different algorithms: (i) Alg(>"), the worst-case optimized online algorithm that does not take into account predictions, but, guarantees the optimal competitive ratio; (ii) Alg(A an algorithm that finds the best possible distrust parameter in an offline manner; this algorithm is not practical since it is fed with the optimal parameter, however, it illustrates the largest possible improvement from predictions under our algorithm; (iii) Alg(X (l))) an online learning algorithm from [16] which selects the parameter using the adversarial Lipschitz algorithm a full-information setting; and (iv) Alg()=ts), an online algorithm that uses the best static À and serves as the baseline for Alg(A ())(). Additional details are in the supplementary material.
Experimental results. We answer QI in Figures (3a) and 3(b) and Q2 in Figures 33c) and 3(d)
Figure 3(a) compare the profit ratios of several algorithms at different error levels. First, it shows that A and Alg(Aalf) noticeably improve the performance
Alg(A*). The upper boxplot whisker of (A*()*) is 1.35, while Alg(> at 1.0 error level has upper boxplot whisker around 1.25. Second, it shows that the gap between Alg(Aerr) and Alg(>alr) is quite small, as the upper boxplot whisker of Alg(X is slightly lower. Comparing the profit ratios of different algorithms with different crash probability values at 1.0 error level in Figure we see that the performance of Alg(A") drastically degrades crash probability 0.45. However, both Alg(Aalf) and Alg (ooff) stable at high crash probability. Figure ((c) compares the average normalized profit of Alg()aIr and Alg() Atte and shows the reward of A1g(A all) converges toward that of Alg (lg())te) the learning process moves forward. Figure (d) indicates that the regret of Alg(Aalf) stabilizes.
7 Concluding remarks
To improve upon the performance of algorithms for online conversion problems that are designed with worst-case guarantees in mind, this paper has incorporated sichined-learned predictions into the design of class of OTA and shown that the learning- auggmentdd OTA can achieve Pareto-optimal vobustness-consisten the robustness and consistency analysis of LOA, with the first being for ski rental problem 4 22). We expect that our method of deriving lower bounds can be extended to more general online optimization problems with capacity constraints. A limitation of this work is that consistency and robustness only measure the competitive performance in two extreme cases, i.c., the predictions are perfectly accurate or completely wrong. Although our approach for design and analysis OTA provides opportunitics to design OTA in ways that guarantee more fine-grained performance metrics, this is left for the future work. Another limitation is that this work provides only empirical evaluation of the algorithm Alg() that selects the robustness parameter in online manner. Deriving theoretical bounds remains open. Last, we cannot see any negative societal impacts of our work.
trade-offs. This result represents only the second tight lower bound result in
10

---

Acknowledgements
Bo Sun and Danny H.K. Tsang acknowledge the support received from the Hong Kong Research Grant Council (RGC) General Research Fund Project 16211220, Russell Lee and Mohammad Hajiesmaili's research supported by NSF CAREER 2045641, CNS 2106299, CNS 2102963, CNS 1908298. Adam Wierman's 's research is funded by NSF CNS-21 and NGSDI-2105648, We also acknowledge the support received from the Resnick Institute and the Center for Autonomous Systems and Technologies at Caltech.
References
[1] S. Angelopoulos, C. Dürr, S. Jin, S. Kamali, and M. Renault. Online computation with untrusted advice. In Proc. of Innovations in Theoretical Computer Science Conference (ITCS), 2020.
[2] A. Antoniadis, C. Coester, M. Elias, A. Polak, and B. Simon. Online metric algorithms with untrusted predictions. In International Conference on Machine Learning, pages 345-355.
PMLR, 2020.
[3] A. Antoniadis, T. Gouleakis, P. Kleer, and P. Kolev. Secretary and online matching problems with machine learned advice. In 34th Conference on Neural Information Processing Systems, 2020.
[4] E. Bamas, A. Maggiori, and O. Svensson. The primal-dual method for learning augmented algorithms. Advances Neural Information Processing Systems, 33, 2020.
[5] A. Blum, Sandholm, and M. Zinkevich. Online algorithms for market clearing. Journal of the ACM (JACM), 53(5):845-879, 2006.
[6] J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld. Recent developments in prophet inequalities. ACM SIGecom Exchanges, 17(1):61-70, 2019.
[7] R. Yaniv. Competitive solutions for online financial problems. ACM Computing Surveys (CSUR), 30(1):28 69, 1998.
[8] R. Yaniv,, A. Fiat, R. M. Karp, and G. Turpin. Optimal search and one-way trading online algorithms. Algorithmica, 30(1):001-13,, 2001.
[9] Y. Emek, P. Fraigniaud, A. Korman, and A. Rosén. Online computation with advice. Theoretical Computer Science, 412(24))242-2656, 2011.
[10] S. Lattanzi, T. Lavastida, B. Moseley, and S. Vassilvitskii. Online scheduling via learned weights. In Proceedings the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1859-1877. SIAM, 2020.
[11] R. Lee, J. Maghakian, M. Hajiesmaili, J. Li, R. Sitaraman, and Z. Liu. Online peak-aware energy scheduling with untrusted advice. In Proceedings of the Twelfth ACM International Conference on Future Energy Systems (ACM eEnergy), 2021.
[12] R. Lee, Y. Zhou, L. Yang, M. Hajiesmaili, and R. Sitaraman. Competitive bidding strategies for online linear optimization with inventory management constraints. Performance Evaluation, 2021.
[13] B. Li and S. C. Hoi. Online portfolio selection: A survey. ACM Computing Surveys (CSUR), 46(3):1-36 2014.
[14] J. Lorenz, K. Panagiotou, and A. Steger. Optimal algorithms for k-search with application in option pricing. Algorithmicca, 55(2):311-328, 2009.
[15] T. Lykouris and Vassilvtiskü.. Competitive caching with machine learned advice. In Interna- tional Conference on Machine Learning, pages 3296-3305. PMLR, 2018.
[16] O.-A. Maillard and R. Munos. Online learning in adversarial lipschitz environments. Joint european conference on machine learning and knowledge discovery in databases, pages 305- 320, 2010.
11

---

[17] D. S. Mitrinovic, J. Pecaric, and A. M. Fink. Inequalities involving functions and their integrals and derivatives, volume 53, Springer Science & Business Media, 1991.
[18] E. Mohr, I. Ahmad, and G. Schmidt. Online algorithms for conversion problems: a survey. Surveys in Operations Research and Management Science, 19(2):87-004, 2014.
[19] M. Purohit, Z. Svitkina, and R. Kumar. Improving online algorithms via ML predictions. Advances in Neural Information Processing Systems, 31:9661-999 16700, 2018.
[20] Schroeder and Kacem. Optimal solutions for online conversion problems with interrelated
prices. Operational Research, pages 1-26, 2020.
[21] B. Sun, A. Zeynali. T. Li, M. Hajiesmaili, A. Wierman, and D. H. Tsang. Competitive algorithms for the online multiple knapsack problem with application to electric vehicle charging. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(3):1 1-3), 2020.
[22] A. Wei and Zhang. Optimal robustness-consiitengg trade-off' for bearnin--augmented online algorithms. Advances in Neural Information Processing Systems, 33, 2020.
[23] L. Yang, M. H. Hajiesmaili, R. Sitaraman, A. Wierman, E. Mallada, and W. S. Wong. Online linear optimization with inventory management constraints. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1-29, 2020.
[24] A. Zeynali, B. Sun, M. Hajiesmaili, and Wierman. Data-driven competitive algorithms for online knapsack and set cover. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10833-10841, 2021.
[25] Z. Zhang, Z. Li, and Wu. Optimal posted prices for online cloud resource allocation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(1):1-26, 2017.
[26] Y. Zhou, D. Chakrabarty, and R. Lukose. Budget constrained bidding in keyword auctions and online knapsack problems. In International Workshop on Internet and Network Economics, pages 566-576. Springer, 2008.
12


Reviews:
[{"review_id": "rImFriTJ5xm", "reviewer": "Reviewer_BJtR", "summary": "This paper provides learning-augmented algorithms for online conversion problems. Suppose you have $1 and want to convert it to a different currency where the exchange rate varies over time. The ideal would be to do the conversion when the exchange is at its highest, but at any time, we do not know if the current exchange rate is in fact the highest (similar to secretary problems). The paper considers both the integer and fractional versions of this problem, i.e., when the conversion of the entire one unit has to be done all at once or when it can be done in fractions multiple times adding up to one. Algorithms are presented for these problems if a prediction of the maximum value is given in advance, the goal being to achieve the optimal tradeoff between consistency and robustness. Matching lower bounds on this tradeoff are also presented. Finally, an empirical evaluation of the algorithms are carried out for the application of trading dollars for bitcoins.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "There are three main contributions of the technical parts in the paper. The first is a general characterization of the threshold function in the online algorithm, and the resulting tradeoff between robustness and consistency (Theorem 3.4). [Lemma 3.3 can be considered to be a restatement of the definitions of consistency and robustness.] The second contribution is to apply this general characterization to the two conversion problems: integral and fractional, and derive corresponding online threshold-based algorithms. The third is to use the characterization to achieve lower bounds on the tradeoff. Of these, the second and third contributions are actually pretty easy if considered directly (without the characterization). For instance, the algorithm for setting a threshold that achieves $\\eta$ consistency and $\\gamma$ robustness in the integral conversion case is based on the following simple observations: (a) do not set a threshold about $U / \\eta = L \\gamma$ since it is sufficient to ensure $\\eta$ consistency for $P > U / \\eta$, (b) do not set a threshold below $L \\gamma$ since it is enough to ensure $\\gamma$ robustness by selling at the final price even if that is just $L$, (c) between these extremes, use a convex combination of $L \\gamma$ and $P / \\eta$ to trade off between consistency and robustness. The fractional case is a little more complicated because the threshold is now a function, but it also follows by applying a similar logic and using the existing online algorithm for this problem (without prediction). Similarly, the lower bounds can be derived by creating instances that represent the limiting cases of the observations given above. So, it is not clear if the complicated framework established by Theorem 3.4 is required for the subsequent theorems for the actual problems. In addition to this lack of technical novelty and clarity of purpose, the problem itself is only of modest importance, and one that is closely related to other problems like secretary problems and prophet inequalities that have been previously considered in the prediction model. (In fact, the authors should add a clear comparison of their results to the existing ones for these problems given the close resemblance.) \n\nThe response to the authors to my initial review was adequate and addressed some of the many shortcomings that I had outlined. I have increased my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No potential negative societal impact that I can think of.\n\nThe authors provide some limitations of their results, particularly in terms of not proving any results that establish graceful degradation, and not allowing the robustness parameter to be chosen online. These are indeed limitations, but the shortcomings mentioned above in terms of lack of technical novelty are more glaring.", "review_text": "", "extra_scores": {"ethical_concerns": "None that I can think of.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "gu8wmbRTkpw", "reviewer": "Reviewer_q5Tj", "summary": "The paper considers learning augmented algorithms for the integral and fractional online conversion problem. One has one unit of some asset that he wishes to convert into another asset. In each step $n = 1,\\dots N$  the conversion rate $v_n$ becomes known to the algorithm, and the algorithm decides what amount $x_n$ (possibly $x_n=0$) of the asset should be converted in this step to obtain $x_n v_n$ of the new asset. Summing over all steps, the algorithm obtains in total $\\sum_{n\\in[N]}x_nv_n$ many units of the new assets, and naturally the objective is to maximise this. In the integer version the whole asset must be converted in only one step, whereas in the fractional version the asset can be converted piece by piece over different steps.\n\nThe paper designs a learning augmented online algorithm that is Pareto optimal between robustness and consistency.\n\nExperimental results are presented where the flunctuation of the bitcoin exchange rate over the last five years is used as input data. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The algorithm developed in the paper is a so-called online threshold-based algorithm. In particular every time a conversion rate is revealed, the algorithm calculates (using a simple rule) the amount of asset that is to be traded in this step based on the amount that has already been traded, the current conversion rate and a specific threshold function. The challenge lies in defining this threshold function. For the integer version of the problem this function is just a constant thershold (in turn the algorithm will trade on the first step on which the conversion rate is higher than that threshold). For the fractional version of the problem the function is a bit more involved and is built upon the optimal competitive ratio.\n\nThe algorithm designed in the paper is elegant and the authors put quite a lot of effort into conveying the intuition behind their ideas. They also provide tight lower bounds implying that their algorithm achieves Pareto optimal tradeoffs between robustness and consistency.\n\nParsing the experimental results was quite difficult, and despite going over the section several times, I still cannot say what the actual performance of the algorithms is on these experiments. I would recommend to at least give more descriptive names to the variables and to the plot labels and to extend the captions.\n\nOverall, the paper is presenting interesting and -- to the best of my knowledge -- original results. I did not carefully check all the calculations but at least at an intuitive level it all checks out. \n\nMinor comments to the authors:\n- your use of $\\epsilon$ is a bit confusing. In general $\\epsilon$ is used for arbitrarily small values, whereas you use it for the prediction error, which is commonly denoted with $\\eta$ and can be quite large in the worst case.\n196: neighbour*hood*", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no limitations, no social impact I can think of.", "review_text": "", "extra_scores": {"ethical_concerns": "no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Lj7HCRxDeGd", "reviewer": "Reviewer_U9U6", "summary": "The paper considers the following conversion problem: You start with a good (e.g. 1 bitcoin) that you can convert into another good (e.g. dollars) at a conversion rate that changes over time. Every day you have the opportunity to convert part of the good at the day's rate. On the last day, you have to convert any remaining amount of the original good that you might still own. The goal is to maximize the final amount owned. It is assumed that upper and lower bounds U and L on the conversion rate are known that hold throughout the time horizon.\n\nTwo versions of this problem are considered: 1-max search, where the good is unsplittable, i.e., one can only convert it as a whole. And a smoother version where arbitrary fractions can be converted, called one-way trading. It seems to me that one-way trading is equivalent to the randomized version of 1-max search.\n\nLet $\\theta=U/L$ be the ratio between the upper and lower bounds. In the classical online setting, for 1-max search it is known that the best competitive ratio is $\\sqrt{\\theta}$, and for one-way trading it is $1+W((\\theta-1)/e)$, where W is the Lambert function.\n\nThis paper considers this problem through the learning-augmented lens: The algorithm receives as additional input at time 0 a prediction of the maximal conversion rate that will be observed. The paper gives algorithms for both problems and proves via upper and lower bounds that they achieve the pareto-optimal trade-off between consistency (i.e., the competitive ratio when the prediction is correct) and robustness (i.e., the competitive ratio in the worst case). For 1-max trading, the result is that if the consistency is a multiplicative factor c better than the classical competitive ratio $\\sqrt{\\theta}$, then the robustness is a factor c worse than $\\sqrt{\\theta}$. The result for one-way trading is more difficult to express and I have no clear intuition of the trade-off. The paper also includes a brief experimental evaluation.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Learning-augmented online algorithms have been a very active research area in recent years, and this paper finds optimal bounds for the conversion problem in this setting, which was not analyzed in this setting before.\n\nThe paper shows that some naive algorithms fail, and the constructed algorithms are non-trivial. There is a chance that the techniques in this paper could also be used to derive more fine-grained results for conversion problems, i.e., to establish bounds that show how fast the competitive ratio degrades as the prediction error increases. The authors also say that their lower bound technique could be useful for other problems, though to me it would seem that the main steps for the lower bound is to identify an appropriate family of worst-case inputs (which is a very simple one here), and turning it into a lower bound proof is then usually a matter of calculation (which is non-trivial here though). The authors emphasize that tight lower bounds on the pareto-optimal trade-off of consistency and robustness were  previously known only for the ski rental problem. While true (I think), one reason is also that for many problems it is simply not necessary to make such a trade-off: E.g. for caching, MTS, load balancing etc one can use predictions to improve performance with good predictions without having to make any (or only insignificant) sacrifices in the worst-case performance. This is different for the conversion problem, where bad predictions come at a higher cost.\n\nI am a bit unsure about how convincing I find the overall motivation for the setting of this problem: Since even in the classical online setting it is assumed already that upper and lower bounds U and L on the conversion rate are known, essentially these are already predictions, so in some sense one could say this paper adds a third prediction to a setting where there were already two.\n\nIn terms of writing, I found this paper relatively hard to read, and I think much of it could be improved by changing the order in which things are presented. For example, the text at the beginning of section 3.2 is hard to understand for someone that has not read Definition 3.2, Lemma 3.3 and Theorem 3.4 yet. The intuition for the algorithms is also hard to appreciate because it is only given much later than when the algorithms were defined. For example, reading the definition of the six constants in (9) and (10) without any intuition is not particularly enjoyable. Also, no real intuition for Theorem 3.4 is given.\n\nIn the experimental setup, some things are unclear to me: How do you choose U and L in the experiments? Are the experiments for the 1-max search algorithm or the one-way trading algorithm? Why not both? Is the adjustment of the error level between 0 and 1 for Figure 3a or also the other figures, and do you actually use 0 somewhere or just 0.6 and 1? For these reasons, I find it hard to evaluate the experimental results.\n\nOverall, I think this is a borderline paper.\n\nAdditional comments:\n- Lines 50-53: The answer to the question *whether* there exists a pareto-optimal algorithm seems to be trivially Yes. The set of pairs of achievable consistency and robustness is well-defined (even if one does not know the set) so it has a well-defined pareto-frontier. The question is rather *what* those pareto-optimal algorithms are and where the pareto-frontier lies.\n- Lines 139-143: The proof of Prop 3.1 only shows an upper bound, but in your discussion you treat it as a lower bound. I agree though that the upper bound in Prop 3.1 seems to be tight.\n- Theorem 3.4: The three \"if\"s in the three cases confused me (where is the \"then\") and might just be deleted.\n- In eq (12) you seem to be doing several steps at once and it would be helpful to break it down.\n- Citation [12] seems to be missing the title of the article\n\n\nCOMMENTS AFTER AUTHORS' RESPONSE:\n\nA large part of the response emphasizes the importance of obtaining rigorous lower bounds. I agree and my original review did not say otherwise.\n\nHowever, the paper is suggesting that the reason why robustness-consistency lower bounds were rarely shown in prior work is due to the difficulty of showing them. While there may exist such problems, I would argue the opposite that the main reason they were not shown/mentioned in most previous works is that often they are simply trivial: E.g. for any MTS (caching and other problems), there is an algorithm with consistency $1+\\epsilon$ and robustness $c+\\epsilon$, where $c$ is the best competitive ratio without predictions, so the pareto frontier is the single point $(c,1)$ (e.g. for caching, $c=\\Theta(\\log k)$) and the lower bound follows trivially from the lower bound of the setting without predictions. Unlike for those other problems, where predictions can be incorporated without significant sacrifices in worst-case performance, this is not possible for the conversion problem and thus it is good they provided the lower bound, but I'm not expecting major impact from this on other problems.\n\nThe interpretation of L and U as stop-loss and take-profit prices makes sense. In the experiments the authors apparently did use L and U as additional \"predictions\" though by setting them to the minimal/maximal conversion rates that will be observed, which is information that would not be available to an actual algoritihm.\n\nOverall, the paper still seems rather borderline to me (for NeurIPS standards).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "4ZO9xKKckoy", "reviewer": "Reviewer_zNZb", "summary": "The paper considers learning-augmented algorithms for the online conversion problem. In the online conversion problem, a trader starts with a unit of money in the source currency. Given a sequence of conversion rates v_i that arrive online, the online conversion problem is to determine what fraction of their money to convert using the current rate so that the total amount of money in the target currency is maximized. The paper considers this problem in both the integral and fractional settings. The primary focus of the paper is to design online algorithms for the online conversion problem when provided with a prediction for the maximum conversion rate that achieves the optimal tradeoff between robustness (competitive ratio) and consistency (competitive ratio when prediction is correct).", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper considers the online conversion problem and designs a pareto optimal family of algorithms that utilizes predictions about the maximum conversion rate.\n\nThe paper first presents a general family of online threshold algorithms (OTA) for conversion problems. I’m a bit unsure about the novelty of this section since OTA’s have been known for online knapsack and one-way trading (essentially fractional online knapsack) from prior work. Even the general framework described here also appears in [15] almost verbatim (see algorithm 1 there). The paper also presents an interesting notion of “generalized competitive ratio” that gives a more fine-grained view into the worst-case behavior of the algorithm on different types of instances.\n\nOverall, the paper is interesting and designs a non-trivial learning-augmented algorithm for a well-studied online problem. Technically, however, the paper feels a bit lacking and in particular adds limited novelty over prior work in [15], [18], [*]\n\nStrengths: It’s great that the paper also demonstrates tight lower bounds and shows that the proposed algorithm is pareto-optimal.\n\nOther comments:\n- The connection with prior work needs to be established better. For instance, the online conversion problem defined here is the fractional version of the online knapsack problem in [18].\n- Line 46: “metrical task systems”\n- Some discussion of how the predicted value can be learned and why the absolute value of the prediction and the actual max conversion rate is the appropriate notion of error in this context would be useful.\n- The references are out-of-date. For instance, [3], [11] have appeared at NeurIPS 2020 and ICML 2018 respectively.\n\n[*] Data-driven Competitive Algorithms for Online Knapsack and Set Cover. Ali Zeynali, Bo Sun,\nMohammad Hajiesmaili, Adam Wierman. AAAI 2021.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides algorithms augmented machine-learned predictions for online conversion problems. The goal is to improve the competitive ratio when predictions are accurate ("consistency"), while also guaranteeing a worst-case competitive ratio regardless of the prediction quality ("robustness"). The authors show their algorithms achieve the Pareto-optimal trade-off of consistency and robustness.

Most reviewers found the paper interesting, original, and having sufficient contribution for acceptance to the conference. They also appreciated elegant design of the algorithms and their formal analysis, and tight lower bounds on the Pareto-optimal trade-off. One of the reviewers felt the paper brings a limited novelty over prior work.

Most of the reviewers raised issues related to the clarity of the presentation. I hope the authors will take into account all these comments to improve the final version of the manuscript.
Decision: Accept (Poster)