A Caltech Library Service

Online Optimization with Feedback Delay and Nonlinear Switching Cost

Pan, Weici and Shi, Guanya and Lin, Yiheng and Wierman, Adam (2022) Online Optimization with Feedback Delay and Nonlinear Switching Cost. In: Abstract Proceedings of the 2022 ACM SIGMETRICS/IFIP PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery , New York, NY, pp. 81-82. ISBN 978-1-4503-9141-2.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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(L^(2k)), 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].

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper ItemJournal Article
Shi, Guanya0000-0002-9075-3705
Lin, Yiheng0000-0001-6524-2877
Wierman, Adam0000-0002-5923-0199
Additional Information:© 2022 Copyright held by the owner/author(s).
Subject Keywords:online learning; online optimization; online control
Record Number:CaltechAUTHORS:20220304-172341428
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:113733
Deposited By: George Porter
Deposited On:07 Mar 2022 20:44
Last Modified:28 Jun 2022 18:17

Repository Staff Only: item control page