2025/10/14 by Bryan Van Scoy, Van Scoy, Bryan, Gianluca Bianchin +1
Decision Sciences · Engineering · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #FOS: Electrical engineering #FOS: Mathematics #Iterative Learning Control Systems #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2510.12512
openalex publication_date 2025/10/14 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
This paper investigates the fundamental performance limits of gradient-based algorithms for time-varying optimization. Leveraging the internal model principle and root locus techniques, we show that temporal variabilities impose intrinsic limits on the achievable rate of convergence. For a problem with condition ratio κ and time variation whose model has degree n, we show that the worst-case convergence rate of any minimal-order gradient-based algorithm is ρTV = ((κ-1)/(κ+1))1/n. This bound reveals a fundamental tradeoff between problem conditioning, temporal complexity, and rate of convergence. We further construct explicit controllers that attain the bound for low-degree models of time variation.