A recent development in Bayesian optimization is the use of local optimization strategies, which can deliver strong empirical performance on high-dimensional problems compared to traditional global strategies. The folk wisdom in the literature is that the focus on local optimization sidesteps the curse of dimensionality; however, little is known concretely about the expected behavior or convergence of Bayesian local optimization routines. We first study the behavior of the local approach, and find that the statistics of individual local solutions of Gaussian process sample paths are surprisingly good compared to what we would expect to recover from global methods. We then present the first rigorous analysis of such a Bayesian local optimization algorithm recently proposed by Müller et al. (2021), and derive convergence rates in both the noisy and noiseless settings.

A recent development in Bayesian optimization is the use of local optimization strategies, which can deliver strong empirical performance on high-dimensional problems compared to traditional global strategies. The "folk wisdom" in the literature is that the focus on local optimization sidesteps the curse of dimensionality; however, little is known concretely about the expected behavior or convergence of Bayesian local optimization routines. We first study the behavior of the local approach, and find that the statistics of individual local solutions of Gaussian process sample paths are surprisingly good compared to what we would expect to recover from global methods. We then present the first rigorous analysis of such a Bayesian local optimization algorithm recently proposed by Müller et al. (2021), and derive convergence rates in both the noisy and noiseless settings.

Agents and market mechanisms are widely elaborated and applied to automate interaction and decision processes among others in robotics, for decentralized control in sensor networks and by algorithmic traders in financial markets. Currently there is a high demand of efficient mechanisms for the provisioning, usage and allocation of distributed services in the Cloud. Such mechanisms and processes are not manually manageable and require decisions taken in quasi real-time. Thus agent decisions should automatically adapt to changing conditions and converge to optimal values. This paper presents a bidding strategy, which is capable of automating the bid generation and utility maximization processes of consumers and providers by the interaction with markets as well as to converge to optimal values. The bidding strategy is applied to the consumer side against benchmark bidding strategies and its behavior and convergence are evaluated in two market mechanisms, a centralized and a decentralized one.