mlsanityData to 7 Oct 2026

Online Optimization with Feedback Delay and Nonlinear Switching Cost

arXiv 2111.00095 ↗First posted 29 Oct 2021cs.LG cs.SY eess.SYcited by 5

Not on the map. Why?

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.

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

Builds on

23 of 41 references.

References · 23

  1. 2013Online Learning under Delayed Feedbackcited by 137
  2. 2019Online Control with Adversarial Disturbancescited by 92
  3. 2020Improper Learning for Non-Stochastic Controlcited by 83
  4. 2018Neural Lander: Stable Drone Landing Control using Learned Dynamicscited by 82
  5. 2019Online Optimal Control with Linear Dynamics and Predictions: Algorithms and Regret Analysiscited by 40
  6. 2019Logarithmic Regret for Online Controlcited by 38
  7. 2020Adaptive Regret for Control of Time-Varying Dynamicscited by 38
  8. 2018Smoothed Online Convex Optimization in High Dimensions via Online Balanced Descentcited by 33
  9. 2019Beyond Online Balanced Descent: An Optimal Algorithm for Smoothed Online Optimizationcited by 31
  10. 2020The Power of Predictions in Online Controlcited by 31
  11. 2018Online Optimization with Predictions and Switching Costs: Fast Algorithms and the Fundamental Limitcited by 27
  12. 2018Smoothed Online Optimization for Regression and Controlcited by 26
11 more
  1. 2021Perturbation-based Regret Analysis of Predictive Control in Linear Time Varying Systemscited by 25
  2. 2021Meta-Adaptive Nonlinear Control: Theory and Algorithmscited by 23
  3. 2018Chasing Nested Convex Bodies Nearly Optimallycited by 21
  4. 2020Neural-Swarm2: Planning and Control of Heterogeneous Multirotor Swarms using Learned Interactionscited by 19
  5. 2019Chasing Convex Bodies Optimallycited by 18
  6. 2015Online Convex Optimization Using Predictionscited by 16
  7. 2019Chasing Convex Bodies with Linear Competitive Ratiocited by 15
  8. 2020Online Agnostic Boosting via Regret Minimizationcited by 12
  9. 2017Online Learning with Local Permutations and Delayed Feedbackcited by 10
  10. 2020Competitive Control with Delayed Imperfect Informationcited by 8
  11. 2018Competitively Chasing Convex Bodiescited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 2; 2024: 0; 2025: 1; 2026: 1.

5 papers.

  1. 2023Robust Learning for Smoothed Online Convex Optimization with Feedback Delaycited by 3
  2. 2026Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memorycited by 2
  3. 2023Learning-Augmented Decentralized Online Convex Optimization in Networkscited by 1
  4. 2022Augmented Lagrangian Methods for Time-varying Constrained Online Convex Optimizationcited by 0
  5. 2025Fairness-Regularized Online Optimization with Switching Costscited by 0