Sammanfattning Vi presenterar en ny klass av decentraliserade första ordningen metoder för nonsmooth och stokastisk optimering problem definierade över multiagent nätverk. Med tanke på att kommunikation är en stor flaskhals i decentraliserad optimering, vårt främsta mål i detta dokument är att utveckla algoritmiska ramar som avsevärt kan minska antalet internode kommunikationer. Vi föreslår först en decentraliserad primal-dual metod som kan hitta en lösning både i form av funktionell optimalitetsgap och genomförbarhetsrester i O(1/ på) internode kommunikationsrundor när de objektiva funktionerna är konvexa och de lokala primära subproblemen är lösta exakt. Vårt stora bidrag är att presentera en ny klass av decentraliserade algoritmer av primal-dual typ, nämligen de decentraliserade kommunikation glider (DCS) metoder, som kan hoppa över internoden kommunikation medan agenter löser de primära subproblemen iterativt genom linjäriseringar av sina lokala objektiva funktioner. Genom att anställa DCS, kan agenter fortfarande hitta en lösning i O(1/ på) (resp., O(1/ н)) kommunikationsrundor för allmänna konvexa funktioner (resp., starkt konvexa funktioner), samtidigt som den O(1/ på 2 ) (resp., O(1/ på)) begränsas till det totala antalet intranode subgradient utvärderingar. Vi presenterar också en stokastisk motsvarighet för dessa algoritmer, betecknad av SDCS, för att lösa stokastiska optimeringsproblem vars objektiva funktion inte kan utvärderas exakt. I jämförelse med befintliga resultat för decentraliserad icke-smooth och stokastisk optimering kan vi minska det totala antalet internode kommunikationsrundor efter storleksordning samtidigt som vi bibehåller de optimala komplexitetsgränserna på intranode stokastiska subgradienta utvärderingar. Gränserna på (stochastic) subgradient utvärderingar är faktiskt jämförbara med dem som krävs för centraliserad nonsmooth och stokastisk optimering under vissa villkor på målnoggrannheten.
I REF föreslås en ny decentraliserad metod av primal-dual typ med en beräkningsmässig komplexitet av O( n/T ) för allmänna konvexa mål.
Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}