Improved Dynamic Regret of Distributed Online Multiple Frank-Wolfe Convex Optimization

MaRDI QIDQ6437478zbMATH OpenFDO

Authors Wentao Zhang, Yang Shi, Baoyong Zhang, Deming Yuan

Publication date 22 May 2023

Abstract: In this paper, we consider a distributed online convex optimization problem over a time-varying multi-agent network. The goal of this network is to minimize a global loss function through local computation and communication with neighbors. To effectively handle the optimization problem with a high-dimensional and complicated constraint set, we develop a distributed online multiple Frank-Wolfe algorithm to avoid the expensive computational cost of projection operation. The dynamic regret bounds are established as $mathcalO(T^{1-gamma}+H_T)$ with the linear oracle number $mathcalO(T^{1+gamma})$, which depends on the horizon (total iteration number) $T$, the function variation $H_T$, and the tuning parameter $0<gamma<1$. In particular, when the stringent computation requirement is satisfied, the bound can be enhanced to $mathcalO(1+H_T)$. Moreover, we illustrate the significant advantages of the multiple iteration technique and reveal a trade-off between computational cost and dynamic regret bound. Finally, the performance of our algorithm is verified and compared through the distributed online ridge regression problems with two constraint sets.

This page was built for publication: Improved Dynamic Regret of Distributed Online Multiple Frank-Wolfe Convex Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437478)