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, \(\mu\)-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$, $\mu$, and the spectral norm ($\sigma$) of the consensus matrix of the underlying undirected graph.

We provide an explicit bound on the step size parameter $\eta$, 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 - \eta \big(1 - \frac{\gamma}{\mu}\big)\) given the Hessian approximation error $\gamma < \mu$, 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.