nips nips2012 nips2012-13 nips2012-13-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Pedro Ortega, Jordi Grau-moya, Tim Genewein, David Balduzzi, Daniel Braun
Abstract: We propose a novel Bayesian approach to solve stochastic optimization problems that involve finding extrema of noisy, nonlinear functions. Previous work has focused on representing possible functions explicitly, which leads to a two-step procedure of first, doing inference over the function space and second, finding the extrema of these functions. Here we skip the representation step and directly model the distribution over extrema. To this end, we devise a non-parametric conjugate prior based on a kernel regressor. The resulting posterior distribution directly captures the uncertainty over the maximum of the unknown function. Given t observations of the function, the posterior can be evaluated efficiently in time O(t2 ) up to a multiplicative constant. Finally, we show how to apply our model to optimize a noisy, non-convex, high-dimensional objective function.
[1] E. Brochu, V. Cora, and N. de Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. Technical Report TR-2009-023, University of British Columbia, Department of Computer Science, 2009.
[2] K. Rawlik, M. Toussaint, and S. Vijayakumar. Approximate inference and stochastic optimal control. arXiv:1009.3958, 2010.
[3] A. Shapiro. Probabilistic Constrained Optimization: Methodology and Applications, chapter Statistical Inference of Stochastic Optimization Problems, pages 282–304. Kluwer Academic Publishers, 2000.
[4] H.J. Kappen, V. G´ mez, and M. Opper. Optimal control as a graphical model inference probo lem. Machine Learning, 87(2):159–182, 2012.
[5] H.J. Kushner and G.G. Yin. Stochastic Approximation Algorithms and Applications. SpringerVerlag, 1997.
[6] J. Mockus. Application of bayesian approach to numerical methods of global and stochastic optimization. Journal of Global Optimization, 4(4):347–365, 1994.
[7] D. Lizotte. Practical Bayesian Optimization. Phd thesis, University of Alberta, 2008.
[8] D.R. Jones, M. Schonlau, and W.J. Welch. Efficient global optimization of expensive blackbox functions. Journal of Global Optimization, 13(4):455–492, 1998.
[9] M.A. Osborne, R. Garnett, and S.J. Roberts. Gaussian processes for global optimization. In 3rd International Conference on Learning and Intelligent Optimization (LION3), 2009.
[10] N. Srinivas, A. Krause, S. Kakade, and M. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In International Conference on Machine Learning, 2010.
[11] T. Hastie, R. Tbshirani, and J. Friedman. The Elements of Statistical Learning. Springer, second edition, 2009.
[12] P.A. Ortega and D.A. Braun. A minimum relative entropy principle for learning and acting. Journal of Artificial Intelligence Research, 38:475–511, 2010.
[13] B.C. May and D.S. Leslie. Simulation studies in optimistic Bayesian sampling in contextualbandit problems. Technical Report 11:02, Statistics Group, Department of Mathematics, University of Bristol, 2011. 9