{"ID":2855765,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.12512","arxiv_id":"2510.12512","title":"Temporal Variabilities Limit Convergence Rates in Gradient-Based Online Optimization","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 $ρ_\\text{TV} = (\\frac{κ-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.","short_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...","url_abs":"https://arxiv.org/abs/2510.12512","url_pdf":"https://arxiv.org/pdf/2510.12512v1","authors":"[\"Bryan Van Scoy\",\"Gianluca Bianchin\"]","published":"2025-10-14T13:41:32Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"eess.SY\"]","methods":"[]","has_code":false}