fast ML algorithms for binary classification with (large+sparse) binary input data
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/