Similarity-based Portfolio Construction for Black-box Optimization
New k-nearest-neighbor approach constructs algorithm portfolios that outperform single-solver methods by 15-20%.
A team of researchers from the Netherlands and France has developed a novel approach to black-box optimization that moves beyond selecting a single algorithm. In their paper "Similarity-based Portfolio Construction for Black-box Optimization," Catalin-Viorel Dinu, Diederick Vermetten, and Carola Doerr address a fundamental challenge: when facing an unknown optimization problem, how do you choose which algorithm to use? Their solution involves creating portfolios of algorithms rather than betting everything on one solver.
Traditional algorithm selection carries inherent risks—even well-performing algorithms can fail on specific instances due to variance or poor fit. The researchers show that splitting evaluation budgets across multiple algorithms in a portfolio provides natural variance reduction and leverages complementary strengths between different solvers. Their key innovation is a k-nearest-neighbor-based finetuning approach that constructs portfolios tailored to specific unseen problem instances by analyzing similarity to training data.
The method works by first identifying problems similar to the target instance from a training set, then constructing an optimal portfolio based on what worked well on those similar problems. This approach outperforms even the "virtual best solver" baseline—an idealized selector that always picks the single best algorithm for each problem. The portfolio method proves particularly effective in fixed-budget scenarios common in real-world applications, where computational resources are limited and reliability matters more than theoretical peak performance.
This research has significant implications for AI development workflows, particularly in areas like hyperparameter optimization, neural architecture search, and automated machine learning pipelines. By providing a more robust approach to algorithm selection, it could lead to more reliable and efficient optimization processes across scientific computing, engineering design, and AI system development.
- Portfolio approach splits evaluation budgets across multiple algorithms instead of selecting single solver
- k-nearest-neighbor method tailors portfolios to specific unseen problems by analyzing similarity to training data
- Outperforms traditional single-algorithm selection and virtual best solver baseline in fixed-budget scenarios
Why It Matters
Enables more reliable AI optimization for hyperparameter tuning, neural architecture search, and scientific computing applications.