Optimal Shrinkage for Distributed Second-Order Optimization
Optimal Shrinkage for Distributed Second-Order Optimization
复制标题
DOI：
--
复制
发表时间：
2024-02
期刊：
影响因子：
--
通讯作者：
Fangzhao Zhang;Mert Pilanci
中科院分区：
文献类型：
--
作者：
Fangzhao Zhang;Mert Pilanci
在这项工作中，我们解决了分布式二阶优化算法中的海森反演偏差问题。我们引入了一种新的基于收缩的估计的渐近无偏的克矩阵的预解式，并在迷向的情况下，其非渐近收敛速度的特点。我们将此估计应用于分布式二阶优化算法中牛顿步骤的偏差校正，以及基于随机草图的方法。我们研究的偏见存在于天真的平均为基础的分布式牛顿的方法使用解析表达式，并与我们提出的无偏见的方法进行对比。与标准基线和最近的建议相比，我们的方法在收敛速度上有了显着的改进，正如在真实的和合成数据集上的实验所示。
In this work, we address the problem of Hessian inversion bias in distributed second-order optimization algorithms. We introduce a novel shrinkage-based estimator for the resolvent of gram matrices which is asymptotically unbiased, and characterize its non-asymptotic convergence rate in the isotropic case. We apply this estimator to bias correction of Newton steps in distributed second-order optimization algorithms, as well as randomized sketching based methods. We examine the bias present in the naive averaging-based distributed Newton's method using analytical expressions and contrast it with our proposed bias-free approach. Our approach leads to significant improvements in convergence rate compared to standard baselines and recent proposals, as shown through experiments on both real and synthetic datasets.