Bayesian Optimization
Part I: Foundations
中文

Foundations

Bayesian optimization is built from a small number of mathematical tools, and this part builds each of them from the ground up for a reader who writes software but has not used probability since school. Probability gives uncertainty a number. Linear algebra gives a way to compute with many uncertain numbers at once. The Gaussian distribution is the one family of distributions that stays closed under every operation the book needs, so that conditioning on data, the central step of every later chapter, has an exact answer. Bayesian inference turns that step into learning, and information theory measures how much a single observation is worth.

Each chapter introduces one tool and immediately puts it to work. By the end of the part you will have derived, not just read, the formula that the next part turns into Gaussian process regression.

Readers fluent in probability and linear algebra can skim this part and return to individual sections when a later chapter points back to them.

Chapters in this part

  1. 1 Optimizing What You Cannot Write Down

    What makes an objective a black box, why each evaluation is precious, and why the answer is to model the objective and spend every evaluation where it teaches the most. A map of the book.

  2. 2 Probability as Bookkeeping for Uncertainty

    Probability as a budget of belief spread over possibilities: random variables, discrete and continuous distributions, and the two rules everything else follows from, the sum rule and the product rule. Bayes' rule falls out of them in one line, and expectation, variance, and independence complete the toolkit.

  3. 3 The Linear Algebra of Uncertainty

    Vectors, matrices as maps of space, positive definite matrices, eigenvectors, the Cholesky factorization, determinants, and block matrices: the linear algebra a Gaussian process needs, with a picture for each idea and a covariance matrix in three dimensions to show what two dimensions hide.

  4. 4 The Gaussian Distribution

    The one distribution the whole book runs on: its shape in one and many dimensions, why a linear map of a Gaussian is Gaussian and how that gives a sampler, and the conditioning formula, derived through the Schur complement, that Gaussian process regression applies unchanged.

  5. 5 Bayesian Inference

    Prior, likelihood, posterior, and predictive distribution, worked out exactly for a coin and then for a line and a plane. Why a point estimate cannot say where to look next, how the evidence weighs models, and why the posterior over a line's weights is the stepping stone to a posterior over whole functions.

  6. 6 Measuring Information

    Entropy, KL divergence, and mutual information, built from the surprise of a single outcome; Lindley's expected information gain for choosing what to ask next; and the information gain of a Gaussian process, whose maximum sets every regret bound in the book and grows quickly with the input dimension.

References for Part I

53 works cited across this part's chapters.

  1. Austin, D. E., Korikov, A., Toroghi, A., and Sanner, S. (2024a). Bayesian Optimization with LLM-Based Acquisition Functions for Natural Language Preference Elicitation. RecSys 2024 (arXiv v2). Ch. 5
  2. Balandat, M., Karrer, B., Jiang, D. R., Daulton, S., Letham, B., Wilson, A. G., and Bakshy, E. (2020). BoTorch: A Framework for Efficient Monte-Carlo Bayesian Optimization. Advances in Neural Information Processing Systems 33 (NeurIPS 2020). Ch. 2
  3. Bar-Hillel, M. (1980). The Base-Rate Fallacy in Probability Judgments. Acta Psychologica. Ch. 2
  4. Bayes, T. (1763). An Essay towards Solving a Problem in the Doctrine of Chances. Philosophical Transactions of the Royal Society of London. Ch. 2
  5. Bergstra, J., and Bengio, Y. (2012). Random Search for Hyper-Parameter Optimization. Journal of Machine Learning Research. Ch. 1
  6. Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. Ch. 2 Ch. 4 Ch. 5 Ch. 6
  7. Blitzstein, J. K., and Hwang, J. (2019). Introduction to Probability. Chapman and Hall/CRC. Ch. 2 Ch. 4
  8. Box, G. E. P., and Muller, M. E. (1958). A Note on the Generation of Random Normal Deviates. The Annals of Mathematical Statistics. Ch. 4
  9. Chaloner, K., and Verdinelli, I. (1995). Bayesian Experimental Design: A Review. Statistical Science. Ch. 6
  10. Chu, W., and Ghahramani, Z. (2005). Preference learning with Gaussian processes. Proceedings of the 22nd international conference on Machine learning - ICML '05. Ch. 5
  11. Cover, T. M., and Thomas, J. A. (2006). Elements of Information Theory. Wiley. Ch. 4 Ch. 6
  12. Cox, R. T. (1946). Probability, Frequency and Reasonable Expectation. American Journal of Physics. Ch. 2
  13. Ding, Y., Kim, M., Kuindersma, S., and Walsh, C. J. (2018). Human-in-the-Loop Optimization of Hip Assistance with a Soft Exosuit during Walking. Science Robotics. Ch. 2
  14. Doumont, C., Fan, D., Maus, N., Gardner, J. R., Moss, H., and Pleiss, G. (2026). We Still Don't Understand High-Dimensional Bayesian Optimization. AISTATS 2026 (best student paper). Ch. 5
  15. Frazier, P. I. (2018). A Tutorial on Bayesian Optimization. arXiv. preprint Ch. 1
  16. Gabry, J., Simpson, D., Vehtari, A., Betancourt, M., and Gelman, A. (2019). Visualization in Bayesian Workflow. Journal of the Royal Statistical Society Series A: Statistics in Society. Ch. 5
  17. Galton, F. (1886). Regression Towards Mediocrity in Hereditary Stature. The Journal of the Anthropological Institute of Great Britain and Ireland. Ch. 4
  18. Gardner, J. R., Pleiss, G., Bindel, D., Weinberger, K. Q., and Wilson, A. G. (2018). GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration. Advances in Neural Information Processing Systems 31 (NeurIPS 2018). Ch. 3
  19. Garnett, R. (2023). Bayesian Optimization. Cambridge University Press. Ch. 1
  20. Gelman, A., Carlin, J. B., Stern, H. S., Dunson, D. B., Vehtari, A., and Rubin, D. B. (2013). Bayesian Data Analysis. Chapman and Hall/CRC. Ch. 5
  21. Gigerenzer, G., and Hoffrage, U. (1995). How to Improve Bayesian Reasoning Without Instruction: Frequency Formats. Psychological Review. Ch. 2
  22. Golub, G. H., and Van Loan, C. F. (2013). Matrix Computations. Johns Hopkins University Press. Ch. 3
  23. González, J., Dai, Z., Damianou, A., and Lawrence, N. D. (2017). Preferential Bayesian Optimization. International Conference on Machine Learning. Ch. 1
  24. Hennig, P., and Schuler, C. J. (2012). Entropy Search for Information-Efficient Global Optimization. Journal of Machine Learning Research. Ch. 6
  25. Hernández-Lobato, J. M., Hoffman, M. W., and Ghahramani, Z. (2014). Predictive Entropy Search for Efficient Global Optimization of Black-box Functions. Advances in Neural Information Processing Systems 27 (NeurIPS 2014). Ch. 6
  26. Higham, N. J. (2002). Computing the Nearest Correlation Matrix: A Problem from Finance. IMA Journal of Numerical Analysis. Ch. 3
  27. Houlsby, N., Huszár, F., Ghahramani, Z., and Lengyel, M. (2011). Bayesian Active Learning for Classification and Preference Learning. arXiv. preprint Ch. 6
  28. Hvarfner, C., Hellsten, E. O., and Nardi, L. (2024). Vanilla Bayesian Optimization Performs Great in High Dimensions. International Conference on Machine Learning. Ch. 6
  29. Jaynes, E. T. (2003). Probability Theory: The Logic of Science. Cambridge University Press. Ch. 2
  30. Jones, D. R., Schonlau, M., and Welch, W. J. (1998). Efficient Global Optimization of Expensive Black-Box Functions. Journal of Global Optimization. Ch. 1
  31. Kahneman, D., and Tversky, A. (1973). On the Psychology of Prediction. Psychological Review. Ch. 2
  32. Kontsevich, L. L., and Tyler, C. W. (1999). Bayesian Adaptive Estimation of Psychometric Slope and Threshold. Vision Research. Ch. 6
  33. Kullback, S., and Leibler, R. A. (1951). On Information and Sufficiency. The Annals of Mathematical Statistics. Ch. 6
  34. Kushner, H. J. (1964). A New Method of Locating the Maximum Point of an Arbitrary Multipeak Curve in the Presence of Noise. Journal of Basic Engineering. Ch. 1
  35. Lindley, D. V. (1956). On a Measure of the Information Provided by an Experiment. The Annals of Mathematical Statistics. Ch. 6
  36. MacKay, D. J. C. (1992). Information-Based Objective Functions for Active Data Selection. Neural Computation. Ch. 6
  37. MacKay, D. J. C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Ch. 2 Ch. 5 Ch. 6
  38. Močkus, J. (1975). On Bayesian Methods for Seeking the Extremum. Optimization Techniques IFIP Technical Conference. Ch. 1
  39. Murphy, K. P. (2022). Probabilistic Machine Learning: An Introduction. MIT Press. Ch. 4
  40. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., … Lowe, R. (2022). Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems. Ch. 6
  41. Petersen, K. B., and Pedersen, M. S. (2012). The Matrix Cookbook. Technical University of Denmark. non-peer-reviewed Ch. 3 Ch. 4
  42. Rasmussen, C. E., and Williams, C. K. I. (2006). Gaussian Processes for Machine Learning. MIT Press. Ch. 3 Ch. 4 Ch. 5
  43. Sanderson, G. (2016). Essence of Linear Algebra. Video series, 3Blue1Brown. non-peer-reviewed Ch. 3
  44. Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and de Freitas, N. (2016). Taking the Human Out of the Loop: A Review of Bayesian Optimization. Proceedings of the IEEE. Ch. 1
  45. Shannon, C. E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal. Ch. 6
  46. Snoek, J., Larochelle, H., and Adams, R. P. (2012). Practical Bayesian Optimization of Machine Learning Algorithms. Advances in Neural Information Processing Systems 25 (NeurIPS 2012). Ch. 1 Ch. 3 Ch. 4
  47. Snoek, J., Rippel, O., Swersky, K., Kiros, R., Satish, N., Sundaram, N., … Adams, R. P. (2015). Scalable Bayesian Optimization Using Deep Neural Networks. Proceedings of the 32nd International Conference on Machine Learning (ICML 2015). Ch. 5
  48. Srinivas, N., Krause, A., Kakade, S. M., and Seeger, M. (2010). Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. ICML 2010. Ch. 6
  49. Strang, G. (2016). Introduction to Linear Algebra. Wellesley-Cambridge Press. Ch. 3
  50. Thompson, W. R. (1933). On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika. Ch. 5
  51. Vakili, S., Khezeli, K., and Picheny, V. (2021a). On Information Gain and Regret Bounds in Gaussian Process Bandits. International Conference on Artificial Intelligence and Statistics. Ch. 6
  52. Wang, Z., and Jegelka, S. (2017). Max-value Entropy Search for Efficient Bayesian Optimization. Proceedings of the 34th International Conference on Machine Learning (ICML 2017). Ch. 6
  53. Watson, A. B., and Pelli, D. G. (1983). QUEST: A Bayesian Adaptive Psychometric Method. Perception & Psychophysics. Ch. 6