mlsanityData to 14 Oct 2026

Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares

arXiv 2605.04364 ↗First posted 6 May 2026cs.LG cs.SY eess.SYcited by 0

Not on the map. Why?

Abstract (arXiv)

We study online prediction for marginally stable, partially observed linear dynamical systems under nonstochastic disturbances. Our objective is to minimize the cumulative squared prediction loss and compete with the best-in-hindsight Luenberger predictor. Standard online learning methods typically rely on bounded domains/gradients, and thus their guarantees may fail to deal with potentially unbounded trajectories in marginally stable systems. In this paper, we introduce an unconstrained online least squares method that stabilizes the learning process via tailored predictive hints. With model knowledge, we prove that hints constructed from any stabilizing Luenberger predictor render the hint residuals uniformly bounded, achieving logarithmic regret despite unbounded trajectory growth. We also discuss model-free prediction and introduce a simple universal hint for symmetric systems, under which logarithmic regret is maintained without model knowledge. Our results provide an adaptive, instance-wise optimal online predictor compared to classical fixed-gain observers under nonstochastic disturbances.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 22 of its 31 references that are in the map. First posted on arXiv 6 May 2026.

Builds on

22 of 31 references.

References · 22

  1. 2019Introduction to Online Convex Optimizationcited by 803
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
  3. 2013Optimization, Learning, and Games with Predictable Sequencescited by 188
  4. 2020Naive Exploration is Optimal for Online LQRcited by 116
  5. 2019Online Control with Adversarial Disturbancescited by 92
  6. 2020Improper Learning for Non-Stochastic Controlcited by 83
  7. 2013Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributionscited by 60
  8. 2019Learning Linear Dynamical Systems with Semi-Parametric Least Squarescited by 58
  9. 2018Online Linear Quadratic Controlcited by 56
  10. 2017Learning Linear Dynamical Systems via Spectral Filteringcited by 46
  11. 2020Logarithmic Regret for Adversarial Online Controlcited by 41
  12. 2019Logarithmic Regret for Online Controlcited by 38
10 more
  1. 2020Logarithmic Regret for Learning Linear Quadratic Regulators Efficientlycited by 35
  2. 2020Online Learning of the Kalman Filter with Logarithmic Regretcited by 21
  3. 2013A Generalized Online Mirror Descent with Applications to Classification and Regressioncited by 19
  4. 2020No-Regret Prediction in Marginally Stable Systemscited by 18
  5. 2018On-Line Learning of Linear Dynamical Systems: Exponential Forgetting in Kalman Filterscited by 16
  6. 2020SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memorycited by 11
  7. 2024Online Linear Regression in Dynamic Environments via Discountingcited by 10
  8. 2025Universal Sequence Preconditioningcited by 6
  9. 2025Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regretcited by 4
  10. 2025Logarithmic Regret and Polynomial Scaling in Online Multi-step-ahead Predictioncited by 1

Built on by

Not cited yet.