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]:
We would like to thank all the reviewers for their comments. The paper after revisions was posted on arxiv today and will be soon publicly visible. Below we enclose answers to reviewers comments:

Reviewer 1: 

We thank the reviewer for the comments. We have highlighted representation learning as an important application in the introduction, and furthermore pointed out that our majorization methods have been applied to this area in previous work in the context of batch learning. Since the main contribution of this paper is to propose a semi-stochastic extension, the results are directly applicable to representation learning. Specific extensions for deep learning are noted as future work in the conclusions. 

Reviewer 2:

We thank the reviewer for the comments.
1) Hessian-free optimization (also known as truncated Newton methods) solve Newton systems (and damped/inexact variants) inexactly to obtain descent directions. While classic methods use full gradients (and so are not competitive in the stochastic setting, w.r.t passes through the data), recent work also uses subsampling for gradient and Hessian approximations. Depending on the accuracy to which second order terms are approximated, these methods may require more or less storage than the method we propose. 

We emphasize that our main contribution in this paper is to show majorization methods can be used in a semi-stochastic setting to compete with state-of-the-art fully stochastic methods, like SGD, ASGD or SAG, with respect to passes through the data.

2) We presented the results on six datasets, three of them are sparse and the remaining ones are dense. The number of examples in these datasets are between 12K and 580K. Among these datasets we have some with 4932 dimensions and 46236 dimensions. These are not small datasets, and in fact commonly used to test new algorithms in the community (see e.g. Le Roux, Schmidt, Bach 2012). 

With regard to Hessian-free optimization, we leave it to future work to compare majorization-based schemes with truncated Newton-based schemes. As far as we know, Hessian-free optimization methods have not been compared with state-of-the-art stochastic methods with respect to passes through the data. Also, in the batch setting, majorization methods have recently performed favorably in comparison to full Newton methods and quasi-Newton methods.

3) Theorem 1 part 1 is correct - it neither relies on  E[Sigma_S^{-1}] = Sigma^{-1}, nor claims the average direction is unbiased. The point is that the average direction (s^k in the paper), although biased, is still gradient related, which we show in part 2. Note that in the definition of s^k = E[(Sigma_S^k + eta I)^{-1}] g^k,  the expectation is taken after the inverse. 

Using the framework of Bertsekas and Tsitsiklis, it is enough to have the average direction be gradient related 'enough', which is shown in (7). 

4) Majorization methods have been shown to be competitive with second order optimization methods in prior work, in the batch setting. The main contribution of this paper is to make these methods competitive in the stochastic setting. While the number of samples used to approximate the gradient increases across iterations until the entire training data is eventually used (we control this rate of increase as explained in the experimental section), the number of samples used to obtain the second order bound-based approximation remains capped at a small number, as also explained in the experimental section. Growing the mini-batch is essential to achieve linear convergence rate as captured in Theorem 2; otherwise the rate of convergence would be sublinear, which is the typical convergence rate of state-of-the-art fully stochastic methods, like e.g. SGD.  

It is not clear what is meant by 'if other methods grow their minibatch'. It is always possible that other methods can be improved, either using some ideas in this paper or other ideas. Our main contribution is to show that majorization-based methods are competitive with state-of-the-art in the stochastic setting. 

Reviewer 3:

We thank the reviewer for the comments.
1) The summary of the paper provided by the reviewer is a nice; however `quadratic bound' is a better title, since the quadratic approximation is based on the bound for the partition function, rather than the Hessian or a standard Hessian approximation. 

2) We leave comparisons with Byrd et al. to future work as their setting differs from ours. In particular Byrd et. al. do not compare to state-of-the-art stochastic methods in their 2012 paper; their experiments show that dynamically growing the batch size is faster than a full batch method of the same type, and more accurate than a Newton-type method that uses a fixed sample size; they also compare with OWL. In their 2011 paper, they consider a batch-gradient, sampled Hessian approach. 

3) We refer the reviewer to Jebara & Choromanska 2012, where the bound method was shown to outperform BFGS and Newton methods in the batch setting (for convex problems), intuitively due to adapting not only locally, like most methods including gradient methods and Newton-like methods, but also globally, to the underlying optimization problem. The main motivation is that when a global tight bound is used, optimization methods based on majorization are competitive with standard optimization methods for problems involving the partition function. 

4) We used the phrase 'maximum likelihood inference' in the context of 
maximum likelihood estimation. Thanks for pointing out this issue, the text has now been corrected. 

5) Different batching strategies indeed have a long history. We found that the theoretical arguments in Friedlander & Schmidt (2011) strongly motivate a batch growing scheme, which we call semi stochastic, and which they also call 'hybrid' (on the other hand, by stochastic we mean having fixed size mini-batch). They show that the convergence rate is a function of the conditioning of the problem and the degree of error in the gradient approximation; therefore, as long as the latter is dominated by the former, we can recover a linear rate in the stochastic setting. 

6) We indeed used word 'iterations' to refer to passes through the data in the phrase pointed by the reviewer. Thanks for pointing out this issue - the text has now been corrected. 

7) We have corrected the introduction according to reviewers suggestions. We have added the comment that we focus on partition functions, which are of central interests in many learning problems, like training CRFs or log-linear models. We also indicated early in the introduction that we will be extending the work of Jebara & Choromanska (2012) to the semi stochastic setting. 

8) The Bound Computation subroutine is directly taken from the previous work of Jebara & Choromanska (2012) (see Algorithm 1). The order indeed matters and slightly affects S, but not z or r.  Jebara & Choromanska (2012) investigated various ordering schemes and noted no significant difference in performance (see page 2).

9) The reviewer is correct,n was indeed undefined. n is now defined when Omega is introduced. 

10) Omega is indeed the set of values that y can take.  We thank the reviewer, this issue has been fixed. 

11) We agree with the reviewer - current results show that curvature information can be incorporated in a way that guarantees convergence to stationarity under weak assumptions (Theorem 1) and the recovery of a linear rate provided an aggressive batch growing scheme for logistic regression (Theorem 2); in both cases the use curvature approximations from samples is not proven to help. We are also interested in finding a stronger result of the type that the reviewer is suggesting, perhaps under suitable assumptions on the problem class, but we leave this to future work. 

12) Note that additional requirements are required to ensure a uniform lower bound on the smallest eigenvalue in the absence of regularization. When eta is present, it provides such a lower bound; so we have removed the corollary and simply noted this. 

13) The problem with missing rho was corrected. We thank the reviewer for pointing this out.

14) We agree with the point made by the reviewer - one recovers the linear rate by essentially controlling the error from sampling to be bounded by the geometric terms from the deterministic setting. The reviewer's point is well taken - the theorem does not show that inverse of the curvature matrix is actually helping, as the empirical results suggest. 

15) The fact that inexact solutions to subproblems can be interpreted as regularization is often used in the inverse problems community, and explained in some detail in Vogel's book. This is in fact the reference we wanted to cite, and we are very grateful that the reviewer caught this error! We have also added the reference that the reviewer suggested. 

16) We thank the reviewer for the remark about Page 7, section 12.1, Lemma 4 - this has been noted prior to the presentation of the lemma.