一种应用特定算法选择的 PAC 方法

Nov, 2015

一种应用特定算法选择的 PAC 方法

A PAC Approach to Application-Specific Algorithm Selection

Rishi Gupta, Tim Roughgarden

TL;DR本文使用统计和在线学习理论的概念来分析特定应用领域下的算法选择问题，并将算法选择建模为统计学习问题，同时研究了在线算法选择问题的可能性和不可能性结果。

Abstract

The best algorithm for a computational problem generally depends on the "relevant inputs," a concept that depends on the application domain and often defies formal articulation. While there is a large literature on empirical approaches to selecting the best algorithm for a given applic

algorithm selection empirical approaches online learning statistical learning theory computational problem

发现论文，激发创造

自动算法选择：调研和视角

该文概述了自动算法选择的研究，涵盖离散问题和连续问题的应用，并讨论算法配置、调度或组合选择等相关方法。此外，文章还提供了离散问题和连续问题的问题实例特征概述，并对未来的工作进行了展望，讨论了许多开放性的研究挑战。

Nov, 2018

组合搜索问题的算法选择：综述

该论文综述了算法选择问题的研究现状及其在组合搜索问题中的性能提升，归纳了目前算法选择的多种方法并且讨论了使用这些方法的不同方向，最后总结出未来研究的方向。

Oct, 2012

节约型算法选择

从 ASLib 中的六个数据集中评估了三种方法：基于预测不确定性的主动学习、使用超时预测器增强算法预测器以及使用逐步增加超时的方式收集训练数据，并展示了每个选项所实现的标记成本的降低。

May, 2024

算法运行时间预测：方法与评估

利用机器学习建模算法的运行时间，对算法分析、自动参数配置等方面有重要应用，本文针对命题可满足性、旅行商问题和混合整数规划等问题，介绍了新的模型和特征，与文献中各种运行时间建模技术进行比较，实证表明本文新模型相比以往方法，具有更好的泛化性和预测准确度。

Nov, 2012

解锁算法特性的力量：算法选择的推广分析

通过算法特征以及一般化观点，我们提出了基于算法特征的算法选择具有可证的保证的第一个模型，并分析了几个因素对一般化误差的影响。我们证明了在复杂的多算法场景中，基于算法特征的模型在一般化方面优于仅依赖问题特征的传统模型，并在分布变化的场景中表现出正相关的一般化误差和训练集与测试集之间的卡方距离。

May, 2024

基于组合投资算法选择的泛化性能

本文探讨了基于组合算法选择的一个有效算法配置过程，分析了三种情况可能导致多样性的算法集合与性能预测之间的差距，提出了一种 end-to-end 的学习理论分析集合组合与算法选择的方法，并通过实验证明个体算法选择器的复杂性和算法性能的学习理论复杂性将会对方案的性能产生重要影响。

Dec, 2020

近似计算调查，第二部分：特定应用和架构近似技术和应用

近十年来，近似计算作为一种新兴解决方案，在设计系统时调整结果质量以提高能源效率和 / 或性能的范式转变引起了学术界和工业界的关注。本研究通过两部分调研，覆盖了近似计算的关键方面（如术语和应用）以及从传统计算堆栈的各个层次（从系统到集成电路）的最新近似技术。在调研的第二部分中，我们对应用特定和架构近似技术进行了分类和详细介绍，这两者都旨在设计资源高效的处理器 / 加速器和系统。此外，我们还详细分析了近似计算的应用领域，并讨论了未来的挑战和发展方向。

Jul, 2023

带有预测的算法学习

介绍了一种算法设计范例 —— 基于学习预测器的算法，将在线学习技术应用于预测器学习、调整鲁棒性 - 一致性折中并绑定样本复杂度，在构建优美的预测器的同时，在二分图匹配、滑雪租赁、页面迁移和作业调度等多场景中优化了多个现有结果，且提供了第一批基于学习理论的担保。

Feb, 2022

论算法选择中探测轨迹的效用

使用机器学习方法来选择算法通常将描述一个实例的数据作为输入，我们提出了一种新颖的基于算法的方法来描述实例，该方法使用短的探测轨迹来训练算法选择模型，并且在计算效率和结果方面比传统的基于特征的方法更有前景。

Jan, 2024

PAC-Bayesian 学习初探

本文对 PAC-Bayes 框架及其主要理论和算法发展进行了自包含的调查研究。

Jan, 2019