Abstrakt. Nyligen har det funnits ett växande intresse för att lösa problem med konsensusoptimering i ett multiagentnätverk. I detta dokument, utvecklar vi en decentraliserad algoritm för konsensusoptimering problem som definieras över ett uppkopplat nätverk av n agenter, där varje funktion f i hålls privat av agent i och kodar agentens data och mål. Alla agenter ska tillsammans hitta minimeraren medan varje agent bara kan kommunicera med sina grannar. Ett sådant beräkningssystem undviker ett datacenter eller fjärrkommunikation och erbjuder bättre belastningsbalans till nätet. I detta dokument föreslås en ny decentraliserad exakt första orderalgoritm (förkortad som EXTRA) för att lösa problemet med konsensusoptimering. Exakt innebär att den kan konvergera till den exakta lösningen. EXTRA kan använda en fast stor stegstorlek, som är oberoende av nätverksstorleken, och har synkroniserat iterationer. Den lokala variabeln för varje agent i konvergerar enhetligt och consensually till en exakt minimerare off. Däremot måste den välkända metoden för decentraliserad lutningsnedstigning (DGD) använda minskande stegstorlekar för att konvergera till en exakt minimering. EXTRA och DGD har samma val av blandning av matriser och liknande komplexitet per iteration. EXTRA använder dock lutningarna av de två senaste iteraterna, till skillnad från DGD som använder just den sista iterat. EXTRA har de mest kända konvergenstalen bland de befintliga första ordningens decentraliserade algoritmer för decentraliserad konsensusoptimering med konvexa Lipschitz-differentierbara mål. Specifikt, om f i s är konvex och har Lipschitz kontinuerliga gradienter, EXTRA har en ergodisk konvergenshastighet O 1 k i termer av den första ordningen optimalitet rest. Iff är också (begränsad) starkt konvex, EXTRA konvergerar till en optimal lösning med en linjär hastighet O(C-k ) för vissa konstant C > 1.
Den senaste papper REF, föreslår en gradient-baserad distribuerad algoritm för konvex objektiv funktion med Lipschitz kontinuerliga gradienter och visar dess konvergens med hastigheten O( 1 T ).
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization
{'venue': None, 'journal': 'arXiv: Optimization and Control', 'mag_field_of_study': ['Computer Science', 'Mathematics']}