NeurIPS 2020poster63 citations
Online Optimization with Memory and Competitive Control
Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, Adam Wierman
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.
BibTeX
@inproceedings{NEURIPS2020_ed46558a,
author = {Shi, Guanya and Lin, Yiheng and Chung, Soon-Jo and Yue, Yisong and Wierman, Adam},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {20636--20647},
publisher = {Curran Associates, Inc.},
title = {Online Optimization with Memory and Competitive Control},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/ed46558a56a4a26b96a68738a0d28273-Paper.pdf},
volume = {33},
year = {2020}
}