A Systems-Theoretic View on the Convergence of Algorithms under Disturbances
This provides a unifying tool for analyzing algorithm performance under noise and disturbances, which is incremental but useful for researchers in systems theory and applied algorithms.
The paper tackles the problem of algorithm convergence under disturbances in complex systems by extending known guarantees to derive stability bounds and convergence rates. It demonstrates applications in distributed learning, machine learning generalization, and privacy through noise injection.
Algorithms increasingly operate within complex physical, social, and engineering systems where they are exposed to disturbances, noise, and interconnections with other dynamical systems. This article extends known convergence guarantees of an algorithm operating in isolation (i.e., without disturbances) and systematically derives stability bounds and convergence rates in the presence of such disturbances. By leveraging converse Lyapunov theorems, we derive key inequalities that quantify the impact of disturbances. We further demonstrate how our result can be utilized to assess the effects of disturbances on algorithmic performance in a wide variety of applications, including communication constraints in distributed learning, sensitivity in machine learning generalization, and intentional noise injection for privacy. This underpins the role of our result as a unifying tool for algorithm analysis in the presence of noise, disturbances, and interconnections with other dynamical systems.