During recent years there has been an increased interest in stochastic adaptations of limited memory quasi-Newton methods, which compared to pure gradientbased routines can improve the convergence by incorporating second order information. In this work we propose a direct least-squares approach conceptually similar to the limited memory quasi-Newton methods, but that computes the search direction in a slightly different way. This is achieved in a fast and numerically robust manner by maintaining a Cholesky factor of low dimension. This is combined with a stochastic line search relying upon fulfilment of the Wolfe condition in a backtracking manner, where the step length is adaptively modified with respect to the optimisation progress. We support our new algorithm by providing several theoretical results guaranteeing its performance. The performance is demonstrated on real-world benchmark problems which shows improved results in comparison with already established methods.
This paper presents a new quasi-Newton method for stochastic optimization that solves a regularized least-squares problem to approximate curvature information that relaxes both the symmetry and secant conditions typically ensured in quasi-Newton methods. In addition to this, the authors propose a stochastic Armijo backtracking line search to determine the steplength that utilizes an initial steplength of 1 but switches to a diminishing steplength in later iterations. In order to make this approach computationally tractable, the authors propose updating and maintaining a Cholesky decomposition of a crucial matrix in the Hessian approximation. Although it is a good attempt at developing a new method, the paper ultimately lacks a convincing explanation (both theoretical and empirical) supporting their ideas, as I will critique below.
1. Stochastic Line Search
Determining a steplength in the stochastic setting is a difficult problem, and I appreciate the authors’ attempt to attack this problem by looking at stochastic line searches. However, the paper lacks much detail and rigorous reasoning in the description and proof for the stochastic line search.
First, the theory gives conditions that the Armijo condition holds in expectation. Proving anything about stochastic line searches is particularly difficult, so I’m on board with proving a result in expectation and doing something different in practice. However, much of the detail on how this is implemented in practice is lacking. 
How are the samples chosen for the line search? If we go along with the proposed theory, then when the function is reevaluated in the line search, a new sample is used. If this is the case, can one guarantee that the practical Armijo condition will hold? How often does the line search fail? How does the choice of the samples affect the cost of evaluating the line search?
The theory also suggests that the particular choice of c is dependent on each iteration, particularly the inner product between the true search direction and the true gradient at iteration k. Does this allow for a fixed c to be used? How is c chosen? Is it fixed or adaptive? What happens as the true gradient approaches 0?
The algorithm also places a limit on the number of backtracks permitted that decreases as the iteration count increases. What does the algorithm do when the line search fails? Does one simply take the step although the Armijo condition does not hold?
In deterministic optimization, BFGS typically needs a smaller steplength in the beginning as the algorithm learns the scale of the problem, then eventually accepts the unit steplength to obtain fast local convergence. The line search proposed here uses an initial steplength of $\min(1, \xi/k)$ so that in early iterations, a steplength of 1 is used and in later iterations the algorithm uses a $\xi/k$ steplength. When this is combined with the diminishing maximum number of backtracking iterations, this will eventually yield an algorithm with a steplength of $\xi/k$. Why is this preferred? Are the other algorithms in the numerical experiments tuned similarly?
The theory also asks for a descent direction to be ensured in expectation. However, it is not the case that $E[\hat{p}_k^T \hat{g}_k] = E[\hat{p}_k]^T g_k$, so it is not correct to claim that a descent direction is ensured in expectation. Rather, the condition is requiring the angle between the negative stochastic gradient direction and search direction to be acute in expectation.
All the proofs also depend on a linear Taylor approximation that is not well-explained, and I’m wary of proofs that utilize approximations in this way. Indeed, the precise statement is that $\hat{f}_{z’} (x + \alpha \hat{p}_z) = \hat{f}_{z’} + \alpha \hat{p}_z’ \hat{g}_z(x + \bar{\alpha} \hat{p}_z)$, where $\bar{\alpha} \in [0, \alpha]$. How does this affect the proof?
Lastly, I would propose for the authors to change the name of their condition to the “Armijo condition” rather than using the term “1st Wolfe condition” since the Wolfe condition is typically associated with the curvature condition (p_k’ g_new >= c_2 p_k’ g_k), hence referring to a very different line search. 
2. Design of the Quasi-Newton Matrix
The authors develop an approach for designing the quasi-Newton matrix that does not strictly impose symmetry or the secant condition. The authors claim that this done because “it is not obvious that enforced symmetry necessarily produces a better search direction” and “treating the [secant] condition less strictly might be helpful when [the Hessian] approximation is poor”. This explanation seems insufficient to me to explain why relaxing these conditions via a regularized least-squares approach would yield a better algorithm, particularly in the noisy or stochastic setting. The lack of symmetry seems particularly strange; one would expect the true Hessian in the stochastic setting to still be symmetric, and one would still expect the secant condition to hold if the “true” gradients were accessible. It is also unclear how this approach takes advantage of the stochastic structure that exists within the problem.
Additionally, the quasi-Newton matrix is defined based on the solution of a regularized least squares problem with a regularization parameter lambda. It seems to me that the key to the approximation is the balance between the two terms in the objective. How is lambda chosen? What is the effect of lambda as a tuned parameter, and how does it affect the quality of the Hessian approximation? It is unclear to me how this could be chosen in a more systematic way.
The matrix also does not ensure positive definiteness, hence requiring a multiple of the gradient direction to be added to the search direction. In this case, the key parameter beta must be chosen carefully. What is a typical value of beta that is used for each of these problems? One would hope that beta is small, but if it is large, it may suggest that the search direction is primarily dominated by the stochastic gradient direction and hence the quasi-Newton matrix is not useful. The interplay of these different parameters needs to be investigated carefully.
Lastly, since (L-)BFGS use a weighted Frobenius norm, I am curious why the authors decided to use a non-weighted Frobenius norm to define the matrix. How does changing the norm affect the Hessian approximation?
All of these questions place the onus on the numerical experiments to see if these relaxations will ultimately yield a better algorithm.
3. Numerical Experiments
As written, although the range of problems is broad and the numerical experiments show much promise, I do not believe that I could replicate the experiments conducted in the paper. In particular, how is SVRG and L-BFGS tuned? How is the steplength chosen? What (initial) batch sizes are used? Is the progressive batching mechanism used? (If the progressive batching mechanism is not used, then the authors should refer to the original multi-batch paper by Berahas, et al. [1] which do not increase the batch size and use a constant steplength.)
In addition, a more fair comparison would include the stochastic quasi-Newton method in [2] that also utilize diminishing steplengths, which use Hessian-vector products in place of gradient differences. Multi-batch L-BFGS will only converge if the batch size is increased or the steplength diminished, and it’s not clear if either of these are done in the paper.
Typos/Grammatical Errors:
- Pg. 1: Commas are needed in some sentences, i.e. “Firstly, for large scale problems, it is…”; “…compute the cost function and its gradients, the result is…”
- Pg. 2: “Interestingly, most SG algorithms…”
- Pg 3: Remove “at least a” in second line
- Pg. 3: suboptimal, not sup-optimal
- Pg. 3: “Such a solution”, not “Such at solution”
- Pg. 3: Capitalize Lemma
- Pg. 4: fulfillment, not fulfilment
- Pg. 7: Capitalize Lemma
- Pg. 11: Before (42), Cov \hat{g} = \sigma_g^2 I
- Pg. 11: Capitalize Lemma
Summary:
In summary, although the ideas appear to provide better numerical performance, it is difficult to evaluate if the ideas proposed in this paper actually yield a better algorithm. Many algorithmic details are left unanswered, and the paper lacks mathematical or empirical evidence to support their claims. More experimental and theoretical work is needed before the manuscript can be considered for publication.
References:
[1] Berahas, Albert S., Jorge Nocedal, and Martin Takác. "A multi-batch l-bfgs method for machine learning." Advances in Neural Information Processing Systems. 2016.
[2] Byrd, Richard H., et al. "A stochastic quasi-Newton method for large-scale optimization." SIAM Journal on Optimization 26.2 (2016): 1008-1031.
[3] Schraudolph, Nicol N., Jin Yu, and Simon Günter. "A stochastic quasi-Newton method for online convex optimization." Artificial Intelligence and Statistics. 2007.