Pan, Weici and Shi, Guanya and Lin, Yiheng and Wierman, Adam (2022) Online Optimization with Feedback Delay and Nonlinear Switching Cost. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6 (1). Art. No. 17. ISSN 2476-1249. doi:10.1145/3508037. https://resolver.caltech.edu/CaltechAUTHORS:20220302-699021182
This is the latest version of this item.
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
See Usage Policy. 810kB |
|
PDF
- Submitted Version
See Usage Policy. 821kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220302-699021182
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(L^(2k)), where L is the Lipschitz constant of the 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.
| Item Type: | Article | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||
| ORCID: |
| ||||||||||||
| Additional Information: | © 2022 Owner/Author. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). | ||||||||||||
| Subject Keywords: | online learning; online optimization; online control | ||||||||||||
| Issue or Number: | 1 | ||||||||||||
| Classification Code: | Computing methodologies → Online learning settings | ||||||||||||
| DOI: | 10.1145/3508037 | ||||||||||||
| Record Number: | CaltechAUTHORS:20220302-699021182 | ||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20220302-699021182 | ||||||||||||
| Official Citation: | Weici Pan, Guanya Shi, Yiheng Lin, and Adam Wierman. 2022. Online Optimization with Feedback Delay and Nonlinear Switching Cost. Proc. ACM Meas. Anal. Comput. Syst. 6, 1, Article 17 (March 2022), 34 pages. DOI: https://doi.org/10.1145/3508037 | ||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
| ID Code: | 113677 | ||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||
| Deposited By: | George Porter | ||||||||||||
| Deposited On: | 02 Mar 2022 10:38 | ||||||||||||
| Last Modified: | 23 Dec 2022 18:34 |
Available Versions of this Item
- Online Optimization with Feedback Delay and Nonlinear Switching Cost. (deposited 02 Mar 2022 10:38) [Currently Displayed]
Commentary/Response Threads
- Pan, Weici and Shi, Guanya and Lin, Yiheng and Wierman, Adam Online Optimization with Feedback Delay and Nonlinear Switching Cost. (deposited 02 Mar 2022 10:38) [Currently Displayed]
Repository Staff Only: item control page
