Pith. sign in

REVIEW 3 major objections 5 minor 52 references

Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Unknown linear systems can be predicted with O(log³ N) regret via a forgetting factor.

desk verdict Genuine improvement in the regret rate (O(log^3 N)), but the 'model-free' claim overreaches: Theorem 1's parameters are tuned with spectral data of the true system. read the letter →

arxiv 2505.08982 v1 pith:YGUYRTOE submitted 2025-05-13 cs.LG cs.SYeess.SPeess.SY

Jiachen Qian , Yang Zheng This is my paper · ORCID
classification cs.LGcs.SYeess.SPeess.SY MSC 93E1193E3568Q32
keywords onlinelearningKalmanfiltermodel-freepredictionlogarithmicregretexponentialforgettingbalancedregressionlineardynamicalsystemsHanson-Wrightinequality
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

To predict the next observation of an unknown, non-explosive linear Gaussian system without knowing the system matrices or noise covariances, this paper proposes an Online Prediction with Forgetting algorithm (OPF) that multiplies past observations by an exponentially decaying rescaling matrix. The paper's central claim is that against the steady-state Kalman filter — which knows the true model — OPF's cumulative squared prediction error is at most poly(M, β, log(1/δ)) O(log³ N) with probability at least 1−δ. That sharpens the previously known logarithmic bounds O(log⁶ N) and O(log¹¹ N). The reason to care is that it turns model-free prediction for the classical Kalman setting into a provably near-optimal online regression problem, and identifies the regression imbalance caused by exponentially decaying Markov parameters as the key obstruction that a forgetting factor can remove.

What carries the argument

The central object is the diagonal rescaling matrix $D_p = \mathrm{diag}(\gamma^{p-1},\ldots,\gamma,1)\otimes I_m$ applied to the vector of the $p$ past observations. Its job is to rebalance the exponentially decaying Markov-parameter blocks so that the learned coefficients $\tilde{G}_p$ have comparable magnitudes across blocks, preventing overfitting of the small tail coefficients. The same $D_p$ makes the forgetting strategy equivalent to a generalized ridge regression with penalty $\lambda\|G D_p^{-1}\|_F^2$, which is the inductive bias that carries the improvement. Around this object the proof organizes three components: an epoch schedule with doubling lengths $T_l = 2^{l-1}T_{\mathrm{init}}+1$ and past horizon $p_l = \lceil \beta \log T_l \rceil$ to control the long-term bias $C(A-LC)^p \hat{x}_{k-p}$; a Hanson–Wright-inequality bound for the Gaussian regression term; and a self-cancellation argument showing that the log-determinant terms of successive epochs telescope with a uniformly bounded residue, which is what reduces the accumulation factor from $O(\log^4 N)$ to $O(\log^2 N)$ and the total regret from $O(\log^6 N)$ to $O(\log^3 N)$.

What would settle it

Run OPF on a marginally stable system with a Jordan block of size $\kappa$ at eigenvalue 1 (the target-tracking example of Section 5), take $\gamma = \rho(A-LC)$, $\beta = (2\kappa+1)/\log(1/\rho(A-LC))$, and record $R_N$ at the end of each doubling epoch. If $R_N/\log^3 N$ grows without bound as $N$ doubles, or if the epoch residue $\log\det\tilde{V}_{2T_l-1,p_l} - \log\det\tilde{V}_{2T_l-1,p_{l-1}}$ does not stay bounded by a constant of the claimed $\mathrm{poly}(1/\sigma_R, m, \beta, \log(1/\delta))$ form, the theorem's $O(\log^3 N)$ claim fails.

Watch

Extended reading notes

Core claim

The paper shows that the main obstruction to model-free Kalman prediction is the imbalance in the linear regression $y_k = G_p Z_{k,p} + C(A-LC)^p \hat{x}_{k-p} + e_k$: the Markov-parameter blocks $C(A-LC)^t L$ decay geometrically, so a plain least-squares fit overfits the small tail blocks. OPF rescales the regressor by $D_p = \mathrm{diag}(\gamma^{p-1},\ldots,1)\otimes I_m$, turning the model into a balanced regression $y_k = \tilde{G}_p D_p Z_{k,p} + \text{bias} + \text{innovation}$, and this rescaling is algebraically the same as a generalized ridge penalty $\lambda\|G D_p^{-1}\|_F^2$ that encodes exponential decay. Theorem 1 then guarantees, for any detectable $(A,C)$ with $A-LC$ diagonalizable, $\gamma \in (\rho(A-LC),1]$, $\beta$ proportional to $\kappa/\log(1/\rho(A-LC))$, and warm-up $T_{\mathrm{init}}$ polynomial in $\beta$ and $\log(1/\delta)$, that the regret against the true steady-state Kalman filter is $O(\log^3 N)$ with high probability. The proof splits the error into regularization, regression, and bias components, bounds the Gaussian regression factor by $O(\log N)$ through a Hanson–Wright-based martingale argument instead of the looser log-determinant bound, and shows that the log-determinant accumulation over doubling epochs self-cancels except for a uniformly bounded residue, so the accumulation factor stays $O(\log^2 N)$.

Load-bearing premise

The proof's load-bearing premise is that the log-determinant residues left after cancelling successive epochs stay bounded by a constant independent of the epoch index, and that the warm-up horizon $T_{\mathrm{init}}$ exceeds the unknown persistent-excitation time $N_0$; if the residue grows with the epoch, or if $T_{\mathrm{init}}$ falls short of $N_0$, the $O(\log^3 N)$ bound gains extra logarithmic factors.

Editorial extensions

If this is right

  • Model-free prediction of non-explosive linear Gaussian systems is guaranteed to track the true Kalman filter up to $O(\log^3 N)$ cumulative squared-error regret, with no knowledge of $A$, $C$, $Q$, $R$, or even the state dimension.
  • Setting the forgetting factor to $\gamma = \rho(A-LC)$ keeps the regularization error at $O(\log N)$ while shrinking the regression and accumulation errors, so the algorithm is both theoretically safe and practically better than no forgetting.
  • Marginally stable systems, where the state grows polynomially, are covered because the bias is controlled through the decaying closed-loop matrix $A-LC$ rather than through $A$.
  • Restarting with a doubled epoch length and rounding the past horizon to $\lceil \beta \log T_l \rceil$ does not change the order of the regret.
  • The same balanced-regression construction extends to systems with bounded control inputs, preserving a logarithmic regret guarantee.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The $D_p$ rescaling is a general recipe: any regression whose true coefficients decay geometrically (IIR models, truncated Volterra kernels, long-memory time series) could use the same balanced ridge penalty to avoid overfitting small tail entries; testing this transfer is a direct next step.
  • The numerical evidence in the appendix shows the cancelled bias term is much smaller than the raw bias term, which suggests the theorem's $\beta = (2\kappa+1)/\log(1/\rho(A-LC))$ is conservative; a refined analysis might lower the required past horizon and cut computation without changing the regret order.
  • The uniform constant in the self-cancellation step grows with $1/\sigma_R$, so very ill-conditioned measurement noise may make the poly factor large in practice; adaptive or matrix-valued forgetting may offer a smoother bias-variance trade-off.
  • Nothing in the proof forces $O(\log^3 N)$ to be tight: the regression term contributes $O(\log N)$ and the accumulation term $O(\log^2 N)$, so a stronger accumulation analysis might push the total to $O(\log^2 N)$ or below.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies online prediction of observations from an unknown, non-explosive linear Gaussian system (1), with regret measured against the steady-state Kalman filter. It proposes OPF (Algorithm 1), which rescales past observations by powers of a forgetting factor γ and learns a balanced regression model via exponentially weighted least squares; this is shown to be equivalent to a generalized ridge regression with penalty λD_p^{-2}. The main theoretical contribution is Theorem 1, which claims a high-probability regret bound of order poly(...) O(log^3 N), improving on the O(log^6 N) bound of Tsiamis and Pappas. The proof divides the regret into accumulation, bias, regression, and regularization errors, and uses Hanson-Wright-type bounds, persistent excitation, and an epoch-wise determinant-cancellation argument. Numerical experiments compare OPF with the algorithm of [12] and with traditional forgetting.

Significance. If the result is correct, the O(log^3 N) rate is a genuine improvement over the cited O(log^6 N) and O(log^11 N) bounds, and the re-balancing interpretation of forgetting is a useful conceptual contribution. The Appendix is detailed, and the main decompositions (19)-(22), the bias bound in C.2, the persistent-excitation argument in C.6, and the determinant accounting in C.7 are largely coherent; the experiments support the qualitative claims and the paper compares fairly with prior algorithms. However, the paper's central 'model-free' claim is not matched by the theorem's parameter choices, and one of the key high-probability bounds in C.5 is not proved as written. These issues need to be resolved before the claims can be accepted in their present form.

major comments (3)
  1. [Section 4.1, Theorem 1] The theorem is not a model-free guarantee as stated. The 'model-free' claim in Section 2.2 requires no knowledge of the system matrices or noise covariances, but Theorem 1 requires γ ∈ (ρ(A−LC), 1] and β = Ω(κ)/log(1/ρ(A−LC)); both are spectral data of the unknown closed-loop system, and the experiments in Section 5 set γ = ρ(A−LC) from the true model. This is not a harmless tuning convention: in the regularization-error bound (23), replacing γ > ρ by γ < ρ changes the geometric factor to (ρ/γ)^i, and with p = β log N the contribution becomes N^{β log(ρ/γ)}, which destroys logarithmic regret. Furthermore, no fixed γ can work for all detectable systems: for any γ < 1 there is a scalar system with A = 1, C = 1, R = 1 and sufficiently small Q such that ρ(A−LC) > γ. The same objection applies to T_init, because Lemma 3's N0 depends on system constants. The claims should be restated as an oracle-tuned or instance-dependent guarantee, or an adaptive choice of γ, β, and T_init should be provided.
  2. [Appendix C.5] The verification of the high-probability bound for the regression factor is not correct as written. After Lemma 5, the paper chooses t = max{2c'^2√(cmp), (2c'^2/c)(log(k^2/δ1)+2m)} and claims that c min{ t^2/(4c'^4‖V^Z‖_F^2), t/(2c'^2‖V^Z‖_2) } ≥ max{ log(2k^2/δ1)+2m, mβ log k }. When the second term in the definition of t dominates, t = Θ(log k), and the left-hand side is asymptotically at most (4/(c mβ)) log k before the factor c is applied; for mβ larger than a universal constant this is smaller than the required 2 log k, so the union bound over k does not follow. When the first term dominates, t = Θ(√(mp)), the exponent is only a constant. Since the regression-factor bound (24) is an essential ingredient in the final log^3 rate, this step must be repaired; taking t = Θ(mp) and using the lower bound on β appears to be a possible fix.
  3. [Appendix C.7] The proof asserts that the constant M1 is of the form poly(1/σ_R, m, β, log(1/δ)) and uses it uniformly over all epochs. The displayed expression contains (p')^{2κ}/(2T_l−1); as a function of l this ratio decays once l is large, so I do not see an epoch-index growth that would break the log^3 order. However, the maximum over l is of order (2κβ/e)^{2κ}, which is not a fixed-degree polynomial in β or κ. Either a genuine polynomial dependence should be proved, or the paper should state that constants may grow exponentially in κ; as written, the advertised 'poly(M,β,log(1/δ))' form is not established.
minor comments (5)
  1. [Algorithm 1, line 7] The line 'Re-balance \tilde Z_{t,p} = D_p Z_{k,p}' should read '\tilde Z_{t,p} = D_p Z_{t,p}'; the subscript k is inconsistent with the loop variable t.
  2. [Proof sketch, after Eq. (25)] The expression 'det \tilde V_{2Tl-1-1,p_{l-1}}' contains a malformed index; please rewrite it as a determinant of a Gram matrix with a clearly defined time index.
  3. [Appendix D.2] The robust-margin analysis introduces β' without defining its relation to the algorithm's β; please clarify the notation and state which quantities are fixed and which are tuned.
  4. [Section 5, Figure 7] The statement that the regret 'appears to be O(log^2 N)' is an empirical observation over a finite horizon and should not be presented as a verification of the O(log^3) theorem; please rephrase to avoid overclaiming.
  5. [Remark 2] The claim that rounding p = ⌈β log T_l⌉ 'will not affect the order of regret' is plausible but should be justified in the proof, since rounding changes the bias exponent and the epoch boundaries by a constant factor.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity in the regret derivation; the system-dependent parameter choices are a scope/validity caveat, not a circular reduction.

full rationale

The regret bound is derived from the algorithm and the stated statistical assumptions; no parameter is fitted to the Kalman-filter benchmark, and no predicted quantity is constructed from the fitted values. The proof decomposes RN via (19), bounds each error term in Appendix C using Gaussian concentration (Lemmas 1 and 5), the persistent-excitation theorem of Tsiamis and Pappas (Lemma 3, Theorem I.1 of [12]), and the chosen forms of gamma and beta. The persistent-excitation and self-normalized martingale bounds are external results that do not assume the target O(log^3 N) bound, and they are not established by the present paper's own derivation. The only load-bearing concern is that Theorem 1 requires gamma in (rho(A-LC),1] and beta = Omega(kappa)/log(1/rho(A-LC)), both of which depend on the true system's spectral data; if those parameters are not available, the advertised 'model-free' claim is not instantiated. This is a validity/scope caveat, not a circular reduction: the theorem is conditional on oracle parameters rather than equivalent to its inputs by construction.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The central bound rests on: (i) standard Kalman-filter facts (detectability gives ρ(A−LC) < 1 and Gaussian innovations); (ii) an imported persistent-excitation lemma (Lemma 3 from Theorem I.1 of [12]) that guarantees the Gram matrix grows linearly, bootstrapped by assuming Tinit ≥ N0 with N0 dependent on unknown constants; (iii) an ad hoc choice of the truncation horizon β = (2κ+1)/log(1/ρ(A−LC)) to kill the bias term; and (iv) tuning parameters γ, β, λ, Tinit, NE with the good regime requiring γ near ρ(A−LC). The proof introduces no invented physical entities; D_p is a coordinate re-parametrization of the regression.

free parameters (5)
  • Forgetting factor γ = γ = ρ(A−LC) in experiments (Section 5); theory allows any γ ∈ (ρ(A−LC), 1]
    Defines the scaling matrix D_p = diag(γ^{p−1},...,1) ⊗ I_m; the regret bound holds on the stated interval, but the practical choice requires knowing ρ(A−LC), and the experiments set it to the true closed-loop spectral radius.
  • Truncation-growth parameter β = β = 2.5 in experiments; theory requires β = Ω(κ)/log(1/ρ(A−LC))
    Sets the past horizon p = β log T_l; controls the bias-variance trade-off in Appendix C.2; requires knowledge of κ and ρ(A−LC).
  • Regularization strength λ = λ = 1 in experiments; theory allows any fixed λ > 0
    Appears in the generalized ridge penalty ‖λ G D_p^{-1}‖²_F in (18); the bound holds without tuning λ.
  • Warm-up horizon Tinit = Tinit = 60 in experiments; theory requires Tinit = poly(β, log(1/δ))
    Must be large enough that the persistent-excitation condition (Lemma 3) holds from the start of the online phase; N0 depends on constants of the unknown system.
  • Number of epochs NE = NE = 7 in experiments
    The horizon is N = 2^{NE} Tinit under the doubling schedule, so NE is determined by the chosen horizon.
assumptions (5)
  • standard math Kalman filter optimality and exponential convergence to steady state under detectability (Assumption 1), giving ρ(A−LC) < 1 and Gaussian mutually uncorrelated innovations
    Sections 2.1 and B.1, cited from [1, 2, 43, 44]; provides the benchmark predictor and the regression model (7).
  • domain assumption A−LC is diagonalizable (Assumption 2), so ‖(A−LC)^t‖ ≤ M ρ(A−LC)^t with M a constant
    Section 2.2, imported from [12, 20]; needed for the constant-M bounds on the exponentially decaying blocks of G_p.
  • domain assumption Persistent excitation: Σ_{t=p}^k Z_{t,p}Z_{t,p}^T ≥ (σ_R/4) k I for k ≥ N0 (Lemma 3)
    Appendix A.3, imported from Theorem I.1 of [12]; load-bearing for the accumulation and cross-term bounds; requires R ≻ 0 and Gaussian noise; bootstrapped by assuming Tinit ≥ N0.
  • domain assumption i.i.d. zero-mean Gaussian noises w_k and v_k with Q ≻ 0 and R ≻ 0 (Section 2.1)
    Gives Gaussian mutually uncorrelated innovations; the logarithmic regret and the Hanson-Wright analysis rely on Gaussian tails.
  • ad hoc to paper Truncation horizon p = ⌈β log T_l⌉ with β = (2κ+1)/log(1/ρ(A−LC)) so that the long-term bias C(A−LC)^p x̂_{k−p} is uniformly bounded
    Appendix C.2; the β selection is introduced to kill the bias term in the proof, and requires knowing κ and ρ(A−LC).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret." pith.science (2026). https://pith.science/paper/YGUYRTOE

@misc{pith2026250508982,
  author       = {Pith},
  title        = {Pith review of: Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YGUYRTOE}},
  note         = {Machine review of arXiv:2505.08982}
}
abstract

We consider the problem of online prediction for an unknown, non-explosive linear stochastic system. With a known system model, the optimal predictor is the celebrated Kalman filter. In the case of unknown systems, existing approaches based on recursive least squares and its variants may suffer from degraded performance due to the highly imbalanced nature of the regression model. This imbalance can easily lead to overfitting and thus degrade prediction accuracy. We tackle this problem by injecting an inductive bias into the regression model via {exponential forgetting}. While exponential forgetting is a common wisdom in online learning, it is typically used for re-weighting data. In contrast, our approach focuses on balancing the regression model. This achieves a better trade-off between {regression} and {regularization errors}, and simultaneously reduces the {accumulation error}. With new proof techniques, we also provide a sharper logarithmic regret bound of $O(\log^3 N)$, where $N$ is the number of observations.

Figures

Figures reproduced from arXiv: 2505.08982 by the authors.

Figure 1
Figure 1. Illustration of the overfitting effect in a simple example. The black curve shows the ground truth that has a highly imbalanced structure, and the blue curve is the estimated model using method provided in [12] that overfits the small blocks. In this paper, we address the imbalanced regression model in model-free online learning of the Kalman filter. We also aim to derive a sharper logarithmic regret bound of our on… view at source ↗
Figure 2
Figure 2. Performance comparison of online prediction with different forgetting strategies: (a) our proposed forgetting; (b) traditional forgetting in [24]. This can be interpreted as a 3-D target tracking problem with an unknown correlated dynamic model [40]. The parameters in our OPF algorithm are chosen as β = 2.5, Tinit = 60, λ = 1, NE = 7. Accordingly, the total horizon is 7680. The comparison result with different forge… view at source ↗
Figure 3
Figure 3. Effect of our forgetting factor on different parts of regret RN in (22). algorithm that injects an inductive bias. This approach leads to a more balanced regression model and helps mitigate overfitting. Using refined proof techniques, we developed a structured regret analysis framework, particu￾larly for marginally stable systems, and we established a sharper regret bound as O(log3 N). Our findings highlight the imp… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Illustration figure for the comparison of regret for different methods. E.2 Discussion on numerical stability In this subsection, we discuss the numerical robustness of the initialization process for each epoch. Note that at the beginning of each time epoch with initia…
Figure 5
Figure 5. Figure 5: Illustration figure for the problem of numerical stability (a) Bias Cancellation (b) Traditional Forget [PITH_FULL_IMAGE:figures/full_fig_p034_5.png]
Figure 6
Figure 6. Figure 6: Supplementary experiments We find in numerical simulation that the bias error term Pk l=p bl,pZ T l,pV¯ −1 k,p Zk+1,p −bk+1,p has an effect of cancellation. That is, even if the term bk+1,p is large, the difference between bk+1,p and Pk l=p bl,pZ T l,pV¯ −1 k,p Zk+1,p …
Figure 7
Figure 7. Figure 7: Illustration figure for the verification of theoretical regret bound. Then we can see that the determinant bound provided by [12, 20, 36] is, to some extent, conservative. The bound provided in this paper is sharper, but there is still some potential to be optimized. T…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 48 canonical work pages

  1. [12]

    Anastasios Tsiamis and George J. Pappas. Online learni ng of the Kalman filter with logarith- mic regret. IEEE Transactions on Automatic Control , 68(5):2774–2789, 2023

    work page 2023

  2. [1]

    R. E. Kalman. A New Approach to Linear Filtering and Predi ction Problems. Journal of Basic Engineering , 82(1):35–45, 03 1960

    work page 1960

  3. [2]

    Brian D. O. Anderson and John B. Moore. Optimal Filtering . Prentice-Hall, Englewood Cliffs, N.J, 1979

    work page 1979

  4. [3]

    State estimation for robotics

    Timothy D Barfoot. State estimation for robotics . Cambridge University Press, 2024

    work page 2024

  5. [4]

    A linear dynamical syste m model for text

    David Belanger and Sham Kakade. A linear dynamical syste m model for text. In International Conference on Machine Learning , pages 833–842. PMLR, 2015

    work page 2015

  6. [5]

    Long short-term memory Kalman filters: Recurrent neural estimat ors for pose regularization

    Huseyin Coskun, Felix Achilles, Robert DiPietro, Nassi r Navab, and Federico Tombari. Long short-term memory Kalman filters: Recurrent neural estimat ors for pose regularization. In Proceedings of the IEEE International Conference on Computer Vi sion, pages 5524–5532, 2017

    work page 2017

  7. [6]

    Kalman and extended Kalman filters : Concept, derivation and proper- ties

    Maria Isabel Ribeiro. Kalman and extended Kalman filters : Concept, derivation and proper- ties. Institute for Systems and Robotics , 43(46):3736–3741, 2004

    work page 2004

  8. [7]

    Cubature Kalman filters

    Ienkaran Arasaratnam and Simon Haykin. Cubature Kalman filters. IEEE Transactions on Automatic Control, 54(6):1254–1269, 2009

    work page 2009

Show all 52 references
  1. [8]

    System identification

    Lennart Ljung. System identification. In Signal analysis and prediction , pages 163–173. Springer, 1998

    1998

  2. [9]

    Fundamentals of adaptive filtering

    Ali H Sayed. Fundamentals of adaptive filtering . John Wiley & Sons, 2003

    2003

  3. [10]

    Learning line ar dynamical systems via spectral filtering

    Elad Hazan, Karan Singh, and Cyril Zhang. Learning line ar dynamical systems via spectral filtering. Advances in Neural Information Processing Systems , 30, 2017. 14

    2017

  4. [11]

    No-regret prediction in marginally stable systems

    Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. No-regret prediction in marginally stable systems. In Conference on Learning Theory, pages 1714–1757. PMLR, 2020

    2020

  5. [13]

    Finite sample a nalysis of stochastic system iden- tification

    Anastasios Tsiamis and George J Pappas. Finite sample a nalysis of stochastic system iden- tification. In 2019 IEEE 58th Conference on Decision and Control (CDC) , pages 3648–3654. IEEE, 2019

    2019

  6. [14]

    Non-asymptotic identification of l inear dynamical systems using multiple trajectories

    Yang Zheng and Na Li. Non-asymptotic identification of l inear dynamical systems using multiple trajectories. IEEE Control Systems Letters , 5(5):1693–1698, 2020

    2020

  7. [15]

    Improved rates for prediction and identific ation of partially observed linear dy- namical systems

    Holden Lee. Improved rates for prediction and identific ation of partially observed linear dy- namical systems. In International Conference on Algorithmic Learning Theory , pages 668–698. PMLR, 2022

    2022

  8. [16]

    Gradient d escent learns linear dynamical systems

    Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient d escent learns linear dynamical systems. Journal of Machine Learning Research , 19(29):1–44, 2018

    2018

  9. [17]

    Recursive identificati on and adaptive prediction in linear stochastic systems

    Tze Leung Lai and Zhiliang Ying. Recursive identificati on and adaptive prediction in linear stochastic systems. SIAM Journal on Control and Optimization , 29(5):1061–1090, 1991

    1991

  10. [18]

    On line learning for time series prediction

    Oren Anava, Elad Hazan, Shie Mannor, and Ohad Shamir. On line learning for time series prediction. In Conference on Learning Theory , pages 172–184. PMLR, 2013

    2013

  11. [19]

    On-line learning of linear dynamical systems: Exponential forgetting in Kalma n filters

    Mark Kozdoba, Jakub Marecek, Tigran Tchrakian, and Shi e Mannor. On-line learning of linear dynamical systems: Exponential forgetting in Kalma n filters. In Proceedings of the AAAI Conference on Artificial Intelligence , volume 33, pages 4098–4105, 2019

    2019

  12. [20]

    SLIP: Learning to predict in unknown dynamical systems with long-term memory

    Paria Rashidinejad, Jiantao Jiao, and Stuart Russell. SLIP: Learning to predict in unknown dynamical systems with long-term memory. Advances in Neural Information Processing Sys- tems, 33:5716–5728, 2020

    2020

  13. [21]

    Regret analysis with a lmost sure convergence for OBF- ARX filter

    Jiayun Li, Yiwen Lu, and Yilin Mo. Regret analysis with a lmost sure convergence for OBF- ARX filter. arXiv preprint arXiv:2409.05390 , 2024

    2024 arXiv

  14. [22]

    Conc urrent learning adaptive control with directional forgetting

    Hae-In Lee, Hyo-Sang Shin, and Antonios Tsourdos. Conc urrent learning adaptive control with directional forgetting. IEEE Transactions on Automatic Control , 64(12):5164–5170, 2019

    2019

  15. [23]

    Online convex programming and gener alized infinitesimal gradient ascent

    Martin Zinkevich. Online convex programming and gener alized infinitesimal gradient ascent. In Proceedings of the 20th international Conference on Machine Learning, pages 928–936, 2003

    2003

  16. [24]

    Online linear regr ession in dynamic environments via discounting

    Andrew Jacobsen and Ashok Cutkosky. Online linear regr ession in dynamic environments via discounting. arXiv preprint arXiv:2405.19175 , 2024

    2024 arXiv

  17. [25]

    Exponential convergence of recursive least squares with ex ponential forgetting factor

    Richard M Johnstone, C Richard Johnson Jr, Robert R Bitm ead, and Brian DO Anderson. Exponential convergence of recursive least squares with ex ponential forgetting factor. Systems & Control Letters , 2(2):77–82, 1982

    1982

  18. [26]

    On the influence of the forgetting factor of the RLS adaptive filter i n system identification

    Silviu Ciochina, Constantin Paleologu, Jacob Benesty , and Andrei Alexandru Enescu. On the influence of the forgetting factor of the RLS adaptive filter i n system identification. In 2009 International Symposium on Signals, Circuits and Systems , pages 1–4, 2009

    2009

  19. [27]

    Generalized forgetti ng recursive least squares: Stability and robustness guarantees

    Brian Lai and Dennis S Bernstein. Generalized forgetti ng recursive least squares: Stability and robustness guarantees. IEEE Transactions on Automatic Control , 2024

    2024

  20. [28]

    Algebraic Riccati Equations

    P Lancaster. Algebraic Riccati Equations. Oxford Science Publications/The Clarendon Press, Oxford University Press, 1995. 15

    1995

  21. [29]

    Consistency and asymptotic normal- ity of some subspace algorithms for systems without observe d inputs

    Dietmar Bauer, Manfred Deistler, and Wolfgang Scherre r. Consistency and asymptotic normal- ity of some subspace algorithms for systems without observe d inputs. Automatica, 35(7):1243– 1254, 1999

    1999

  22. [30]

    Applied regression analysis

    NR Draper. Applied regression analysis . McGraw-Hill. Inc, 1998

    1998

  23. [31]

    Logistic regression: The importance of being improper

    Dylan J Foster, Satyen Kale, Haipeng Luo, Mehryar Mohri , and Karthik Sridharan. Logistic regression: The importance of being improper. In Conference on Learning Theory , pages 167–208. PMLR, 2018

    2018

  24. [32]

    Prediction, learning, and games

    Nicolo Cesa-Bianchi and G´ abor Lugosi. Prediction, learning, and games . Cambridge university press, 2006

    2006

  25. [33]

    A robust variable forgetting factor recursive least-squares algorithm for system identificati on

    Constantin Paleologu, Jacob Benesty, and Silviu Cioch ina. A robust variable forgetting factor recursive least-squares algorithm for system identificati on. IEEE Signal Processing Letters , 15:597–600, 2008

    2008

  26. [34]

    Discounted a daptive online learning: Towards better regularization

    Zhiyu Zhang, David Bombara, and Heng Yang. Discounted a daptive online learning: Towards better regularization. In Forty-first International Conference on Machine Learning , 2024

    2024

  27. [35]

    Predictive linear online tracking for unknown targets

    Anastasios Tsiamis, Aren Karapetyan, Yueshan Li, Efe C Balta, and John Lygeros. Predictive linear online tracking for unknown targets. arXiv preprint arXiv:2402.10036 , 2024

    2024 arXiv

  28. [36]

    Improved algorithms for linear stochastic bandits

    Yasin Abbasi-Yadkori, D´ avid P´ al, and Csaba Szepesv´ ari. Improved algorithms for linear stochastic bandits. Advances in neural Information Processing Systems , 24, 2011

    2011

  29. [37]

    Ridge regression: B iased estimation for nonorthogonal problems

    Arthur E Hoerl and Robert W Kennard. Ridge regression: B iased estimation for nonorthogonal problems. Technometrics, 12(1):55–67, 1970

    1970

  30. [38]

    A bound on tail p robabilities for quadratic forms in independent random variables

    David Lee Hanson and Farroll Tim Wright. A bound on tail p robabilities for quadratic forms in independent random variables. The Annals of Mathematical Statistics , 42(3):1079–1083, 1971

    1971

  31. [39]

    High-dimensional probability: An introduction with appli cations in data science, volume 47

    Roman Vershynin. High-dimensional probability: An introduction with appli cations in data science, volume 47. Cambridge university press, 2018

    2018

  32. [40]

    Cattivelli and Ali H

    Federico S. Cattivelli and Ali H. Sayed. Diffusion strate gies for distributed Kalman filtering and smoothing. IEEE Transactions on Automatic Control , 55(9):2069–2084, 2010

    2010

  33. [41]

    Willems’ funda mental lemma for nonlinear systems with koopman linear embedding

    Xu Shang, Jorge Cort´ es, and Yang Zheng. Willems’ funda mental lemma for nonlinear systems with koopman linear embedding. IEEE Control Systems Letters , 2024

    2024

  34. [42]

    Adaptive estimat ion of a quadratic functional by model selection

    Beatrice Laurent and Pascal Massart. Adaptive estimat ion of a quadratic functional by model selection. Annals of statistics , pages 1302–1338, 2000

    2000

  35. [43]

    Sayed, and Babak Hassibi

    Thomas Kailath, Ali H. Sayed, and Babak Hassibi. Linear Estimation . Prentice Hall, 2000

    2000

  36. [44]

    Stochastic processes, estimation, and control

    Jason L Speyer and Walter H Chung. Stochastic processes, estimation, and control . SIAM, 2008. 16 Appendix In this appendix, we provide extra discussions, proof details, and f urther numerical results. In particular, we organize this appendix as follows: • Appendix A provides ...

    2008

  37. [45]

    The steady-state performance of the above recursion satisfie s the discrete-time algebraic Riccati equation P =APA T +Q −APC T( CPC T +R )−1 CPA T

    The recursion ( B.3) will converge to steady-state exponentially fast with the increas e of the time step k. The steady-state performance of the above recursion satisfie s the discrete-time algebraic Riccati equation P =APA T +Q −APC T( CPC T +R )−1 CPA T. (B.4)

  38. [46]

    Denoteek =yk − ˆyk as the prediction error, also called innovation, at time step k

    Let L =APC T( CPC T +R )−1 , then there is ρ(A −LC)< 1. Denoteek =yk − ˆyk as the prediction error, also called innovation, at time step k. Then from [ 44, P98], we have the following results

  39. [47]

    With the basic assumptions of the stochastic system ( A.1), we have E { eleT k } = ¯Rδl,k, where δl,k = 1 if l =k and δl,k = 0 if l ⁄=k. 21 B.2 Multi-dimensional self-normalizing vector martingal es In this subsection, we will provide the basic result about Hanson-Wr ight ineq...

  40. [48]

    While for the term det ˜Z22 = det   ˜V2Tl−2 − p′−1∑ k=p DpZk,pZ T k,pDp  , conditioned on the event EPE and EZ, we have ‖ ‖ ‖ ( ΓZ k,p )−1/2 Zk,p ‖ ‖ ‖ 2 ≤ √ mp + √ 2 log 4k δ1

    ≥ det(λI) ≥λm(p′−p). While for the term det ˜Z22 = det   ˜V2Tl−2 − p′−1∑ k=p DpZk,pZ T k,pDp  , conditioned on the event EPE and EZ, we have ‖ ‖ ‖ ( ΓZ k,p )−1/2 Zk,p ‖ ‖ ‖ 2 ≤ √ mp + √ 2 log 4k δ1 . Hence, we can obtain that Zk,pZ T k,p ≤ ( √mp + √ 2 log 4k δ1 )2 ΓZ k,p ≤...

  41. [49]

    If β is chosen to be β = 2κ+1 log(1/ρ(A−LC)) , then conditioned on Ex we have P { sup 1≤l≤NE sup Tl≤k≤2Tl−2 ‖ ‖ ‖Bk,p ¯Z T k,p ¯V − 1 2 k,p ‖ ‖ ‖ 2 2 ≤ poly ( M, log ( 1 δ1 ))} ≥ 1 − π2δ1 6 , and P { NE∑ l=1 2Tl−2∑ k=Tl ‖bk+1,p‖2 2 ≤ poly ( M, log ( 1 δ1 )) logN } ≥ 1 − π2δ1 6

  42. [50]

    Conditioned on Ee, we have P { sup 1≤l≤NE sup Tl≤k≤2Tl−2 ‖ ‖ ‖Ek,p ¯Z T k,p ¯V − 1 2 k,p ‖ ‖ ‖ 2 2 ≤ poly ( ¯σ ¯R,m,β, log ( 1 δ1 )) logN } ≥ 1 − π2δ1 6

  43. [51]

    Conditioned on EPE and Ee, we have P { sup 1≤l≤NE sup Tl≤k≤2Tl−2 ‖ ‖ ‖ ¯V − 1 2 k,p ¯V 1 2 k+1,p ‖ ‖ ‖ 2 2 ≤ poly ( d MσR , ‖a‖2,β, log 1 δ1 , ¯σ ¯R )} ≥ 1 − ( 1 + π2 6 ) δ1

  44. [52]

    Together with the cross-term bound, we have for probability at lea st 1 − ( 3 + 5π2 6 ) δ1, there is RN ≤ poly ( M,m,β, log 1 δ1 ,d, ‖a‖2 ) log3(N )

    Conditioned on EPE and EZ , we have P { N∑ k=Tinit ‖ ‖ ‖ ¯V − 1 2 k+1,pZk+1,p ‖ ‖ ‖ 2 2 ≤ poly ( M,m,β, log 1 δ ) log2N } ≥ 1 − ( 1 + π2 6 ) δ1. Together with the cross-term bound, we have for probability at lea st 1 − ( 3 + 5π2 6 ) δ1, there is RN ≤ poly ( M,m,β, log 1 δ1 ,d,...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.