  We consider online convex optimization (OCO) over a heterogeneous network
with communication delay, where multiple workers together with a master execute
a sequence of decisions to minimize the accumulation of time-varying global
costs. The local data may not be independent or identically distributed, and
the global cost functions may not be locally separable. Due to communication
delay, neither the master nor the workers have in-time information about the
current global cost function. We propose a new algorithm, termed Hierarchical
OCO (HiOCO), which takes full advantage of the network heterogeneity in
information timeliness and computation capacity to enable multi-step gradient
descent at both the workers and the master. We analyze the impacts of the
unique hierarchical architecture, multi-slot delay, and gradient estimation
error to derive upper bounds on the dynamic regret of HiOCO, which measures the
gap of costs between HiOCO and an offline globally optimal performance
benchmark.
