Best ML approach for huge number of classes I have an problem where the dataset consists of:

400k observations
40k classes (mutually exclusive)

The problem is about predicting what is the supplier of an invoice (from which supplier/shop a purchase was made) based on the text of the invoice.
As you can understand there are hundreds of thousands if not millions of suppliers in a country hence the so big number of (mutually exclusive) classes.
In terms of features, I use a TF-IDF algorithm so I end up with 1.5M features. I apply feature selection and they are eventually relatively reduced in number. In any case, the features approach is something that I can and I am open to change so the number of features should not be considered as fixed.
However, this huge number of classes (along with the number of observations, features) results in me having to use huge amount of hardware to make things run and in many cases the VMs just die because of lack of memory.
All these happen when using ML algorithms such as random forest or SGD.
I am thinking that may be Tensorflow and GPUs can be a solution (?) although again this is a kind of hardware solution so I am wondering if I should reframe somehow the problem to make its solution more scalable.
How would you approach this problem IN AN ML WAY to make things scalable given also that the number of classes will be significantly growing in the future (finally there will be around 1M classes)?
Given data will keep increasing in the future along with the classes. You need to look at fast methods of doing things. Look at approximate KNN to do classification in high-volume data. Approximate KNN will solve your problem. Here's the library for it. Your accuracy will suffer a bit but this method would scale.