Summary
This paper is about the classic Online List Labeling problem in the recent model of algorithms with predictions (a.k.a. learning-augmented algorithms).
In this problem n orderable items (say, integers) arrive over time. We need to keep them in the sorted order in an array of size c*n, for some constant c. When the i-th item arrives, we know its relative ordering only with respect to the i-1 items that arrived before, so we do not know where to put it, and we might need to reinsert it later at a different location (in order to have space for future items while maintaining the sorted order). Our goal is to minimize the number of such reinsertions.
There is already known a deterministic data structure with amortized cost O(log^2 n) per insert, and a randomized one with cost O(log^3/2 n).
In this paper the authors propose a data structure that together with each new item receives a prediction on what would be the final rank of that item among all n items.
The data structure uses internally as a black-box a classic (prediction-less) data structure for the problem. Denoting by f(n) the cost of this internal black-box data structure – so, f(n) = O(log^2 n) if we want a deterministic solution, and f(n) = O(log^3/2 n) if we are fine with a randomized one – and assuming all predicted ranks are within eta from the true ranks, the amortized cost of the new algorithm is O(f(eta)). Moreover, if prediction errors are distributed according to a Gaussian distribution with mean mu and variance var, the cost is O(f((mu + var)^2)).
The main idea of the data structure is to maintain a tree-like structure over the inserted items, and delegate maintaining items in non-overlapping subtrees of different sizes to instances of a classic data structure for the problem. Locations of items in the tree are guided by their predicted ranks. If a data structure corresponding to a subtree becomes overfull because of prediction errors, it gets merged with neighboring subtrees. This general idea was already present in the literature around the problem, but the details of implementation and analysis are very novel.
The authors also provide results of some simple experiments. What is nice (and always present in learning-augmented literature) is that the predictions are actually learned from training data, so the experiments can be considered end-to-end. The cost improvements observed over classic data structures are roughly 50%.
Strengths
1) The main algorithm is nontrivial, yet simple and with a clearly visible main idea.
2) I like the additional analysis of the algorithm's performance under prediction errors coming from a Gaussian distribution (on top of the more standard analysis in terms of the maximum prediction error).
3) The algorithm uses existing classic data structures in a black-box manner, so it should be easy to implement and can leverage already optimized implementations of these data structures.
4) The authors provide a matching lower bound (albeit only for deterministic algorithms).
5) The paper is well written and easy to follow.
Simply speaking, it is one of the most interesting recent papers that I have read in this area.
Weaknesses
1) The studied problem seems relevant in practice, but I am not sure how important it really is – however, even if it is not, I find the paper sufficiently appealing on purely theoretical grounds to merit acceptance.
2) The experiments are of a proof-of-concept style – e.g., datasets are adapted from benchmarks for other problems that have not much to do with this one – but it is a common thing for papers in this area.
Questions
Would it be feasible to prove bounds in terms of average L1 prediction error per item, instead of L_inf error? In other words, is it really the case that only a few items with terrible predictions can ruin performance of the whole data structure?
I'd be very interested in seeing results of similar experiments but done in an online learning, rather than batch learning, fashion. That is, using all the data as test data, and predicting rank of item i based on its relative rank among the previous i-1 items (possibly with the linear interpolation trick that you employed and some learning-with-experts algorithm telling whether to use the trick or not).
The claim in line 37 (that there are no earlier works that analyze effect of errors on learning-augmented data structures) seems not very accurate – see, e.g., the section on robustness guarantees in [12]. Similarly, a similar claim in lines 403–404 seems unjustified.
Minor remarks:
Line 54: "moves O(log^2 n) elements" -> "moves O(log^2 n) elements per insert"
Line 56: "a \Omega" -> "an \Omega"
Line 67: "a LLA" -> "an LLA"
Line 68: "worst case" – if the bounds are only amortized, this is misleading
Lines 146–150: you mention the randomized result very late, I think it should be mentioned already in line 57, where you talk about the deterministic result.
Line 72: "would ideal" -> "would be ideal"
Line 96: the footnote mark's location is unfortunate, it reads "C squared"
Line 194: "(PMA)[4,30]" -> "(PMA) [4,30]"
Line 220: it would be nice to mention that such idea of a tree-like data structure already appears in the classic PMA
Line 243: "i_p=\ell" -> "i_s=\ell"
Line 329: "that inserts n items" -> "that, for any n, inserts n items"
Line 515 in the full version: "lemma" -> "theorem"
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
There are only some minor limitations to this work:
1) The lower bound holds only against deterministic algorithms.
2) The performance guarantees are using the L_infty error measure, so it is not clear how the algorithm behaves when there is one outlier item with huge error but all other items are predicted almost correctly. The natural distribution analysis gives some hints that the performance of the algorithm should be good in such a case, but there is no formal proof.
3) There are only pretty basic proof-of-concept experiments.