Grid search vs. random search for hyperparameter tuning I am interested in comparing the computational cost of grid search vs. random search algorithm for hyperparameter tuning.
Is random search computationally less expensive then grid search? Is there an article/paper that talks about this topic?
Thank you,
 A: Computational cost of what exactly? In both cases you check a list of parameter values, so it's $O(n)$. They only differ in how the list is created. For grid search, the list is deterministic, where you compare different combinations of listed parameter values. In random search the examples are created randomly. Both have same computational cost. The difference is quality of the results, where usually grid search is more efficient, hence it might need fewer examples.
A: Answering what I think you're asking and to follow-up on @Tim's answer, think about a cube. The sidelength of the cube is smaller than the diagonal length of a face. This is in turn smaller than the distance between opposite corners. In higher dimensions, the problem worsens, so you can end up with systematically very sparse regions despite having many sampled points. From what I understand, random search is less sensitive to this, but you still run into sparse regions, just not systematically. In my mind, pseudo-random Sobol sequences take the best of both worlds (grid search and random search) and is generally considered better than random search. To guarantee the nice statistical properties of a Sobol search, you have to sample in base-2 increments.

*

*https://en.wikipedia.org/wiki/Sobol_sequence (see the 2D comparison of Sobol vs. random)

*https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.qmc.Sobol.html

*https://ax.dev/docs/models.html#sobol-sequence
