Reproduce “Quasi-Newton Updating for Large-Scale Distributed Learning” on OpenResearch

About this paper

Shuyuan Wu, Danyang Huang, Hansheng Wang

Researchers from Shanghai University of Finance and Economics, Renmin University of China, and Peking University introduce a distributed quasi-Newton framework for large-scale statistical learning. This method achieves optimal statistical efficiency with O(p) communication cost per iteration within a finite number of stages, demonstrating superior computational and communication times compared to existing distributed learning algorithms.

Key insights

• The one-stage DQN (DQN(1)) estimator achieves optimal statistical efficiency (asymptotic equivalence to global MLE) under the mild condition N(p log p)²/n⁴ → 0, requiring only 3 rounds of O(p) communication.
• Multi-stage DQN(K) estimators further improve statistical efficiency, achieving optimality under even weaker conditions (N p^(2K) (log p)^(K+1) / n^(2K+2) → 0), with K representing a small, finite number of stages.
• The proposed framework inherently avoids O(p³) computation associated with Hessian inversion and O(p²) communication of Hessian matrices, instead relying on O(p) vector operations per communication round.

Summary by alphaXiv.