Distributed Online Optimization over a Heterogeneous Network
In distributed online optimization over a computing network with heterogeneous nodes, slow nodes can adversely affect the progress of fast nodes, leading to drastic slowdown of the overall convergence process. To address this issue, we consider a new algorithm termed Distributed Any-Batch Mirror Descent (DABMD), which is based on distributed Mirror Descent but uses a fixed per-round computing time to limit the waiting by fast nodes to receive information updates from slow nodes. DABMD is characterized by varying minibatch sizes across nodes. It is applicable to a broader range of problems compared with existing distributed online optimization methods such as those based on dual averaging, and it accommodates time-varying network topology. We study two versions of DABMD, depending on whether the computing nodes average their primal variables via single or multiple consensus iterations. We show that both versions provide strong theoretical performance guarantee, by deriving upperbounds on their expected dynamic regret, which capture the variability in minibatch sizes. Our experimental results show substantial reduction in cost and acceleration in convergence compared with the known best alternative.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Design of heterogeneous multi-agent system for distributed computation
A group behavior of a heterogeneous multi-agent system is studied which obeys an "average of individual vector fields" under strong couplings among the agents. Under stability of the averaged dynamics (not asking stabili…
Distributed OptimizationState EstimationUncertain Multi-Agent Systems with Distributed Constrained Optimization Missions and Event-Triggered Communications: Application to Resource Allocation
This paper deals with solving distributed optimization problems with equality constraints by a class of uncertain nonlinear heterogeneous dynamic multi-agent systems. It is assumed that each agent with an uncertain dynam…
Distributed OptimizationDistributed Optimization with Gradient Tracking over Heterogeneous Delay-Prone Directed Networks
In this paper, we address the distributed optimization problem over unidirectional networks with possibly time-invariant heterogeneous bounded transmission delays. In particular, we propose a modified version of the Acce…
Distributed OptimizationDistributed Online Big Data Classification Using Context Information
Distributed, online data mining systems have emerged as a result of applications requiring analysis of large amounts of correlated and high-dimensional data produced by multiple distributed data sources. We propose a dis…
ClassificationGeneral ClassificationDecentralized Online Big Data Classification - a Bandit Framework
Distributed, online data mining systems have emerged as a result of applications requiring analysis of large amounts of correlated and high-dimensional data produced by multiple distributed data sources. We propose a dis…
ClassificationGeneral Classification