SEGA: Variance Reduction via Gradient Sketching
Filip Hanzely Konstantin Mishchenko Peter Richtárik King Abdullah University of Science and Technology, Kingdom of Saudi ArabiaKing Abdullah University of Science and Technology, Kingdom of Saudi ArabiaKing Abdullah University of Science and Technology, Kingdom of Saudi Arabia — School of Mathematics, University of Edinburgh, United Kingdom — Moscow Institute of Physics and Technology, Russia
Abstract
We propose a randomized first order optimization method—SEGA (SkEtched GrAdient)—which progressively throughout its iterations builds a variance-reduced estimate of the gradient from random linear measurements (sketches) of the gradient obtained from an oracle. In each iteration, SEGA updates the current estimate of the gradient through a sketch-and-project operation using the information provided by the latest sketch, and this is subsequently used to compute an unbiased estimate of the true gradient through a random relaxation procedure. This unbiased estimate is then used to perform a gradient step. Unlike standard subspace descent methods, such as coordinate descent, SEGA can be used for optimization problems with a non-separable proximal term. We provide a general convergence analysis and prove linear convergence for strongly convex objectives. In the special case of coordinate sketches, SEGA can be enhanced with various techniques such as importance sampling, minibatching and acceleration, and its rate is up to a small constant factor identical to the best-known rate of coordinate descent.
中文速览
坐标下降（Coordinate Descent）等子空间优化方法只能处理可分离的正则项，遇到非可分离约束就束手无策，而梯度草图（gradient sketch）这类随机线性观测信息又难以直接用于带正则项的复合优化。针对这一缺口，论文提出了 SEGA（SkEtched GrAdient）算法：每轮迭代中，SEGA 用"草图-投影"操作把最新的梯度草图融入累积估计，再通过随机松弛构造出真实梯度的无偏估计，最后以此为方向执行近端梯度步；随着迭代推进，该估计的方差逐渐趋零，使 SEGA 具有方差缩减性质。理论分析证明，在强凸目标下 SEGA 线性收敛，且在坐标草图的特例下，结合重要性采样、小批量和加速技术后，其收敛速率与目前已知最优的坐标下降率仅差一个小常数因子。这项工作的重要性在于，它将坐标/子空间下降方法的适用范围从可分离正则项扩展到任意凸正则项，同时支持几乎任意分布的草图，为约束优化、零阶优化等众多场景打开了新的大门。
原文 arXiv:1809.03054;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1809.03054v2