3.2.1 鲁棒性
机器学习的鲁棒性问题一直是其实际应用的主要挑战。与此同时，
我们迫切需要利用机器学习技术来改进传统仅针对最坏情况性能设计的算法。最近，一种带有预测的算法设计框架被提出。该框架利用机器学习所提供的额外信息，以实现鲁棒性需求。在这个新框架中，算法可以访问通过机器学习技术得到的不可信的预测器，并且需要在预先不了解预测器具体性能的情况下，同时实现有效利用预测器提供的信息和具备最坏情况性能保证（即鲁棒性）。实现这一目标需要考虑以下几个关键环节：针对具体问题，利用机器学习方法从历史数据中得到对未来数据本身或最优解的预测器。针对研究问题，综合考虑预测器的特点，设计一种对预测器误差的衡量方法。根据误差衡量和预测器所提供的信息，对已有具备最坏情况保证的算法进行改造，以在不牺牲最坏情况保证的前提下，充分利用预测器的信息。这一步是整个框架的重点和技术难点，需要综合具体问题、算法、预测器以及误差衡量的结构和性质来进行设计，因此需要具体问题具体分析。通过有机地结合这些步骤，我们可以获得一种新的高效鲁棒算法，该算法可以有效地利用机器学习预测，同时保证鲁棒性。这一创新性框架为克服机器学习应用中的鲁棒性难题，并提高传统算法的性能，带来了新的可能性。
这一框架一经提出，便受到广泛认可和应用，在短短 3 年多时间内，已经受到了国际上诸多知名学者的关注。相比之下，国内在这一领域的研究处于相对起步阶段。然而，这个方向与传统算法研究有很多交叉点，与工业界的需求紧密结合，并正在成为国际上的研究热点和国内新兴方向，具有广阔的研究前景。
目前带预测的算法框架主要被用于研究在线问题，但它也可被用于提高非在线问题的算法性能，例如算法的运行时间或近似比。传统的“超越最坏情况分析”为了提升近似算法的性能，往往考虑的是一些特殊的图或平均情形的图。然而，带有预测的算法在最坏情况下，如果加上合适的预测，可以改进算法的近似比。