Randomized Gradient-Free Distributed Online Optimization with Time-Varying Objective Functions
Yipeng Pang, Guoqiang Hu · 2019
This paper presents a randomized gradient-free distributed online optimization algorithm, with a group of agents whose local objective functions are time-varying. It is worth noting that the value of the local objective function is only revealed to the corresponding agent after the decision is made at each time-step. Thus, each agent updates the decision variable using the local objective function value of its last decision and the information collected from its immediate in-neighbors. A randomized gradient-free oracle is built locally in replacement of the true gradient information in guiding the updates of the decision variable. The notion of dynamic regret is brought forward to measure the difference between the total cost incurred by the agent's state estimation and the offline centralized optimal solution where the objective functions are available a priori. Under the assumptions of strongly connected communication graph and bounded subgradients of the local objective functions, we characterize the dynamic regret associated with each agent as a function of the time duration $T$ and the deviation of the minimizer sequence. Averaging the dynamic regret over the time duration, we establish the asymptotic convergence to a small neighborhood of zero with a rate of $\mathcal{O}(\ln T/\sqrt{T})$. The effectiveness of this algorithm is illustrated through numerical simulations.