Research map / Optimization / Distributed and compressed
Communication Efficient Distributed Newton Method over Unreliable Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RED-New, a packet-loss-resilient distributed approximate Newton method that transmits O(d) vectors per round with a statistical loss-rate scaling strategy, and proves local linear-quadratic convergence.
Problem
Distributed second-order (Newton-type) optimization over unreliable uplink networks where packet loss corrupts gradients and local Hessian-based directions, causing instability and high communication cost of O(d^2) Hessian transmission.
Approach
Clients send gradients and local approximate Newton directions (local Hessian inverse times the global gradient) in packetized form over lossy uplink; the server aggregates each block with a scaling factor 1/(1 - empirical packet-loss rate) estimated from zero-valued received blocks, requiring no prior knowledge of the loss rate.
Key results
- At 40% packet loss, RED-New reduces traffic by an average of 92.33% vs. gradient descent and 61.69% vs. GIANT to reach the target objective.
- The standard distributed Newton method fails to converge even at 5% packet loss, while RED-New and GIANT converge much faster than gradient descent.
- RED-New achieves a local linear-quadratic convergence rate under Hessian-sketching assumptions (Theorems 1-2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RED-New instead of GIANT | Distributed logistic regression · a9a, w8a, and gisette; 5%, 20%, and 40% packet loss | traffic volume (KB): 356 -> 325; 664 -> 593; 39 -> 39; 500 -> 331; 945 -> 585; 78 -> 39; 887 -> 337; 1555 -> 679; 117.19 -> 39 | Helped |
| Use RED-New instead of GD | Distributed logistic regression · a9a, w8a, and gisette; 5%, 20%, and 40% packet loss | traffic volume (KB): 3931 -> 325; 2449 -> 593; 12343 -> 39; 4668 -> 331; 2875 -> 585; 14726 -> 39; 6246 -> 337; 3902 -> 679; 19512 -> 39 | Helped |
| Apply packet-loss-resilient RED-New rather than standard distributed Newton | Distributed logistic regression · a9a, w8a, and gisette; packet loss from 5% to 40% | training loss convergence | Helped |
| Apply RED-New rather than GIANT | Distributed logistic regression · a9a, w8a, and gisette; high packet loss | training rounds to convergence | Helped |
Surprising findings
- The standard Newton method does not converge even at 5% packet loss, showing extreme sensitivity to Hessian imprecision.
Limitations
- Experiments limited to logistic regression on three LIBSVM datasets with 8 workers.
- Theory relies on sketching-based local Hessian approximation assumptions and holds only locally.
- Uses a uniform, i.i.d. packet loss model; the trade-off with FEC/retransmission is left as future work.
Experimental setup
Datasets: a9a w8a gisette
Benchmarks: a9a w8a gisette
Metrics: training loss uplink traffic volume (KB) number of training rounds
Baselines: distributed gradient descent standard distributed Newton method GIANT
Builds on: GIANT FedNL Distributed Learning over Unreliable Networks (RSP) Approximate Newton Methods
Closest papers by meaning
- Distributed Second Order Methods with Fast Rates and Compressed Communication (ICML 2021 · similarity 0.88)
- Distributed Newton Can Communicate Less and Resist Byzantine Workers (NeurIPS 2020 · similarity 0.88)
- Near-Optimal Distributed Minimax Optimization under the Second-Order Similarity (NeurIPS 2024 · similarity 0.86)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.85)
- Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity (NeurIPS 2024 · similarity 0.85)
- Distributed Bilevel Optimization with Communication Compression (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.