Learning to Optimize Computational Resources: Frugal Training with Generalization Guarantees
This work provides a solution for practitioners in fields like integer programming and clustering to automate parameter tuning, reducing tedious manual effort, though it builds incrementally on existing research.
The paper tackles the problem of tuning algorithm parameters to optimize computational resources, presenting an algorithm that learns a finite set of promising parameters from an infinite set, addressing limitations of prior data-independent discretization methods.
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 recent line of research provides algorithms that return nearly-optimal parameters from within a finite set. These algorithms can be used when the parameter space is infinite by providing as input a random sample of parameters. This data-independent discretization, however, might miss pockets of nearly-optimal parameters: prior research has presented scenarios where the only viable parameters lie within an arbitrarily small region. We provide an algorithm that learns a finite set of promising parameters from within an infinite set. Our algorithm can help compile a configuration portfolio, or it can be used to select the input to a configuration algorithm for finite parameter spaces. Our approach applies to any configuration problem that satisfies a simple yet ubiquitous structure: the algorithm's performance is a piecewise constant function of its parameters. Prior research has exhibited this structure in domains from integer programming to clustering.