Timezone: »

Online Optimization with Memory and Competitive Control
Guanya Shi · Yiheng Lin · Soon-Jo Chung · Yisong Yue · Adam Wierman

Thu Dec 10 09:00 PM -- 11:00 PM (PST) @ Poster Session 6 #1804
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.

Author Information

Guanya Shi (Caltech)

PhD student in machine learning and robotics

Yiheng Lin (California Institute of Technology)
Soon-Jo Chung (Caltech)
Yisong Yue (Caltech)
Adam Wierman (California Institute of Technology)

More from the Same Authors