Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares

• URL: http://arxiv.org/abs/2605.04364v1
• Date: Wed, 06 May 2026 00:01:54 GMT
• Title: Online Nonstochastic Prediction: Logarithmic Regret via Predictive Online Least Squares
• Abstract summary: We study online prediction for marginally stable, partially observed linear dynamical systems under nonstochastic disturbances.<n>Our objective is to minimize the cumulative squared prediction loss and compete with the best-in-hindsight Luenberger predictor.
• Score: 3.490684506493613
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Koopman-Based Robust Model Predictive Control for Nonlinear Systems with Stochastic Intermittent Measurements [11.153670606528545]
  Intermittent state measurements pose fundamental challenges to model predictive control of constrained nonlinear systems.<n>This paper develops a Koopman-based MPC framework with probabilistically truncated soft constraints.
  arXiv  Detail & Related papers  (2026-09-02T04:08:49Z)
• Symbolic Neural ODEs: Learning interpretable models from time-series data [0.0]
  We present a machine learning framework for identifying sparse, interpretable models of dynamical systems from time-series data.<n>Our approach parameterizes the underlying vector field using a neural architecture and trains it by minimizing a multi-step prediction loss over a finite horizon.<n>We show that multi-step training yields models with accurate short-term dynamics and strong agreement in long-time statistical properties.
  arXiv  Detail & Related papers  (2026-08-22T21:31:07Z)
• Non-Parametric Rehearsal Learning via Conditional Mean Embeddings [88.89267783967263]
  We propose a non-parametric rehearsal learning approach for textitavoiding undesired future (AUF) problems.<n>Specifically, we use kernel machinery to reformulate the AUF objective into a unified representation that disentangles desirability modeling from action-induced distributional changes.
  arXiv  Detail & Related papers  (2026-05-09T15:30:52Z)
• Generative forecasting with joint probability models [2.8367488114717094]
  Chaotic dynamical systems exhibit strong sensitivity to initial conditions and often contain unresolved multiscale processes.<n>Generative models offer an appealing alternative by learning distributions over plausible system evolutions.<n>We show that joint generative models yield improved short-term predictive skill, preserve attractor geometry, and achieve substantially more accurate long-range statistical behaviour.
  arXiv  Detail & Related papers  (2025-12-30T20:00:09Z)
• ResAD: Normalized Residual Trajectory Modeling for End-to-End Autonomous Driving [64.42138266293202]
  ResAD is a Normalized Residual Trajectory Modeling framework.<n>It reframes the learning task to predict the residual deviation from an inertial reference.<n>On the NAVSIM benchmark, ResAD achieves a state-of-the-art PDMS of 88.6 using a vanilla diffusion policy.
  arXiv  Detail & Related papers  (2025-10-09T17:59:36Z)
• Certified Neural Approximations of Nonlinear Dynamics [51.01318247729693]
  In safety-critical contexts, the use of neural approximations requires formal bounds on their closeness to the underlying system.<n>We propose a novel, adaptive, and parallelizable verification method based on certified first-order models.
  arXiv  Detail & Related papers  (2025-05-21T13:22:20Z)
• Gradient Equilibrium in Online Learning: Theory and Applications [56.02856551198923]
  gradient equilibrium is achieved by standard online learning methods.<n> gradient equilibrium translates into an interpretable and meaningful property in online prediction problems.<n>We show that gradient equilibrium framework can be used to develop a debiasing scheme for black-box predictions.
  arXiv  Detail & Related papers  (2025-01-14T18:59:09Z)
• Bayesian Inference for Consistent Predictions in Overparameterized Nonlinear Regression [0.0]
  This study explores the predictive properties of over parameterized nonlinear regression within the Bayesian framework. Posterior contraction is established for generalized linear and single-neuron models with Lipschitz continuous activation functions. The proposed method was validated via numerical simulations and a real data application.
  arXiv  Detail & Related papers  (2024-04-06T04:22:48Z)
• High-Probability Risk Bounds via Sequential Predictors [20.741036493022442]
  We show that online to batch conversions applied to general online learning algorithms can bypass regret bounds. We obtain nearly optimal high-probability risk bounds for several classical statistical estimation problems. Our analysis relies on the fact that many online learning algorithms are improper, as they are not restricted to use predictors from a given reference class.
  arXiv  Detail & Related papers  (2023-08-15T06:19:31Z)
• Time varying regression with hidden linear dynamics [74.9914602730208]
  We revisit a model for time-varying linear regression that assumes the unknown parameters evolve according to a linear dynamical system. Counterintuitively, we show that when the underlying dynamics are stable the parameters of this model can be estimated from data by combining just two ordinary least squares estimates.
  arXiv  Detail & Related papers  (2021-12-29T23:37:06Z)
• Self-Supervised Hybrid Inference in State-Space Models [0.0]
  We perform approximate inference in state-space models that allow for nonlinear higher-order Markov chains in latent space. We do not rely on an additional parameterization of the generative model or supervision via uncorrupted observations or ground truth latent states. We obtain competitive results on the chaotic Lorenz system compared to a fully supervised approach and outperform a method based on variational inference.
  arXiv  Detail & Related papers  (2021-07-28T13:26:14Z)
• Learning Probabilistic Ordinal Embeddings for Uncertainty-Aware Regression [91.3373131262391]
  Uncertainty is the only certainty there is. Traditionally, the direct regression formulation is considered and the uncertainty is modeled by modifying the output space to a certain family of probabilistic distributions. How to model the uncertainty within the present-day technologies for regression remains an open issue.
  arXiv  Detail & Related papers  (2021-03-25T06:56:09Z)
• Deep learning: a statistical viewpoint [120.94133818355645]
  Deep learning has revealed some major surprises from a theoretical perspective. In particular, simple gradient methods easily find near-perfect solutions to non-optimal training problems. We conjecture that specific principles underlie these phenomena.
  arXiv  Detail & Related papers  (2021-03-16T16:26:36Z)
• Online Learning of the Kalman Filter with Logarithmic Regret [2.0305676256390934]
  We show that it is possible to achieve a regret of the order of $mathrmpolylog(N)$ with high probability, where $N$ is the number of observations collected. This is achieved using an online least-squares algorithm, which exploits the approximately linear relation between future observations and past observations.
  arXiv  Detail & Related papers  (2020-02-12T18:31:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.