{"id":"a2a47e28-eb08-4562-bf7f-1677fcb415fb","arxiv_id":"2505.08982","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"For unknown non-explosive linear Gaussian systems, the OPF algorithm with per-coordinate forgetting achieves O(log³ N) regret against the Kalman filter, improving over the prior O(log⁶ N) bound.","lead":"This paper presents an online prediction algorithm (OPF) for unknown noisy linear systems that uses coordinate-wise exponential scaling to balance the regression model, and proves a cumulative regret bound of O(log³ N) against the Kalman filter. The result improves the best known logarithmic guarantee by three log factors and is accompanied by simulations showing reduced prediction error.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The model-free claim is not supported: Theorem 1 requires γ and β to be set using ρ(A−LC) and κ, so the O(log³ N) guarantee is oracle-tuned rather than model-free.","rationale":"The reader's verdict was CONDITIONAL, with the weakest assumption in Appendix C.7's residue bound. I agree that C.7 is under-verified and deserves an independent derivation. However, the more immediately load-bearing issue is the contradiction between the paper's model-free claim and the oracle-tuned hyperparameters in Theorem 1. The algorithm is advertised as requiring no knowledge of the system model, but γ and β are chosen from ρ(A−LC) and κ, and the experiments use the true ρ(A−LC). Because a fixed choice of γ, β cannot work for all admissible systems, the central claim as stated is not a model-free guarantee. This does not invalidate the O(log³ N) bound as a conditional, oracle-tuned statement, and the proof may well be repairable; hence REJECT is too strong. The paper needs either an adaptive hyperparameter schedule or a revised claim that does not call the algorithm model-free. Since the reader's CONDITIONAL verdict already requires such a response, my read does not change the verdict.","tokens_in":30727,"tokens_out":24237,"duration_ms":252705,"concrete_test":"Prove or disprove the existence of a model-independent instantiation: for any fixed (γ, β, Tinit), construct a system satisfying Assumptions 1–2 with ρ(A−LC) > γ and (2κ+1)/log(1/ρ) > β; such a construction shows that no universal parameter setting satisfies Theorem 1. As a numerical spot-check, run Algorithm 1 with fixed γ=0.5, β=10, Tinit=100 on the scalar system A=1, C=1, Q=10^{-4}, R=1 (here ρ(A−LC) ≈ 0.99 > γ) and measure the regret slope on a log-log scale. If the slope is positive rather than polylogarithmic, the mis-specified γ is not benign and the model-free claim fails. An adaptive schedule for γ and β that provably maintains O(log³ N) without model knowledge would refute the objection.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim, stated in the abstract and Section 2.2, is that OPF predicts 'without requiring any knowledge of the system matrices or noise covariances.' Yet Theorem 1 can only be instantiated by choosing γ ∈ (ρ(A−LC), 1] and β = Ω(κ)/log(1/ρ(A−LC)). Both quantities are spectral data of the true model. This is not a harmless tuning convention: if γ < ρ(A−LC), the regularization bound in C.4 becomes ∑_{i=1}^p M(ρ/γ)^i, and with p = β log N this contributes N^{β log(ρ/γ)} to the regret bound, so a slightly too-small γ destroys logarithmic regret. Moreover, no fixed (γ, β, Tinit) can work for all systems: for any γ < 1 there is a detectable scalar system with ρ(A−LC) > γ (e.g., A=1, C=1, R=1, Q→0), and for any fixed β there is a system with larger κ/log(1/ρ) (a Jordan block at eigenvalue 1 with ρ→1). The experiments confirm the oracle dependence by setting γ = ρ(A−LC) from the true model in Section 5. Thus the paper's headline 'model-free' claim is not established; the theorem as written is a tuned-parameter guarantee. This concern is load-bearing even if every step of Appendix C is correct, because it attacks the stated scope of the central claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":30919,"tokens_out":17175,"duration_ms":174811,"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":[{"comment":"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.","section":"Section 4.1, Theorem 1"},{"comment":"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.","section":"Appendix C.5"},{"comment":"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.","section":"Appendix C.7"}],"minor_comments":[{"comment":"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.","section":"Algorithm 1, line 7"},{"comment":"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.","section":"Proof sketch, after Eq. (25)"},{"comment":"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.","section":"Appendix D.2"},{"comment":"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.","section":"Section 5, Figure 7"},{"comment":"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.","section":"Remark 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be of interest to the control and online-learning community. The main obstacle is the gap between the advertised model-free claim and the theorem's oracle-tuned parameters; I would encourage the authors to consider either an adaptive parameter-selection scheme or a careful restatement of the scope of the guarantee. I also recommend that the proof of the regression-factor bound in C.5 be carefully revised, as the current union-bound argument appears incorrect as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look: the paper genuinely improves the regret bound for online prediction against the Kalman filter from O(log^6 N) to O(log^3 N), and the OPF algorithm's coordinate-wise forgetting is a sensible new re-parameterization. But the headline 'model-free' claim is not supported by the theorem. Gamma is chosen in (rho(A-LC), 1] and beta = Omega(kappa)/log(1/rho(A-LC)); both are spectral data of the true model. No fixed choice of (gamma, beta) works for all systems: for any gamma < 1 there is a detectable scalar system with rho(A-LC) > gamma, and for any fixed beta there is a system with larger kappa/log(1/rho). The experiments set gamma = rho(A-LC) from the model. So Theorem 1 is a tuned-parameter guarantee, not a model-free one. The D.2 robustness margin (gamma = rho/(1+c rho)) gives some slack but still requires rho and beta.\n\nThat said, the mathematical core is worth serious attention. I didn't find circularity: constants are not fitted to data, and the imported PE and Hanson-Wright results are external. The trace-based Hanson-Wright bound and the inter-epoch determinant cancellation are new tools, and the regret decomposition is coherent. The numerics (regret around log^2 N, better constants with gamma near rho) support the qualitative claims.\n\nSoft spots, in proportion. The C.7 self-cancellation step needs a careful check: the uniform residue M1 across epochs is only sketched, and the persistent-excitation bootstrap assumes T_init >= N0 with N0 depending on unknown system constants. These are gaps, not obvious errors. Also, the pseudocode in Algorithm 1 uses the direct initialization that the authors themselves replace in Appendix E.2 due to numerical instability; that should be fixed for reproducibility.\n\nWho this is for: anyone working on online learning for partially observed linear systems or on regret bounds for adaptive filtering. It deserves a serious referee. I'd send it out, with a request to qualify the model-free claim and to tighten the C.7 and PE arguments. Major revision, not desk reject.","headline":"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.","tokens_in":31612,"tokens_out":2722,"would_cite":true,"duration_ms":25884,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93E11","93E35","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Unknown linear systems can be predicted with O(log³ N) regret via a forgetting factor.","keywords":["online learning","Kalman filter","model-free prediction","logarithmic regret","exponential forgetting","balanced regression","linear dynamical systems","Hanson-Wright inequality"],"falsifier":"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.","tokens_in":30323,"feed_emoji":"📉","tokens_out":10316,"duration_ms":94658,"temperature":0.7,"pith_summary":"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.","feed_headline":"Forgetting factor cuts Kalman-learning regret to O(log³ N)","feed_subtitle":"Rescaling past observations fixes the overfit-prone regression behind model-free Kalman prediction.","key_machinery":"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)$.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the regression model, the doubling-epoch structure, the persistent-excitation theorem, and the $O(\\log^6 N)$ baseline that this paper sharpens to $O(\\log^3 N)$.","marker":"[12]"},{"why":"Establishes the $O(\\log^{11} N)$ low-rank spectral approximation baseline; serves as a comparison target in Table 1 and in experiments.","marker":"[20]"},{"why":"Introduces the spectral-filtering framework for learning linear dynamical systems and the $O(\\sqrt{N})$ regret baseline that this line improves.","marker":"[10]"},{"why":"Provides the self-normalized martingale and log-determinant bound that earlier proofs use; the paper replaces it with a Hanson–Wright-based bound.","marker":"[36]"},{"why":"Is the original Hanson–Wright inequality used to bound Gaussian quadratic forms in the regression-error analysis.","marker":"[38]"},{"why":"Supplies the high-dimensional probability tools (sub-Gaussian norms, epsilon nets) behind the vectorized Hanson–Wright lemma.","marker":"[39]"},{"why":"Provides the traditional discounting baseline; its uniform re-weighting is shown to lose information while OPF's balancing rescaling does not.","marker":"[24]"},{"why":"Motivates the doubling-trick epoch schedule that keeps the past horizon $p$ growing as $O(\\log T_l)$.","marker":"[32]"}],"fun_headline_variants":["Forgetting factor turns Kalman learning into O(log³ N) regret","Balanced regression via forgetting gives log-cubed Kalman regret","Model-free Kalman: forgetting factor yields logarithmic regret bound","Forgetting as ridge penalty: Kalman regret drops to O(log³ N)","Log-cubed regret for model-free Kalman with regression balancing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Forgetting factor turns Kalman learning into O(log³ N) regret","Balanced regression via forgetting gives log-cubed Kalman regret","Model-free Kalman: forgetting factor yields logarithmic regret bound","Forgetting as ridge penalty: Kalman regret drops to O(log³ N)","Log-cubed regret for model-free Kalman with regression balancing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000982,"raw_usage":{"total_tokens":4233,"prompt_tokens":1074,"completion_tokens":3159,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":690,"completion_tokens_details":{"reasoning_tokens":3067}},"tokens_in":690,"tokens_out":3159,"duration_ms":21933,"temperature":1.0,"reasoning_tokens":3067,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:45:24.035659+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the regression model, the doubling-epoch structure, the persistent-excitation theorem, and the $O(\\log^6 N)$ baseline that this paper sharpens to $O(\\log^3 N)$."},{"cited_title":"SLIP: Learning to predict in unknown dynamical systems with long-term memory","cited_arxiv_id":null,"evidence_quote":"Establishes the $O(\\log^{11} N)$ low-rank spectral approximation baseline; serves as a comparison target in Table 1 and in experiments."},{"cited_title":"Learning line ar dynamical systems via spectral filtering","cited_arxiv_id":null,"evidence_quote":"Introduces the spectral-filtering framework for learning linear dynamical systems and the $O(\\sqrt{N})$ regret baseline that this line improves."},{"cited_title":"Improved algorithms for linear stochastic bandits","cited_arxiv_id":null,"evidence_quote":"Provides the self-normalized martingale and log-determinant bound that earlier proofs use; the paper replaces it with a Hanson–Wright-based bound."},{"cited_title":"A bound on tail p robabilities for quadratic forms in independent random variables","cited_arxiv_id":null,"evidence_quote":"Is the original Hanson–Wright inequality used to bound Gaussian quadratic forms in the regression-error analysis."}],"review_version":1}