These are good points about computational complexity, but there's more to it: the NN architecture regularizes the representations which may be learned. A fully

These are good points about computational complexity, but there's more to it: the NN architecture regularizes the representations which may be learned. A fully connected architecture may be fully general, but without powerful regularization you won't be able to train it to get the performance of an architecture which encodes some of the structure of the problem. Even disregarding the computational load of the increased number of parameters.