Descente de gradient stochastique à un bit aplatie : optimisation distribuée compressée avec variance contrôlée

Nous proposons un nouvel algorithme pour la descente de gradient stochastique distribuée (SGD) avec communication de gradients compressés dans le cadre d'un serveur de paramètres. Notre technique de compression de gradients, nommée descente de gradient stochastique à un bit aplatie (FO-SGD), repose sur deux idées algorithmiques simples : (i) une procédure de quantification à un bit tirant parti de la technique de dithering, et (ii) une transformation de Walsh-Hadamard rapide randomisée pour aplatir le gradient stochastique avant la quantification. En conséquence, l'approximation du véritable gradient dans ce schéma est biaisée, mais elle prévient les problèmes algorithmiques courants, tels que la variance explosive dans le régime de compression à un bit, la détérioration des performances dans le cas de gradients rares, et les hypothèses restrictives sur la distribution des gradients stochastiques. En fait, nous montrons des garanties de convergence similaires à SGD sous des conditions légères. La technique de compression peut être utilisée dans les deux sens de la communication travailleur-serveur, permettant ainsi une optimisation distribuée avec une compression complète de communication.