# Online Optimization with Feedback Delay and Nonlinear Switching Cost

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 29 Oct 2021.

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Online Control with Adversarial Disturbances](https://mlsanity.com/paper/1902.08721/) (2019)
- [Neural Lander: Stable Drone Landing Control using Learned Dynamics](https://mlsanity.com/paper/1811.08027/) (2018)
- [Improper Learning for Non-Stochastic Control](https://mlsanity.com/paper/2001.09254/) (2020)
- [Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysis](https://mlsanity.com/paper/1906.11378/) (2019)
- [Logarithmic Regret for Online Control](https://mlsanity.com/paper/1909.05062/) (2019)
- [Adaptive Regret for Control of Time-Varying Dynamics](https://mlsanity.com/paper/2007.04393/) (2020)
- [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)
- [The Power of Predictions in Online Control](https://mlsanity.com/paper/2006.07569/) (2020)
- [Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limit](https://mlsanity.com/paper/1801.07780/) (2018)
- [Smoothed Online Optimization for Regression and Control](https://mlsanity.com/paper/1810.10132/) (2018)
- [Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systems](https://mlsanity.com/paper/2106.10497/) (2021)
- [Meta-Adaptive Nonlinear Control: Theory and Algorithms](https://mlsanity.com/paper/2106.06098/) (2021)
- [Chasing Nested Convex Bodies Nearly Optimally](https://mlsanity.com/paper/1811.00999/) (2018)
- [Neural-Swarm2: Planning and Control of Heterogeneous Multirotor Swarms using Learned Interactions](https://mlsanity.com/paper/2012.05457/) (2020)
- [Chasing Convex Bodies Optimally](https://mlsanity.com/paper/1905.11968/) (2019)
- [Online Convex Optimization Using Predictions](https://mlsanity.com/paper/1504.06681/) (2015)
- [Chasing Convex Bodies with Linear Competitive Ratio](https://mlsanity.com/paper/1905.11877/) (2019)
- [Online Agnostic Boosting via Regret Minimization](https://mlsanity.com/paper/2003.01150/) (2020)
- [Online Learning with Local Permutations and Delayed Feedback](https://mlsanity.com/paper/1703.04274/) (2017)
- [Competitive Control with Delayed Imperfect Information](https://mlsanity.com/paper/2010.11637/) (2020)
- [Competitively Chasing Convex Bodies](https://mlsanity.com/paper/1811.00887/) (2018)

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

- [Robust Learning for Smoothed Online Convex Optimization with Feedback Delay](https://mlsanity.com/paper/2310.20098/) (2023)
- [Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory](https://mlsanity.com/paper/2602.06902/) (2026)
- [Learning-Augmented Decentralized Online Convex Optimization in Networks](https://mlsanity.com/paper/2306.10158/) (2023)
- [Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimization](https://mlsanity.com/paper/2205.09571/) (2022)
- [Fairness-Regularized Online Optimization with Switching Costs](https://mlsanity.com/paper/2512.11131/) (2025)

## Abstract (arXiv)

We study a variant of online optimization in which the learner receives k-round textitdelayed feedback about hitting cost and there is a multi-step nonlinear switching cost, i.e., costs depend on multiple previous actions in a nonlinear manner. Our main result shows that a novel Iterative Regularized Online Balanced Descent (iROBD) algorithm has a constant, dimension-free competitive ratio that is O(L2k), where L is the Lipschitz constant of the switching cost. Additionally, we provide lower bounds that illustrate the Lipschitz condition is required and the dependencies on k and L are tight. Finally, via reductions, we show that this setting is closely related to online control problems with delay, nonlinear dynamics, and adversarial disturbances, where iROBD directly offers constant-competitive online policies.