Better Mini-Batch Algorithms via Accelerated Gradient Methods
Andrew Cotter TTIC Chicago, IL 60637 USA Ohad Shamir Microsoft Research Cambridge, MA 02142, USA Nathan Srebro TTIC Chicago, IL 60637 USA Karthik Sridharan TTIC Chicago, IL 60637 USA
Abstract
Mini-batch algorithms have been proposed as a way to speed-up stochastic convex optimization problems. We study how such algorithms can be improved using accelerated gradient methods. We provide a novel analysis, which shows how standard gradient methods may sometimes be insufficient to obtain a significant speed-up and propose a novel accelerated gradient algorithm, which deals with this deficiency, enjoys a uniformly superior guarantee and works well in practice.
中文速览
随机优化中的小批量（mini-batch）训练可以通过并行计算加快速度，但普通随机梯度下降（SGD）在某些关键场景下——尤其是当目标函数的最优损失值 L(w*) 接近零（如线性可分问题）时——无论批量多大都几乎得不到加速，这一缺陷此前未被充分揭示。本文通过引入损失函数的"自界性质"（self-bounding property），对 SGD 和加速梯度（accelerated gradient, AG）方法同时给出了依赖于 L(w*) 的更精细收敛界，清楚地刻画了两者在不同参数区间下的行为差异。在此基础上，作者提出了一种新的小批量加速梯度算法，其步长按幂次 i^p（p<1）增长，隐式自适应于 L(w*)，理论上始终能从增大批量中获得显著加速，且收敛上界在所有参数区间均优于标准 SGD。实验结果验证了理论预测，表明在实际学习任务中该加速方法确实比 SGD 收敛更快，为大规模并行优化提供了更有效的理论工具和实用算法。
原文 arXiv:1106.4574;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1106.4574v1