Regarding Neural Networks, this topic has been very nicely covered in a recent NeurIPS 2020 paper entitled
The Pitfalls of Simplicity Bias in Neural Networks (Shah et al.).
I totally recommend reading the paper, I think it is very nicely structured and rigorous. Here is an attempt to summarize its main ideas:
The core of the problem is that the field seems to associate simplicity bias to "justify why NNs work well", but not to their "lack of robustness".
The authors tackle this problem via the design of datasets that comprise multiple predictive features with varying levels of simplicity. These will serve as control variables.
Following a series of theoretical analyses and targeted experiments, they found that the simplicity bias given by Stochastic Gradient Descent can be extreme, that common approaches to overcome this can fail, and in general, that there is still quite a way to go in order to better understand SB in NNs.
The proposed datasets and methods can serve as a basis for future work in that direction.
This principle of SB for NNs is very much embedded in the Deep Learning culture: See e.g. this video from the Udacity "Deep Learning" course (Vanhoucke et al.), where they use the "stretch pants" analogy. The idea is that instead of trying to guess the right pant size, you start with several extra sizes and "stretch them down" until they fit perfectly. This way, training is seen as reducing the capacity of the model wherever there is room to do so.
The paper above questions the general validity of this principle, showing that when trained with SGD, the pants tend to fit the simpler legs, no matter how many dimensions they have.
So whereas the original question is from 2015, this topic is still extremely current. Particularly, the following OP sentence is right on point:
Today's computing power enables us to build increasingly complex models with ever-greater ability for prediction. As a result of this increasing ceiling in computing power, do we really still need to gravitate toward simplicity?
Since the paper above shows that the ever-growing NN architectures still invariably gravitate towards simpler features when trained with SGD.
I would also like to finish commenting about another bias related to SB, that is Inductive Bias, "the set of assumptions that the learner uses to predict outputs of given inputs that it has not encountered".
Instead of assuming simplicity, inductive bias assumes any other arbitrary property. For example, when training a NN for transcription of piano music, it is safe to assume that all keyboard strokes generate mainly harmonic waveforms that have an onset and decay exponentially. In terms of "no free lunch", correctly applying an inductive bias would translate to getting lunch for a good prize. Physical models are known for their extremely precise and rigorous application of inductive biases.
Another amazing ICLR 2020 paper that treats the systematic introduction of Inductive Bias into NN design and training is
With application of DDSP techniques it can be observed that introducing inductive biases helps the models satisfactorily solve complex tasks with less capacity, also the SGD convergence is faster and requires less training data.
So again coming back to the OP: While the No Free Lunch theorem states that no algorithm will work better than other for all kinds of problems, inductive biases are a good mechanism to gain performance without sacrificing much interpretability, if you are willing to reduce the set of targeted problems.