Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: **I am happy to see some good responses from the authors to my questions. I am raising my score a bit higher. 

Summary: 
A new stochastic method based on trust region (TR) is proposed. Experiments show improved generalization over mini-batch SGD, which is the main positive aspect of this paper. The main algorithm has not been properly developed; there is too much focus on the convergence aspects of the inner iterations, for which there are many good algorithms already in the optimization literature. There are no good explanations for why the method yields better generalization. Overall, TR seems like an interesting idea, but it has neither been carefully expanded or investigated. 

Let me state the main interesting results before going into criticisms:
1. TR method seems to generalize better than mini-batch SGD. 
2. TR seems to lose generalization more gracefully than SGD when batch size is increased. [But note here that mini-batch SGD is not a closed chapter. With better ways of adjusting the noise level via step-size control (larger step sizes mean more noise) the loss of generalization associated with large mini-batch sizes can be brought down. See, for example: https://arxiv.org/pdf/1711.00489.pdf.]
3. Hybrid method is even better. This only means that more understanding is needed as to how TR can be combined with SGD.

Trust region methods are generally batch methods. Algorithm 1 is also stated from that thinking and it is a well-known optimization algorithm. The authors never mention mini-batch when Algorithm 1 is introduced. But the authors clearly have only the stochastic min-batch implementation of the algorithm in mind. 

One has to wait till we go into the experiments section to read something like:
"Lastly, although in theory, we need full gradient and full Hessian to guarantee convergence, calculating them in each iteration is not practical, so we calculate both Hessian and gradient on subsampled data to replace the whole dataset"
for readers to realize that the authors are talking about a stochastic mini-batch method. This is a bad way of introducing the main method. This stochastic version obviously requires a step size; so it would have been proper to state the stochastic version of the algorithm instead of the batch algorithm in Algorithm 1.

Instead of saying that in passing why not explicitly state it in key places, including the abstract and title? I suggest TR be replaced by "Stochastic TR" everywhere. Also, what does "step size" mean in the TR method? I suggest that all these are fully clarified as parts of Algorithm 1 itself. 

Trust region subproblem (TRS) has been analyzed and developed so much in the optimization literature. For example, the conjugate gradient-based method leading to the Steihaug-Toint point is so much used. [Note: Here, the gradient refers to the gradient of the quadratic model, and it uses only Hessian-vector products.] http://www.ii.uib.no/~trond/publications/papers/trust.pdf. The authors spend so much effort developing their own algorithm! Also, in actual implementation, they only use a crude version of the inner algorithm for reasons of efficiency.

The paper does not say anything about the convergence of the full algorithm. How good are the trust region updates based on q_t given the huge variability associated with the mini-batch operation? The authors should look at several existing papers on stochastic trust region and stochastic quasi-Newton methods, e.g., papers from Katya Scheinberg (Lehigh) and Richard Byrd (Colorado)'s groups.

The best-claimed method of the method, called "Hybrid method" is also mentioned only in passing, and that too in a scratchy fashion (see end of subsec 4.3):
"To enjoy the best of both worlds, we also introduce a “hybrid” method in the Figure 3, that is, first run TR method for several epochs to get coarse solution and then run SGD for a while until fully converge. Our rule of thumb is, when the training accuracy raises slowly, run SGD for 10 epochs (because it’s already close to minimum). We find this “hybrid” method is both fast and accurate, for both small batch and large batch."

Explanations of better generalization properties of TR over SGD are important. I feel this part is badly done in the paper. For example, there is this statement:
"We observe that our method (TR) converges to solutions with much better test error but
worse training error when batch size is larger than 128. We postulate this is because SGD is easy to overfit training data and “stick” to a solution that has a high loss in testing data, especially with the large batch case as the inherent noise cannot push the iterate out of loss valley while our TR method can."
Frankly, I am unable to decipher what is being said here.

There is an explanation indicating that switching from SGD to TR causes an uphill movement (which I presume, is due to the trust region radius r being large); but statements such as - this will lead to climbing over to a wide minimum etc. are too strong; no evidence is given for this.

There is a statement - "even if the exact local minima is reached, the subsampled Hessian may still have negative curvature" - again, there is no evidence.

Overall, the paper only has a few interesting observations, but there is no good and detailed experimental analysis that help explain these observations.

The writing of the paper needs a lot of improvement.







review_title: A new stochastic method based on trust region (TR) is proposed. Experiments show improved generalization over mini-batch SGD. But the algorithm and its usefulness are neither developed nor explained well.

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper develops an efficient algorithm to solve the subproblem of the trust region method with an asymptotic linear convergence guarantee, and they demonstrate the performances of the trust region method incorporating their efficient solver in deep learning problems.  It shows better generation errors by trust region methods than SGD in different tasks, despite slower running time, and the authors speculate that trust-region method can escape sharp minima and converge to wide minima and they illustrated that through some hybrid experiment.
The paper is organized well.

1.  The result in Section 4.3 empirically showed that Trust Region Method could escape from sharp local minimum.  The results are interesting but not quite convincing.  The terms about sharp and wide minima are ambiguous.  At best, this provides a data point in an area that has received attention, but the lack of precision about sharp and wide makes it difficult to know what the more general conclusions are.  It might help to show the distance between the actual model parameters that those algorithms converge to.

2. As well know, VGG16 with well training strategy (learning rate decay) could achieve at least 92 percent accuracy. In the paper, the author only got around 83 percent accuracy with SGD and 85 percent accuracy with TR.  Why is this.

3. In section 4.2, it said "Although we can also define Hessian on ReLU function, it is not well supported on major platforms (Theano/PyTorch).  Likewise, we find max-pooling is also not supported by platforms to calculate higher order derivative, one way to walk around is to change all the max-pooling layers to avg- pooling, it hurts accuracy a little bit, albeit this is not our primary concern." It is my understanding that Pytorch support higher order derivative both for ReLu and Max-pooling.  Hence, it is not an explanation for not using ReLu and Max-pooling.  Please clarify

4. In section 4.3, the authors claimed that numerical diffentiation only hurts 1 percent error for second derivative. Please provide numerical support.

5. The setting of numerical experiments is not clear, e.g. value of N1 and N2.  This makes it hard to reproduce results.

5. It's not clear whether this is a theoretical paper or an empirical paper.  For example, there is a lot of math, but in Section 4.5 the authors seem to hedge and say "We give an intuitive explanation ... and leave the rigorous analysis to future works."  Please clarify.


review_title: See below.

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper proposes training neural networks using a trust region method, in which at each iteration a (non-convex) quadratic approximation of the objective function is found, and the minimizer of this quadratic within a fixed radius is chosen as the next iterate, with the radius of the trust region growing or shrinking at each iteration based on how closely the gains of the quadratic approximation matched those observed on the objective function. The authors claim that this approach is better at avoiding "narrow" local optima, and therefore will tend to generalize better than minibatched SGD. The main novelty seems to be algorithm 2, which finds the minimizer of the quadratic approximation within the trust region by performing GD iterations until the boundary is hit (if it is--it might not, if the quadratic is convex), and then Riemannian GD along the boundary.

The paper contains several grammatical mistakes, and in my opinion could explain things more clearly, particularly when arguing that the algorithm 2 will converge. I had particular difficulty accepting that the phase 1 GD iterates would never hit the boundary if the quadratic was strongly convex, although I accept that it is true due to the careful choice of step size and initialization (assumptions 1 and 2).

The central claim of the paper, that a trust region method will be better at avoiding narrow basins, seems plausible, since if the trust region is sufficiently large then it will simply pass straight over them. But if this is the case, wouldn't that imply that the quadratic approximation to the objective function is poor, and therefore that line 5 of algorithm 1 should shrink the trust region radius? Additionally, at some times the authors seem to indicate that the trust region method should be good at escaping from narrow basins (as opposed to avoiding them in the first place), see for example the left plot of figure 4. I don't see why this is true--the quadratic approximation would be likely to capture the narrow basin only.

This skepticism aside, the experiments in figure 2 do clearly show that, while the proposed approach doesn't converge nearly as quickly as SGD in terms of training loss, it does ultimately find a solution that generalizes better, as long as both SGD and TR use the same batch size (but I don't see why they should be using the same batch size). How does SGD with a batch size of 1 compare to TR with the batch sizes of 512 (CIFAR10) or 1024 (STL10)?

Section 4.3 (Figure 3) contain a very nice experiment that I think directly explores this issue, and seems to show that SGD with a batch size of 64 generalizes better than TR at any of the considered batch sizes (but not as well as the proposed TR+SGD hybrid). Furthermore, 64 was the smallest batch size considered, but SGD was performing monotonically better as the batch size decreased, so one would expect it to be still better for 32, 16, etc.

Smaller comments:

You say that you base the Hessian and gradient estimates on minibatched samples. I assume that the same is true for the evaluations of F on line 4 of Algorithm 1? Do these all use the same minibatch, at each iteration?

On the top of page 3: "M is the matrix size". Is this the number of elements, or the number of rows/columns?

Lemma 1: This looks correct to me, but are these the KKT conditions, which I understand to be first order optimality conditions (these are second order)? You cite Nocedal & Wright, but could you please provide a page number (or at least a chapter)?

On the top of page 5, "Line 10 of Algorithm 1": I think you mean Line 11 of Algorithm 2.
review_title: I'm not fully convinced by the experiments, and the writing quality could be improved.

Meta-review: There are two parts to this paper (1) an efficient procedure for solving trust-region subproblems in second-order optimization of neural nets, and (2) evidence that the proposed trust region method leads to better generalization performance than SGD in the large-batch setting. In both cases, there are some promising leads here. But it feels like two separate papers here, and I'm not sure either individual contribution is well enough supported to merit publication in ICLR.

For (1), the contribution is novel and potentially useful, to the best of my knowledge. But as there's been a lot of work on trust region solvers and second-order optimization of neural nets more generally, claims about computational efficiency would require comparisons against existing methods. The focus on efficiency also doesn't seem to fit with the experiments section, where the proposed method optimizes less efficiently than SGD and is instead meant to provide a regularization benefit.

For (2), it's an interesting empirical finding that the method improves generalization, but the explanation for this is very hand-wavy. If second-order optimization in general turned out to help with sharp minima, this would be an interesting finding indeed, but it doesn't seem to be supported by other work in the area. The training curves in Table 1 are interesting, but don't really distinguish the claims of Section 4.5 from other possible hypotheses.

Decision: Reject