Abstract: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.
From: Souvik Das [view email]
[v1]
Mon, 16 Feb 2026 15:22:04 UTC (1,056 KB)
[v2]
Fri, 3 Jul 2026 03:45:21 UTC (1,134 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。