A Distributed Online Learning Method Over Time-Varying Unbalanced Directed Graphs via Improved Regret Analysis

This paper investigates the distributed online learning problem under dual time-varying conditions of the objective functions and network topologies. The goal is to enable agents to track the global minimum of the time-varying objective functions through online collaboration. An online gradient descent algorithm combining a soft update mechanism and projection method is proposed for time-varying unbalanced directed graphs. The projection method ensures that decision variables consistently satisfy constraints after each iteration. In our design, the soft update is a trade-off strategy that balances the relationship between current consensus decisions and new decisions derived from local projected gradients by introducing a step-size parameter. This approach can regulate the convergence rate and stability of the algorithm. Dynamic regret bound related to the minimum path length, step-size, and smoothing parameter is given by an improved regret analysis method. It is shown that the bound is not explicitly related to the time horizon, and thus tighter than the bounds in most prior work. The performance of the proposed algorithm is validated through a simulation experiment.