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.
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.