Competing with the Empirical Risk Minimizer in a Single Pass
Roy Frostig Stanford University Rong Ge Microsoft Research, New England Sham M. Kakade Microsoft Research, New England Aaron Sidford MIT
Abstract
In many estimation problems, e.g. linear and logistic regression, we wish to minimize an unknown objective given only unbiased samples of the objective function. Furthermore, we aim to achieve this using as few samples as possible. In the absence of computational constraints, the minimizer of a sample average of observed data – commonly referred to as either the empirical risk minimizer (ERM) or the $M$ -estimator – is widely regarded as the estimation strategy of choice due to its desirable statistical convergence properties. Our goal in this work is to perform as well as the ERM, on every problem, while minimizing the use of computational resources such as running time and space usage.
中文速览
经验风险最小化（ERM, Empirical Risk Minimizer）在统计上被公认为最优估计策略，但直接计算它需要存储全部数据并反复遍历，代价高昂。这篇论文提出了一种名为 Streaming SVRG 的流式算法，只需对数据做单次扫描、占用常数级内存，就能在统计收敛率上与 ERM 完全匹配——不仅渐近等价，连常数因子都对齐，且初始误差以超多项式速率衰减。研究者同时给出了 ERM 本身的有限样本上下界，并严格量化了该算法在多少样本之后开始与 ERM 竞争，关键门槛约为问题条件数 κ=L/μ 的常数倍。这一结果首次在线性回归、逻辑回归等一大类广义线性模型上，同时实现了"统计最优、线性时间、常数内存、易并行"四个目标，为大规模在线学习提供了理论上有保障的实用方案。
原文 arXiv:1412.6606;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1412.6606v2