Algorithm portfolios for noisy optimization

DOI10.1007/S10472-015-9486-2MaRDI QIDQ276539zbMATH OpenOpenAlexFDO

Authors Marie-Liesse Cauwet, Jialin Liu, Baptiste Rozière, Olivier Teytaud

Publication date 4 May 2016

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.01277

zbMATH Keywords

algorithm selectionblack-box noisy optimizationportfolio algorithmssimple regret

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Abstract: Noisy optimization is the optimization of objective functions corrupted by noise. A portfolio of solvers is a set of solvers equipped with an algorithm selection tool for distributing the computational power among them. Portfolios are widely and successfully used in combinatorial optimization. In this work, we study portfolios of noisy optimization solvers. We obtain mathematically proved performance (in the sense that the portfolio performs nearly as well as the best of its solvers) by an ad hoc portfolio algorithm dedicated to noisy optimization. A somehow surprising result is that it is better to compare solvers with some lag, i.e., propose the current recommendation of best solver based on their performance earlier in the run. An additional finding is a principled method for distributing the computational power among solvers in the portfolio.

Recommendations

• Algorithm portfolios
• Portfolio approaches for constraint optimization problems
• Advanced Portfolio Techniques
• scientific article; zbMATH DE number 2013531
• Automatic construction of optimal static sequential portfolios for AI planning and beyond

Cites work

• scientific article; zbMATH DE number 3431710 (Why is no real title available?)
• 10.1162/153244303321897663
• A self-adaptive multi-engine solver for quantified Boolean formulas
• A sublinear-time randomized approximation algorithm for matrix games
• Adaptive stochastic approximation by the simultaneous perturbation method
• Algorithm portfolios for noisy optimization
• Asymptotically efficient adaptive allocation rules
• Combinatorial search: from algorithms to systems
• Confronting hardness using a hybrid approach
• Differential evolution -- a simple and efficient heuristic for global optimization over continuous spaces
• Feedback and Weighting Mechanisms for Improving Jacobian Estimates in the Adaptive Simultaneous Perturbation Algorithm
• Hybrid regression-classification models for algorithm selection
• Learning dynamic algorithm portfolios
• Log-linear convergence and divergence of the scale-invariant \((1+1)\)-ES in noisy environments
• Lower rate of convergence for locating a maximum of a function
• Pure exploration in multi-armed bandits problems
• Recent progress in unconstrained nonlinear optimization without derivatives
• SATzilla: portfolio-based algorithm selection for SAT
• Simple and cumulative regret for continuous noisy optimization
• Stochastic Approximation of Minima with Improved Asymptotic Speed

Cited in

(4)

• Sorting by swaps with noisy comparisons
• Algorithm portfolios for noisy optimization
• Algorithm portfolios
• Learning parallel portfolios of algorithms

Describes a project that uses

Uses Software

• SATzilla
• DFO

This page was built for publication: Algorithm portfolios for noisy optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q276539)