Published February 13, 2020
| Accepted Version
Discussion Paper
Open
Online Optimization with Memory and Competitive Control
Chicago
An error occurred while generating the citation.
Abstract
This paper presents competitive algorithms for a novel class of online optimization problems with memory. We consider a setting where the learner seeks to minimize the sum of a hitting cost and a switching cost that depends on the previous p decisions. This setting generalizes Smoothed Online Convex Optimization. The proposed approach, Optimistic Regularized Online Balanced Descent, achieves a constant, dimension-free competitive ratio. Further, we show a connection between online optimization with memory and online control with adversarial disturbances. This connection, in turn, leads to a new constant-competitive policy for a rich class of online control problems.
Additional Information
This project was supported in part by funding from Raytheon, DARPA PAI, AitF-1637598 and CNS-1518941, with additional support for Guanya Shi provided by the Simoudis Discovery Prize. We see no ethical concerns related to the results in this paper.Attached Files
Accepted Version - 2002.05318.pdf
Files
2002.05318.pdf
Files
(683.6 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:43ca70070d36797d5537d01cbef193ea
|
683.6 kB | Preview Download |
Additional details
- Alternative title
- Beyond No-Regret: Competitive Control via Online Optimization with Memory
- Eprint ID
- 101303
- Resolver ID
- CaltechAUTHORS:20200214-105606928
- Raytheon Company
- Defense Advanced Research Projects Agency (DARPA)
- NSF
- CCF-1637598
- NSF
- CNS-1518941
- Simoudis Discovery Prize
- Created
-
2020-02-14Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field
- Caltech groups
- GALCIT