Minimize cost and maximize quality of function in four variables

Question

Problem: Find optimal values for four parameters which are used to tune an algorithm under the constraints of accuracy, time and memory.

I have an indexing scheme used to search for the K-nearest neighbors of a point in many dimensions. This indexing scheme has four adjustable parameters. For each given fixed problem size (total number of points, number of nearest neighbors to find, number of dimensions, desired accuracy) I plan to run a solver to find the optimal values for these four parameters. Here are the constraints:

1) If the accuracy is below desired accuracy (say 95%), prefer parameter values that maximize the accuracy.

2) Once the accuracy equals or exceeds the desired accuracy, prefer parameters that minimize the execution time.

3) Do not exhaust all system memory.

I handle #3 by restricting the one parameter that is directly proportional to memory usage based on numerous manual tests.

One of the parameters is discrete: it may only take on integer values. (This is the one that affects memory size).

Three of the parameters always move in the same direction as accuracy: as they increase, accuracy always remains the same or increases, up to a maximum of 100%. Each of these three parameters also moves in the same direction as cost: as they increase, the cost always increases (without bound).

The fourth parameter has the smallest (and least predictable) influence on cost. The accuracy will always decrease as you move farther away from the optimal value, either up or down.

Because of the 100% accuracy cutoff, the function has places with no derivative (is not smooth).

I have hundreds of combinations to optimize, varying # of dimensions versus # of points. My current approach runs all night without completing all the cases and produces erratic results (poor solver algorithm that gravitates toward high accuracy and horrible time cost). Given the nature of the constraints I have described and the number of parameters, which class of algorithms should I investigate? I understand the gradient method, but worry that it will perform poorly (too many steps) or not work with the non-smoothness of the function.

It might be possible to seed each successively larger case with the best results from the next smaller case; the parameter values should vary smoothly as the case sizes increase. the cost of evaluating the execution time and accuracy increases with the number of points and with the number of dimensions.

Current algorithm:

1) Start with seed values for each parameter, as determined after days of manual testing.

2) Holding all parameters fixed but one and varying that one, find its best value. Test values in increasing order, stopping when the accuracy is acceptable.

3) Repeat for all parameters.

4) Make five passes over all parameters. At each pass, use a finer grid for the search.

My approach is basically using an inefficient gradient search in one dimension at a time. It is slow and produces good results for the smaller cases but soon yields poor results for the medium sized cases.

The Four adjustable parameters

In thinking about them, I have decided that three of the parameters can be represented as discrete integer values, and only one is continuous.

a) Perms = Number of permutations of the index to create. Each index takes up memory. This parameter has the dominant influence on memory usage. This ranges from 3 to 20. Depending on the number of points indexed, somewhere between 20 and 32 indices will use up all memory.

b) Margin = Number of points to select in each index probe. If K is the number of neighbors sought, Margin typically varies from 3*K to 20*K.

c) Box-Points = Number of random faces of a hypercube surrounding the search point to probe. This ranges from 1 to 2*dimensions.

d) Box-Size = A fraction to multiply by the characteristic hypercube size to define the volume of hyperspace to search. Typically ranges from 0.3 to 1.5.

Answer 1

So, simplifying a bit, you want to maximize an objective function $\Phi(w,x,y,z)$, where $\Phi$ has the following properties:

• $\Phi(w,x,y,z)$ is monotonically increasing in $w$, in $x$, and in $y$

• for any fixed $w,x,y$, $\Phi(w,x,y,z)$ is monotonically increasing-then-decreasing in $z$, i.e., there exists some $z_0$ such that $\Phi(w,x,y,z)$ is monotonically increasing in $z$ for $z \le z_0$ and is monotonically decreasing in $z$ for $z \ge z_0$.

Here $\Phi(w,x,y,z)$ represents the accuracy.

There are efficient algorithms to maximize this objective function, if $\Phi$ has some additional nice properties. I'll describe how to do so, in several steps.

Given $w,x,y$, it is possible to efficiently find the $z$ that maximizes $\Phi(w,x,y,z)$ using ternary search (see also here). Let $\Phi_3(w,x,y)$ denote the value of $\Phi(w,x,y,z)$ for the value of $z$ that maximizes $\Phi(w,x,y,z)$, i.e.,

$$\Phi_3(w,x,y) = \max_z \Phi(w,x,y,z).$$

The comment above indicates that you can efficiently compute $\Phi_3(w,x,y)$ using ternary search. If $z$ comes from a discrete space with $N$ possible values, the running time to compute $\Phi_3(w,x,y)$ will be $\Theta(N)$; if it comes from a continuous space, you can find the approximate value of $\Phi_3(w,x,y)$, and for typical functions, it the convergence rate will often be very fast (the number of iterations will be proportional to the number of digits of accuracy you want in the answer).

Now, if we are lucky, $\Phi_3$ will be monotonically increasing in $w,x,y$. If this happens, we can continue to apply a similar idea, as follows.

Under this condition, given $w,x$, it is possible to efficiently find the $y$ that maximizes $\Phi_3(w,x,y)$. How? Use binary search on $y$, and use the fact that we know how to efficiently compute $\Phi_3(w,x,y)$. So, define

$$\Phi_2(w,x) = \max_y \Phi_3(w,x,y),$$

and note that this gives us an efficient way to compute $\Phi_2(w,x)$. The running time will again be efficient, i.e., $\Theta(\lg N)$ evaluations of $\Phi_3$ if $y$ comes from a discrete space with $N$ possible values, otherwise we can get an approximate optimal value efficiently (typically, the number of evaluations of $\Phi_3$ needed is proportional to the number of digits of accuracy we want in the answer).

Suppose that $\Phi_2(w,x)$ is monotonically increasing in $w,x$ and $\Phi_1(w) = \max_x \Phi_2(w,x)$ is monotonically increasing in $w$. Then Applying the same techniques, we can see that given $w$ it is possible to efficiently find the $x$ that maximizes $\Phi_2(w,x)$ (using binary search), and thus that it is possible to find the $w$ that maximizes $\Phi_1(w)$. Finally, the maximum value of $\Phi_1(w)$ is exactly the maximum value of $\Phi(w,x,y,z)$ over all $w,x,y,z$.

So if $\Phi$ has some additional nice properties, there are efficient algorithms. The resulting algorithm will have running time $O(k^4)$, where $k = \lg N$ if each parameter comes from a discrete space; or where $k$ is typically proportional to the number of bits of accuracy desired if the parameter comes from a continuous space.

Therefore I suggest you try this and see if your $\Phi$ has the required nice properties. If it does, you are in good shape and you can try a technique based on this.

---

What do you do if $\Phi$ doesn't have these nice properties? Probably your best next bet is to try some standard black-box mathematical optimization routine, e.g., hill-climbing, gradient descent, or convex optimization. If $\Phi$ is a relatively smooth function, I suspect they might work pretty well.