A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 5 SQN Framework [132] <s> RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments can be prohibitive in high dimensional problems. Application of second order methods, on the other hand, is impracticable because computation of objective function Hessian inverses incurs excessive computational cost. BFGS modifies gradient descent by introducing a Hessian approximation matrix computed from finite gradient differences. RES utilizes stochastic gradients in lieu of deterministic gradients for both, the determination of descent directions and the approximation of the objective function's curvature. Since stochastic gradients can be computed at manageable computational cost RES is realizable and retains the convergence rate advantages of its deterministic counterparts. Convergence results show that lower and upper bounds on the Hessian egeinvalues of the sample functions are sufficient to guarantee convergence to optimal arguments. Numerical experiments showcase reductions in convergence time relative to stochastic gradient descent algorithms and non-regularized stochastic versions of BFGS. An application of RES to the implementation of support vector machines is developed. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 5 SQN Framework [132] <s> Global convergence of an online (stochastic) limited memory version of the Broyden-Fletcher- Goldfarb-Shanno (BFGS) quasi-Newton method for solving optimization problems with stochastic objectives that arise in large scale machine learning is established. Lower and upper bounds on the Hessian eigenvalues of the sample functions are shown to suffice to guarantee that the curvature approximation matrices have bounded determinants and traces, which, in turn, permits establishing convergence to optimal arguments with probability 1. Numerical experiments on support vector machines with synthetic data showcase reductions in convergence time relative to stochastic gradient descent algorithms as well as reductions in storage and computation relative to other online quasi-Newton methods. Experimental evaluation on a search engine advertising problem corroborates that these advantages also manifest in practical applications. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 5 SQN Framework [132] <s> The question of how to incorporate curvature information in stochastic approximation methods is challenging. The direct application of classical quasi- Newton updating techniques for deterministic optimization leads to noisy curvature estimates that have harmful effects on the robustness of the iteration. In this paper, we propose a stochastic quasi-Newton method that is efficient, robust and scalable. It employs the classical BFGS update formula in its limited memory form, and is based on the observation that it is beneficial to collect curvature information pointwise, and at regular intervals, through (sub-sampled) Hessian-vector products. This technique differs from the classical approach that would compute differences of gradients, and where controlling the quality of the curvature estimates can be difficult. We present numerical results on problems arising in machine learning that suggest that the proposed method shows much promise. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 5 SQN Framework [132] <s> We propose a new stochastic L-BFGS algorithm and prove a linear convergence rate for strongly convex and smooth functions. Our algorithm draws heavily from a recent stochastic variant of L-BFGS proposed in Byrd et al. (2014) as well as a recent approach to variance reduction for stochastic gradient descent from Johnson and Zhang (2013). We demonstrate experimentally that our algorithm performs well on large-scale convex and non-convex optimization problems, exhibiting linear convergence and rapidly solving the optimization problems to high levels of precision. Furthermore, we show that our algorithm performs well for a wide-range of step sizes, often differing by several orders of magnitude. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> Algorithm 5 SQN Framework [132] <s> We propose a novel limited-memory stochastic block BFGS update for incorporating enriched curvature information in stochastic approximation methods. In our method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. We propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods. <s> BIB005
Input: The solution θ * for t=1, 2, 3, 4,....., do s ′ t = H t g t using the two-loop recursion. In the above algorithm, V = {s t , u t } is a collection of m displacement pairs, and g t is the current stochastic gradient ∇F St (θ t ). Meanwhile, the matrix-vector product H t g t can be computed by a two-loop recursion as described in the previous section. Recently, more and more work has achieved very good results in stochastic quasi-Newton. Specifically, a regularized stochastic BFGS method was proposed, which makes a corresponding analysis of the convergence of this optimization method BIB001 . Further, an online L-BFGS was presented in BIB002 . A linearly convergent method was proposed BIB004 , which combines the L-BFGS method in BIB003 with the variance reduction technique. Besides these, a variance reduced block L-BFGS method was proposed, which works by employing the actions of a sub-sampled Hessian on a set of random vectors BIB005 . To sum up, we have discussed the techniques of using stochastic methods in second-order optimization. The stochastic quasi-Newton method is a combination of the stochastic method and the quasi-Newton method, which makes the quasiNewton method extend to large datasets. We introduced the related work of the stochastic quasi-Newton method in recent years, which reflects the potential of the stochastic quasiNewton method in machine learning applications.