Online Optimization with Feedback Delay and Nonlinear Switching Cost
Open Access
- 20 June 2022
- journal article
- abstracts
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 50 (1) , 81-82
Abstract
We study a variant of online optimization in which the learner receives k-round delayed feedback about hitting cost and there is a multi-step nonlinear switching cost, i.e., costs depend on multiple previous actions in a nonlinear manner. Our main result shows that a novel Iterative Regularized Online Balanced Descent (iROBD) algorithm has a constant, dimension-free competitive ratio that is O(L2k), where L is the Lipschitz constant of the nonlinear switching cost. Additionally, we provide lower bounds that illustrate the Lipschitz condition is required and the dependencies on k and L are tight. Finally, via reductions, we show that this setting is closely related to online control problems with delay, nonlinear dynamics, and adversarial disturbances, where iROBD directly offers constant-competitive online policies. This extended abstract is an abridged version of [2].Keywords
Funding Information
- NSF (CPS-2136197, CNS-2106403, NGSDI-2105648)
- Amazon Web Services
This publication has 1 reference indexed in Scilit:
- The First 5G-LTE Comparative Study in Extreme MobilityProceedings of the ACM on Measurement and Analysis of Computing Systems, 2022