Accelerated Distributed Approximate Newton Method.

Area of Science:

• Machine Learning
• Optimization Theory
• Distributed Computing

Background:

• Distributed second-order optimization is crucial for large-scale machine learning due to low communication complexity.
• Existing methods like DANE, AIDE, and SPAG require precise subproblem solutions, leading to high computation costs.
• This high computational burden hinders the development and application of current distributed optimization algorithms.

Purpose of the Study:

• To design a novel distributed second-order algorithm, the accelerated distributed approximate Newton (ADAN) method.
• To overcome the significant computation costs associated with existing distributed second-order optimization algorithms.
• To achieve both communication and computational efficiency in distributed optimization.

Main Methods:

• Developed the accelerated distributed approximate Newton (ADAN) method.
• ADAN is founded on inexact Newton theory, differing from the relative smooth theory used by DANE, AIDE, and SPAG.
• The method efficiently handles expensive subproblems with steps independent of target precision and incorporates acceleration.

Main Results:

• ADAN efficiently solves subproblems, reducing computation costs compared to existing methods.
• The algorithm leverages acceleration and curvature information for low communication complexity.
• Empirical studies validate ADAN's superior performance over existing distributed second-order algorithms.

Conclusions:

• The ADAN method achieves both communication and computational efficiency, a significant advancement over prior algorithms.
• Its foundation in inexact Newton theory allows for efficient subproblem handling, independent of precision requirements.
• ADAN offers a more efficient approach to distributed second-order optimization for large-scale machine learning.