> because the test distribution could be arbitrarily different,

In that case all bets are off for all machine learning algorithms anyway. If the changes are not arbitrarily different then some of the lost performance can be recovered.

You talk about generalization a lot, but perhaps you are not aware that the technical term is defined under the assumption that test and train distribution are the same.