[tune] A few differences between the Hyperband implementation and the original paper

[haoyangz]

Comparing to the original post, I spotted a few differences (not sure if there are others):

• s_max is currently a fixed value (=5). It should be calculated from max_t (with the definition in the original post) and eta (using int(log(max_iter)/log(eta)))

• n_0 is calculated differently. The original post rounded (s_max+1)/(s+1) whereas the current implementation doesn't, leading to trial sizes that are different from the original post (always an exponent of 3).

[haoyangz]

@richardliaw

[richardliaw]

Nice! It would probably be good to clarify all of these points in the implementation details.

For context, our original implementation of Hyperband actually followed the paper, but after using it for a while, we realized that the given parameters led to many unintuitive and impractical bracket configurations.

1. Both s_max (representing the number of brackets - 1) and eta, representing the downsampling rate, are fixed. In many practical settings, you may have R >= 200. For simplicity, assume eta = 3. Between R = 200 and R = 1000, you end up with a huge range of the number trials needed to fill up all brackets -
   
   Now, assume R = 300. If you want to find a better eta, you realize also that the configurations generated aren't very intuitive:
   
   We figured that it would be a lot easier for majority of people to use if we fixed the parameters to be the same as the example given in the paper and only exposed max_t. I actually wouldn't worry too much about these deviations from theory, because HyperBand is actually quite inefficient in implementation (both in our experience and noted by the authors, who propose a fix that we will soon provide).

2. The example in the post to calculate n_0 is actually a little different than the algorithm given in the paper. We implement according to the paper (Screenshot from the original paper):
   

In fact, not rounding the calculation inside actually provides fairer resource allocation to all of the brackets! Allocation is calculated by sum(n * r for n, r in bracket).

3. There are also implementation specific details like how trials are placed into brackets which are not covered in the paper. Also, the recent PR [tune] Hyperband Max Iter Fix #1620 aims to cut trials after max_t, which might actually not be the semantic definition in the paper, but makes much more sense to the end user.

tldr implementation details may deviate slightly from theory but are focused on increasing usability

[ericl]

@richardliaw it could be useful to move that info into a doc, e.g. in the hyperband page of #1642

[richardliaw]

#1642 is merged now; closing this. Feel free to open if anything else comes up!