Online Optimization with Memory and Competitive Control

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.

arXiv commentNeural Information Processing Systems (NeurIPS 2020)

References in corpus (9)

• Neural Lander: Stable Drone Landing Control using Learned Dynamics
• Online Control with Adversarial Disturbances
• Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis
• Logarithmic Regret Bound in Partially Observable Linear Dynamical Systems
• Logarithmic Regret for Online Control
• Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization
• Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit
• Online Linear Quadratic Control
• Online Inventory Management with Application to Energy Procurement in Data Centers

Cited by in corpus (11)

• Robustness and Consistency in Linear Quadratic Control with Untrusted Predictions
• Non-stationary Online Learning with Memory and Non-stochastic Control
• Improved Analysis for Dynamic Regret of Strongly Convex and Smooth Functions
• The Power of Predictions in Online Control
• Regret-optimal control in dynamic environments
• Expert-Calibrated Learning for Online Optimization with Switching Costs
• Online Robust Control of Nonlinear Systems with Large Uncertainty
• Lazy OCO: Online Convex Optimization on a Switching Budget
• Adversarial Tracking Control via Strongly Adaptive Online Learning with Memory
• Implementation of Algorithms for Right-Sizing Data Centers
• Robust Online Control with Model Misspecification