We propose a new model for augmenting algorithms with predictions by
requiring that they are formally learnable and instance robust. Learnability
ensures that predictions can be efficiently constructed from a reasonable
amount of past data. Instance robustness ensures that the prediction is robust
to modest changes in the problem input, where the measure of the change may be
problem specific. Instance robustness insists on a smooth degradation in
performance as a function of the change. Ideally, the performance is never
worse than worst-case bounds. This also allows predictions to be objectively
compared.
We design online algorithms with predictions for a network flow allocation
problem and restricted assignment makespan minimization. For both problems, two
key properties are established: high quality predictions can be learned from a
small sample of prior instances and these predictions are robust to errors that
smoothly degrade as the underlying problem instance changes.

本文提出了一种新的模型来增强算法的预测能力，该模型要求算法具有形式上可学性和实例鲁棒性；通过构造在线可学习算法，为网络流量分配问题和受限指派最小化问题提供高质量的预测性能，并证明了这些预测对少量训练实例的数据具有鲁棒性。