N. Agarwal, B. Bullins, and E. Hazan, Second-order stochastic optimization for machine learning in linear time, The Journal of Machine Learning Research, vol.18, issue.1, pp.4148-4187, 2017.

S. Albert, R. Berahas, J. Bollapragada, and . Nocedal, An investigation of Newton-sketch and subsampled Newton methods, 2017.

S. Albert, J. Berahas, and . Nocedal, year=2016 Taká?, Martin, bookti-tle=Advances in Neural Information Processing Systems. A multi-batch l-bfgs method for machine learning, pp.1055-1063

. Charles-g-broyden, Quasi-Newton methods and their application to function minimisation, Mathematics of Computation, vol.21, issue.99, pp.368-381, 1967.

H. Richard, G. M. Byrd, W. Chin, J. Neveitt, and . Nocedal, On the use of stochastic hessian information in optimization methods for machine learning, SIAM Journal on Optimization, vol.21, issue.3, pp.977-995, 2011.

H. Richard, S. L. Byrd, J. Hansen, Y. Nocedal, and . Singer, A stochastic quasi-Newton method for large-scale optimization, SIAM Journal on Optimization, vol.26, issue.2, pp.1008-1031, 2016.

C. Chang and C. Lin, Libsvm: A library for support vector machines, ACM Trans. Intell. Syst. Technol, vol.2, issue.3, p.27, 2011.

F. Curtis, A self-correcting variable-metric algorithm for stochastic optimization, International Conference on Machine Learning, pp.632-641, 2016.

A. Charles, . Desoer, H. Barry, and . Whalen, A note on pseudoinverses, Journal of the Society of Industrial and Applied Mathematics, vol.11, issue.2, pp.442-447, 1963.

R. Fletcher, A new approach to variable metric algorithms, The computer journal, vol.13, issue.3, pp.317-322, 1970.

D. Goldfarb, A family of variable-metric methods derived by variational means, Mathematics of computation, vol.24, issue.109, pp.23-26, 1970.

M. Robert, D. Gower, P. Goldfarb, and . Richtárik, Stochastic block BFGS: Squeezing more curvature out of data, International Conference on Machine Learning, pp.1869-1878, 2016.

M. Robert, P. Gower, and . Richtárik, Randomized iterative methods for linear systems, SIAM Journal on Matrix Analysis and Applications, vol.36, issue.4, pp.1660-1690, 2015.

M. Robert, P. Gower, and . Richtárik, Stochastic dual ascent for solving linear systems, 2015.

M. Robert, P. Gower, and . Richtárik, Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms, SIAM Journal on Matrix Analysis and Applications, vol.38, issue.4, pp.1380-1409, 2017.

S. Kaczmarz, Angenäherte Auflösung von Systemen linearer Gleichungen, Sciences et des Lettres, vol.35, pp.355-357, 1937.

C. Dong, J. Liu, and . Nocedal, On the limited memory BFGS method for large scale optimization. Mathematical programming, vol.45, pp.503-528, 1989.

J. Liu, J. Stephen, and . Wright, An accelerated randomized Kaczmarz algorithm, Math. Comput, vol.85, issue.297, pp.153-178, 2016.

N. Loizou and P. Richtárik, Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods, 2017.

A. Mokhtari and A. Ribeiro, Global convergence of online limited memory BFGS, The Journal of Machine Learning Research, vol.16, pp.3151-3181, 2015.

P. Moritz, R. Nishihara, and M. Jordan, A linearly-convergent stochastic L-BFGS algorithm, Artificial Intelligence and Statistics, pp.249-258, 2016.

Y. Nesterov, A method of solving a convex programming problem with convergence rate O(1/k 2 ), Soviet Mathematics Doklady, vol.27, issue.2, pp.372-376, 1983.

Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM Journal on Optimization, vol.22, issue.2, pp.341-362, 2012.

Y. Nesterov, U. Sebastian, and . Stich, Efficiency of the accelerated coordinate descent method on structured optimization problems, SIAM Journal on Optimization, vol.27, issue.1, pp.110-123, 2017.

K. Gert and . Pedersen, Graduate Texts in Mathematics, 1996.

M. Pilanci, J. Martin, and . Wainwright, Newton sketch: A near linear-time optimization algorithm with linear-quadratic convergence, SIAM Journal on Optimization, vol.27, issue.1, pp.205-245, 2017.

P. Richtárik and M. Taká?, Stochastic reformulations of linear systems: accelerated method. Manuscript, 2017.

P. Richtárik and M. Taká?, Stochastic reformulations of linear systems: algorithms and convergence theory, 2017.

N. Nicol, J. Schraudolph, S. Yu, and . Günter, A stochastic quasi-Newton method for online convex optimization, Artificial Intelligence and Statistics, pp.436-443, 2007.

F. David and . Shanno, Conditioning of quasi-Newton methods for function minimization, Mathematics of computation, vol.24, issue.111, pp.647-656, 1970.

U. Sebastian and . Stich, Convex Optimization with Random Pursuit, 22111.

U. Sebastian, . Stich, L. Christian, B. Müller, and . Gärtner, Variable metric random pursuit, Mathematical Programming, vol.156, issue.1, pp.549-579, 2016.

T. Strohmer and R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, Journal of Fourier Analysis and Applications, vol.15, issue.2, p.262, 2009.

S. Tu, S. Venkataraman, C. Ashia, A. Wilson, . Gittens et al., Breaking locality accelerates block Gauss-Seidel, Proceedings of the 34th International Conference on Machine Learning, pp.3482-3491, 2017.

X. Wang, S. Ma, D. Goldfarb, and W. Liu, Stochastic quasi-Newton methods for nonconvex stochastic optimization, SIAM Journal on Optimization, vol.27, issue.2, pp.927-956, 2017.

J. Stephen and . Wright, Coordinate descent algorithms, Math. Program, vol.151, issue.1, pp.3-34, 2015.

P. Xu, F. Roosta-khorasani, and M. W. Mahoney, Newton-type methods for non-convex optimization under inexact hessian information, 2017.

P. Xu, J. Yang, F. Roosta-khorasani, C. Ré, and M. W. Mahoney, Sub-sampled newton methods with non-uniform sampling, Advances in Neural Information Processing Systems, pp.3000-3008, 2016.