[ssivark]

I've mostly worked on continuous high-dimensional problems (and not as high-dimensional as large neural networks), often times grounded in physical situations, where one can anticipate reasonably convex behavior close to the optima -- things like bundle adjustment, different kinds of generalized calibration, etc. In all these cases, (approximate) second-order optimization methods have worked great (Just throwing out a few non-MECE names eg: Conjugate-Gradient and variants, Levenberg-Marquardt, BFGS, etc.).

In the context of probabilistic modeling, my experiences with belief propagation have been good, but somewhat mixed. Sometimes it feels like mean-field methods could give more bang for the buck given how much less memory they use.