Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices in such a way that all iterates (approximate solutions) generated by the algorithm are positive definite matrices themselves. This opens the way for many applications in the field of optimization and machine learning. As an application of our general theory, we develop the first accelerated (deterministic and stochastic) quasi-Newton updates. Our updates lead to provably more aggressive approximations of the inverse Hessian, and lead to speed-ups over classical non-accelerated rules in numerical experiments. Experiments with empirical risk minimization show that our rules can accelerate training of machine learning models.
This paper presents an accelerated version of the sketch-and-project algorithm, an accelerated algorithm for matrix inversion and accelerated variants of deterministic and stochastic quasi-Newton updates. I strongly believe that this line of research is of interest for the ML and optimization communities, and that the algorithms and theoretical results presented in this paper are significant and novel. Moreover, the numerical results presented in the paper clearly illustrate the effectiveness of the approaches presented in the paper. For this reason, I strongly recommend this paper for publication. Below I list my minor concerns with the paper.  - The paper is clearly written and easy to read, however, I believe that in several places there are grammatical errors or minor typos. These are easy to fix. A few examples are: — Line 25: liner system in each iteration -> linear system at each iteration — Line 27: in particular the BFGS -> in particular BFGS — Line 116: which in term -> which in turn — Line 122-123: Sentence starting with “This is a very general problem…” has a grammatical issue. — Line 142: in the special case -> for the special case — Line 247: inverting a matrix symmetric positive matrix A -> inverting a symmetric positive definite matrix A — Line 263-264: Sentence starting with “We also observe from…” is not clear. — Line 266: as fast as nonaccelerated algorithm -> as fast as the nonaccelerated algorithm  - I strongly believe that a Final Remarks and Future Work (Extensions) section is missing from the paper. This section would help the reader summarize the contributions of the paper and understand the significance and possible extensions of this work.  - Other Minor Issues: — The authors should explain how alpha, beta and gamma are chosen in the Algorithms, and why these choices were made.  — Line 207: Issue with reference to (4.2)? — Line 230: Issue with equation reference? — Reference [32] and [33] is the same — Reference section lacks consistency (names of authors)   - I believe that there are some missing references in the paper.  — stochastic quasi-Newton methods: 1) A self-correcting variable-metric algorithm for stochastic optimization (http://proceedings.mlr.press/v48/curtis16.pdf), 2) A multi-batch l-bfgs method for machine learning (http://papers.nips.cc/paper/6145-a-multi-batch-l-bfgs-method-for-machine-learning.pdf) — subsampled Newton methods: 1) Sub-sampled Newton methods I: globally convergent algorithms (https://arxiv.org/pdf/1601.04737.pdf), 2) Newton-type methods for non-convex optimization under inexact hessian information (https://arxiv.org/pdf/1708.07164.pdf), 3) On the use of stochastic hessian information in optimization methods for machine learning (https://pdfs.semanticscholar.org/ba21/5739785c21704dc2a6c8fa235c52cab0f45d.pdf), (4) Convergence rates of sub-sampled Newton methods (https://arxiv.org/abs/1508.02810)