How to treat sparse categorical features in a Neural Network for multiclass classification with Tensorflow?
Having more features than batchsize it's not a problem indeed is the rule in many fields like computer vision. Having a very sparse dataset is also the norm in NLP. Both communities rely on dropout to prevent overfitting. 

You may see an example of using drouput with Tensorflow here.