Communication-efficient distributed cubic Newton with compressed lazy Hessian.

Area of Science:

• Distributed machine learning
• Optimization algorithms

Background:

• Second-order distributed optimization algorithms offer faster convergence than first-order methods.
• A major challenge is the communication bottleneck inherent in second-order algorithms.

Purpose of the Study:

• To propose communication-efficient second-order distributed optimization algorithms within the parameter-server framework.
• To address the communication bottleneck while retaining the benefits of second-order methods.

Main Methods:

• Incorporation of cubic Newton methods with compressed lazy Hessians.
• Workers communicate compressed Hessians with the server selectively, reducing communication overhead.
• Application of gradient regularization for convex problems.

Main Results:

• Theoretical proof of reduced communication costs for non-convex problems compared to state-of-the-art methods.
• Maintained iteration complexity of O(ϵ -3/2) for non-convex problems, matching centralized cubic Newton methods.
• Achieved global convergence for convex problems and local superlinear convergence for strongly convex problems.

Conclusions:

• The proposed algorithms effectively reduce communication costs in distributed learning.
• They maintain competitive iteration complexity and achieve strong convergence guarantees for various problem types.
• Numerical experiments validate the high efficiency of the developed algorithms.