A Minimalist Bayesian Framework for Stochastic Optimization
This work addresses the challenge of incorporating complex constraints in Bayesian optimization for researchers and practitioners in machine learning, offering a more flexible approach, though it is incremental in refining existing methods.
The authors tackled the problem of Bayesian optimization's reliance on full probabilistic models by introducing a minimalist framework that places priors only on the component of interest, eliminating nuisance parameters via profile likelihood, and developed the MINTS algorithm with applications in structured problems like bandits and dynamic pricing, achieving near-optimal regret guarantees.
The Bayesian paradigm offers principled tools for sequential decision-making under uncertainty, but its reliance on a probabilistic model for all parameters can hinder the incorporation of complex structural constraints. We introduce a minimalist Bayesian framework that places a prior only on the component of interest, such as the location of the optimum. Nuisance parameters are eliminated via profile likelihood, which naturally handles constraints. As a direct instantiation, we develop a MINimalist Thompson Sampling (MINTS) algorithm. Our framework accommodates structured problems, including continuum-armed Lipschitz bandits and dynamic pricing. It also provides a probabilistic lens on classical convex optimization algorithms such as the center of gravity and ellipsoid methods. We further analyze MINTS for multi-armed bandits and establish near-optimal regret guarantees.