Computation-Aware Distributed Optimization over Networks: A Hybrid Dynamical Systems Approach

We study the robustness properties of computationally-aware dual-based distributed optimization algorithm over networks. Contrary to existing literature, we follow a hybrid dynamical systems approach to analyze the stability properties of the distributed Nesterov's ODE when explicitly taking into account the computational resources and time required by a dual first-order oracle to generates an approximate gradient. We show that in such scenario, the distributed Nesterov's ODE is unstable in the Lyapunov sense, i.e., there exist an arbitrarily bounded perturbation function for which the inexact oracle drives the system unstable. Moreover, we propose modified dynamics that are provable stable and robust, and which provably minimizes smooth and strongly convex functions.