Lower Bounds on the Noiseless Worst-Case Complexity of Efficient Global Optimization.

Efficient global optimization is a widely used method for optimizing expensive black-box functions. In this paper, we study the worst-case oracle complexity of the efficient global optimization problem. In contrast to existing kernel-specific results, we derive a unified lower bound for the oracle complexity of efficient global optimization in terms of the metric entropy of a ball in its corresponding reproducing kernel Hilbert space. Moreover, we show that this lower bound nearly matches the upper bound attained by non-adaptive search algorithms, for the commonly used squared exponential kernel and the Matérn kernel with a large smoothness parameter ν. This matching is up to a replacement of d/2 by d and a logarithmic term logRϵ, where d is the dimension of input space, R is the upper bound for the norm of the unknown black-box function, and ϵ is the desired accuracy. That is to say, our lower bound is nearly optimal for these kernels.

Parametric polytope reconstruction, an application to crystal shape estimation.

In situ imaging techniques are a promising direction for monitoring the distribution of crystal sizes and shapes during a crystallization process. Nevertheless, no tractable method yet exists for estimating complex crystal shapes. In this paper, an in situ imaging setup is presented and a novel algorithm for crystal shape estimation from a pair of images is presented. It is shown that such a shape estimation problem can be turned into parametric polytope reconstruction from projections. Based on results in polyhedral geometry, it is demonstrated that an accurate estimate of the crystal shape can be computed by solving a nonlinear least-squares problem built from samples in images and a prior model of the crystal. Effectiveness of the approach is proven on artificial and real images. Results show that very accurate estimations of crystal shapes can be obtained from well-chosen data points sampled on images.