On the Curse of Dimensionality

If there is one tip that I would give to anyone in machine learning, this would be it: never forget the curse of dimensionality. The traditional explanation goes something like this: “Well, if you have a lot of input dimensions, then your problem becomes computationally expensive and difficult to solve”. Yes, this is true, but why is it true? Let’s talk about this in more detail.