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]:
This paper looks at performing a stochastic truncated Newton method to general linear models (GLMs), utilizing a bound to the partition function from Jebra & Choromanska (2012).  Some basic theory is given, along with some experiments with logistic regression.

Stochastic or semi-stochastic truncated Newton methods such as Hessian-free optimization, and the work of Byrd et al. have already been applied to learning neural networks whose objective functions correspond to the negative LL of neural networks prediction under cross entropy error, which is like taking a GLM replacing theta in the definition expression with g(theta), where g is the neural network function.  In the special case that g=I this correspond exactly to logistic regression. 

One thing I'm very confused about is what the bounding scheme of Jebra & Choromanska (2012) that is applied in this paper actually does.  Since it involves summing over all possible states, it can't be more efficient than just computing the partition function, and its various derivatives and second-directives directly.  Why use it then?  The Hessian of the negative LL of a general linear model will already be PSD, so that can't be the reason. 


Detailed comments:

Abs:  What do you mean by 'maximum likelihood inference'?  Do you mean estimation?  Learning?

Page 1: There are versions of those batch methods that can use minibatches and they seem to work pretty well, despite lack of strong theoretical results.  I guess though that this would fall into the category of what you are calling 'semi-stochastic'?  Actually, having read further it appears that you would only call these stochastic if the size of the minibatch grows during optimization.

Page 1: When you say that stochastic methods converge in less iterations that batch ones, this makes no sense.  Perhaps you meant to say passes over the training set, not iterations.

Page 2: The abstract made prominent mention of partition functions.  Yet, the introduction doesn't make any mention of them, and seems to be describing a new optimization method for standard tractable objective functions.

Your intro should mention that you will be focusing on generalized linear models (what you are calling generalized linear model) and extending the work of Jebra & Choromanska (2012) to the stochastic case.  This becomes clear only once the author has read well passed the intro.



Page 3: I think you should have some discussion of this Bound Computation subroutine.  It looks quite mysterious.  Does the order at which the loop goes over the different y's matter?  I can't see why it wouldn't, and that seems problematic.



Page 3:  You don't define n.  Is this the size of Omega?

Page 3:  'dataset Omega'?   I thought Omega was the set of values that y can take.

Page 4:  The statement and proof of Theorem 1 seems similar to one of the theorems from the Byrd et al (2011) paper you cite.  And like that result, it is extremely weak.  Basically all it says is that as long as the curvature matrices are not so badly behaved that the size of their inverses grow arbitrarily, multiplying the gradient by their inverses won't prevent gradient descent from converging, provided the learning rate becomes small enough to combat the finite amount of blowing up that there is.  It says nothing about why you might actually *want* to multiply by the inverse of this matrix.  But I guess in this general setting there is nothing stronger that can be shown, since in general, multiplying the the inverse curvature matrix computing on only a subset of the data may sometimes do a lot more harm than good.

Page 6:  I don't see why the first part of Cor 1 should be true.  In particular, it isn't enough to for the matrix to be positive definite everywhere.  It has to be positive definite with a lower bound on the smallest eigenvalue that works for all x (i.e. a uniform bound).

Page 6:  Theorem 2 should start 'there exists mu, L>0, and rho>0'.  You are missing the rho.

Page 6:  This theorem doesn't seem to show that multiplying by the inverse curvature matrix is actually helping.  One could just as easily prove a similar bound for standard SGD.  Like this bound, it certainly wouldn't give linear convergence for SGD (an absurdity!), due to presence of the Ck term in the bound, which will eventually dominate in stochastic optimization.


Page 6:  Could you elaborate more on the point 'further regularizes the sub-problems'?   There is a detailed discussion of this kind effect in 'Training Deep and Recurrent Neural Networks with Hessian-Free Optimization', section 8.7.  What in particular does [38] say about this?

Page 7:  In section 12.1 from the above mentioned article, a similar result to Lemma 4 is proved.  It is shown that the quadratic associated with the CG optimization is bounded, which implies the range result (since if the vector is not in the range, the optimization must be unbounded).  They look at the Gauss-Newton matrix, but for general linear models, the Hessian has the same structure, or the matrix from the bound from Jebra & Choromanska (2012) has the same basic structure as this matrix.