A d-Dimensional Binary Search for Integer Pareto Frontiers

For finite integer $d$-cubes, we consider the problem of learning a classification $I$ that respects Pareto domination. The setup is natural in dynamic programming settings. We show that a generalization of the binary search algorithm achieves an optimal $\theta(n^{d-1})$ worst-case run time for $d\geq 2$.