Almost every "number" "in" N doesn't actually exist. In the search for numbers that exist, we will most likely only ever find a finite set of numbers before the Universe or humanity dies.

("Scare quotes")

Searches happen in finite time an space and, more importantly, systems performing those searches have practical finite limits on parameters that determine size of the space within which that search can take place (such as available memory).

Even within fairly modest finite limits, you can produce a solution space that cannot be significantly searched with the available finite matter and time available in the observable universe.

Thus, the problem with using search isn't that solution spaces can be infinite, but that finite solution spaces can be unimaginably large.

Gradient descent is a search. Where does it say the search space has to be small?