När man löser problem med konsensusoptimering över en graf, det finns ofta en uttrycklig karakterisering av konvergensen av Gradient Descent (GD) med hjälp av spektrumet av grafen Laplacian. Samma typ av problem under Alternating Direction Method of Multipliers (ADMM) är dock dåligt förstådd. Till exempel har man ännu inte analyserat enkla men viktiga problem med icke-konvergens, särskilt när det gäller konvergensgradens beroende av graftopologin. För ett icke-konvext samförståndsproblem föreslogs nyligen ett samband mellan distribuerade ADMM och liftade Markov-kedjor, följt av en förmodan att ADMM är snabbare än GD av en kvadratrotsfaktor i sin konvergenstid, i nära analogi med den blandning hastighet som uppnås genom att lyfta flera Markov-kedjor. Det saknas dock fortfarande bevis för ett sådant påstående. Här ger vi en fullständig karakterisering av konvergensen av distribuerade överavskuret ADMM för samma typ av konsensus problem i termer av topologin för den underliggande grafen. Våra resultat ger explicita formler för optimalt parameterval i termer av det näst största eigenvärdet av övergångsmatrisen för grafens slumpmässiga gång. En annan konsekvens av våra resultat är ett bevis på ovanstående antaganden, som intressant nog visar att det gäller för alla grafer, även de vars slumpmässiga promenader inte kan påskyndas via Markovs kedjelyft. - Vad är det för fel på dig?
Förhållandet mellan konvergensgraden för ADMM och topologin för underliggande graf undersöks med hjälp av lyft Markov kedja REF.
How is Distributed ADMM Affected by Network Topology?
{'venue': None, 'journal': 'arXiv: Machine Learning', 'mag_field_of_study': ['Mathematics']}