FROST—Fast row-stochastic optimization with uncoordinated step-sizes
| Autor: | Usman A. Khan, Ran Xin, Chenguang Xi |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Linear convergence
Mathematical optimization Computer science Multi-agent system lcsh:Electronics lcsh:TK7800-8360 Contrast (statistics) 020206 networking & telecommunications 02 engineering and technology Directed graph Distributed optimization lcsh:Telecommunication Rate of convergence Optimization and Control (math.OC) Multiagent systems lcsh:TK5101-6720 Frost FOS: Mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Stochastic optimization Convex function Mathematics - Optimization and Control Directed graphs |
| Zdroj: | EURASIP Journal on Advances in Signal Processing, Vol 2019, Iss 1, Pp 1-14 (2019) |
| ISSN: | 1687-6180 |
| DOI: | 10.1186/s13634-018-0596-y |
| Popis: | In this paper, we discuss distributed optimization over directed graphs, where doubly-stochastic weights cannot be constructed. Most of the existing algorithms overcome this issue by applying push-sum consensus, which utilizes column-stochastic weights. The formulation of column-stochastic weights requires each agent to know (at least) its out-degree, which may be impractical in e.g., broadcast-based communication protocols. In contrast, we describe FROST (Fast Row-stochastic-Optimization with uncoordinated STep-sizes), an optimization algorithm applicable to directed graphs that does not require the knowledge of out-degrees; the implementation of which is straightforward as each agent locally assigns weights to the incoming information and locally chooses a suitable step-size. We show that FROST converges linearly to the optimal solution for smooth and strongly-convex functions given that the largest step-size is positive and sufficiently small. Comment: Submitted for journal publication, currently under review |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink