Accelerated Stochastic DIANA

Author

Sana Kurungadan, Mohamed bin Zayed University of Artificial IntelligenceFollow

Date of Award

4-30-2024

Document Type

Thesis

Degree Name

Master of Science in Machine Learning

Department

Machine Learning

First Advisor

Dr. Samuel Horvath

Second Advisor

Dr. Huan Xiong

Abstract

This thesis introduces ASDIANA, an algorithm that extends the Accelerated Compressed Gradient Descent (ACGD) and its distributed framework by incorporating stochastic gradient descent (SGD) techniques, specifically designed for distributed and Federated Learning environments. Aimed at addressing the high communication costs and privacy concerns inherent in these settings, ASDIANA emerges as a stochastic-based optimization technique that combines gradient compression and acceleration. L In the single-machine setting, we establish that ACSGD achieves the convergence rate of O max √κ,σ2 µε (1+ω)log 1 ε for µ-strongly convex problems and for convex problems O (1+ω) ε + (1+ω)σ2 ε2 , assuming that ∥∇f(x) − g(x)∥2 ≤ σ2. When variance (σ2) is equal to zero, we retrieve the convergence rate of ACGD ([29]), where a full batch is utilized for gradient computation.We also introduce a distributed version of ACSGD, called ASDIANA, and we establish that ACSGD enjoys the rate O ω +ω L nµ + ω5 2σ2 εµ2n logΨ0 ε when n, the number of devices is less than or equal to the compression operator ω and O ω+ L µ + Lω µ ω n + σ2 ω3 εµ2 n + 4 ω3 n logΨ0 ε greater than the compression operator ω. when the number of devices is Finally, we carry out numerous experiments with real-world datasets that validate our theoretical findings and demonstrate the practical advantage of our accelerated compressed stochastic techniques. Our results highlight ASDIANA’s efficiency, adaptability, and reliability in managing large and complex data problems, demonstrating its potential to reduce communication overhead without compromising computational accuracy.

Comments

Thesis submitted to the Deanship of Graduate and Postdoctoral Studies

In partial fulfilment of the requirements for the M.Sc degree in Machine Learning

Advisors: Samuel Horvath, Huan Xiong

Online access available for MBZUAI patrons

Recommended Citation

S. Kurungadan, "Accelerated Stochastic DIANA,", Apr 2024.