2017/02/02 by Aryan Mokhtari, Mark Eisen, Mokhtari, Aryan +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1702.00709
openalex publication_date 2017/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The problem of minimizing an objective that can be written as the sum of a\nset of n smooth and strongly convex functions is considered. The Incremental\nQuasi-Newton (IQN) method proposed here belongs to the family of stochastic and\nincremental methods that have a cost per iteration independent of n. IQN\niterations are a stochastic version of BFGS iterations that use memory to\nreduce the variance of stochastic approximations. The convergence properties of\nIQN bridge a gap between deterministic and stochastic quasi-Newton methods.\nDeterministic quasi-Newton methods exploit the possibility of approximating the\nNewton step using objective gradient differences. They are appealing because\nthey have a smaller computational cost per iteration relative to Newton's\nmethod and achieve a superlinear convergence rate under customary regularity\nassumptions. Stochastic quasi-Newton methods utilize stochastic gradient\ndifferences in lieu of actual gradient differences. This makes their\ncomputational cost per iteration independent of the number of objective\nfunctions n. However, existing stochastic quasi-Newton methods have sublinear\nor linear convergence at best. IQN is the first stochastic quasi-Newton method\nproven to converge superlinearly in a local neighborhood of the optimal\nsolution. IQN differs from state-of-the-art incremental quasi-Newton methods in\nthree aspects: (i) The use of aggregated information of variables, gradients,\nand quasi-Newton Hessian approximation matrices to reduce the noise of gradient\nand Hessian approximations. (ii) The approximation of each individual function\nby its Taylor's expansion in which the linear and quadratic terms are evaluated\nwith respect to the same iterate. (iii) The use of a cyclic scheme to update\nthe functions in lieu of a random selection routine. We use these fundamental\nproperties of IQN to establish its local superlinear convergence rate.\n