ImpatientCapsAndRuns: Approximately Optimal Algorithm Configuration from an Infinite Pool
Algorithm configuration procedures optimize parameters of a given algorithm to perform well over a distribution of inputs. Recent theoretical work focused on the case of selecting between a small number of alternatives. In practice, parameter spaces are often very large or infinite, and so successful heuristic procedures discard parameters ``impatiently'', based on very few observations. Inspired by this idea, we introduce ImpatientCapsAndRuns, which quickly discards less promising configurations, significantly speeding up the search procedure compared to previous algorithms with theoretical guarantees, while still achieving optimal runtime up to logarithmic factors under mild assumptions. Experimental results demonstrate a practical improvement.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Utilitarian Algorithm Configuration for Infinite Parameter Spaces
Utilitarian algorithm configuration is a general-purpose technique for automatically searching the parameter space of a given algorithm to optimize its performance, as measured by a given utility function, on a given set…
Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees
Algorithms typically come with tunable parameters that have a considerable impact on the computational resources they consume. Too often, practitioners must hand-tune the parameters, a tedious and error-prone task. A rec…
ClusteringExploring $k$ out of Top $ρ$ Fraction of Arms in Stochastic Bandits
This paper studies the problem of identifying any $k$ distinct arms among the top $\rho$ fraction (e.g., top 5\%) of arms from a finite or infinite set with a probably approximately correct (PAC) tolerance $\epsilon$. We…
LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration
We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on average…
LeapsAndBounds: A Method for Approximately Optimal Algorithm Configuration
We consider the problem of configuring general-purpose solvers to run efficiently on problem instances drawn from an unknown distribution. The goal of the configurator is to find a configuration that runs fast on av…