0
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – A_Murphy
    Commented May 7, 2020 at 13:01
  • $\begingroup$ 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 $\endgroup$
    – BlackCurrant
    Commented May 7, 2020 at 13:12
  • $\begingroup$ 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? $\endgroup$
    – A_Murphy
    Commented May 8, 2020 at 16:35
  • $\begingroup$ 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/… $\endgroup$
    – BlackCurrant
    Commented May 8, 2020 at 16:58
  • $\begingroup$ 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 $\endgroup$
    – A_Murphy
    Commented May 8, 2020 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.