I am comparing two hyperparameter optimization algorithms: "Bayesian optimization" (henceforth called B) and "Quasirandom sampling" (Q). I use them to choose parameters for training a complicated regression model. These algorithms are iterative; I train the model on a training set with one set of parameters, then evaluate it on a separate validation set and record the error. Next, the algorithm spits out a new set of parameters to try. Q is only dependent on what the previously chosen parameters were and merely seeks to sample the space as thoroughly as possible. B is also dependent on what the validation errors were and seeks to preferentially sample those areas with lower error.

I think it is likely that initially the two algorithms are similar. Then as B develops a better picture of the error landscape, it will evaluate better points than Q. Then once B has a good picture of the best parts of the landscape, it will start evaluating the worse parts (because there is the best chance for improvement even though it is slim) and its performance will drop below Q's.

I am curious where these changes in quality take place (if they do at all). I can compute approximately 40 steps per day for either algorithm. So 30 samples in each algorithm where a sample consists of 40 steps would take 60 days.

  • My first thought was to do a hypothesis test for a difference in error mean for each step. But at 95% conf/80% power, that requires 32 samples in each. I don't want my PC tied up for 61 more days of computation. (And that ignores that I'd like to know which algorithm is better ... so I'd need two tests.)
  • Then I thought I could look at groups of 11 steps and compare the mean error in each group. Then I can get 33 "samples" drawn from the first 11 steps by using only 3 runs each - another 3 days of computation. Unfortunately the B steps are not independent. (Though there is some appearance thereof: pairwise dependence between steps at several distances cannot be detected by Hoeffding's D Statistic.) Neither are the Q steps, but they are reasonably close ... consider them a pseudorandom sequence.

Is there a way to find out when one algorithm is better than the other without too much more computation? I'm looking for an answer of the form "Q is indistinguishable from B before step 10 but has higher error between steps 10 and 20 and then lower after step 20." I'm especially interested in methods that would apply beyond just B and Q to other similar pairs of algorithms because I'm thinking of implementing another, less common, search algorithm and wouldn't mind being able to investigate its characteristics.

  • 1
    $\begingroup$ Your title does not match your question, you might want to edit it so as to get more visits from people who can answer your question. $\endgroup$
    – jbowman
    Jan 25, 2018 at 15:59
  • $\begingroup$ @jbowman Thank you. Could you suggest a better title? In my mind, $Q$ and $B$ are stochastic processes composed of $Q_i$, and $B_i$. I want to find out on what intervals of $i$, $E[Q_i]$ < $E[B_i]$. The current title is a simplification of that understanding of the question. $\endgroup$
    – Eponymous
    Jan 25, 2018 at 17:49
  • $\begingroup$ Your question really is about the relative quality of the optimization algorithms, not about which (if either) of two stochastic processes are better. I understand how you got from one to the other, but for someone reading only the title it doesn't look like the question has anything to do with evaluating algorithms. Something like "How can I compare Bayesian Optimization and Quasirandom sampling for hyperparameter optimization?", if you think that matches what you really want. $\endgroup$
    – jbowman
    Jan 25, 2018 at 18:01


Your Answer

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