Surrogate Functions

In some optimizations problems, the objective-function is just too complicated to evaluate directly at every iteration, and in this case, we use surrogate functions, functions that mimic most of the properties of the true objective-function, but that is much simpler analytically and/or computationally.

Lately, I have done some thinking about what properties a surrogate function (or surrogate model) should have to be practical.

The Wikipedia on surrogate models is informative, but leaves many questions opened.

For example, should a surrogate function have its derivative’s zeroes in the same place as the real function’s derivative? Should it have its derivative’s signs match the signs of the real function’s derivatives?

In some cases, it’s quite possible to do have such a surrogate function. Let’s suppose you need to know, not the exact distance, but which points on a sphere is further than an other. If you’re dealing with the unit sphere centered on (0,0,0) and points expressed as x, y, z, coordinates also centered on (0,0,0), then if u is a point and v another, \cos^{-1}(u^Tv) is the distance between u and v as measured on the sphere.

But let’s pretend that, for some reason, \cos^{-1}(u^Tv) is troublesome to compute. We will want to use the surrogate \|u-v\|, the L_2, or Euclidean distance, between the two points u and v.

The surrogate \|u-v\| is well behaved, relative to \cos^{-1}(u^Tv). As for \cos^{-1}(u^Tv), if you rotate u around v, \|u-v\| is unchanged. If you bring u closer to v (while remaining on the sphere), both decrease—while not a the same rate. If you push u further from v, both grow—again not at the same rate.

The figure illustrates the regions:

*
* *

So \|u-v\| behaves mostly as \cos^{-1}(u^Tv), and, by hypothesis, is much easier to compute (if a square root is a lot less costly to compute than arccos, which remains to be seen). For many algorithms, \|u-v\| could be used as a cromulent surrogate.

This is of course a rather simple example of surrogate, and I wonder how much one can build into the surrogate. What are the conditions for a surrogate to be well-behaved? What does it even mean to be well-behaved?

I searched a bit but found precious little on the topic. I now uncompunctiously ask from you, reader, to hint me, to suggest me books, articles, or any resources on the topic.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 73 other followers

%d bloggers like this: