Sorting with Predictions
Authors: Xingjian Bai
Christian Coester
Venue: NeurIPS 2023 poster (2023)
Keywords: sorting
learning-augmented algorithms
algorithms with predictions
adaptive sorting
TL;DR: We explore sorting in the algorithms-with-predictions setting, and design algorithms with asymptotically optimal comparison complexity.

Abstract: We explore the fundamental problem of sorting through the lens of learning-augmented algorithms, where algorithms can leverage possibly erroneous predictions to improve their efficiency. We consider two different settings: In the first setting, each item is provided a prediction of its position in the sorted list. In the second setting, we assume there is a ``quick-and-dirty'' way of comparing items, in addition to slow-and-exact comparisons. For both settings, we design new and simple algorithms using only $O(\sum_i \log \eta_i)$ exact comparisons, where $\eta_i$ is a suitably defined prediction error for the $i$th element. In particular, as the quality of predictions deteriorates, the number of comparisons degrades smoothly from $O(n)$ to $O(n\log n)$. We prove that this comparison complexity is theoretically optimal with respect to the examined error measures. An experimental evaluation against existing adaptive and non-adaptive sorting algorithms demonstrates the potential of applying learning-augmented algorithms in sorting tasks.

Sorting with Predictions
Xingjian Bai Department of Computer Science University of Oxford, UK xingjian. bai@sjc. c. ox ac.uk
Christian Coester
Department Computer Science
University of Oxford, UK christian wwwsterdss.cc................... ox ac
Abstract
We explore the fundamental problem of sorting through the lens of learning- augmented algorithms, where algorithms can leverage possibly erroneous pre- dictions to improve their efficiency. We consider two different settings: In the first setting, each item is provided a prediction of its position in the sorted list. In the second setting, we assume there "quick-and-dirty" way of comparing items, in addition to slow-and-exact comparisons. For both settings, we design new and simple algorithms using only O log 17:) exact comparisons, where n a suitably defined prediction eπror for the ith element. In particular, as the quality of predictions deteriorates, the number of comparisons degrades smoothly from O(n) to OO log n.). We prove that this comparison complexity is theoretically optimal with respect to the examined error measures. An experimental evaluation against existing adaptive and non-adaptive sorting algorithms demonstrates the potential of applying sarming-augment algorithms in sorting tasks.
Introduction
Sorting is of the most basic algorithmic problems, commonly featured as of the initial topics in computer science education, and with a vast array of applications spanning various domains. In recent years, the emerging field of algorithms with predictions (Lykouris and Vassilvitskii 2021 Mitzenmacher and Vissilvitskii 2022), also known as up new possibilities for algorithmic improvement, where algorithms aim leverage predictions (possibly generated through machine learning. or otherwise) to improve their performance. However, the classical sorting problem with predictions. along with the discussion of different types of predictors for sorting, appears to have been largely overlooked by this recent movement. This paper explores the problem of sorting through the lens of algorithms with predictions in two settings, aiming to overcome the classical ((n log n.) barrier with the aid of various types of predictors.
algorithms, has opened
The first setting involves each item having prediction of its position in the sorted list. This type of predictor is commonly found in real-world scenarios. For instance, empirical estimations of element distribution can generate positional predictions. Another example that fixed set of items has their ranking evolve over time, with minor changes at each timestep. Here, an outdated ranking can serve as natural prediction for the current ranking. As re-evaluating the true relation between items can be costly, the provided positional predictions offer useful information. The positional prediction setting closely related to adaptive sorting of inputs with existing presortedness (Estivill- Casttro and Wood 1992). but we consider different measures of eтror on the predictor, resulting in algorithms with more fine-grained complexity.
In the second setting, a "dirty" comparison function is provided to assist sorting. In biological experiments, for instance, some "indicating factors" might be used approximately compare two molecules or drugs. Despite potential errors due to the oversight of minor factors, these comparisons can still offer preliminary insights into the properties of the subjects. More broadly, in experimental science, researchers often carry out costly experiments to compare subject behaviours. By utilizing a
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

proficient sorting algorithm that capitalizes on dirty comparisons, the need for costly experiments can be reduced and substituted by less expensive, albeit noisier, experiments.
We propose sorting algorithms to leverage either type of predictor. In the positional prediction setting, design two deterministic algorithms with different complexity bounds, while in the dirty comparisons setting, we develop a randomized algorithm. In all settings, we provide bounds of the form Di log(7% + 2)) on the number of exact comparisons, for different notions of element-wise prediction errors E [0, va.. In particular, all three proposed algorithms only require ((z) exact comparisons if predictions are accurate (consistency), never use more than O( log n) comparison regardless of prediction quality (robustness), and their performance degrades slowly as a function of prediction error (smoothness). Moreover, we show that all algorithms have optimal comparison complexity with respect to the eπтor measures examined.
Finally, through experiments both synthetic and real-world data, we evaluate the proposed algo- rithms against existing (adaptive and non-adaptive) algorithms. Results demonstrate their superiority over the baselines in multiple scenarios.
1.1 Preliminaries
Let A (a.,.... a.,) be an array of items, equipped with strict linear order <. Let p: [n]] + [n]] be the permutation that maps each index i to the position of a; in the sorted list; that is, (1))(1) < (2) < < (p)1(n)- We consider two settings of sorting with predictions.
Sorting with Positional Predictions. In sorting with positional predictions, the algorithm receives for each item a; prediction p(i) its position p(i) in the sorted list. We allow ý be any function [n] + [n]] which need not be permutation (i.e., it is possible that pii) - p(j) for some + j).
Positional predictions can be generated by models that roughly sort the items, e.g. focusing on major factors while neglecting minor ones. Or they can stem from past item rankings, while the properties of the items evolve over time. In such cases, the objective is to obtain the latest ranking of items.
The error of a positional prediction can be naturally quantified by the displacement of each element's prediction; that is, the absolute difference of the predicted ranking and the true ranking. We define the displacement error of item 0g as
= 1 (p(p) p())
The following notion of one-sided error provides an alternative perspective to evaluate the complexity of algorithms with positional predictions. We denote the left-error and right-error of item a, as
n/ == Kij E [m]: p(J) S 5(1) A p(j) > p(t) Tf ij [m]: P() p(i) A p() p(())-
In certain contexts, it may be impossible to obtain a predictor with small displacement error, but possible obtain one with small one-sided error. By developing algorithms for this setting, expand the space of problems where sorting algorithms with predictions can be applied.
Sorting with Dirty and Clean Comparisons. The other setting we consider involves predictor that estimates which of two elements is larger without conducting a proper comparison, providing a faster but possibly inaccurate result. This type of predictor is applicable in scenarios where exact comparisons are costly but a rough estimate the comparison outcome can be obtained more easily.
Formally, in sorting with dirty comparisons, the algorithm has access to complete, asymmetric relation on the items, while still also having access to the exact comparisons <. That is, for any two distinct items a, and aj, either 2 aj az < az We think of & as an unreliable, but much faster to evaluate prediction of <. We also refer to the (fast) comparisons according to & as dirty whereas the (slow) comparisons according to are clean. We emphasize that the relation 2 need not be transitive, so it is not necessarily linear order. Instead, 2 induces tournament graph on the items of A, containing a directed edge (a,,a)) if and only if a; 2 aj, and in many applications, we expect this graph to have cycles.
We denote by 7i the number of incorrect dirty comparisons involving a, that is,
7 ;= |Íj [n]: (as <a)) # (ai 2 a,))].
2

---

1.2
Main Results
Our main result for the dirty comparison setting is given by the following theorem:
Theorem 1.1. Augmented with dirty comparisons, there a randomized algorithm that sorts an array within (n log n) running time, (n log n)) queries to dirty comparisons, and O (-i=1 log (7/ + 2))
clean comparisons in expectation.
By the classical lower bound, the total number of dirty + clean comparisons must be at least S2(n log n) regardless of prediction quality, but for sufficiently good predictions the theorem allows us to replace most clean comparisons with dirty ones. The case where dirty comparisons are probabilistic is discussed in Section B
The following theorem generalizes the previous one to the case that there are ks different dirty comparison operators:
Theorem 1.2. Augmented with S 20(n/ logn) dirty comparison predictors, where the error of the pth predictor is denoted by Tf,, there is a randomized algorithm that sorts an array with at most (min,, Di= log(1) + 2)) clean comparisons.
In other words, the number of clean comparisons is as good if we knew in advance which of the As predictors is best. The bound on & is almost tight, since already le 2 2n log would mean there could be one predictor for each of the n! possible sorting outcomes, which would render them useless. The proof of Theorem 1.2 is given in Appendix B.2
The next two theorems capture our algorithms for the positional prediction setting:
Theorem 1.3, Augmented with positional predictor, there is deterministic algorithm that sorts an array within (Ei=1 log (nt² + +2) running time and comparisons.
Theorem 1.4. Augmented with positional predictor, there is deterministic algorithm that sorts an array within O (Σ log (min (n's TT + 2)) comparisons.
We remark that there exist instances where the bound of Theorem is stronger than that of Theorem 1.4/and vice versa D
The following theorem, proved in Appendix E shows tightness of the aforementioned upper bounds.
Theorem 1.5. Augmented with dirty comparisons, sorting algorithm uses (-i= log (1/ + 2)) clean comparisons. Augmented with a positional predictor, no sorting algorithm uses Eh log (1,² + 2)) or (E= log(min {n)- 1T + 2)) comparisons.
Bounds in Terms of Global Error. One may wonder how the above bounds translate to a global error measure such the number of item pairs where the larger one is incorrectly predicted to be no larger than the smaller one. Writing D for this error measure, in the dirty comparison setting simply have D= 2/2 E, The and in the positional prediction setting D 2 >, n by (Rohatgi 2020 Lemma 11). Thus, concavity of logarithm and Jensen's ' inequality yield an upper bound of log 2 + 2)) for both settings. This bound is tight" as a function of D and corresponds the optimal complexity of adaptive sorting as a function of the number of inversions (Mannila 1985).
However, guarantees in terms of element- wise inequality is not tight, i.c., when the 77 are non-uniform. Furthermore, it is reasonable to expect predictors exhibit varying levels of error for different items, especially when the error originates from element-wise noise.
strictly stronger whenever Jensen's
1.3 Related Works
Algorithms with Predictions. Our study aligns with the broader field of Baaming--uugment algorithms, also known as algorithms with predictions. The majority of research has focused on
'If predictions are correct except that the positions of the v smallest and v largest items are swapped,
then E, log(n,, + 2) = On)) but E, loggmmi (n). mi } 2)) ) = ((n log n). Conversely, if p(t) = p(1) + vn mod n, then Σ, log inf + 2) O log n). )), but Σ, logg ( nf + 2)) ((n).
'Indeed, our proof of Theorem 1.5 constructs a family of instances where each 1) is bounded by the same
quantity, Jensen's 's inequality is tight for these instances.
3

---

classical online problems such caching Lykouris and Vassilvitskii
2021 Rohatgi 2020 Wei
2020
Bansal et al. 2022). , rent-or-buy problems (Purohit et al. 2018
Gollapudi and Panigrahi
2019
Angelopoulos et al. 2020 Wang et al. 2020 Antoniadis et al.
[021]
scheduling (Purohit et al.
2018
Lattanzi et al. |2020] Mitzenmacher] 2020 Azar et al.] |021
2022
Lindermayr and Megow
2022)
and many others. In comparison, research on
auggented algorithms to improve runnning
time for offline problems is relatively sparser, but examples include matching (Dinitz et al.
202
Sakaue and Oki, 2022), clustering (Ergun et al. 2022), and graph algorithms (Chen et al.
2022
Davies et al. (023). 3). Motivated by (Kraska et al. 2018), (Lykouris and Vassilvitskii 202 describes a
simple method to speed up binary search with predictions, which has been inspirational for our work.
algorithms have also been applied to data structures such as binary search trees
(Lin et al. 2022 Cao et al. (2023). and empirical works demonstrate the benefits of ML-augmentation
for index structures (Kraska et al.
2018) and database systems (Kraska et al. 2019). There has also
been increasing interest in settings where algorithms have access to multiple predictors (Gollapudi)
and Panigrahi| 2019] Wang et al. 2020. Bhaskara et al.] [2000] Almanza et al. 2021 Emek et al.
2021 Dinitz al., 2022 Anand et al. 2022 Antoniadis al. 2023).
Related to sorting. Lu et al. (2021) studied learning-augmented generalized sorting, a variant of sorting where some comparisons are allowed while others are forbidden. The predictions they consider are similar to our dirty comparisons. They proposed two algorithms with comparison complexities On log + w) and (nww), where w is the total number of incorrect dirty comparisons. In the classical mnon-generalized) setting with all comparisons allowed, only the second bound theoretically improves upon O(n n), but the dependence on the error is exponentially worse than for our algorithms; even with a single incorrect dirty comparison per item, the ((rw) bound becomes (n²), whereas ours is O(n). A recent work of Erlebach et al. (2023) studies sorting under explorable uncertainty with predictions, where initially only an interval around the value of each item known, the exact values can be queried, prediction of these values is given, and the goal is to minimize the number of queries needed to sort the list.
Deep Searning-Based Sorting, The thriving development of deep learning has inspired research into new sorting paradigms. A DeepMind study (Mankowitz et al. 2023) recast sorting single- player game, training agents to perform effectively, thus uncovering faster sorting routines for short sequences. Kristo et al. (2020) proposed a sorting algorithm that uses learning component to improve the empirical performance of sorting numerical values. Their algorithm tries to approximate the empirical CDF of the input by applying ML techniques to small subset of the input. This setting diverges from ours: If inputs are non-numeric (and no monotonous mapping to numbers is known), then one has rely on a comparison function, and the approach of Kristo al. (2020) would not be well-defined, whereas our algorithms can sort arbitrary data types.
Conversely, the input in (Kristo et al. 2020) is solely the item list, without any additional predictions. Note that predictions (or other assumptions) are necessary to beat the entropic 22 log lower bound.
Noisy Sorting. Noisy sorting contemplates scenarios where comparison results may be incorrect. This model is useful to simulate potential faults in large systems. Two noisy sorting settings have primarily been considered: In independent noisy setting, each query's result is independently flipped with probability E (0, ). Recently, Gu and Xu (2023) provided optimal bounds on the number of queries to sort n elements with high probability. Recurrent noisy setting (Braverman and Mossel 2008) further assumes any repeated comparisons will yield consistent results. Geissmann et al. (2019) present an optimal algorithm that guarantees On log n.) time, O(log n) maximum dislocation, and (n)) total dislocation with high probability. While the recurrent noisy setting is closely related to dirty comparisons, studies in that field focus primarily on approximate sorting; to the best of our knowledge, no exact sorting algorithms that use both dirty and clean comparisons have been studied.
Adaptive Sorting. Adaptive sorting algorithms leverage various types of existing order in the input, achieving better complexity for partially sorted data. Examples include TimSort (Peters! 2002). which is the standard sorting algorithm in a variety of programming languages, Cook- Kim division
'The theoretical guarantee of their algorithm is O(n²), although they observe much better empirical perfor- mance. Indeed, this makes sense for numerical inputs drawn from a sufficiently nice distribution, since then one extrapolate from small part of the input the rest.

---

(Cook and Kim 1980), and Powersort (Munro and Wild 2018), which recently replaced TimSort in Python's 's standard library. We refer the survey of Estivill--Cast and Wood (1992) for a broader overview. The concept of pre-sortedness is closely related to positional predictions; however, without the motivation from predictors, the complexity bound on adaptive sorting algorithms was often considered under error measures on the entire array, instead of on each element. In contrast, our error measure is element-wise, allowing algorithms with stronger complexity bounds.
Sorting with Dirty Comparisons
Given dirty predictor 2, our goal is to sort A with the least possible number of clean comparisons. Note that, if < is accurate, A can be sorted using only O(n) clean comparisons and O(n log n) dirty comparisons. This could be achieved, for example, by performing Merge Sort with dirty comparisons and then validating the result through clean comparisons between adjacent elements. This observation motivates consider that all O dirty comparisons are necessary, and we should devise an algorithm minimizing the number of both clean and dirty comparisons.
We propose randomized algorithm that sorts A with expected O log(2 + +.)) clean comparisons, expected (n log π.) dirty comparisons, and expected O log n) running time. The key idea consists of three parts: 1) Sequentially insert each element of A into a binary search tree, following random order; 2) Guide each insertion primarily with dirty comparisons, while verifying the correctness using minimal number of clean comparisons. 3) Correct the mistake induced by the dirty insertion, ensuring that the clean comparisons needed for correction is (log n)) in expectation.
We describe the algorithm in Section 2.1 and prove its performance guarantees in Section Appendix B we discuss extensions of the dirty comparison setting.
In
2.1 Algorithm
We now describe the sorting algorithm with dirty comparisons in detail (Algorithm D. B as an empty binary search tree (BST). For any vertex v, we denote by left(v) and right(v) its left and right children, and by root(B B) the root of B. Slightly abusing notation, we write u also for the item stored at vertex v. If any of these vertices is missing, the respective variable has value NIL.
We initialize
Algorithm 1: Sorting with dirty and clean comparisons
Input: A = (a1,..... (a.....,an) dirty comparator X, clean comparator < B empty binary tree
for i E in] in uniformly random order do
(1, + (-xc, root (B), oc) 1-1
while C. き NIL
b Dirty search
if a; 2 C. then (L++1; C441, C141) + (L,, (L,, else (L411, Co+1, R(+1) Ce+1, ) & (Ce, right(C),C,, P.)
(6|+1
C- Cr., where ts < is maximal s.t. Ly a, R while C # NIL do
Verification
10
Clean search
if < C then C left(C)
12
else C' <- (C)
13
Insert a; at
return inorder traversal of B
Within each iteration of the for-loop starting in line 2 we select one item a; of A uniformly randomly from the items that have not been processed yet. Then, we insert this item a; into B, while maintaining the invariant that B remains a BST with respect to clean comparisons <.
The first phase involves performing search for the insertion position using dirty comparisons <, keeping track of the search path. Here, denote by C2 the tth vertex this path, and by L, and R, the lower and upper
Inserting item a; into B requires three phases, as illustrated in Figure 2.
5

---

root
dirty search
step t
verification
clean search
X
failed verification
successful verification
a
step T
Figure 2.1: The insertion process in dirty comparison sorting.
bounds on items that be inserted the subtree rooted at C. without violating the BST property with respect to <. Correctness of the choice of L, and RG follows from the fact that B was a BST with respect to before the current insertion. This dirty procedure stops when the search path reaches NIL-leaf, regarded as the predicted position for a, insertion. However, since we used dirty comparisons trace the path, a, might violate one of the boundary conditions L; a, or a, Rg at some recursion step f. We call a recursion step valid for if T < < R4- Then, we enter the verification phase in line 2 We traverse the dirty search path in reverse order locate the last valid step t", A naive method to do this (which is sufficient for our asymptotic guarantees) is to repeatedly decrease by 1 until is valid; we discuss an alternate, more efficient method in Remark AA. which yields better constant factor.
The final phase involves performing a clean search starting from C.+ to determine the correct insertion position for ag After inserting into that position. B remains BST with respect to <. Once all items of A are inserted into B, we can obtain the sorted order through the inorder traversal of B.
2.2 Complexity Analysis
The idea show that the dirty search path has expected depth Olog nt). whereas the verification path and the clean search path only have expected depth O(log n:). Therefore, the algorithm only needs (log 2) dirty and (llog n;) clean comparisons for inserting each a;; Theorem 1.1 established consequently. The full proof is given in Appendix A
3 Sorting with Positional Predictions
In this section, we propose two algorithms that capable of leveraging positional predictions. The first one has complexity bounds in terms of the displacement error measure, and the second one has complexity bounds in terms of 1/' and v7",, the one-sided error measures. Each algorithm effective in some tasks, where the given prediction is accurate with respect to its corresponding error measure.
3.1 Displacement Sort
We present a sorting algorithm with positional prediction, whose comparison and time complexity rely solely the displacement error of the predictor. The algorithm is adapted from Local Insertion Sort (Mannila 1985), an adaptive sorting algorithm proven to be optimal for various measures of presortedness.
We use classic data structure called finger tree (Guibas et al. 1977). which is a balanced binary search tree (BBST) equipped with pointer ("finger") pointing towards the last inserted vertex. When a new value e is to be inserted, rather than searching for insertion position from the root, the insertion position is found by moving the finger from the last inserted vertex the suitable new position. By the balance property BBST, the insertion can be performed in Oloog d(u, u)) amortized time, where d( u,, v) is the number of vertices in the tree whose value lies in the closed interval from
Algorithm details the proposed method. We first bucket sort (in time ((n)) the items A based on their predicted positions, such that we may assume for all < j that p(i) S (()). Following the

---

rearranged order. items in A are sequentially inserted into an initially empty finger tree T. After all insertions, we obtain the exactly sorted array by an inorder traversal of T.
Algorithm 2: Sorting with complexity on 1//
Input: A= (a1..... an), prediction
BucketSori(A,, p);
Bucket Sort A according to p. so that p(1) S p(2) S ... S p(()
2 T < an empty one-finger tree;
for i mari=1..... 1,...,7 n do
L Insert 0, into T;
5 return nodes T in sorted order (via inorder traversal);
The full proof of run time and comparison complexity of Algorithm is in Appendix C
3.2 Double-Hoover Sort
Now we turn our focus to settings where one-sided errors are small. We first describe a simple algorithm with comparison complexity as a function either r' or or Following this, we introduce our algorithm Double-Hooved Sort, which has comparison complexity Both algorithms begin by bucket sorting A with respect to the positional prediction in ((n) time. Thus, may subsequently assume that A is rearranged such that Vi < j.p(t)= S p(j).
claimed in Theorem T.4
A First Approach. A left-sided sorting complexity of , log(2 + -f()) can be easily achieved using the standard technique
Maaning-auggeettn binary search, as described in (Lykouris and Vassilvitskii 2021 Mitzenmacher and Vassilvitskii] 2022). Specifically, sorted array L is maintained, and 01, Un are sequentially inserted into L. During each insertion, we perform a learning- augmented binary search starting from the rightmost position of L, taking (log -2) comparisons to find the correct insertion position. In total, O log(n) + 2)) comparisons are taken among all insertions. By replacing the array with an appropriate data structure (e.g.. a BBST with a finger that always returns to the rightmost element), one can achieve the same bound also for time complexity. reversed "right-sided" version of this algorithm achieves complexity O log(n) + 2)). By simultaneously running the left-sided and right-sided algorithms, one can achieve the complexity bound of O (min (E== log (2 + n/), Σn= log(2 + n7, H)). However, moving the min operator inside the summation requires more elaborate approach.
Houble-Hoover Sort. The basic idea is that, to utilize a similar insertion scheme to that employed in the one-sided algorithm, maintain two sorted structures L and R at the same time, and insert each item into one of them, depending on which operation is faster, hereby achieving a complexity bound of O(log(min()) of + 2)). Then, final sorted list is attained by merging L and R in linear time. However, a significant issue yet to be addressed is how to decide the insertion order of different items.
Consider two items 0n and 0g with u < (so p(u) S p(v) by Bucket Sort). In our algorithm, both are to be inserted into L. it is crucial that a, inserted prior to a,. Otherwise, the insertion complexity of a, could exceed the bound of log(n', + 2). Conversely, both an and a, are to be inserted into Rt then a, should be inserted prior to a,. Since cannot predict whether an item will be inserted into L or Rt formulating an appropriate insertion order that respects the constraints on both sides is impossible.
We tackle this issue of insertion order with a greegtth-bssed log n-rounds insertion scheme. Intu- itively, we think of I. and R as two "hoovers". with their "suction power" increasing simultaneously over time. Each item (as "dust") is extracted from the array and inserted into one hoover once the suction power reaches the required strength: a hoover with suction power à is able to absorb items that can be inserted into it with Olog 6) comparisons. Details are illustrated in Algorithm 3
The sorted structures L and R can be implemented by arrays, though alternative data structures could provide better time complexity.
We conduct insertions in [log ni] rounds, setting ó to be 1,, 20ggn In each round, we iterate over d1,,... 4n to decide if they should be inserted to T. in the current round. Then, we iterate over an an...., dj reversely, to decide if they should be inserted to R in the current round. Note that if an
7

---

Algorithm 3: Double-Hoover Sort
Input: (a1..... .l)),.,,nn.,,....... prediction
BucketSort(A,, (A,p;
Bucket Sort A according to ý, so that ((1) s ((2) S ... ........ s((n)
2 L, < ():
3 for = 20, 22,2),..... ..... [ngn]] do
for i
I...., if has not been inserted do
I +- {aj : < <i};
1/ < if [ < then -co else 8th largest item in L L
if a; > 1/ then
Insert a, into by binary search, starting on interval {ar E L: 1/ S 11),
where 1' == ming<s l/.
10
for i = n. , if a; has not been inserted do
11
R²1 {az E R R:j > i}:
12
33 - if [ < 5 then oo else öth smallest item in R²1
13
af; < r then
Insert a, into R by binary search, starting on interval {a R: r' S x S r
where 7 = ma
15
16 return merge(L. R);
A: a1 a2
a;
an
items in
O
O
000
inserted item comparison with boundary
strength:
binary search
insert a; to L
Figure 3.1: An example of the insertion process in the Double-Hoover sort.
item is inserted into either or R, it is omitted in later rounds. The insertion process of an item in one round is depicted in Figure 3.1
To decide whether a; should be inserted into L with strength ò, let l denote the 5th largest item in L with index smaller than i, representing the "boundary value" in this round. If there are less than 5 eligible items in L, set l3 to be -c. Let 1' represent ming<<8 13., the minimum boundary value in previous rounds. 15 is smaller than a, we employ binary search insert ag into L, starting with the interval (a E I.: 13 < }. Conversely, decide whether a; should be inserted into R, we adopt a symmetrical approach as depicted in lines 11 to 15 of Algorithm 3
After all insertion rounds, we merge L and linear time obtain the sorted result.
The correctness the Double-Hoover Hoover Sort arises from the invariance that both L and R remain sorted after all insertions. It is sufficient to show that the initial insertion intervals at line 8 and line 14 always cover the value of a; At line 8, 133 < a, holds trivially by conditioning. Since a; not inserted into L in any previous round, a, < lg for 8' < 8. Since the minimum operation preserves inequality, a; also holds. similar argument can be made for the interval at line 14.
Correctness.
To discern the comparison complexity of the proposed algorithm, we propose the following lemma. Lemma 3.1. Upon the insertion of item a into L, all items in L L are larger than 4. Similarly, when an Htmm as is inserted into R, all items in R \ R21 are smaller than rú. As a result, the initial interval line 8 and line 14 are subsets of L and REi, and hence have sizes larger than 8. Theorem 3.2. For each item a, its insertion process takes Ollog(min { (1/ vi + 2)) comparisons.
The full proof of Lemmal 3.1 and Theorem 3.2 are given in Appendix D

---

Then, Theorem 1.4 can be obtained from Theorem 3.2 by summing the number of comparisons in the insertion process of each a,,
Experiments
In this section, we conduct experiments both on synthetic data, crafted to simulate predic- tions in real-world settings, and also on real-world data of countries' population ranking. The source code used for experiments is available at learning augmented-sortan
looo/xinniaannaia jan-baiinaaaa bai-
We assess the performance of our proposed sorting algorithms against five well-established baselines. Quick Sort and Merge Sort are classic sorting algorithms with On logn) complexity; Tim Sort (Peters) 2002) is popular hybrid sorting algorithm designed to perform efficiently on real-world datasets and widely adopted in standard libraries. Further, we choose two adaptive sorting algorithms.
Odd-Even Straight Merge Sort (Estivill-Castee and Wood (992) and Cook- Cook-Kim division (Cook and Kim 1980), which are proven to be optimal with respect to several measures of disorderness. They serve adaptive variants of Merge Sort and Quick Sort. To apply adaptive sorting algorithms in positional prediction settings, we first execute bucket sort on the items by their predicted ranking, breaking ties arbitrarily. This "sorted-by sorteddby-predictioon" preddiciion" array is then inputted into the baselines. In we also show results of an experimental comparison against Insertion Sort.
Appendix F.2
synthetic data generation process. In many sorting tasks, items belong to different "grades", which represent a coarse version of the ranking. For example, students classified into grades A, B, C, and D based on their exam scores; with their grades in hand, we want to find out their accurate ranking. We denote this scenario as the class setfing. Specifically,
Positional Predictions. First, elaborate
divide an array of items into classes, sampling the thresholds to = 0 S t < f2 < to uniformly at random. Then, for items a; with f < i S tR. we say that they belong to the kth class, and their predicted position is uniformly generated from (ta-1, tx].
To model the tasks where we have an "outdated" ranking, we design the decay setting. The accurate ranking is obtained as the prediction at time 0. Then, during each time step, one item is randomly selected to be perturbed: its predicted position is shifted by 1, towards either left or right, with uniform probability. We then ask the sorting algorithms retrieve the original ranking of items based on the prediction at each time step.
We also utilize data from real-world setting. We draw the annual population ranking of countries and smaller regions from 1960 to 2010 from World Bank (2023). Then, we feed in the ranking in year 1960, 2010 respectively the prediction, and ask the sorting algorithm to predict the ranking in year 2010.
Desisomee sect
comparioons
#darses/1
Figure 4.1: Sorting with positional predictions (left: class setting; middle: decay setting: right: country population ranking). n = 1, 000, 000 for class and decay settings, n 263 for country population ranking.
In all the plots, the X-axis indicates the quality of predictions, and the Y-axis indicates the number of comparisons used. The red dotted line loga n. The bold curves represent the proposed algorithms. All experiments are repeated 30 times, with the standard deviation indicated by shade. A scapegoat tree implementation of Hoobee Sort is used for synthetic settings, while an array implementation is used for population ranking given the small sample size.

---

As depicted in Figure 4.1 our algorithms consistently outperform the baselines in all settings with various task sizes. Specifically, the class setting with Double-Hoover Sort outperform all baselines when the number of classes is larger than 0.05m. In the decay setting, both our algorithms perform better than the others as time progresses. the real- woal-world dataset, country population ranking, Displacement Sort needs the fewest comparisons when the given prediction is within years, and Couble-Hoover Sort dominates the rest when the prediction obtained 6 to 60 years ago. These experiments illustrate that the proposed algorithms can leverage positional predictions more effectively than traditional adaptive and non-adaptive sorting algorithms in variety of settings.
000, 000, Displacement Sort and
Dirty Comparisons. In some sorting scenarios, some "indicating factors" can be used cheaply compare two items. For instance. in biology, we can compare the binding affinities of two molecules for specific target protein and provide information about their potential efficacy drugs. However, comparisons based on indicating factors may have error induced by element deeeettwisee wise noise. Hence, we consider two dirty- compariso settings in which ratio of items is damaged. We say dirty comparison is perturbed if its outcome is uniformly random. In the Good- Good-Dominating setting. a dirty comparison between two items is perturbed if both are damaged; in the Bad- Bud-Dominating setting, dirty comparison between two items is perturbed if either item is damaged.
In dirty comparisons settings,
the 3-approximation feedback are algorithm proposed by |ilon et al. (2008) to preprocess the dirty comparisons. This algorithm uses On log n) dirty comparisons, the same order of magnitude our Dirty-Clean Sort, construct a positional prediction that roughly aligns with the given dirty comparisons. Then, we feed in the induced positional prediction the baselines.
Merge
Quick
Displazemant Douste-Hoover
GRSM
Mity-Clean Sort
# comparisons
comparisons
Quick
Dlupi acement
Doutl Ho-oovrr Sort
OESH
Dirty Clean sor:
damage ratio
damage ratio
Figure 4.2: Sorting with dirty comparisons, good- and bad-dominating settings.
As showcased in Figure 4.2 when 100, 000, in the Good- Dominanting setting, our proposed Dirty-Clean CCean Sort outperforms baselines when < 0.7: : in the Bad- Bad-Dominating setting, it outperforms other algorithms when < 0.25. If the damage ratio large, the prediction becomes chaotic, but still performs essentially no worse than Quick Sort for reasons discussed in Remark A.6 in the Appendix.
Limitations and Future Work
In the dirty-clean setting, our algorithm still requires time complexity of O(n logn) n) due to the processing of O(n log n) dirty comparisons. Consequently, the algorithm is more appropriate for situations where exact comparisons expensive than for those where comparisons are fast. In the positional prediction setting, Displacement Sort achieves a bound of O(E, log(n, + 2)) for achieves its guarantee nt } + +2) only for comparison complexity. An intriguing question is whether the latter bound be achieved for time complexity well. Another potential limitation is that predictions might not be learnable in some sorting settings; future work could focus on exploring the conditions under which predictions learnable.
both comparison and time complexity, whereas the Double-Hoover O
Broader Impact. Our paper proposes efficient sorting algorithms when a predictor available. do not expect any negative socictal impact.
10

---

We thank the anonymous reviewers at NeurIPS and Luke Melas Marlazi for their valuable comments.
Acknowledgments.
References
N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: Ranking and
clustering. J. ACM, 15(5):2::1-23:27, 2008. URL fttts:://doo.or//100/ 101//00011///44150
1411513
M. Almanza, F. Chierichetti, S. Lattanzi, A. Panconesi, and G. Re. Online facility location with multiple advice. In NewrIPS, 2021. URLhttps://proceddnggs wttp://eee......pee//////.
html
K. Anand, R. Ge, A. Kumar, and D. Panigrahi. Online algorithms with multiple predictions, In ICML, 2022. URL/lttps//prrceeddinn
m1r wtw.://nnnww....ee.e..eee...e.ee haad6///aand22aa.. html
S. Angelopoulos, C. Dür,, S. Jin, S. Kamali, and M. P. Renault. Online computation with untrusted advice. In /TCS, 2020. URL :/doi::///o.... //g::////oio//././//// wtt.:/......./......... 4230/LIPIcs, ITCS. 2020.52
A. Antoniadis, C. Coester, M. Eliás, A. Polak, and Simon. dynamic power management with multiple states via new ski rental bounds. In NeurlPS, 2021.
laaming-augmenter
URL htttps://proceedinggs www.nneuriiccmm http://eeeeeeeeeeeeeeeeeee//eppe http:/ps....ppppe/22////////////
html
A. Antoniadis, C. Coester, M. Eliás, A. Polak, and B. Simon. Mixing predictions for online metric algorithms. In ICML, 2023. URL URL.https://prrceediinn mlr. pptpss//v022/anoonnaaaooooee html
Y. Azar, S. Leonardi, and N. Touitou. Flow time scheduling with uncertain processing time. In STOC, 2021. UtL/https:///// / htt:://oo.oogggooo
wrgg//..0110... 10. 11////111111530025555555555
Y. Azar, S. Leonardi, and N. Touitou. Distortionnoollivious a for minimizing flow time, In SODA, 2022. URL /ttp::///aaa.orr//.0113311111111
N. Bansal, C. Coester, R. Kumar, M. Purohit, and E. Vee. Leamiing-aggmented weighted paging. In SODA, 2022. URL https: org/ 1117/11711111 113771.978161117777733
A. Bhaskara, A. Cutkosky, R. Kumar, and M. Purohit. Online linear optimization with many hints. In NeurlPS, 2020. URL
M. Braverman and E. Mossel. Noisy sorting without resampling. In SODA, 2008 URL http:
//dl. acm. org/ citatiin...nn/ -tm 1347112
X. Cao, J. Chen, L. Chen, C. Lambert, R. Peng. and D. Sleator. Learning-augmented b-trees, 2023. URL httpt:tttttoo....eto/ttt/ org/ 4855:1..88555/arrii.. 2303. 15379
J. Y. Chen, S. Silwal, A. Vakilian, and F. Zhang, Faster fundamental graph algorithms via learned predictions. In ICML, 2022. http:////..ptpp/pooooooooinnao.a
ppesss/v62/cchn22222 html
C. R. Cook and D. J. Kim. Best sorting algorithm for nearly sorted lists. Commun. ACM, 23(11): 620-624, 1980. URL https::::://oi..
10.
S. Davies, B. Moseley, S. Vassilvitskii, and Y. Wang. Predictive flows for faster ford-fulkerson In ICML., 2023. htRl//tttss:/prrceeeiiii
mlr pttp:p/eeeeeeeeeeeeeeeeeee html
M. Dinitz, S. Im, T. Lavastida, B. Moseley, and S. Vassilvitskii. Faster matchings via learned duals. In NewrIPS, 2021. URL https: http://pooeeanggeeeeeeeeee...eep hashh/
M. Dinitz, S. Im. T. Lavastida, B. Moseley, and S. Vassilvitskii. Algorithms with prediction port- folios. In NewrIPS, 2022. URL URU.httpp//pppprr.mpp...oo httpppee_..llee/pppp////////a// TF2223SScccaaaaaaaaaaaeeeeeeeee3
.ttl
Y. Emek. S. Kutten, and Y. Shi. Online paging with vanishing regret. In ITCS, 2021. URL https: :ttps:///oi... //doii org/10. 10. 4230/LIPICS. ITCS 2021.667
Ergun, Z. Feng, Silwal, D. Woodruff, and S. Zhou. Beaaming-augmeete k-means clustering.
In ICLR, 2022. URL http:///ww.///////////////////aa http:///ww....tooooooooooootetee

---

T. Erlebach, M. S. de Lima, N. Megow, and J. Schlöter. Sorting and hypergraph orientation under uncertainty with predictions. In IJCAI, 2023. URL https::////oi 24963/./..ca.................... 2023/ 619
V. Estivill-Castro and D. Wood. A survey of adaptive sorting algorithms. ACM Compul. Surv., 24(4):
441-476, 1992. URL UtI.https: httpp:://doi.ogg/1......... 1ttp://00..114//437..001100 146380
Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciencess, Sccieeemeeeinncss555555 (5() 1997. URL www.:sssiiiccdccc...c. http:://www.siiencccieeetttt wtt.://iieeett.ccooccccceeeeeeee htt.a//www.oooooooo.o......o/...
B. Geissmann, S. Leucci, C. Liu, and P. Penna. Optimal sorting with persistent comparison errors. In
ESA, 2019. URL https://doi. org.doi.....goggo htt.://...r.......////111....... 4230//2IIIIIs.... ESA 2019
S. Gollapudi and D. Panigrahi. Online algorithms for rent-or-buy with expert advice. In ICML, 2019. URI. httt::://poceeedinnggg//
mlr. http://////oollppuiiiiagm httppp/wwooaaaaaalooroooooooorap htmm
Y. Gu and Y. Xu. Optimal bounds for noisy sorting. In STOC, 2023. URL aattps://doi.org
1145/3564246 3381542233333511111
3585131
J. Guibas, E. M. McCreight, M. F. Plass, and J. R. Roberts. A new representation for linear lists. In STOC, 1977. URL https: org/ 10. 1011/115//90 800105. 1041/110010155... 803395
T. Kraska, A. Beutel, E. H. Chi. J. Dean, and N. Polyzotis. The case for learned index structures, In SIGMOD, 2018. URL https:://oi. org/10...1ooo 1145/3183713. 3196909
T. Kraska, M. Alizadeh, A. Beutel, H. Chi, Kristo, G. Leclere, S. Madden, H. Mao, and
V. Nathan. SageDB: A learned database system. In CIDR, 2019. http::///ciirr org/ http://pppppppp1/k/aaaapea
cidr19 pdf]
A. Kristo, K. Vaidya, U. Çetintemel, S. Misra, and T. Kraska. The case for a learned sorting algorithm. In SIGMOD, 2020. https:tts://doi. org/ 10. 1145/1143333 01555/331444.... 3389752
Lattanzi, T. Lavastida, B. Moseley, and Vassilvitskii. Online scheduling via learned weights. In SODA, 2020. URL httpps://oi....
1111/11171111111771111 www.9978111199999 .14
H. Lin, T. Luo, and D. P. Woodruff. Learing augmented binary search trees. In ICML, 2022. URL
mlr pttp:///...ppppe////////2221..1. html
A. Lindermayr and N. Megow. Permutation prediccion for non-clairvoyant scheduling. In SPAA,
2022.
Lu, X. Ren, E. Sun, and Zhang. Generalized sorting with predictions. In SOSA, 2021. URL
https://doi.oo
T. Lykouris and S. Vassilvitskii. Competitive 24:1-24:25, 2021. URL http:tttt.....rrg//////// 1145/3447579
cachiin caching with machine learned advice. J. ACM, 68(4):
D. J. Mankowitz, A. Michi, A. Zhernov, M. Gelmi, M. Selvi, C. Paduraru, E. Leurent, S. Iqbal, B.B.. Lespiau A. Abern, T. Köppe, K. Millikin, S. Gaffney, S. Elster, J. Broshear, C. Gamble, K. Milan, R. Tung, M. Hwang, T. Cemgil, M. Barckatain, Y. Li, A. Mandhane, T. Hubert, Schrittwieser, D. Hassabis, P. Kohli, M. Riedmiller, O. Vinyals, and D. Silver. Faster sorting algorithms discovered using deep reinforcement learning. Nature, 618(7964)257--23, 2023. URL https://doi.ore org/ 10. 1038/ 023-/411111---6-600222223
H. Mannila. Measures presortedness and optimal sorting algorithms. IEEE Trans. Computers, 34 (4):318-325, 1985.
1109/TC. 1985. 5009382
M. Mitzemmacher. Scheduling with predictions and the price of misprediction. ITCS, 2020. URL https:://doi.rrg/ htt.:/10..43//1PIII...... ITCS ..w.ICCCS......
M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. Commun. ACM, 65(7):33-35. /528888
2022.
J. I. Munro and Wild. Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs. In ESA, 2018.
200.0.2230/PPPPP. ESA 2018, 63
T. Peters. [Python-Dev] Sorting. Python Developers Mailinglist, 2002. URL https: //mail
python. orgoorgg/.....oo http://pwwapapaa.aaaa///////////
M. Purohit, z. Svitkina, and R. Kumar. Improving online algorithms via ML predic- tions. In NewrlPS, 2018. URL httpp//tee/p/ppooeiinnnseeeeeeep
12

---

D. Rohatgi. Nparmoptimal bounds for online caching with machine learned advice. In SODA, 2020. URL
11tp:///111111711777711111111111 1797711.98111117999999 112
S. Sakaue and T. Oki. Dissorteccoovsaaallyyiissssdddis frameookk for warm-starting algorithms with predictions. In NeurlPS,, 2022. URL
fatrrrffflleepppeeeee / .tmm
hashh844e61 http:/444e511222222aoo6666262222 htt.a//eae.....a..ee..oeoe..eaaa
S. Wang, J. Li, and S. Wang. Online algorithms for multi--hopp ski rental with machine learned advice. NeurIPS, 2020. URL http:://prooceedings /ttpo//ooooo///////oooooooooooo.
nww.igs...........p... /ttp://ooooooooaoooooooooooaa//r cc/paaper/2000///ashh
5cccb755c00000445544e666555-5-5- Abstract html
A. Wei. Better and simpler leamnnng-uugmentee online caching. In APPROX/RANDOM 2020. URL
htttps:/doi..org/ 10. 4230/LIPIcs APPROX//ANDDM. 20200 2020.60
World Bank. Population, total, 2023. httphhtps://daed worldbank htt.baak..rr//ddiaattoo////////a POP
TOTL. United Nations Population Division. World Population Prospects: 2022 Revision.
13

---

A Proof of Comparison Complexity of Dirty-Clean Sort
The goal of this section is to prove Theorem 1.1 behavior of dirty search and clean search, focusing on a single iteration of the for-loop corresponding to item aç.
We start with several lemmas on the expected
For an iteration of the dirty and clean search while-loops, respectively, we call the vertex stored as Ca resp. C' at the start of the iteration the pivor; the subtree rooted at the pivot is referred to as the active subtree. The size of a subtree is the number of non-NIL vertices it contains. For the dirty search, let s denote the size of the active subtree iteration and T denote the number of recursion steps needed. diny Denote by minny and makun the number of iterations of the dirty and clean search where the size of the active subtree lies in ( s]. In particular, ms = |[t: St E (3.
Lemma A.I. E Bime (11) and E [mmagaan (1) for all Moreover, Elmm. ditty O(1) and Em
|
8
clean 8p- = s' = ( all 8 < s' with P(s,- = 8') > O.
Proof. We employ percentile argument. Consider the first step of either while-loop where the active subtree has at most 8 vertices, and let V be the set of these vertices. Note that the pivot in this step is the first element in V inserted into the tree. Conditioned on the vertices of the active subtree being V. elements of V are equally likely to be the pivot, since their insertion order is uniformly random. This true even when conditioned on S;- s', since reordering the elements within the V does not change the value of St", which is determined at higher vertices of the tree. Thus, we have at least a 50% chance that the pivot lies between the 25th percentile and the 75th percentile, in which case both children subtrees contain at most " [ vertices each. Hence, the size of active subtree shrinks by a factor of j after at most steps in expectation, and it shrinks to size smaller than & after most (1) steps in expectation.
Based on this lemma, are able to characterize the expected length of dirty search, clean search, and dirty search after time t"
Lemma A.2. A dirty search takes Ollogn) steps in expectation, Le. E [ = O n).
Proof. In each dirty search, the initial largest subtree has size at most n. We can apply Lemma A. repeated on s n. 1 I......... ......... 1. By linearity of expectation, we derive that a dirty search takes nl O(1) = Ollog n) steps in expectation.
Lemma A.3. clean search takes O(E[og(s:- + +1)) steps in expectation; in dirty search after reaching (", there are O(E[log(s: 881- + 1]]) steps in expectation, i.e. E[T - ==] + 1)])-
Proof. Assume s,- = s'. Then, in dirty search after t², the initial largest subtree has size s', and the rest of the active subtrees all have size at most s' 1. By applying the second part of Lemma A. on = 5' 1, s'-1 ..... and summing, we obtain E [T t" [s s'I O(log(s' 1)). Thus,
T 1- Σ E - (* = 8' P [st- = 8' = O (E [log (8 + +)))
The bound clean search follows in the same way.
In order to relate E log (st. + 1)] to the prediction error 7/i the next lemma first characterizes the probability of given time step t being t" as function of the subtree size st.
Lemma A.4. For any and k P = t* 8 E (2 [0]=1,2*]] S m/
Proof. Recall that 1" is the last valid time step. A shift from a valid time step an invalid time step occurs only if the dirty comparison between the pivot and a; is wrong. Among all potential pivots, most 7/ can have mistaken dirty comparisons with a,, and they equally likely to be the pivot (depending on which of them was inserted first). Hence, given St E (2* 2 the probability of pivot with mistaken comparison is at most Tk/S S m
Based on Lemma A.4 we present the central claim bridging prediction error with comparison complexity.
14

---

Lemma A.5. E [log (s-- )] = O (log (n + 1)).
Proof. We have
IP St- (2*-1,2%)
Σ P and 9t (2k-1, [2]]
IP Σ P St E 12
t" 8t (2t-1,20
diny' m2z
$ 1bb
( ")
where the first inequality uses Lemma A.4 and the second is due to Lemma
A.1 Thus,
E [loo(ss--) }] S log(n) + 1) +
P [ E (2"-1,20 ,291] k
k= [11]
00
S log(1): + 1) + 7
Σ
0 (k2
k= 1=]1og(n++1]
= 0 (log (mx + 1)).
Theorem 1.1 is subsequently deduced.
Dirty comparisons are only conducted during dirty search, when the recursion step is incremented by one. As per Lemma A.2 the total number of dirty comparisons is bounded by the sum of steps across insertions, which
Proof of Theorem L.7
O(log n).
In each verification phase, as we traverse the dirty search in reverse order to locate t", at most T - t" clean comparisons suffice. In each clean search phase, the expected number of clean comparisons is the expected number of steps in clean search. Therefore, based on Lemma A.3 An3 and Lemma A.5 the total number of clean comparisons performed in both phases is (2 log (w: + 2)).
Additionally, the running time is dominated by the number of dirty and clean comparisons.
Remark A.6. The algorithm can be implemented such that the number of clean comparisons is at most that of quicksort plus Onn log log n), regardless prediction error. Thus, even with terrible predictions our algorithm matches the performance of quicksort up to factor that tends to 1 as - 0o.
To achieve this, we can implement the verification step by decreasing in geometrically increasing step sizes until valid has been found, and then perform binary search for t* between the last two attempted values of t. This reduces the number of clean comparisons in line 9 from O - t*) (log(T )*)), which is most Oloog log n)) in expectation by Lemma A.2 and most O(n log n2 for all verification steps together. The remaining clean comparisons are performed during the clean searches. In the worst case (when all dirty comparisons are incorrect) all clean searches start from the root, and together they perform exactly the same set of comparisons as quicksort (by a coupling argument between the random choices of the two algorithms: E.g., the root of the search tree corresponds to the initial uniformly random pivot of quicksort).
B Extentions of Dirty Comparison Setting
We consider two extensions of the dirty comparison setting. The first one assumes that dirty compar- isons are probabilistic; the second one discusses the setting where multiple predictors are available. We briefly discuss the extension of our algorithms and results in these settings.
15

---

B.1 Probabilistic Dirty Comparisons
Our algorithm extends to the case where dirty comparisons are probabilistic. Assume that for each pair of objects j. the dirty comparison between them yields an incorrect result with probability Mkj. Algorithm T can be directly applied in this setting, achieving the same guarantees by defining Mi E, Mky- The proof remains unchanged.
If repeatedly querying the same dirty comparison multiple times yields independent results, the number of clean comparisons can be further reduced: Let Gy := min (73 1/2)]. When querying a dirty comparison 2k times, the probability that the correct answer fails to secure majority vote is at most (4e,) (1 e; For Tky 2 0.5, this bound is trivial. Otherwise, there are 2 strings of length 2k over the alphahet (correct, incorrect), and each string that is at least half incorrect has probability at most (ei,(1 - -,
So by repeating each dirty comparison query 2k times, we obtain an algorithm that performs Okkn log n) dirty comparisons and O (2: log (4es((1 (1-=
ec,)))) (4)
clean comparisons.
B.2 Multiple Predictors
We now discuss the setting where multiple predictors are available and prove Theorem T.2 Suppose we have different dirty comparison predictors. Let v7." denote the number of incorrect comparisons by predictor p for item i.
We prove Theorem 1.2 by reduction the problem of "prediction with expert advice": In this problem, there are k experts, and each incurs a loss in the range [0. 1] per time step. An algorithm must select an expert in each round before the losses are revealed and then incurs the loss of the chosen expert. According to (Freund and Schapire 1997] Equation(9)), (9),, their algorithm HEDGE has an expected loss of (L + log(k)), where L is the total loss of the best expert in hindsight.
In our case, the experts correspond to the predictors, and time steps correspond to the n iterations of the for-loop of A Algorithm [ where item is inserted into the BST. We define the loss of expert p in the time step where ag ought to be inserted by L. log(1 [ + 7//) log(n), where 7i. < 1/. is the number of incorrect comparisons of predictor p between a, and the items already in the BST at this time. Note that the value of 77. can be determined at the end of the time step (once a, is correctly placed in the BST) without any additional clean comparisons; the division by log ensures that Ef E [0. 1] as required.
The algorithm for multiple predictors proceeds Algorithm| I querying for dirty comparisons at a given time step the predictor corresponding to the expert chosen by HEDGE at that time step. Recall from the analysis in Section 2.2 that the expected number of clean comparisons in this time step is then Oloog(1 + 17.') )), which is an O(log n) factor larger than the loss suffered by HEDGE. Consequently, by the O(L + log k) bound on the cost of HEDGE, the total expected number of clean comparisons is Omin, E, log(1 + v//" + log(k) log(n)). Since k < 20(n/ log n), the term log(k) log(n) = (n)) is negligible, and Theorem 1.2 follows.
C Proof of Comparison Complexity of Displacement Sort
Proof of Theorem I.3 We focus the insertion process of each item a; in Algorithm 2 Let d; denote the number of nodes between and a;- in an inorder traversal of the tree after inserting a;, including themselves. These nodes must have their correct ranking in the final sorted list between p(i 1) and p()): hence
d, S p(1) - p(i - 1)1 + 1, for all i = 2,...,
16

---

Therefore, the running time and number of comparisons among all insertions are bounded by
Σ (l)g(()))) - Σ O(log(p((i) - p(i - 1) +))
2
O(log(((()) - -(0) + lp(i - 1) - -i(i -i(i-)))== p(0) - f(i 1) + 1))
Oloo((3 max + - 1,8(1) 0(2 - 1) 11))
O(n) Ollo(n + +1))
00 Σ log(n, + +2)
The second inequality is by p(i - 1) S p(i) and the triangle inequality; the third inequality is by monotonicity of logarithm. The penultimate inequality is justified by log(max(2, y, z}) S log x + logy + log for all x, y. 2 1 and
log(p(i) - p(i - +)
(p(1) p(i 1)) s n.. 1=
This concludes the proof of Theorem 1.3
D Proof of Comparison Complexity of Double-Hoover Sort
Lemma D.1. Upon the insertion of an item o, into L, all items in L L' larger than 4. Similarly, when an item a is inserted into R, all items in R \ R² are smaller than Tú, As a result, the initial interval line 8 and line 14 are subsets of T and R and hence have sizes larger than 6.
Proof. Assume a; is inserted into L in round d. Consider any aj E L L at the time of ag insertion. Then, aj inserted into L previously with smaller insertion strength 8' 5. By the insert condition, aj > I2..
Since L is subset of L the 8'th largest item of the latter set must exist and be no smaller than the 8'th largest items of the former set. Then, we obtain
aj > 21
Hence, the interval {i E LIG < S }'} only contains items in L Since there are items in L that are no smaller than 13. the interval has at most items. An analogous proof shows the symmetric property in R.
Theorem D.2. For each item its insertion process takes O(log(min {n/. nf + 2)) comparisons.
Proof. Each item a; goes through some rejected insertions in earlier rounds, and then gets inserted into L or R in a certain round. We refer to them as the exploration phase and insertion phase, respectively, and prove that the number of comparisons needed in both phases is bounded by Ollo((min (v/. vf] 2)).
First, we claim that each a; is inserted into either I. or R prior or during the round with insertion strength 6/ : 20log(n++2) +2)1, If a; inserted before round 6% the claim trivially holds. The claim also holds if at round 6%. ن contains fewer than 6% items. In the absence of these conditions.
Ha, E L. aj > a = Ha, E L:j < <inii > atH
S Ki E [m] P() & p(0 AP() > p(HH
n/ < 8%
17

---

Hence, in round 8,, must be larger than the boundary value, which is the 8'th largest item in L Consequently it will be inserted into L in round o..
similar argument shows that a, will be inserted prior to or during round 2[log(n +2)1, Combining these two bounds, find that a, must be inserted prior to during round 6; 2 log(min (l +211
Hence, the exploration phase only needs Ollog (min| (7/- 1y! + 2)) comparisons.
Next, we continue to examine the number of comparisons needed in the insertion phase. Suppose a; inserted into some round S 84. Then, the binary search starts with an interval size
1 E L: 13 S x S 1' S
- 8. Omin {nk. nf
2).
The first inequality is due to Lemma 3.1 Hence, the insertion phase of a; by binary search needs Ollog (1/ 3 2)) comparisons.
E Lower Bounds on Comparison Complexity
We prove the lower bounds stated in Theorem 1.5
E.1
Optimality of Displacement Sort
In this section, we show that an exact sorting algorithm, augmented with a positional prediction, cannot sort the arayy with v( log(n;") comparisons.
Definition E.1. Given n, positional prediction p, and real number U, define the size of the U'candidate set as
can U) = {A E S. Σ log(n, +2) S U}
where Sn is the set of permutations of [n]] (viewed as an array), r7 is calculated accordingly for each A against p.
Theorem E.2. Given any function f(U) =
o(maxpes. log(cand U))), there does not exist any positional augmented sorting algorithm with comparison complexity (f(( for instances with E lo + 2) U.
Proof. Given the predictor ş and an upper bound U on the error, a sorting algorithm needs to determine the correct permutation A from candidate set of size cand(p, U). If the algorithm only uses æ comparisons, then it can only distinguish 2 different outcomes; if 2 is smaller than the number of candidates, it cannot determine the correct answer in every situation, since the information given by comparisons is not sufficient to distinguish all candidates. Hence, at least [log cand (,. U' comparisons are needed.
Theorem E.3. For all n SU U < (n log n.), we have maxpes, log cand U)) QUU).
Proof. Proof by construction. Assume without loss of generality that U is multiple of and let U' = U/nn Take ý 2., n). candidate permutations
the identity prediction. We aim to construct sufficient number of S,, which all fall in the U-candidate set.
Consider every permutation A E S,, constructed the follow way: Initially, set = (1, ..... n). "
Then, divide A into 207 adjacent subarrays, each containing 2 items (the last subarray is potentially smaller if there are not enough remaining elements). Finally, we permute the items in each subarray arbitrarily, and retrieve A after the permutation.
In each possible outcome A, log A < U' for all since each item is only permuted locally. Hence, the error of f w.r.t. A is no larger than U' = U. Each A falls inside the U-candidate set. Counting the number of possible different outcomes in our construction, we obtain
cand( U) 2 [
18

---

where the right- hand-side represents the possible ways to permute 2 items in each subarray. By Stirling's formula,
log (f, U) 2 Ω 2 (2" U*) (QU))
Directly combining Theorem E.2 and Theorem E.3 and noting that at least Q(n) comparisons are always needed verify correctness of sorted list, obtain the following:
Corollary E.4. For sorting with positional predictions, there exists algorithm with compurison complexity of EE== log(n + 2)).
E.2
Optimality Dirty Comparisons Sort and Double-Hoover Sort
We can use the same definition of cpn U' and construction as above. Every positional prediction can be view as a total linear relation on array therefore induces unique dirty-comparison predictor.
Since each element is locally perturbed, we can prove that for each permutation A obtained from the construction, Σi= log(1): + 2) and >= log(mnin (1/s n/ } + 2) are also upper bounded by U.
Hence, the optimality of Algorithm 2 and can be proven in the exact same way, and Theorem 1.5 follows.
F
Extra Experimental Results
F. Synthetic Datasets with Varying Sizes
This section presents additional experimental results to provide a more comprehensive evaluation of our proposed algorithms. As scalability is crucial aspect, conducted further experiments synthetic datasets with varying sizes from n = 1,000 to n 1,000,000. Results are shown in Figure and F3
In these figures, the shaded area denotes the standard deviation of each run among 30 repetitions. As the results show, our proposed algorithms perform consistently with relatively small deviations.
F22 Comparisons against Insertion Sort
The performance of Insertion Sort against our proposed algorithms is shown Figure F.4 As the plots show, insertion sort runs fast for small errors in the decay and country settings, though the performance declines steeply when predictions deteriorate (i.e., smoothness worse, and robustness is non-existent). The experimental results suggest that in practical settings, it is good idea to incorporate insertion sort as fall-back option case predictions are extremely accurate.
19

---

Merge Sort
Cook 4im Sort
Merge Sort
Cook 43m Sort
280
quiox Sort
Dsplacement Sort
quice
Dsplacement Sort
Sart
Doubrerfowwar Sort
Tim Surt
Gouble-Hotrwe
CESN
CESH
# companisons
# comparisons
#classes
#classes
(a) class setting,
(b) class setting, 10, 000
Herge Sort
Cook-ktmm Sort
Merge Sort Cook-i0m Sort
Cuick Sort
Displacement Sort
Quick Sort
Dispaacemnnt sort
# companison I
Tim Sert CESN
Doubler/forva Sort
Tim Sart
CESH
Gousterfooree Sart
comparisoon
#classes
#classes
(c) class sctting, 100, 000
.00,000
(d) class setting, 1,000, 000
Figure F.1: Class Settings.
* comparisons 1
# comparisons n
Ne ge
Cook din soxt
Verge Sott
Cool fart Dosble
Sont TE:0
Doubl roower Sort
0EEM
#timesteps/ n
Wtimesteps /n
(a) decay setting. n 1, 000
(b) decay setting, 10, 000
# comparisons mn
125-
comparisons
25
Quars Sac
Ores See
Destirement Seat
Den Hesowe Scrt
#timesteps/
#timesteps
(c) decay setting, 100, 000
(d) decay setting, 1, 0000, 000
Figure F.2: Decay Settings.
20

---

Merge Sort
Cook-im Sort
Merge Sort
Cook-kim Sort
Quick sont
Displacement Sort
Quick Soit
Dispbaement Sort
Dsuble-iotver
souble-toover
comparisans (n
Drty- Clean
Dirty- Sort
comparisons
damage ratio
damage ratio
(a) good-dominating n 1, 000
(b) good-dominating, n 10, 000
Merge
Quick Sort
Displacement
Tim Seft
Double Hoover Sort
# companisons |n
DESM
Dirty Clean Sort
# comparisons
Merge Sort
Cook: Sort
Duick Sor:
Displacement Sort
Time Sort
Doublee-toover Sart
DESN
Dirty Clean Sart
damage ratio
damage ratio
(c) good-dominating, 100, 000
(d) bad- and-dominating, 1, 000
# comparisons In
comparisons Im
X0-
Morgo
Durty-Clean
Dirty-Clean
damage ratio
damage ratio
(e) bad-dominating, n 10, 000
(f) bad-dominating, n = 100,000 000
Figure F3:: Sorting with dirty comparisons, good- and bad-dominating settings
21

---

compertoom
Wclasses 7.
#timestess
# comparison ssons In
Bi aoanm Sat
gap
ce colleercovee 2017
Deglemmer
Dary Mayclheeehh
Gamage
damage ratio
(a) Results of insertion in positional and firtycoomparion settings. Due to the O(n²) complexity of comparisons, n 10, (rather than 1, 000, 000 as in main text) is used in the class, good dominaain.. and bad bad-dominating settings,
Diuuk
coaeerifiin Nonss 10
f COmTOr toorss Cr
damage
damage
(b) Zoomed-in plots for class setting, good- and bad-dominating settings.
Figure F.4: Comparison with Insertion Sort
22


Reviews:
[{"review_id": "BZyOnTmpYt", "reviewer": "Reviewer_JwAo", "summary": "The paper proposes algorithms for sorting a set of items when unreliable extra information is available in the form of positional predictions or comparisons. The paper proposes a randomized algorithm for the former and deterministic algorithms for the latter problem.", "questions": "- Will it help to detect at some point in the algorithm that the dirty comparisons are going to hurt more than help i.e., if the algorithm can learn/find out that it will spend more comparisons (dirty + clean) than just the O(nlogn) clean comparisons, it might abandon the dirty comparisons and thus help in reducing the total number of comparisons. Is this possible in the suggested algorithms? Is there a learning component that is natural here? \n- Standard metrics for comparing two permutations include the Kendall-Tau distance (between permutations), pairwise disagreement error (permutation vs tournament), etc. It might be useful to state the results in terms of these metrics.\n- How do these algorithms change when one has a budget of clean comparisons to work with? \n- An important pairwise comparison setup in the machine learning context is when the comparisons are not deterministic but probabilistic - for instance when a clean comparison is made between items i and j, the result might be based on the toss of a coin with probability P_{ij} = s_i/ (s_i + s_j) where s_k is the score of item k (The Bradley-Terry-Luce model). Here, one needs to learn the score vector to be able to rank (or sort) the items. How easy/hard is it to extend the results in this paper where one needs to be able to learn these scores from dirty or clean comparisons - if yes, this will make the work much more relevant to the ML community. \n", "limitations": "Listed above in the weakness section - the results are less suited to a ML venue in my opinion. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes interesting algorithms for sorting when additional unreliable information is available.\nThe algorithms are simple and intuitive and the analysis (though several ideas are standard) is effective.\n", "weaknesses": "- A potential weakness is the relevance to the learning (NeuRIPS) community. In my opinion, the paper is more suited to a theoretical computer science venue as opposed to an ML venue such as NeuRIPS. Would like to understand the author's view on this\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and interesting suggestions. We believe we can address the perceived potential weakness of suitability for NeurIPS, and provide answers to this and other questions below.\n\n**Suitability to the NeurIPS community:** We recognize that our paper is not a classical ML paper, but the call for papers is explicitly broad in encouraging submissions from a wide range. For the area of “algorithms with predictions” (that our paper belongs to), NeurIPS and ICML have actually been the main venues: In fact, there have been more papers from this area at NeurIPS alone than at the classical theory/algorithms venues STOC, FOCS, SODA, ICALP and ESA combined. (There is a website tracking papers from the area to verify this, but we are not allowed to provide links here.) Machine Learning is often a natural way of generating predictions, and while there are some works that prove this rigorously, it requires distributional assumptions. Since powerful predictions can often be obtained even without provable guarantees (via ML or otherwise), the majority of these theoretical works focus on how to utilize predictions rather than how to generate them. Some examples just from last year’s NeurIPS alone include Bernardini et al. “A Universal Error Measure for Input Predictions Applied to Online Graph Problems”, Grigorescu et al. “Learning-Augmented Algorithms for Online Linear and Semidefinite Programming”,  and Jin and Ma “Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model”. Given a history of many more similar works at NeurIPS in recent years, we believe that it is the ideal venue for our paper.\n\n**Suggestion of completely abandoning dirty comparisons if they are detected unhelpful:** This is indeed possible via existing learning techniques, which learn online which of two algorithms performs best. However, it would not improve the theoretical guarantees: Note that even with arbitrarily bad predictions, the total number of dirty + clean comparisons of our algorithm is never worse than $O(n \\log n)$, since $\\eta_i\\le n$.\n\n**Other error measures:** If positional predictions are bijective (so that Kendall-Tau distance is well-defined), then Kendall-Tau is equal (up to a factor 2) to $\\sum_i \\eta_i$. Similarly, in the dirty-clean setting, pairwise disagreement error is equal to $\\sum_i \\eta_i$. Writing $D$ for either of these measures, the guarantees of our algorithms are $O(n\\log(D/n))$ by Jensen’s inequality, and this is optimal as a function of $D$ (our same lower bound construction applies). Note, however, that our more refined bounds are stronger. We will expand the related discussion currently in lines 67-73 and move it to a more prominent place in the final version.\n\n**Budget of clean comparisons:** This is an interesting idea. A budget less than what our algorithm achieves wouldn’t allow to *exactly* sort the input, due to our lower bounds. However, it is conceivable that one could prove interesting results in such a setting if the goal is to approximately sort the input, or if dirty comparisons are random and it can help to query the same dirty comparison multiple times.\n\nThe question about probabilistic dirty comparisons, as well as an additional result about combining multiple predictors via learning techniques, are discussed in our general response to all reviewers.\n"}, {"review_id": "n0uTZKh3Kc", "reviewer": "Reviewer_S6Cj", "summary": "The paper studies the oracle-augmented sorting problem, in which, in addition to the array, an oracle is provided to return ‘reference answers’ for the sorting of the array. The oracle is presumably efficient – queries are assumed to take $O(1)$ time – but might be noisy, i.e., at times return incorrect answers. The key question is to design algorithms that 1). When the oracle is great, the number of comparisons is significantly smaller than the baseline algorithms; and 2). When the oracle is very bad, the number of comparisons is still comparable to the baseline algorithms. \n\nTo this end, the paper considered oracles under two settings: a). An oracle that gives ‘dirty comparisons’ – a list of ‘all-pair’ comparisons that may include some errors and b). An oracle that gives a positional list – a list of predicted positions for each element in the array. The paper then designs algorithms under both models. In particular, for the dirty comparison model, the proposed algorithm achieves $O(\\sum_{i=1}^{n} \\log \\eta_{i})$ number of true comparisons and $O(n \\log n)$ dirty comparisons, where $\\eta_i$ is the number of ‘wrong comparisons’ based on element $a_i$. This demonstrates a smooth tradeoff between the number of true comparisons needed and the prediction error. The paper also obtained similar results for positional list predictions under different notions of error.\n\nI read the dirty-clean comparison algorithm and proofs to some details, and they look correct as far as I can tell. I skimmed the claims for the positional list algorithms, but did not verify the proofs (these algorithms seem to have built on more recent ideas). For the dirty-clean comparison, I think a key observation here is that the binary comparison trees are fairly ‘robust’ against perturbations in the sense that 1). The error is consistent – if there is $R<L$ on level $t$, then the error also happens for all $t’>t$ and 2). Thanks to randomization, the probability of the mess-up of the upper and lower bounds becomes exponentially small when the level moves up. As such, the binary search tree should be able to travel sufficiently deep in the tree based only on the dirty comparisons unless a very large chunk of the comparisons is corrupted. These observations, although not technically novel, do seem to be neat and cute for this problem.\n\nOverall I think the paper makes a significant contribution to a fundamental problem, and the setting is interesting and well-motivated. The paper is also well-written and easy to follow; the experiments also demonstrate competitive performance for the new algorithms. As such, I have a positive evaluation of the paper.\n", "questions": "- In your clean-dirty comparison model, I think you have this ‘deterministic error’ that if the comparison between a and b is wrong, you cannot get the correct answer by querying it again. This crucially separates your model from the classical noisy comparison line of work (your ‘dirty perturbation’ is not random). If what I said is correct, I would suggest adding a discussion about this.\n- In your experiments, the dirty-clean sorting seems extremely robust even when the damage ratio approaches $1$. Is this an artifact of your experiment setting/your implementation, or is there a reason that the algorithm performs in such a nice way? (Note that your proof shows only *asymptotically* competitive, but it seems even the constant is very competitive when the damage ratio is high.)\n(More presentation-related)\n- Does the term BST on page 4 stand for ‘binary search tree’? The abbreviation was never mentioned before.\n- Line 185, it’s a bit weird to talk about ‘timestep’ here – I think you mean the recursion step.\n", "limitations": "Most of the limitations are discussed in the ‘weakness’ section. From a broader societal perspective, since the work is of theoretical nature, there is no immediate negative impact, and I could not foresee any (take it with a grain of salt since I do not have experience in ethical/societal review). ", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "As I mentioned in the general evaluation, I think the paper is in a nice shape both in terms of the contributions and the presentations. To elaborate a bit more:\n- The paper follows a recent line of work on ‘learning-augmented algorithm’/’algorithm with advice’, and it tackles a very important and fundamental problem. It is surprising that previous work has not considered the problem. \n- Although the techniques are not complicated, the algorithms are based on several neat observations. The upper bounds are also tight by matching the lower bounds (unfortunately deferred to the appendix).\n- In addition to the theoretical results, the experimental performance is also quite competitive – one interesting observation is that the dirty-clean sort remains very competitive to baseline even when the corruption rate approaches 1. Furthermore, the experiments are run on large scales, which verifies the efficiency also from the practical time side (not necessarily captured by the theoretical time complexity).", "weaknesses": "- One potential criticism of the work is that the techniques are not novel and perhaps easy to come up with. This is true for the dirty-clean sorting algorithm; and although I *personally* do *not* think this is an issue, this perspective is frequently flagged for theoretical work. The positional list with left-right errors seems to require more involved techniques, but I do not really like that definition of error. \n- It seems the two settings of the oracles in this paper are very natural. However, there could still be other settings that your model does not capture. For instance, one can define a dirty comparison oracle with amortized error only (across ${n \\choose 2}$ comparisons), and what will be the optimal bound therein? That being said, I don’t think it’s very fair to ask a paper to address all possible models, so I’m not letting this question affect my evaluation.\n- Some (minor) presentation issues: In the binary tree search subroutines of algorithm 1, the use of tuples makes the text slightly confusing. I struggled for a minute to parse the value assignment of tuples. Maybe you can say we use tuples to represent (lower-bound, pivot, upper-bound) before pointing the readers to the algorithm. Also, what does it mean for ‘return inorder traversal of B’? (I know what it means, but is this the best way to say it?)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and interesting questions and observations.\n\n**Simplicity:** We believe that the simplicity of our algorithms is a strength as it makes them more widely appreciable, especially given that this is the initial investigation of the subject.\n\n**Amortized error:** Assuming that “amortized error” refers to the sum or average of the $\\eta_i$, then our algorithms do in fact achieve optimal bounds in terms of this measure as well. Please see our response to reviewer JwAo under the heading “Other error measures”.\n\n**Noisy sorting:** The distinction between the dirty-clean model and noisy sorting as observed by the reviewer is correct. Moreover, the noisy model does not allow *exact* sorting, which we overcome by allowing clean comparisons. We will expand our existing discussion on noisy sorting to clarify this. In our general response to all reviewers, we discuss how our algorithms can also be extended to probabilistic dirty comparisons (note some dirty comparisons might have error probability $\\ge 1/2$, which noisy sorting doesn’t allow).\n\n**Good-looking constant factors in experiments:** Indeed, a slightly more careful analysis shows that even if dirty comparisons are arbitrarily bad, the expected number of clean comparisons is at most that of quicksort plus $O(n\\log\\log n)$ (and in particular, the leading $n\\log n$ term in the bad-prediction case has the same constant factor as for quicksort). This crucially relies on what we mention in the footnote on page 4, which makes the verification step negligible (a naive implementation of the verification step would lose a factor of 2). In the worst case where all dirty comparisons are incorrect, all clean searches start from the root. But then all clean searches together perform exactly the same set of comparisons as quicksort (by a coupling argument between the random choices of the two algorithms: E.g., the root of the search tree corresponds to the initial uniformly random pivot of quicksort). This explains why even with terrible predictions, dirty-clean sorting matches the performance of quicksort up to a factor that tends to 1 for large n.\n\nWe thank the reviewer for additional suggestions that we will incorporate in the final version (in particular, yes, BST = binary search tree).\n"}, {"review_id": "H2BinO7sgq", "reviewer": "Reviewer_HoTq", "summary": "This paper studies learning-augmented sorting, where an algorithm obtains access to a potentially erroneous prediction on the sorting of an array. The paper considers two prediction models. In the positional predictor, every item has a prediction for its place in the sorted array, and the error of item i is the number of indices its predicted location is from its true location in the sorted array. The also consider a one sided error model for that prediction. In sorting with dirty comparisons, every pair of items has a < or > relation between them. Note that the dirty comparisons do not have to satisfy transitivity, thus potentially giving rise to cycles. A query between two elements is called a clean comparison.\n\nThe authors design sorting algorithms that use these predictions, and the performance of the algorithms depends on the error in the prediction. The performance is measured by the number of comparisons. Two of the main results (given with matching lower bounds) are:\n- Given access to dirty comparisons, there is a randomized alg sorting in O(n log n) runtime, O(n log n) dirty comparisons, and O(sum_i log(eta_i + 2)) clean comparisons in expectation.\n- Given a positional predictor, there is an alg sorting in O(sum_i log(|p(i)-\\hat{p}_i|+ 2)) runtime and comparisons.", "questions": "(Please see questions in Weaknesses and Strengths)\n\nMany grammatical typos throughout, I highlights a few below but I recommend a full read through before submitting a CR to Neurips or submitting to another venue. Here are some things I noticed below:\n- (lines 15-17) The first sentence in the intro is oddly phrased, consider rewording.\n- (lines 24-38) Add citations for the examples of how learning-augmented sorting could be useful.\n- (line 41) In *the* dirty comparison setting…\n- (line 42) comparison *bounds* on the error…\n- (line 126-127) While *the* recurrent noisy… \n- (Lines 176-179) I think slightly more detail here could be added. The point is that with the dirty comparisons you end up without a total ordering, so the point is the go to the closest subtree that contains something breaking the total ordering and then fix that element’s position in this subtree? So this clean search is what will remove the cycles.\n- (Line 293) We design *the* decay setting.", "limitations": "na", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written, and I believe the theoretical results to be correct. \n- The experimental results sufficiently back the theory (for my taste). \n- Overall, I like the paper well enough. However, I’m concerned about how much new insight into sorting with predictions this is contributing, given that similar problems have been studied and the authors do not thoroughly compare to these prior works. Can the authors comment more on this?\n", "weaknesses": "- While the paper gives a nice background on learning-augmented algorithms, I think several key works are missing that need to be compared against. For example, I need a thorough comparison against The Case for a Learned Sorting Algorithm by Kristo et al. Also, the papers The Case for Learned Index Structures by Kraska et al and SageDB: a Learned Database System by Kraska et al should be at least mentioned. I would also like a few more sentences explaining why the Lu et al and Kristo et al algorithms are not amenable to this setting/ what the notable differences are.\n- From a cursory glance, I believe the paper from Kristo et al has analysis that depends on the total error of the indices, whereas the paper here considers a more fine-grained analysis by depending on each indices error. I don’t know how/ if the algorithms are different. Can the authors please comment more on this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and in particular pointing out additional related works. We inspected these works more closely, and while they may seem similar at first glance, they actually consider different problems, and the techniques from these papers cannot be used to conclude any of our results, as discussed below. Nonetheless, we shall indeed expand the discussion of related works in our paper to better contrast it from prior work and avoid misunderstandings. We hope this will address the reviewer’s concerns.\n\nFirst, we wonder whether there may have been some misunderstandings about our paper, since the reviewer’s summary mentions that our algorithm for positional predictions makes dirty comparisons, although these are two completely separate settings (when given positional predictions, we do not make any dirty comparisons). There also appears to be some mix-up regarding running times in the review’s summary of results.\n\nWe are confused by the reviewer’s statement that “the problem has already been studied”. We are not aware of any works that study the classical sorting problem in a setting where the algorithm’s input is augmented with predictions. Granted, the paper of Lu et al. that we cite studies *generalized* sorting with predictions, but for the non-generalized setting they do not obtain any non-trivial guarantees (details below). The positional prediction model is similar to adaptive sorting, as we mention in the paper, though the perspective via predictions motivates the more refined error measures (and this also leads to better experimental performance compared to popular adaptive sorting algorithms).\n\n**Comparison with Kristo et al.:** The paper of Kristo et al. proposes an algorithm for sorting numerical values that performs well in empirical tests. In the first step, their algorithm tries to approximate the empirical CDF of the entire input by applying ML techniques to a small subset of the input. However, although the algorithm has a learning component, it does not really fall into the area of “algorithms with predictions” since the input to the algorithm is just the list of items (no additional predictions). Without providing additional information to the algorithm’s input (via e.g. predictions), it is not possible to sort faster than $O(n \\log n)$ on average due to the entropic lower bound (unless one makes other assumptions, e.g. numeric inputs drawn from an efficiently approximable CDF, or input values belonging to a bounded range of integers). The reviewer states “From a cursory glance, I believe the paper from Kristo et al has an analysis that depends on the total error of the indices”. We do not find any such analysis in the paper of Kristo et al. As far as we see, the paper never defines an error measure – please let us know in case we missed something. The paper is mostly empirical, whereas ours is mostly theoretical. That said, Kristo et al. does contain a brief theoretical discussion, but it appears the theoretical complexity of their algorithm is $O(n^2)$ due to an insertion sort step, though they argue that empirically it runs much faster. Indeed, this makes sense for numerical inputs drawn from a sufficiently nice distribution, since then one can extrapolate from a small part of the input to the rest. If inputs are non-numeric (and no monotonous mapping to numbers is known), then one has to rely on a comparison function, and the approach of Kristo et al. would not be well-defined. In contrast, our algorithms can sort arbitrary types of items since we only assume access to a comparison function and predictions (the latter being necessary to beat $O(n \\log n)$). We do not see any significant similarities between our algorithms and theirs, and already the settings are entirely different. That said, we acknowledge that we should have discussed their work due to a similar high-level motivation.\n\n**More details on Lu et al.:** As mentioned in our paper, this work studies the so-called “generalized sorting” problem with predictions. In generalized sorting, some comparisons are forbidden and others are allowed, and the goal is to sort the array by making only allowed comparisons (assuming this is possible). The paper considers the setting where for each allowed comparison, a prediction on the outcome is available (which is similar to our dirty comparisons, so we shall use the terminology of dirty and clean comparisons hereafter). They provide two algorithms whose numbers of clean comparisons are $O(n \\log n + w)$ and $O(nw)$ respectively, where $w$ is the total number of incorrect dirty comparisons. The running time in both cases is polynomial (the exact polynomial is not stated). These bounds are interesting when a significant portion of comparisons are forbidden, since then it is not known how to sort faster than $O(n^{1.5})$ without predictions. But note that in the non-generalized setting where *all* comparisons are allowed, the first bound is never better than what can already be achieved without predictions. The second bound could be better than $O(n \\log n)$ if predictions are very good, but already when each item is involved in only a single incorrect and otherwise correct dirty comparison, the $O(nw)$ bound becomes $O(n^2)$, whereas ours is $O(n)$. Adapting these algorithms to our dirty comparison setting would yield an exponentially worse error dependence compared to our algorithms, and the ideas in this paper would not be suitable to obtain any of our results.\n\nWe will expand the discussion on related work in the final version of our paper, including also the other (mostly empirical) works by Kraska et al. The provided references along with the other feedback will help us improve our paper. However, we do not see a concern that our work might be close to others’ validated.\n"}, {"review_id": "byRticyxbZ", "reviewer": "Reviewer_gjeT", "summary": "This paper presents sorting algorithms augmented by prediction under two settings: (i) sorting with positional predictions and (ii) sorting with dirty and clean comparisons. In (i), the algorithm can use a predicted position $\\hat{p}(i)$ of each element $i$, and in (ii), the algorithm is provided a faster but possibly inaccurate comparison oracle besides a slow but accurate comparison. In both settings, the authors present provably faster algorithms making use of the positional predictions/dirty comparisons. They also show that the complexities of the presented algorithms are asymptotically optimal. The efficacy of the algorithms is validated through numerical experiments on synthetic and real-world datasets.", "questions": "- The height of a binary search tree can be deterministically maintained within a logarithmic order of #nodes by using the \"rotation\" operation. Can the presented algorithm with dirty comparisons also be derandomized by rotating the tree?\n- What happens if there are ties in the correct order of elements? Are your sorting algorithms work? If so, are they stable? Can you extend your result to the setting where the dirty comparison for two elements reports that \"they are in the same order\"?\n- The insertion sort runs fast if the array is almost sorted. Thus, in the positional prediction setting, the bucket sort (by the prediction) followed by the insertion sort seems to run fast. I'm interested in an experimental comparison.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The two settings introduced in this paper are well-grounded in real-world scenarios, demonstrating their relevance and applicability. The algorithms proposed are elegant and straightforward, contributing to their practical utility. I also find the lower-bound results commendable. The paper is well-composed, particularly the introduction, which provides an accessible entry point for readers unfamiliar with algorithm-with-predictions research. Therefore, my overall assessment leans towards a positive evaluation of this paper.", "weaknesses": "- The sorting algorithm with dirty comparisons is randomized and takes $O(n \\log n)$ comparisons, as explained in Section 5. The contribution of this paper will be stronger if the algorithm is derandomized and/or the worst-case time-complexity bound is improved to $O(\\sum_i \\log (\\eta_i^\\triangle + 2))$.\n- The algorithms cannot be implemented in the \"in-place manner\" because they use extra binary trees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and interesting comments. We address specific comments below.\n\n- Derandomizing the dirty comparison algorithm is an interesting question, and we do not know how to do this. Indeed the height of the tree can be made O(log n) deterministically via rotations. But the main purpose of randomization is to ensure that the root of each subtree is a uniformly random element from that subtree, so that the probability of an incorrect dirty comparison is at most $\\eta_i$ divided by the number of elements in that subtree. For example, if there is just a single bad element that has incorrect dirty comparisons with all other elements, while other dirty comparisons are correct, then one would have to prevent an adversary from tricking a deterministic algorithm into placing that bad element at the root. We don’t know how to do this, but it is a nice question for future research.\n- Improving the running time of the dirty comparison algorithm to match the number of clean comparisons isn’t possible: Even if all dirty comparisons are correct, the total number of (dirty or clean) comparisons needs to be at least $n\\log n$ due to the lower bounds on classical sorting.\n- All our algorithms work also if there are elements of equal value (essentially, this only helps the algorithms to run faster; we disregarded this case in the write-up in the interest of simplicity of presentation). If stability is desired, this could be achieved by adding a tie-breaker that compares, whenever a comparison turns out equal, the positions of the two items in the input array (this may seem like a hack, but it does not affect the asymptotic guarantees). It is also possible to allow dirty comparisons to output “equal”, and count this as an error of 1/2 if they are non-equal. Also here, the same guarantees can be achieved (idea: any equal dirty comparison can be interpreted as random).\n- The question regarding comparison with Insertion sort is addressed in our general response to all reviewers.\n"}]

Author rebuttal:
We thank all reviewers for their valuable feedback and many interesting questions and suggestions. We provide answers in individual responses. It appears the main concerns besides otherwise mostly positive feedback were whether our work is suitable for the NeurIPS community (reviewer JwAo) and that the relationship with prior work wasn’t sufficiently discussed (reviewer HoTq), which may have additionally led to a mistaken impression that the problem was already studied. We believe that we can address both concerns, as outlined in the individual responses. Should there be more questions though, we would be happy to provide further information.

Additionally, this general answer addresses three points that might be of interest to all reviewers:

**Probabilistic dirty comparisons:** Reviewer JwAo asked whether our algorithms extend to settings with probabilistic dirty comparisons. A first answer is that one can apply our algorithm as is, achieving the same guarantee when defining $\eta_i=\sum_j \eta_{ij}$, where $\eta_{ij}$ is the probability that dirty comparison between i and j is incorrect. The proof is completely unchanged. If repeated queries to the same dirty comparison give independent results, one can do better: Let $\epsilon_{ij} := \min(\eta_{ij}, 1/2)$. Then, querying this dirty comparison 2k times, the probability that the correct answer fails to win the majority vote is at most $(4\epsilon_{ij}(1-\epsilon_{ij}))^k$. (For $\eta_{ij} \ge 1/2$ this is trivial. Otherwise, there are $2^{2k}$ length-2k-strings over the alphabet {correct,incorrect}, and each at-least-half-incorrect string has probability at most $(\epsilon_{ij}(1-\epsilon_{ij}))^k$.) So by reduction to our first answer to this question, we obtain an algorithm with $O(k n\log n)$ dirty comparisons and $O(\sum_i \log(\sum_j (4\epsilon_{ij}(1-\epsilon_{ij}))^k))$ clean comparisons. More sophisticated algorithms are conceivable that choose different k for different pairs $(i,j)$. Also, the problem where each dirty comparison costs 1, clean comparisons cost $M>1$, and the goal is to minimize the total cost becomes interesting in the probabilistic case. We will add a discussion to our paper.

**Multiple predictors:** Reviewer JwAo’s questions about strengthening the links to Learning further motivate us to include an additional result in our paper. It is about a setting with $k$ different dirty comparison operators (aka predictors), where the best operator is unknown. Let $\eta_i^p$ be the number of wrong comparisons of predictor p for item i. We claim that as long as $k\le \exp(n / \log n)$, we can sort with at most $O(\min_p \sum_i \log(2+\eta_i^p) )$ clean comparisons, i.e., as good as if we knew in advance which predictor was best. This follows via reduction to the problem of “prediction with expert advice”: There are $k$ experts, each suffering a loss in [0,1] per time step. An algorithm has to choose an expert in each round before losses are revealed, and then suffers the loss of the chosen expert. By [Freund and Schapire. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. Equation (9)], there is an algorithm with expected loss $O(L+\log(k))$, where $L$ is the total loss of the best expert. In our case, the experts correspond to the predictors, and the loss of expert $p$ in round $i$ can be defined as $\log(1+\eta_i^p) / \log(n)$ so that it lies in [0,1] as required (to be more precise, since knowing $\eta_i^p$ would require many clean comparisons, this should be replaced by the according quantity restricted to the set of items that were already inserted into the BST). So loss is a $1 / \log(n)$ fraction of number of clean comparisons when using predictor $p$ to guide the insertion of item i. Then the total number of clean comparisons is $O(\min_p \sum_i \log(\eta_i^p) + \log(k)\log(n))$, where the term $\log(k)\log(n) = O(n)$ is negligible for $k\le \exp(n / \log n)$. The bound on $k$ is essentially tight since already $k=\exp(n\log n)$ would mean there could be one predictor for each of the n! possible sorting outcomes, which would render them useless.

**Experimental comparison with insertion sort:** Reviewer gjeT asked for an experimental comparison with bucket sort (according to predictions) followed by insertion sort. The reviewer’s expectation that this runs fast for small errors is correct in some settings (and indeed, in some experiments, there’s a range where it outperforms our algorithms for small error), though the performance deteriorates steeply when predictions get worse (i.e., smoothness is worse, and robustness non-existent). Plots with results are attached. This suggests that for practical settings it is a good idea to incorporate insertion sort as a fall-back option in case predictions are extremely good.


Meta-review: The authors are encouraged to incorporate parts of their response in the paper. In particular, they should:
* Elaborate on the tightness claim.
* Incorporate, as extensions, the settings of probabilistic dirty comparisons, multiple predictors
* Add the experimental results with insertion sort.
* Highlight connections with/differences from the works by Kristo et al. and Lu et al.
* Implement the numerous smaller improvements (typos, presentation, etc.)
Decision: Accept (poster)