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 introduces a certain second-order method that is based on quadratic upper-bounds to convex functions and
on slowly increasing the size of the batch.  A few results show that the method is well-behaved and has reasonable
convergence rates on logistic regression. 

This work is very similar to Hessian-free optimization, because it also uses CG to invert low-rank approximations 
to the curvature matrix, and it has comparable cost but greater memory complexity due to its need to store many
parameter vectors.   Likewise, it builds up on previous work that finds quadratic upper bounds to convex functions,
but a quadratic upper bound seems restrictive, and perhaps a quadratic approximation would be more appropriate.


Pros:  Method is somewhat novel.


Cons:  
 - Experiments very small and unrealistic (sometimes tens of dimensions), and there is no comparison with Hessian-free optimization
 - Theorem 1 part 1 is wrong:  the method is biased, because while E[Sigma_S] = Sigma,  E[Sigma_S^{-1}] != Sigma^{-1}.  In general,
 second order methods that use modest numbers of samples for the curvature matrix are necessarily biased.
 - The paper has two ideas:  a certain second order method, and a simple scheme for growing the minibatch.  But which of these is essential?  Would we get similar results if we didn't grow the minibtach?  How large would the minibatch end up being?   What if the other methods grow their minibatch as well, do
 they become competitive?