Shadowheart SGD : an extensive study of the Development, Convergence Analysis and Time Complexity for a new Asyncronus Bandwidth-Aware Compression Algorithm for Distributed Learning

This project presents a comprehensive investigation into the theoretical foundations and practical implications of a new compression algorithm for distributed learning [15, 11], which is asynchronus and bandwidth-aware. We use unbiased compressors, algorithmic intricacies, and critical assumptions underlying the proposed models. A standard procedure to establish the convergence of the algorithm in different setting is presented every time, passing through a key lemma (AC [26, 6, 13] or ABC-inequality [12] according to the context). Bandwidth theory in a convex setting is addressed, encompassing assumptions, time com- plexity considerations, and an exploration of time complexity bounds. The paper further delves into minimizing time complexity for fixed compressors, transitioning from continuous to discrete optimization, and introducing a significant main result. Special cases, such as scenarios with no compression, identical times, distinct times, and variations in worker speeds, are thoroughly analyzed. A general convergence theory is for- mulated, supported by illustrative examples. The paper extends its focus to finding optimal algorithms in stochastic cases, introducing gradient estimators with mini-batch processing and various optimization choices. The exploration continues into non-convex cases with homogeneous data, providing a general theory and a key lemma for convergence. The transition from homogeneous data to heteroge- neous data is studied, addressing cases with varying numbers of workers and introducing time complexity bounds. The paper concludes with an examination of stochastic cases with heterogeneous data, in- vestigating convergence under different conditions and proposing a variety of time complexity bounds. The introduction of batch size for stochastic gradients, considerations of computational time, and bounds for time complexity in diverse scenarios further contribute to the depth of the research. The findings presented in this thesis offer an extensive study on a new algorithm with po- tential application in several fields of distributed learning The most important outcomes of the presented study are presented in "Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity" [25], as the highest level of analysis that our study could produce until now.

Questo progetto presenta un'indagine approfondita sulle fondamenta teoriche e sulle implicazioni pratiche di un nuovo algoritmo di compressione per l'apprendimento distribuito [15, 11], che è asincrono e consapevole della larghezza di banda. Utilizziamo compressori non tendenziosi, complessità algoritmiche e assunzioni critiche sottostanti ai modelli proposti. Viene presentata una procedura standard per stabilire la convergenza dell'algoritmo in diversi contesti, passando attraverso un lemma chiave (AC [26, 6, 13] o disuguaglianza ABC [12] a seconda del contesto). La teoria della larghezza di banda in un contesto convesso è affrontata, includendo assunzioni, considerazioni sulla complessità temporale e un'esplorazione dei limiti della complessità temporale. Il documento approfondisce ulteriormente la minimizzazione della complessità temporale per compressori fissi, passando dall'ottimizzazione continua a quella discreta e introducendo un risultato principale significativo. I casi speciali, come scenari senza compressione, tempi identici, tempi distinti e variazioni nella velocità dei lavoratori, sono analizzati approfonditamente. Viene formulata una teoria generale di convergenza, supportata da esempi illustrativi. Il documento estende il suo focus alla ricerca di algoritmi ottimali nei casi stocastici, introducendo stimatori del gradiente con elaborazione a mini-batch e varie scelte di ottimizzazione. L'esplorazione continua nei casi non convessi con dati omogenei fornisce una teoria generale e un lemma chiave per la convergenza. Viene studiata la transizione dai dati omogenei a quelli eterogenei, affrontando casi con un numero variabile di lavoratori e introducendo limiti della complessità temporale. Il documento conclude con un'esame dei casi stocastici con dati eterogenei, investigando la convergenza in diverse condizioni e proponendo una varietà di limiti della complessità temporale. L'introduzione della dimensione del batch per i gradienti stocastici, considerazioni sul tempo computazionale e limiti della complessità temporale in scenari diversi contribuiscono ulteriormente alla profondità della ricerca. Le scoperte presentate in questa tesi offrono uno studio approfondito su un nuovo algoritmo con potenziale applicazione in diversi campi dell'apprendimento distribuito. I risultati più importanti dello studio presentato sono esposti in "Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity" [25], come il livello più alto di analisi che il nostro studio potesse produrre finora.