A surrogate function is a simpler function than the objective function to evaluate. An acquisition function is used to propose sampling points.
In the context of Bayesian optimisation and Gaussian processes, what's the intuition behind the acquisition function and the surrogate function? How are these functions related?
I think of an acquisition function as describing the utility of the point to be evaluated next in the Bayesian optimization framework.
To give more details, let's think about the general concept of Bayesian Optimization and the setting in which it is usually applied. Consider a black-box function $f$ which is expensive to evaluate and we want to find the optimal point of $f$ over a search space $X$ with minimum number of function evaluations. Since $f$ is blackbox, we model $f$ with a Gaussian process(GP) based on some assumptions(captured in the type of kernel(rbf, periodic, etc.)) and update the GP iteratively based on new function($f$) evaluations. Therefore, GP acts a cheap surrogate for $f$.
Following is a pseudo code for the complete process:
Intialize a GP model $M$
For maximum number of iterations allowed:
Find next point to evaluate($x^*$)
Update GP based on $x^*$
return the best evaluated point as the optimal point
All parts other than 'Find next point to evaluate($x^*$)' are straightforward here. Now, how should we pick this point for evaluating the function at each iteration. One idea is to pick it randomly from the search space but that doesn't seem really insightful. Remember our GP learns more and more about the function as we evaluate more points. Therefore, we should somehow utilize this information contained in the GP to pick the next point. Here comes the acquisition function! An acquisition function utilizes the GP's information to find the utility of a point to be evaluated next in the above process. Intuitively, we can think of an acquisition function trying to figure out the value of points in $X$ as the "potential optimal point" based on the information contained in GP.
Let's try to come up with an acquisition function ourselves. GPs allows us to compute the predictive mean $\mu(x)$ of a point $x$ in the search space $X$. Should we go ahead and pick the point with maximum $\mu$ then? No, this will result in over confidence in the current state of our GP. Remember, our GP is learning more about the function as we evaluate more points. We should account for the fact that the current $\mu$ might be a bad approximation of the value of some points. This is captured by the predictive variance $\sigma(x)$ given by the GP. Therefore, we should also allow our acquisition function to explore a bit. Let's make a trade-off between $\mu$ and $\sigma$ with a parameter $\beta$. And there we have it, an acquisition function given as $\mu(x)+ \beta \sigma(x)$. This is one of the most popular acquisition function in BO known as GP-UCB[1].
Some of the arguments might be handwavy here but they were mostly meant for intuition and not technical rigor.
[1]. Srinivas et al., Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design (https://arxiv.org/pdf/0912.3995.pdf)
