# Robustified Learning for Online Optimization with Memory Costs

arXiv: https://arxiv.org/abs/2305.00677 · HTML: https://mlsanity.com/paper/2305.00677/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 45 references that are in the map.
- First posted on arXiv 1 May 2023.

## Builds on (most cited first, 26 of 26)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Projection-Based Constrained Policy Optimization](https://mlsanity.com/paper/2010.03152/) (2020)
- [Learning to Optimize](https://mlsanity.com/paper/1606.01885/) (2016)
- [Differentiable MPC for End-to-end Planning and Control](https://mlsanity.com/paper/1810.13400/) (2018)
- [Conservative Offline Distributional Reinforcement Learning](https://mlsanity.com/paper/2107.06106/) (2021)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Coping with Label Shift via Distributionally Robust Optimisation](https://mlsanity.com/paper/2010.12230/) (2020)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descent](https://mlsanity.com/paper/1803.10366/) (2018)
- [Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimization](https://mlsanity.com/paper/1905.12776/) (2019)
- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Risk Bounds and Calibration for a Smart Predict-then-Optimize Method](https://mlsanity.com/paper/2108.08887/) (2021)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [Safeguarded Learned Convex Optimization](https://mlsanity.com/paper/2003.01880/) (2020)
- [Chasing Convex Bodies and Functions with Black-Box Advice](https://mlsanity.com/paper/2206.11780/) (2022)
- [Online Optimization with Predictions and Non-convex Losses](https://mlsanity.com/paper/1911.03827/) (2019)
- [Leveraging Predictions in Smoothed Online Convex Optimization via Gradient-based Algorithms](https://mlsanity.com/paper/2011.12539/) (2020)
- [Robust Learning-Augmented Caching: An Experimental Study](https://mlsanity.com/paper/2106.14693/) (2021)
- [A Regression Approach to Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2205.08717/) (2022)
- [Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach](https://mlsanity.com/paper/2109.10380/) (2021)
- [A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning](https://mlsanity.com/paper/2106.11692/) (2021)
- [Adversarial Deep Learning for Online Resource Allocation](https://mlsanity.com/paper/2111.10285/) (2021)
- [Expert-Calibrated Learning for Online Optimization with Switching Costs](https://mlsanity.com/paper/2204.08572/) (2022)

## Built on by (most cited first, 4 of 4)

- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Learning-Augmented Decentralized Online Convex Optimization in Networks](https://mlsanity.com/paper/2306.10158/) (2023)
- [Anytime-Competitive Reinforcement Learning with Policy Prior](https://mlsanity.com/paper/2311.01568/) (2023)
- [Smoothed Online Optimization for Target Tracking: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2509.05930/) (2025)

## Abstract (arXiv)

Online optimization with memory costs has many real-world applications, where sequential actions are made without knowing the future input. Nonetheless, the memory cost couples the actions over time, adding substantial challenges. Conventionally, this problem has been approached by various expert-designed online algorithms with the goal of achieving bounded worst-case competitive ratios, but the resulting average performance is often unsatisfactory. On the other hand, emerging machine learning (ML) based optimizers can improve the average performance, but suffer from the lack of worst-case performance robustness. In this paper, we propose a novel expert-robustified learning (ERL) approach, achieving both good average performance and robustness. More concretely, for robustness, ERL introduces a novel projection operator that robustifies ML actions by utilizing an expert online algorithm; for average performance, ERL trains the ML optimizer based on a recurrent architecture by explicitly considering downstream expert robustification. We prove that, for any λ≥1, ERL can achieve λ-competitive against the expert algorithm and λ· C-competitive against the optimal offline algorithm (where C is the expert's competitive ratio). Additionally, we extend our analysis to a novel setting of multi-step memory costs. Finally, our analysis is supported by empirical experiments for an energy scheduling application.