Distributed Gradient-Regularized Newton Method: Scheduled Consensus and O(epsilon^{-1}) Global Iteration Complexity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910235051950080 |
|---|---|
| author | Hu, Wei Xie, Pengcheng Yuan, Ya-Xiang Zhang, Li |
| author_facet | Hu, Wei Xie, Pengcheng Yuan, Ya-Xiang Zhang, Li |
| contents | We propose DisGrem, a fully decentralized second-order method for convex consensus optimization over networks. Each agent solves a local Newton system with vanishing gradient-norm regularization and an eigenvalue-shift stabilizer, communicating through a two-stage gossip-mixing mechanism. We introduce a reference-step framework that reduces the network-wide update to an inexact centralized regularized Newton step, replacing the static Hessian-heterogeneity assumptions of prior work with an increment-based dispersion analysis that imposes no irreducible accuracy floor. Under a bounded-iterates assumption, after a burn-in phase whose order is controlled by the scheduled consensus accuracy, the post-burn-in phase achieves an O(epsilon^{-1}) iteration complexity for driving the gradient norm below epsilon, matching the centralized regularized Newton rate without line search or stepsize tuning. For a logarithmic schedule with p >= 3, the total iteration complexity remains O(epsilon^{-1}). For a fixed connected network, this yields O(epsilon^{-1} log(1/epsilon)) neighbor communication rounds, with explicit spectral-gap dependence O((1-rho)^{-1} epsilon^{-1} log(1/epsilon)) as rho approaches 1. Under strong convexity and a relative tracking-accuracy condition, we further establish conditional local superlinear convergence of order 3/2. In our nine-problem benchmark suite, the DisGrem family attains relF <= 10^{-6} on every test instance, while the tested baselines stagnate or diverge on at least one problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_19396 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distributed Gradient-Regularized Newton Method: Scheduled Consensus and O(epsilon^{-1}) Global Iteration Complexity Hu, Wei Xie, Pengcheng Yuan, Ya-Xiang Zhang, Li Optimization and Control 90C25, 90C30, 65K05, 68W15 We propose DisGrem, a fully decentralized second-order method for convex consensus optimization over networks. Each agent solves a local Newton system with vanishing gradient-norm regularization and an eigenvalue-shift stabilizer, communicating through a two-stage gossip-mixing mechanism. We introduce a reference-step framework that reduces the network-wide update to an inexact centralized regularized Newton step, replacing the static Hessian-heterogeneity assumptions of prior work with an increment-based dispersion analysis that imposes no irreducible accuracy floor. Under a bounded-iterates assumption, after a burn-in phase whose order is controlled by the scheduled consensus accuracy, the post-burn-in phase achieves an O(epsilon^{-1}) iteration complexity for driving the gradient norm below epsilon, matching the centralized regularized Newton rate without line search or stepsize tuning. For a logarithmic schedule with p >= 3, the total iteration complexity remains O(epsilon^{-1}). For a fixed connected network, this yields O(epsilon^{-1} log(1/epsilon)) neighbor communication rounds, with explicit spectral-gap dependence O((1-rho)^{-1} epsilon^{-1} log(1/epsilon)) as rho approaches 1. Under strong convexity and a relative tracking-accuracy condition, we further establish conditional local superlinear convergence of order 3/2. In our nine-problem benchmark suite, the DisGrem family attains relF <= 10^{-6} on every test instance, while the tested baselines stagnate or diverge on at least one problem. |
| title | Distributed Gradient-Regularized Newton Method: Scheduled Consensus and O(epsilon^{-1}) Global Iteration Complexity |
| topic | Optimization and Control 90C25, 90C30, 65K05, 68W15 |
| url | https://arxiv.org/abs/2605.19396 |