# Hill Climbing Algorithm - Optimum Step Size

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!

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.

• Hey BlackCurrant, thanks for the quick post! Do you have any reference for the step size being search size divided by the number of iterations? The paper proposing a self-adaptive step size is very interesting but wouldn't be appropriate in this case. – A_Murphy May 7 at 13:01
• I have implemented annealing rate in context of gradient decent algorithms , if you are able to extend the concept here- cs231n.github.io/neural-networks-3/#anneal few articles- towardsdatascience.com/… jeremyjordan.me/nn-learning-rate one in context of deep learning- auai.org/uai2015/proceedings/papers/73.pdf – BlackCurrant May 7 at 13:12
• Sorry about the delay I was spending time looking through the attached! However, I am struggling to see how to implement an adaptive step size for hill climbing, how would the gradient be calculated in this situation? – A_Murphy May 8 at 16:35
• Here is the article with code handy, i shall have to dug to find mine, basically you just divide the learning rate in each iteration by iteration count. This is simple break down- machinelearningmastery.com/… – BlackCurrant May 8 at 16:58
• That makes perfect sense thanks! The only thing left unclear is the start value for the step size. In my problem the search space can vary massively so what size should the first step be in terms of the search space? I'm happy to anneal it thereafter as a good solution – A_Murphy May 8 at 17:17