fast ML algorithms for binary classification with (large+sparse) binary input data I'm sorry that this is so very broad, but as a non-ML scientist it feels to be almost impossible to keep up with recent developments (esp. in deep learning etc.). Hence, I'm asking for guidance on how to handle this specific use case:

The goal is to predict a binary output from ~50,000 binary input variables (the input data being rather sparse with about 1,000 1s on average). The training dataset includes several thousand (fairly balanced) labeled samples. I already have a non-ML solution to this giving good results but it is computationally expensive. Thus, my questions:


Which ML algorithms work well (i.e. train reasonably fast on a small HPC-cluster) on binary data of that scale.
Do they allow to extract information about the inputs (i.e. the magnitude of loadings of the individual binary variables).
How large are the performance advantages of having binary data? As opposed to using the 50k binary input variables I could run a PCA and use the first couple hundred PCs (it takes about 500 to recover 90% of the variance) for training/prediction. What would the advantages/caveats be?


The order of the input variables is not really "random", but their importance might be. Hence I think CNNs would not be the best idea, but are non-convoluting NNs even feasible at this scale? Additionally, it is usually only a few input variables that mostly decide the output, if that makes any difference in model selection.

I have worked with ML in the past, but this is several years ago and my theoretical knowledge is more than rusty. Also, the variety of NN architectures / frameworks etc. has exploded since then, hence I wanted to ask for some input before blindly trying out everything.
I mentioned in a comment that boosting might be a option. However, after second thoughts, I guess (as far as I can tell from the description of your data)  that you might be better off starting with logistic regression with regularization (lasso, elastic net, ridge). Why?


You want to learn „fast“ (not much tuning etc)
Your data tends to be of high dimension
You don‘t know what feature(s) are good predictors


This together makes me think, that 1) trying lasso would be the thing to start. If this fails, 2) go on with ridge. 

Lasso can shrink the impact of features to zero (good in high dimensional data). However, this may lead to a situation in which „too much“ regularization happens. So you can try ridge, in which case features are „shrunken“, but will never become zero.

I don‘t know if you work with R or Python, but lasso/ridge is available in both. Make sure you find the right lambda (tuning parameter for regularization) by cross validation (this is not too expensive).

Here is a good R tutorial: https://web.stanford.edu/~hastie/glmnet/glmnet_alpha.html

For Python, there are also good tutorials around.

Some background can be found in „Introduction to statistical learning“, for which R and Python code is online. http://www-bcf.usc.edu/~gareth/ISL/