Semistochastic Quadratic Bound Methods
Authors: Aleksandr Y. Aravkin, Anna Choromanska, Tony Jebara, Dimitri Kanevsky
ICLR 2014

Abstract: Partition functions arise in a variety of settings, including conditional random fields, logistic regression, and latent gaussian models. In this paper, we consider semistochastic quadratic bound (SQB) methods for maximum likelihood inference based on partition function optimization. Batch methods based on the quadratic bound were recently proposed for this class of problems, and performed favorably in comparison to state-of-the-art techniques. Semistochastic methods fall in between batch algorithms, which use all the data, and stochastic gradient type methods, which use small random selections at each iteration. We build semistochastic quadratic bound-based methods, and prove both global convergence (to a stationary point) under very weak assumptions, and linear convergence rate under stronger assumptions on the objective. To make the proposed methods faster and more stable, we consider inexact subproblem minimization and batch-size selection schemes. The efficacy of SQB methods is demonstrated via comparison with several state-of-the-art techniques on commonly used datasets.


Peer review:
[Review]:
The paper describes a second order stochastic optimization method where the gradient is computed on mini-batches of increasing size and the curvature is estimated using a bound computed on a possibly separate mini-batch of possibly constant size. This is clearly a state-of-the-art method. The authors derive a rather complete ensemble of theoretical guarantees, including the guarantee of converging with a nice linear rate.  This is a strong paper about stochastic optimization.  In the specific context of ICLR, I regret that the authors did not explain why this technique is useful to learn representations. The basic setup is that of maximum likelihood training of an exponential family model.  In practice, there are many reasons to believe that such a technique would work on mixture models or models that induce representations (although the theory might not be as simple.)  I believe that this paper should be accepted provided that the author pay at least some lip service to 'representation learning'.