Distributed Newton Step Projection Algorithm for Online Convex Optimization Over Time-Varying Unbalanced Networks

Abstract

In this paper, we investigate distributed online optimization over multi-agent networks, where a group of agents aim to cooperatively seek the minimum value of a time-varying global loss function that can be expressed as the sum of the local loss functions privately owned by a single agent on the network at each iteration. In addition, all agents do not know the future loss function, and information about the loss function is disclosed only after the agent has made a decision. We are interested in scenarios where the communication topology of a multi-agent network is a sequence of time-varying unbalanced graphs and the loss function of each agent is a class of non-strongly convex functions. We generalize the distributed online Newton step algorithm to a more general multi-agent network by introducing a consensual-based auxiliary estimation to rescale the contribution of each agent in optimization. Our algorithm only uses row stochastic matrices and does not require the agent to know the out-degree of its in-neighbors. The convergence of regret bound over time-varying unbalanced networks is rigorously proved. Simulation results also verify the effectiveness of the proposed algorithm, and show its advantage in convergence speed compared with the first-order algorithms.

Keywords

• Distributed optimization
• online convex optimization
• Newton step projection algorithm
• multi-agent network
• time-varying unbalanced directed graphs