Stochastic Quasi-Gradient Methods: Variance Reduction via Jacobian Sketching
Robert M. Gower222Télécom ParisTech, France. Peter Richtárik333King Abdullah University of Science and Technology (KAUST), Saudi Arabia — University of Edinburgh, United Kingdom — Moscow Institute of Physics and Technology (MIPT), Russia. Francis Bach444INRIA - ENS - PSL Research University, France.
Abstract
We develop a new family of variance reduced stochastic gradient descent methods for minimizing the average of a very large number of smooth functions. Our method—JacSketch—is motivated by novel developments in randomized numerical linear algebra, and operates by maintaining a stochastic estimate of a Jacobian matrix composed of the gradients of individual functions. In each iteration, JacSketch efficiently updates the Jacobian matrix by first obtaining a random linear measurement of the true Jacobian through (cheap) sketching, and then projecting the previous estimate onto the solution space of a linear matrix equation whose solutions are consistent with the measurement. The Jacobian estimate is then used to compute a variance-reduced unbiased estimator of the gradient, followed by a stochastic gradient descent step. Our strategy is analogous to the way quasi-Newton methods maintain an estimate of the Hessian, and hence our method can be seen as a stochastic quasi-gradient method. Indeed, quasi-Newton methods project the current Hessian estimate onto a solution space of a linear equation consistent with a certain linear (but non-random) measurement of the true Hessian. Our method c
中文速览
有一大类机器学习训练问题可以写成"对海量函数求平均再最小化"的形式，而现有的随机梯度方法（如SAGA）要么方差大、收敛慢，要么对重要性采样和小批量策略缺乏完整的理论保证。这篇论文提出了一种叫做"雅可比矩阵素描"（Jacobian Sketching，JacSketch）的新框架：每次迭代时，先用一个随机"素描矩阵"对真实雅可比矩阵做廉价的随机线性测量，再把上一步的雅可比估计投影到与该测量相容的解空间，从而持续维护并更新一个低成本的雅可比估计，进而构造出方差逐步收缩的无偏梯度估计量来驱动随机梯度下降——这一思路与拟牛顿法维护黑塞矩阵估计的逻辑高度类比。理论上，作者证明了在强凸光滑条件下JacSketch线性收敛，并通过选取不同的素描策略，将SAGA及其众多小批量、重要性采样变体统一纳入同一框架，同时证明了Schmidt等人2015年关于SAGA重要性采样最优速率的猜想，并给出了首个带重要性采样的小批量SAGA方法。这项工作不仅在理论上填补了方差缩减方法长期存在的空白，也为系统性地设计和分析新型随机优化算法提供了统一的工具。
原文 arXiv:1805.02632;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1805.02632v1