Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.15216 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917791711363072 |
|---|---|
| author | Gupta, Sunny Jindal, Mohit Kashyap, Pankhi Jeevan, Pranav Sethi, Amit |
| author_facet | Gupta, Sunny Jindal, Mohit Kashyap, Pankhi Jeevan, Pranav Sethi, Amit |
| contents | Federated learning faces a critical challenge in balancing communication efficiency with rapid convergence, especially for second-order methods. While Newton-type algorithms achieve linear convergence in communication rounds, transmitting full Hessian matrices is often impractical due to quadratic complexity. We introduce Federated Learning with Enhanced Nesterov-Newton Sketch (FLeNS), a novel method that harnesses both the acceleration capabilities of Nesterov's method and the dimensionality reduction benefits of Hessian sketching. FLeNS approximates the centralized Newton's method without relying on the exact Hessian, significantly reducing communication overhead. By combining Nesterov's acceleration with adaptive Hessian sketching, FLeNS preserves crucial second-order information while preserving the rapid convergence characteristics. Our theoretical analysis, grounded in statistical learning, demonstrates that FLeNS achieves super-linear convergence rates in communication rounds - a notable advancement in federated optimization. We provide rigorous convergence guarantees and characterize tradeoffs between acceleration, sketch size, and convergence speed. Extensive empirical evaluation validates our theoretical findings, showcasing FLeNS's state-of-the-art performance with reduced communication requirements, particularly in privacy-sensitive and edge-computing scenarios. The code is available at https://github.com/sunnyinAI/FLeNS |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15216 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch Gupta, Sunny Jindal, Mohit Kashyap, Pankhi Jeevan, Pranav Sethi, Amit Machine Learning Computer Vision and Pattern Recognition Distributed, Parallel, and Cluster Computing Optimization and Control I.2.6; C.1.4; D.1.3; I.5.1; H.3.4 Federated learning faces a critical challenge in balancing communication efficiency with rapid convergence, especially for second-order methods. While Newton-type algorithms achieve linear convergence in communication rounds, transmitting full Hessian matrices is often impractical due to quadratic complexity. We introduce Federated Learning with Enhanced Nesterov-Newton Sketch (FLeNS), a novel method that harnesses both the acceleration capabilities of Nesterov's method and the dimensionality reduction benefits of Hessian sketching. FLeNS approximates the centralized Newton's method without relying on the exact Hessian, significantly reducing communication overhead. By combining Nesterov's acceleration with adaptive Hessian sketching, FLeNS preserves crucial second-order information while preserving the rapid convergence characteristics. Our theoretical analysis, grounded in statistical learning, demonstrates that FLeNS achieves super-linear convergence rates in communication rounds - a notable advancement in federated optimization. We provide rigorous convergence guarantees and characterize tradeoffs between acceleration, sketch size, and convergence speed. Extensive empirical evaluation validates our theoretical findings, showcasing FLeNS's state-of-the-art performance with reduced communication requirements, particularly in privacy-sensitive and edge-computing scenarios. The code is available at https://github.com/sunnyinAI/FLeNS |
| title | FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch |
| topic | Machine Learning Computer Vision and Pattern Recognition Distributed, Parallel, and Cluster Computing Optimization and Control I.2.6; C.1.4; D.1.3; I.5.1; H.3.4 |
| url | https://arxiv.org/abs/2409.15216 |