A major technique in learning-augmented online algorithms is combining
multiple algorithms or predictors. Since the performance of each predictor may
vary over time, it is desirable to use not the single best predictor as a
benchmark, but rather a dynamic combination which follows different predictors
at different times. We design algorithms that combine predictions and are
competitive against such dynamic combinations for a wide class of online
problems, namely, metrical task systems. Against the best (in hindsight)
unconstrained combination of $\ell$ predictors, we obtain a competitive ratio
of $O(\ell^2)$, and show that this is best possible. However, for a benchmark
with slightly constrained number of switches between different predictors, we
can get a $(1+\epsilon)$-competitive algorithm. Moreover, our algorithms can be
adapted to access predictors in a bandit-like fashion, querying only one
predictor at a time. An unexpected implication of one of our lower bounds is a
new structural insight about covering formulations for the $k$-server problem.

本文阐述了一种基于多种算法或预测器的学习增强在线算法技术，通过针对在线问题的分析，设计出与动态组合相竞争的算法，能够在多种预测器之间切换，具有灵活性和实用性。

在线度量算法的混合预测

Mixing predictions for online metric algorithms

The emerging field of learning-augmented online algorithms uses ML techniques
to predict future input parameters and thereby improve the performance of
online algorithms. Since these parameters are, in general, real-valued
functions, a natural approach is to use regression techniques to make these
predictions. We introduce this approach in this paper, and explore it in the
context of a general online search framework that captures classic problems
like (generalized) ski rental, bin packing, minimum makespan scheduling, etc.
We show nearly tight bounds on the sample complexity of this regression
problem, and extend our results to the agnostic setting. From a technical
standpoint, we show that the key is to incorporate online optimization
benchmarks in the design of the loss function for the regression problem,
thereby diverging from the use of off-the-shelf regression tools with standard
bounds on statistical error.

本文介绍了在学习增强的在线算法中使用回归技术来预测未来输入参数的方法，并在广义滑雪租赁、装箱问题、最小完成时间调度等一般在线搜索方案的背景下探讨了这种方法。通过在设计回归问题的损失函数中结合在线优化基准，我们显示了这种回归问题样本复杂度的近似上下界，并将我们的结果扩展到了不可知设置。