Hill Climbing Algorithm - Optimum Step Size

Question

I am implementing a standard hill climbing algorithm to optimise hyper-parameters for a predictive model. The hill climbing algorithm is being applied as part of a two-stage approach:

1. Apply grid search with large values applied to the hyper-parameter to find a 'best' starting point
2. Apply hill climbing algorithm in this space with a large number of different, random start points to find a local optimum

The large values that are passed in the first step, the grid search are

1*10^seq(-4, 5, by=1)
 [1] 1e-04 1e-03 1e-02 1e-01 1e+00 1e+01 1e+02 1e+03 1e+04 1e+05

So I am struggling to choose an optimum step size that isn't too large that is skips the peak or too small that it takes too long to converge. I don't think a single value for the step size is appropriate for all values passed in the grid search since, for example the difference between 1e-04 and 1e-03 is vastly different to 1e03 and 1e04. So I want the step size to be proportionate to the grid search start point. I know the search space I'm looking at is

grid_search_optimum/10 to grid_search_optimum*10

My question, therefore, is what is an accepted value for the step size in relation to the search space? I haven't found any opinions in literature around this and, in general, the only advice is to choose a step size that is "sufficiently small". Any advice or pointers to relevant papers would be greatly appreciated!

Answer 1

Usually it worked for me that if the search space was know then annealing rate (divide the size size with number of iteration)helped to decrease/increase the step size gradually to get to local max/min but the draw back is it might get stuck in local and might need some "momentum" to go on, another draw back it it might be very slow.however it doesn't seems like the case with your question that you bother about it.

Please refer- https://courses.cs.washington.edu/courses/csep573/11wi/lectures/04-lsearch.pdf

This paper proposes self adaptive step size search- https://link.springer.com/chapter/10.1007%2F3-540-34783-6_56