2020/11/20 by Abolfazl Hashemi, Hashemi, Abolfazl, Anish Acharya +10 · 2 citations
Computer Science · Engineering · Mathematics · #Artificial intelligence #Artificial neural network #Benchmark (surveying) #Combinatorics #Computer science #Constant (computer programming) #Convergence (economics) #Convex function #Convex optimization #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Mathematics #Gossip #Gradient descent #Lossy compression #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical optimization #Mathematics #Optimization and Control (math.OC) #Optimization problem #Parallel #Rate of convergence #Regular polygon #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Telecommunications #and Cluster Computing (cs.DC) #cs.DC #cs.LG #math.OC #stat.ML
paper · pdf · doi:10.48550/arxiv.2011.10643
published in arXiv (Cornell University) (Cornell University)
arxiv created 2020/11/20 · openalex publication_date 2020/11/20 · arxiv updated 2020/11/24 · openalex created_date 2022/07/25 · openalex updated_date 2026/08/05
In decentralized optimization, it is common algorithmic practice to have\nnodes interleave (local) gradient descent iterations with gossip (i.e.\naveraging over the network) steps. Motivated by the training of large-scale\nmachine learning models, it is also increasingly common to require that\nmessages be em lossy compressed versions of the local parameters. In this\npaper, we show that, in such compressed decentralized optimization settings,\nthere are benefits to having em multiple gossip steps between subsequent\ngradient iterations, even when the cost of doing so is appropriately accounted\nfor e.g. by means of reducing the precision of compressed information. In\nparticular, we show that having O(\log\(1)/(\ε)) gradient iterations\nwith constant step size - and O(\log\(1)/(\ε)) gossip steps\nbetween every pair of these iterations - enables convergence to within\n\ε of the optimal value for smooth non-convex objectives satisfying\nPolyak- Lojasiewicz condition. This result also holds for smooth strongly\nconvex objectives. To our knowledge, this is the first work that derives\nconvergence results for nonconvex optimization under arbitrary communication\ncompression.\n