A Stochastic Newton Algorithm for Distributed Convex Optimization
A Stochastic Newton Algorithm for Distributed Convex Optimization
复制标题
DOI：
--
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Brian Bullins;Kumar Kshitij Patel;Ohad Shamir;N. Srebro;Blake E. Woodworth
中科院分区：
文献类型：
--
作者：
Brian Bullins;Kumar Kshitij Patel;Ohad Shamir;N. Srebro;Blake E. Woodworth
我们提出并分析了均匀分布随机凸优化的随机牛顿算法，其中每台机器可以计算相同人口目标的随机梯度，以及随机Hessian向量乘积（人口目标的Hessian的独立无偏估计与任意向量的乘积），在通信轮之间执行许多这样的随机计算。我们表明，与现有方法相比，我们的方法可以减少所需通信轮的数量和频率，而不会损害性能，通过证明准自协调目标的收敛保证（例如，逻辑回归（logistic regression），以及经验证据。
We propose and analyze a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization, where each machine can calculate stochastic gradients of the same population objective, as well as stochastic Hessian-vector products (products of an independent unbiased estimator of the Hessian of the population objective with arbitrary vectors), with many such stochastic computations performed between rounds of communication. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance, by proving convergence guarantees for quasi-self-concordant objectives (e.g., logistic regression), alongside empirical evidence.