Before revision: This paper proposes a new model for augmenting algorithms with useful predictions that go beyond worst-case bounds on the algorithm performance. By refining existing models, our model ensures predictions are formally learnable and instance robust.
After revision: This paper proposes a new model for augmenting algorithms with predictions by requiring that they are formally learnable and instance robust.