2

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,

HDB
  • 249
  • 1
  • 6
  • That depends. Is the search space the same? Obviously the larger the search the more expensive... – astel Nov 22 '20 at 20:49
  • 2
    There’s a pathology in the difference. A classic grid assumes some thing about the characteristic phenomenology of the system. You can think of it as the wavenumber analog to Nyquist sampling frequency. If you sample to sparsely on your grin you miss it. This is one of the great advantages that the uniform random sampling gives. One of the things that comes with it as a higher cost. If you knew ahead of time the characteristic frequency than the grid is going to require fewer samples, all else being equal. If you do not know your characteristic frequency, what do you do then? That’s the really – EngrStudent Nov 22 '20 at 21:04

1 Answers1

1

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.

Tim
  • 108,699
  • 20
  • 212
  • 390