1

Someone told me grid search suffers greatly from the curse of dimensionality while the random search algorithm doesn't. Does this mean that it is computationally more costly to tune the parameters with the grid search algorithm than the random search algorithm if the data is high-dimensional? why do people exactly mean when they say the grid search suffers from the curse of dimensionality?

Alexis
  • 26,219
  • 5
  • 78
  • 131
HDB
  • 249
  • 1
  • 6
  • 2
    Hint: the very smallest possible grid has just two points in each dimension. In, say, 1000 dimensions how many points would you have to visit in the grid for a full search? – whuber Nov 22 '20 at 21:40
  • 2
    And following on @whuber's comment, how does the random search algorithm avoid full search (and by running what risk)? – Alexis Nov 22 '20 at 21:42
  • @whuber I kind of get it. so if we need to optimize $p$ parameters and each one takes at most $v$ values, then the computational cost of the grid search algorithm would be $O(v^p)$...am I correct? In comparison to grid search algorithm, I am not sure what the computational cost of the random search algorithm would be....is this just $O(p)$ since the grid is not set but randomized? – HDB Nov 22 '20 at 21:56

0 Answers0