SUCAG: Stochastic Unbiased Curvature-aided Gradient Method for Distributed Optimization
SUCAG: Stochastic Unbiased Curvature-aided Gradient Method for Distributed Optimization
复制标题
DOI：
10.1109/cdc.2018.8619336
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Hoi-To Wai;N. Freris;A. Nedić;A. Scaglione
中科院分区：
文献类型：
--
作者：
Hoi-To Wai;N. Freris;A. Nedić;A. Scaglione
针对有限和优化问题，我们提出并分析了一种新的随机梯度算法，称为随机无偏曲率辅助梯度算法(SUCAG)。SUCAG构成了一种利用海森信息加速收敛的无偏总梯度跟踪技术。我们在一般的异步计算模型下分析了我们的方法，在该模型中，每个函数被无限频繁地选择，并且可能具有无界(但次线性)延迟。对于强凸问题，我们建立了SUCAG方法的线性收敛。当初始点足够接近最优解时，所建立的收敛速度仅依赖于问题的条件数，使其严格快于已知的SAGA方法的收敛速度。此外，我们描述了一种马尔可夫驱动的方法，通过沿着无向通信图上的随机游走进行八卦，在分布式异步多代理环境中实现SUCAG方法。我们证明了只要图是连通的，我们的分析就适用，并且值得注意的是，我们的分析建立了对图的拓扑鲁棒的渐近线性收敛速度。数值结果证明了该算法优于已有方法的优点。
We propose and analyze a new stochastic gradient method, which we call Stochastic Unbiased Curvature-aided Gradient (SUCAG), for finite sum optimization problems. SUCAG constitutes an unbiased total gradient tracking technique that uses Hessian information to accelerate convergence. We analyze our method under the general asynchronous model of computation, in which each function is selected infinitely often with possibly unbounded (but sublinear) delay. For strongly convex problems, we establish linear convergence for the SUCAG method. When the initialization point is sufficiently close to the optimal solution, the established convergence rate is only dependent on the condition number of the problem, making it strictly faster than the known rate for the SAGA method. Furthermore, we describe a Markov-driven approach of implementing the SUCAG method in a distributed asynchronous multi-agent setting, via gossiping along a random walk on an undirected communication graph. We show that our analysis applies as long as the graph is connected and, notably, establishes an asymptotic linear convergence rate that is robust to the graph topology. Numerical results demonstrate the merits of our algorithm over existing methods.