A Caltech Library Service

Online Optimization with Memory and Competitive Control

Shi, Guanya and Lin, Yiheng and Chung, Soon-Jo and Yue, Yisong and Wierman, Adam (2020) Online Optimization with Memory and Competitive Control. . (Unpublished)

[img] PDF (16 Jun 2020) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Chung, Soon-Jo0000-0002-6657-3907
Yue, Yisong0000-0001-9127-1989
Alternate Title:Beyond No-Regret: Competitive Control via Online Optimization with Memory
Record Number:CaltechAUTHORS:20200214-105606928
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101303
Deposited By: George Porter
Deposited On:14 Feb 2020 20:52
Last Modified:14 Oct 2020 21:55

Repository Staff Only: item control page