Under which conditions is one of the optimization methods offered by VW (SGD, bfgs with/without conjugate gradient, FTRL) expected to be better than others? I am mainly interested in regression and classification problems. Any references would be extremely valuable.
In general, the default SGD method will suffice in almost all cases. The LBFGS method is more of a backup, it's mainly there when you want to find a high accuracy solution, typically to help debug issues with SGD. It also provides a useful baseline for comparing methods against.
The stochasticity in SGD helps regularize the solution, so if you use a batch method (LBFGS/CG) you need to be more careful with the L2 regularizer you use. I believe L1 regularization is only supported with the stochastic methods as well. Performance wise, the LBFGS implementation will take many more epochs to converge than SGD, depending on your data size this may not be a problem. I've used the SGD option for datasets of 100GB+ without issue, which is not practical with LBFGS.
The FTRL implementation (technically FTRL-proximal, regular FTRL is actually just SGD in this setting) is mainly there for comparison reasons, so they could test their SGD implementation against it. I haven't done a direct comparison, but I believe it's not hugely different in terms of performance. You may see some difference for sparse problems.