Temporal Variabilities Limit Convergence Rates in Gradient-Based Online Optimization
(2026) American Control Conference. Proceedings — (2026)
Files
251012512v1.pdf
Open Access - Adobe PDF
- 497.62 KB
Details
- Authors
- Abstract
- 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
- Affiliations
Citations
Van Scoy, B., & Bianchin, G. (2026). Temporal Variabilities Limit Convergence Rates in Gradient-Based Online Optimization. American Control Conference. Proceedings. Submitted. https://hdl.handle.net/2078.5/266852 (Original work published 2026)