On Convergence Analysis of Network-GIANT: An Approximate Hessian-Based Fully Distributed Optimization Algorithm

This paper presents a detailed convergence and performance analysis of a recently developed approximate Newton -type fully distributed optimization method for L-smooth, µ-strongly convex local loss functions, called Network-GIANT (inspired by the Federated learning algorithm GIANT possessing mixed linear- quadratic convergence properties). Network-GIANT has been empirically seen to achieve faster linear convergence properties compared to its gradient-based counterparts, and several other existing second order distributed algorithms, while having the same communication complexity (per iteration) as its first order distributed counterparts. We first explicitly characterize a global linear convergence rate for Network-GIANT, which can be computed as the spectral radius of a 3 × 3 matrix dependent on L, µ, and the spectral norm (σ) of the consensus matrix of the underlying undirected graph. We provide an explicit bound on the step size parameter η, below which this spectral radius is guaranteed to be less than 1. Furthermore, we derive a mixed linear- quadratic inequality based upper bound for the optimality gap norm, and provide a rigorous proof of a local asymptotic convergence rate of (Formula presented) given the Hessian approximation error γ < µ, which formally explains the faster convergence rate of Network-GIANT. Numerical experiments are carried out with a reduced CovType dataset for binary logistic regression over a variety of graphs, including heterogeneous data distributions, to illustrate the above theoretical results.