| HN Mirror

There's a couple different points there, so lemme see if I can answer each of them.

First off, the use of the term "kernel trick" appears, I think, primarily within the machine learning community. It refers to the idea that some other (likely more useful) representation of the data of interest exists, but that the representation might be in a much larger, or even infinite-dimensional, space. Fortunately, in the context of certain algorithms such as support vector machines, that representation never appears by itself ... it only appears when inner-producted (not a word) with another such representation associated with some other piece of data. For certain representations, that inner product can be represented by a reproducing (also called positive definite) kernel, and thus can be computed without ever forming the larger representation. This concept appears in Wikipedia https://en.wikipedia.org/wiki/Reproducing_kernel_Hilbert_spa..., both for the Hilbert space inner product and for the Mercer's series representation. Unfortunately, as is the case with a lot of higher math on Wikipedia, it's more useful as a reference for an expert than to get you rolling on a new topic.

As far as kernel methods in general, those pop up all over the place, including in the context of Gaussian processes. Gaussian process regression (GPR), also called kernel-based approximation in the numerical analysis community, is one great example of that. I generally try to think of it not as an infinite dimensional linear regression method, but rather as a constrained optimization problem. There are infinitely many functions that pass through a given set of data, thus asking for the "one" is ill-posed ... I am interested in the most well-behaved one. We define the behavior of a function as its RKHS-norm, and the function that minimizes that norm, but still respects the observed data, is the solution to the GPR problem.

Regarding why SigOpt performs better than a good old-fashioned grid, that can be for multiple reasons. Probably the most important one, at least in my mind, is that SigOpt is not trying to create some perfect model of the function at hand - SigOpt is only interested in optimizing that function. That drives every decision we make, and actually it is something I often need to remind myself of because I grew up in approximation theory. A basic design of experiments is interested in understanding how the function works everywhere, but we can save some expense by more swiftly discarding regions unlikely to contain the optimum.

As far as why RKHS in particular work very well - that deals with the optimality theorems underlying approximation using reproducing kernels. Assuming you have a reasonable function on a reasonable domain it probably belongs to a RKHS - such functions can be represented very effectively by an appropriate kernel. Now, determining that kernel can be a complicated task (maximum likelihood estimation or cross-validation are common tools) but if you have an acceptable kernel you can make strong statements about the quality of the model. Because the quality of the model is constantly improving, the GP-backed optimization tool is constantly providing a better representation of the true function, and thus pointing towards the optimum more quickly.

There's another more fundamental reason why searching on a grid in higher dimensions is trouble, and it deals with the fact that the ratio of the volume of a sphere and of a cube with the same radius decreases as the dimension increases. This means that there is increasingly much volume away from the center of a box in increasingly many dimensions. Using a grid to try and fill that space becomes unacceptably costly. Of course, Gaussian processes have their own issues for larger problems (>30 dimensions, maybe) but SigOpt has more than just Gaussian processes behind the scenes. Also, there have been improvements over the years in GP performance in higher dimensions (for example, http://epubs.siam.org/doi/abs/10.1137/10080138X).

There's some pretty solid notes for graduate students on this topic at http://math.iit.edu/~fass/590/. That was the class I took to first learn this stuff as a student and I've tried to contribute back to them over the years. It comes at the topic first from the math side, not the stats side, but there's some stats stuff in there as well. Chapter 8 of those slides contains that theorem regarding the minimum-norm interpolant.

Hope that helps.