The relevant aspect which makes a Euclidean distance metric relevant is not “all the dimensions change a bit at once”. The relevant aspect is “cost of testing the change is a function of Euclidean distance”—e.g. in the e-coli case, the energy expended during straight-line swimming should be roughly proportional to the distance traveled.
I’m not sure about your visit-the-cousin example. My intuition is that O(1/n) is the default cost to e-coli-style optimization when there’s no special structure to the exploration cost which we can exploit, but I don’t have a strong mathematical argument for that which would apply in an obvious way to the cousin example. My weak argument would be “absent any special knowledge about the problem structure, we have to treat visiting-the-cousin as an independent knob to turn same as all the other knobs”—i.e. we don’t have a prior reason to believe that the effects of the visit are a combination of other (available) knobs.
The relevant aspect which makes a Euclidean distance metric relevant is not “all the dimensions change a bit at once”. The relevant aspect is “cost of testing the change is a function of Euclidean distance”—e.g. in the e-coli case, the energy expended during straight-line swimming should be roughly proportional to the distance traveled.
I’m not sure about your visit-the-cousin example. My intuition is that O(1/n) is the default cost to e-coli-style optimization when there’s no special structure to the exploration cost which we can exploit, but I don’t have a strong mathematical argument for that which would apply in an obvious way to the cousin example. My weak argument would be “absent any special knowledge about the problem structure, we have to treat visiting-the-cousin as an independent knob to turn same as all the other knobs”—i.e. we don’t have a prior reason to believe that the effects of the visit are a combination of other (available) knobs.