Why would overfitting occur on a dataset with 30 million rows and 500 columns? A simple 32x16 multi-layer perceptron is apparently overfitting my dataset. The training error goes way down while the test error balloons. Note that with smaller MLPs like 8x8 the training and test error both go down. Anything larger than 8x8 seems to result in overfitting.
Given that the dataset seems huge to me (30 million rows, 500 columns), this suggests that the training examples must be similar in some way, but I don't know how to diagnose this. How would I go about confirming that overfitting is indeed the issue? And is there anything I can do to alleviate it?
 A: There seem's to be another question with exactly the same problem pointed out:
The problem might just be the size of your training set and the choice of a deeper than required network.
The fact that a smaller MLP doesn't exhibit this behaviour indicates that a deeper network is memorizing random noise. You could possibly try training with fewer observations (counter intuitive) or stick to using a smaller network as you've already tried.
Also, it could very well be that despite you having 30 million observations and 500 columns, most of them are sparse or have low variance. 
A: Maybe try:


*

*Find how the validation error changes as you increase the number of observations sampled

*Use that "optimal" number of observations for a bagging model, see how the performance changes as you increase the number of models in the ensemble.

A: Look into Regularization; you should try punishing your model for input complexity.  You never mentioned why type of data you are using, but if you have 500 features per observation, it's possible (likely) that some of those are spurious and dont actually represent reality but rather random patterns in the input space.
