Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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.) 

The 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.
limitations_and_societal_impact: No potential negative societal impact that I can think of.

The 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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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).
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.

The 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.

Overall, 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], [*]

Strengths: It’s great that the paper also demonstrates tight lower bounds and shows that the proposed algorithm is pareto-optimal.

Other comments:
- 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].
- Line 46: “metrical task systems”
- 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.
- The references are out-of-date. For instance, [3], [11] have appeared at NeurIPS 2020 and ICML 2018 respectively.

[*] Data-driven Competitive Algorithms for Online Knapsack and Set Cover. Ali Zeynali, Bo Sun,
Mohammad Hajiesmaili, Adam Wierman. AAAI 2021.

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.

Two 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.

Let $\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.

This 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.
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.

The 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.

I 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.

In 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.

In 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.

Overall, I think this is a borderline paper.

Additional comments:
- 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.
- 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.
- Theorem 3.4: The three "if"s in the three cases confused me (where is the "then") and might just be deleted.
- In eq (12) you seem to be doing several steps at once and it would be helpful to break it down.
- Citation [12] seems to be missing the title of the article


COMMENTS AFTER AUTHORS' RESPONSE:

A large part of the response emphasizes the importance of obtaining rigorous lower bounds. I agree and my original review did not say otherwise.

However, 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.

The 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.

Overall, the paper still seems rather borderline to me (for NeurIPS standards).
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

The paper designs a learning augmented online algorithm that is Pareto optimal between robustness and consistency.

Experimental results are presented where the flunctuation of the bitcoin exchange rate over the last five years is used as input data. 
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.

The 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.

Parsing 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.

Overall, 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. 

Minor comments to the authors:
- 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.
196: neighbour*hood*
limitations_and_societal_impact: no limitations, no social impact I can think of.
review_title: null

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)