Stochastic Bound Majorization
This provides a more efficient optimization method for machine learning practitioners working with high-dimensional log-linear models, though it appears incremental as it builds on existing bound majorization.
The authors tackled optimization of log-linear models by developing a stochastic version of bound majorization with low-rank modifications for high-dimensional data, resulting in a method that outperforms stochastic gradient descent in iterations, computation time, and parameter quality.
Recently a majorization method for optimizing partition functions of log-linear models was proposed alongside a novel quadratic variational upper-bound. In the batch setting, it outperformed state-of-the-art first- and second-order optimization methods on various learning tasks. We propose a stochastic version of this bound majorization method as well as a low-rank modification for high-dimensional data-sets. The resulting stochastic second-order method outperforms stochastic gradient descent (across variations and various tunings) both in terms of the number of iterations and computation time till convergence while finding a better quality parameter setting. The proposed method bridges first- and second-order stochastic optimization methods by maintaining a computational complexity that is linear in the data dimension and while exploiting second order information about the pseudo-global curvature of the objective function (as opposed to the local curvature in the Hessian).