Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published February 14, 2020 | Accepted Version
Report Open

Online Optimization with Memory and Competitive Control


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 (683.6 kB)
Name Size Download all
683.6 kB Preview Download

Additional details

August 19, 2023
October 19, 2023