Cosmin G. Petra

Andrei Draganescu, Cosmin Petra

In this article we construct and analyze multigrid preconditioners for discretizations of operators of the form D+K* K, where D is the multiplication with a relatively smooth positive function and K is a compact linear operator. These systems arise when applying interior point methods to the minimization problem min_u (||K u-f||^2 +b||u||^2) with box-constraints on the controls u. The presented preconditioning technique is closely related to the one developed by Draganescu and Dupont in [11] for the associated unconstrained problem, and is intended for large-scale problems. As in [11], the quality of the resulting preconditioners is shown to increase with increasing resolution but decreases as the diagonal of D becomes less smooth. We test this algorithm first on a Tikhonov-regularized backward parabolic equation with box-constraints on the control, and then on a standard elliptic-constrained optimization problem. In both cases it is shown that the number of linear iterations per optimization step, as well as the total number of fine-scale matrix-vector multiplications is decreasing with increasing resolution, thus showing the method to be potentially very efficient for truly large-scale problems.

Jingyi Wang, Haowei Wang, Szu Hui Ng et al.

Expected improvement (EI) is one of the most widely used acquisition functions in Bayesian optimization (BO). Despite its proven empirical success in applications, the cumulative regret upper bound of EI remains an open question. In this paper, we analyze the classic noisy Gaussian process expected improvement (GP-EI) algorithm. We consider the Bayesian setting, where the objective is a sample from a GP. Three commonly used incumbents, namely the best posterior mean incumbent (BPMI), the best sampled posterior mean incumbent (BSPMI), and the best observation incumbent (BOI) are considered as the choices of the current best value in GP-EI. We present for the first time the cumulative regret upper bounds of GP-EI with BPMI and BSPMI. Importantly, we show that in both cases, GP-EI is a no-regret algorithm for both squared exponential (SE) and Matérn kernels. Further, we present for the first time that GP-EI with BOI either achieves a sublinear cumulative regret upper bound or has a fast converging noisy simple regret bound for SE and Matérn kernels. Our results provide theoretical guidance to the choice of incumbent when practitioners apply GP-EI in the noisy setting. Numerical experiments are conducted to validate our findings.