On Convergence Analysis of Network-GIANT: An approximate Hessian-based fully distributed optimization algorithm

Abstract

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 \emph{global linear convergence rate} for Network-GIANT, which can be computed as the spectral radius of a $3\times 3$ matrix dependent on $L$, $\hat{I}¼$, and the spectral norm ($\ddot{I}ƒ$) of the consensus matrix of the underlying undirected graph. We provide an explicit bound on the step size parameter $\hat{I}\cdot$, 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 \(1 - η\big(1 - \fracγμ\big)\) given the Hessian approximation error ${\hat{I}}^3<\hat{I}¼$, 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.

12 pages, 9 figures