分析算法在扰动下的收敛性，给出稳定性和收敛速率的量化边界。
A Systems-Theoretic View on the Convergence of Algorithms under Disturbances
- 基于反向李雅普诺夫定理，推导扰动影响的关键不等式。
- 揭示通信约束、泛化敏感性和隐私噪声对算法性能的影响机制。
- 适用于分布式学习、机器学习和隐私保护等多场景分析。
算法越来越多地运行在复杂物理、社会和工程系统中，面临扰动、噪声以及与其他动态系统的互联。本文拓展了算法在孤立环境下（无扰动）已知的收敛保证，系统性地推导出存在扰动时的稳定性边界和收敛速率。通过利用反向李雅普诺夫定理，我们推导出关键不等式，量化扰动的影响。进一步展示了该结果如何用于评估多种应用场景中扰动对算法性能的影响，包括分布式学习中的通信约束、机器学习泛化中的敏感性，以及为隐私而有意注入的噪声。这凸显了该结果作为噪声、扰动及与其他动态系统互联情形下算法分析的统一工具的价值。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。