重新思考离线数据驱动优化中的可学习性

黑盒优化（BBO）已得到广泛应用，但随着真实世界 BBO 问题日益复杂，进化算法和贝叶斯优化面临效率挑战。数据驱动优化通过从数据中学习来提高 BBO 算法的效率。离线数据驱动优化仅利用一组固定的历史评估来寻求高质量解，因此受到广泛关注，因为它不需要额外的在线评估。已提出许多离线优化方法，但一个根本问题仍未得到解答：什么样的可学习性足以支持离线优化？先前的理论研究表明，Probably Approximately Correct（PAC）可学习性并不足够，因为即使大多数区域都已被很好地学习，最优区域仍可能学得很差。在本文中，我们提出了依赖算法的可学习性，它只要求在优化器的轨迹上保持准确。我们证明，其值查询形式足以覆盖具有代表性的离散场景，包括用于子模最大化的 greedy 和局部搜索；而其一阶对应形式则足以支持凸最小化中的投影梯度下降。受这一概念启发，我们形式化了一个轨迹学习框架，由轨迹构建、轨迹建模和候选生成组成，并在此框架下分析了现有基于轨迹的方法。我们进一步提出 Uncertainty-aware Gradient-guided Trajectory Learning（UGTL），其构建反映合理搜索路径的局部连贯改进轨迹，使用条件扩散对其建模，并选择一个多样化的候选集。在五个 Design-Bench 任务上，UGTL 在 25 种方法中取得了最佳的总体平均排名，$3.1/25$。受控轨迹分析和跨架构替换验证表明，我们的轨迹构建在性能提升中发挥了重要作用。