May, 2024

无尽参数空间的功利算法配置

PDF
TL;DR通用的功利算法配置是一种自动搜索给定算法的参数空间以优化其在给定输入集上通过给定效用函数度量的性能的技术。最近引入的功利配置过程提供了关于返回的参数化的最优性保证，同时可证明适应了底层问题的困难程度。然而，这些方法的适用范围受到严重限制，因为它们只搜索了有限的、相对较小的参数集。它们无法有效地搜索具有连续或不可数参数的算法配置空间。在本文中，我们引入了一种新的方法，将其称为 COUP（连续、乐观的功利拖延）。COUP 旨在高效地搜索无限参数空间以快速找到良好的配置。此外，当应用于有限参数空间时，COUP 仍然保持之前功利配置过程的理论优势，但在速度上有明显提升，无论是从理论上还是实验证明。
发现论文，激发创造
  • 功利主义算法配置

    我们提出了第一个非平凡的程序，用于配置启发式算法以最大化其为最终用户提供的效用，并同时提供关于性能的理论保证。我们展示了实用目标也带来了相当大的算法好处，在平均运行时间最小化无法捕捉到算法设计者的偏好的情况下表现出更好的性能。本文基于此思想描述了有效且具有理论基础的配置程序，并在理论下界类似的情况下证明了这些程序的运行时间上界，同时通过实验证明了它们的性能。

    Oct, 2023

  • 算法配置中的注意事项与最佳实践

    研究自动化算法配置的困境及解决方案，提出了避免实验设计问题和达到最新性能的最佳实践，并介绍了可处理多个问题的工具 GenericWrapper4AC。

    May, 2017

  • 算法配置问题

    算法优化领域已经通过自动配置算法参数的方法显著进展。本文深入研究了算法配置问题，重点优化针对特定决策 / 优化问题实例的参数化算法。我们提出了一个全面的框架，不仅形式化了算法配置问题，还概述了利用机器学习模型和启发式策略解决该问题的不同方法。本文将已有的方法论分为按实例和按问题的方法，并区分了模型构建和部署的离线和在线策略。通过综合这些方法，我们旨在为理解和应对算法配置中固有的复杂性提供清晰的路径。

    Mar, 2024

  • 自动算法配置中的性能估计

    本文探讨了自动算法配置 (AAC) 中的性能估计问题，首先证明了在实际设置中的通用最佳性能估计器，然后分别考虑了有限和无限配置空间，建立了估计误差的理论界限，并在四个涉及不同问题领域的算法配置情景中进行了广泛的实验验证。此外，本文还提出了加强现有 AAC 方法的见解。

    Nov, 2019

  • 正式化运行时分布的偏好

    该论文旨在通过形式化运行时分布的喜好来解决在算法选择中的竞争。我们提出了一种基于效用理论的方法，描述了算法偏好的评分函数，这些函数依赖于解决问题的价值如何随时间降低以及满足的时间分布。我们展示了实用程序函数的例子，并展示了如何利用最大熵方法来建模未规定的时间分布，最后，我们展示了如何从运行时样本中高效估计算法的预期效用。

    May, 2022

  • 基于模型算法配置的热启动

    提出一种基于预测模型的算法配置方法，利用算法在先前基准测试的性能信息来对新类型的基准测试进行热启动配置，实验证明相较于现有的算法配置方法，该方法在优化硬组合问题求解器时可大幅提升速度（最高可达 165 倍），同时可以在相同的计算预算下找到更好的配置。

    Sep, 2017

  • 通过概率重参数化实现离散和混合空间的贝叶斯优化

    利用概率重参数化方法（PR）在混合或高基数离散搜索空间中最大化收购功能（AF），可显著提高贝叶斯优化（BO）的优化表现，并且能够很自然地扩展到具有多个目标和黑盒约束的设置。

    Oct, 2022

  • ParamILS: 自动算法配置框架

    本文描述了一种自动化算法配置框架，其中提供了用于通过变化一组序数和 / 或分类参数来优化目标算法在给定问题实例类上的性能的方法，并提供了用于加速本地搜索的算法配置过程的新技术，同时通过对 SAT 的完整和不完整算法进行配置，评估了我们方法的结果，同时还提供了关于自动配置 CPLEX 混合整数规划求解器的首个已知结果。

    Jan, 2014

  • 组合分区问题算法配置的学习理论基础

    本研究提出了一种针对各种划分问题的机器学习算法，通过样本学习来获得适合特定应用场景的算法配置，同时也为算法配置的基础和学习理论的发展做出了贡献。

    Nov, 2016

  • 基于最小极大遗憾的广义可加效用引出

    在该研究中，我们使用最小化最大后悔标准描述了提取广义加性独立效用的语义基础，并提出了若干新的查询类型和策略；通过利用模型中的局部 GAI 结构，实现了计算可行性；所得结果提供了实现基于偏好的受限配置优化以及在多属性产品数据库中进行有效搜索的实用方法。

    Jun, 2012