REVIEW 3 major objections 4 minor 27 references
Efficient Spectral Control of Partially Observed Linear Dynamical Systems
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Double Spectral Control claims O~(sqrt(T)/gamma^11) regret with polylog(T/gamma) per-step runtime for partially observed linear systems under adversarial disturbances and convex losses.
desk verdict Novel two-level spectral method with a plausible but incomplete proof: parameter typo, unproved imported tail bound, and a narrower-than-claimed comparator class. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing machinery is a two-level spectral approximation of a stable linear dynamical controller. The first level approximates any $(\kappa,\gamma)$-diagonalizably stable LDC by a spectral-projection linear controller whose filters are top eigenvectors of a Hankel matrix $H_{ij}=(1-\gamma)^{i+j-1}/(i+j-1)$; the key step expands the geometric vectors $\mu_\alpha=(1,\alpha,\ldots,\alpha^m)$ in that orthonormal eigenbasis. The second level approximates the resulting open-loop controller by convolving the natural observation sequence with a second Hankel eigenbasis, yielding a controller linear in learnable matrices $M$. The analysis is carried by an imported spectral-tail bound, Lemma 7.4 of [7], which says the tail coefficients of those geometric expansions decay like $\exp(-\pi^2 h/(16 \log T))$; this is what lets $h$ and $\tilde{h}$ be only logarithmic in $T$ while preserving $O(\sqrt{T})$ approximation error. The learning step is projected online gradient descent over a convex set $K$, and fast online convolution makes each round polylogarithmic.
What would settle it
Compute the tail sum $\sum_{i=h+1}^{m} |\phi_i^\top \mu_\alpha|$ for the Hankel matrix $H_{ij}=(1-\gamma)^{i+j-1}/(i+j-1)$ with $m = \gamma^{-1} \log T$, $T = 10^4$, $\gamma = 0.01$, and $\alpha = 1-\gamma$. If the tail does not scale like $\exp(-\pi^2 h/(16 \log T))$ for $h$ between $1$ and $4 \log T$, then the spectral-tail bound imported from [7] fails in the regime the proof requires and Lemma A.2's $O(\sqrt{T})$ approximation is unsupported. A direct algorithm-level check is to run DSC with $h$ below and above $2 \log T \log(1/\gamma)$ and observe whether the regret drops sharply at the prescribed threshold.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the disturbance-response map of any $(\kappa,\gamma)$-diagonalizably stable linear dynamical controller can be approximated, up to $O(\sqrt{T})$ cumulative cost error, by a convex parameterization over double-filtered natural observations. The natural observation sequence $y_t^{\mathrm{nat}}$, defined as the output the system would produce under zero controls, is computed online through a fictitious internal state and is independent of the learner's parameters. Convolving this sequence first with top eigenvectors of the Hankel matrix $H_{ij}=(1-\gamma)^{i+j-1}/(i+j-1)$ in a spectral lifting stage, and then with a second Hankel eigenbasis in a spectral filtering stage, produces features that are linear in the parameter matrix $M$. Projected online gradient descent over the resulting convex set yields the regret bound $O~(\sqrt{T}/\gamma^{11})$ with per-step runtime $\mathrm{polylog}(T/\gamma)$.
Load-bearing premise
The load-bearing premise is an estimate imported from another paper and not proved here: when a sequence $(1,\alpha,\alpha^2,\ldots)$ is expanded in the paper's spectral filter basis, the tail of the expansion must shrink exponentially, at rate $\exp(-\pi^2 h/(16 \log T))$, for filter counts $h$ that are only logarithmic in the time horizon. If that estimate is wrong, the $O(\sqrt{T})$ approximation error, and with it the whole regret guarantee, collapses.
Editorial extensions
If this is right
- If Theorem 4.1 is correct, DSC is the first algorithm for partially observed linear systems with adversarial disturbances and general convex losses whose per-step runtime is polylogarithmic in $T$ and in the inverse stability margin, whereas the previous GRC baseline scales polynomially in $1/\gamma$.
- The regret bound $O~(\sqrt{T}/\gamma^{11})$ matches the best known regret order for nonstochastic control, so the exponential runtime improvement does not trade away the statistical guarantee.
- Because the per-step runtime is $\mathrm{polylog}(T/\gamma)$, the hidden state dimension enters the guarantees through constants rather than through per-step computation, making the method usable for high-dimensional systems within the comparator class.
- The convex relaxation yields an improper-learning guarantee: DSC competes with the best stable linear dynamical controller in hindsight without solving the nonconvex problem of optimizing directly over LDC parameters.
- The approximation result implies the Hankel filter bank can be precomputed once, before seeing the cost sequence or disturbances, and still represent any controller in the comparator class to $O(\sqrt{T})$ cumulative cost error.
Reading between the lines
- Inference: the spectral-tail decay bound is the true bottleneck of the method, so a standalone numerical check of Lemma 7.4 in the regime $h \approx \log T$ would decisively test whether the polylogarithmic filter counts are achievable or whether the runtime must scale as a power of $1/\gamma$.
- Inference: the two-level spectral recipe is more general than this paper: any comparator class whose impulse responses lie close to the span of a small number of Hankel eigenvectors could be learned in polylog time by repeated spectral convolution, potentially covering stable nonlinear or time-varying systems through linearization.
- Inference: the theory predicts a sharp transition in approximation error as the number of filters $h$ crosses $2 \log T \log(1/\gamma)$, which could be used as a model-selection rule and measured in synthetic experiments beyond the ones reported.
- Inference: because DSC uses the natural observation sequence instead of a learned state estimator, its practical behavior under model misspecification of the system matrices may degrade more gracefully than observer-based methods; this is not tested in the paper.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes Double Spectral Control (DSC), an online algorithm for partially observed linear dynamical systems with adversarial disturbances and convex costs. The algorithm competes against the class S of (κ,γ)-diagonalizably stable linear dynamical controllers by expressing the disturbance-response map in a two-level spectral basis built from eigenvectors of a universal Hankel matrix. The main claim, Theorem 4.1, is a regret bound Regret_T = O~(sqrt(T)/γ^11) with per-step runtime polylog(T/γ), which would be the first such result combining partial observation, adversarial noise, general convex losses, and polylogarithmic runtime. The proof proceeds by approximating any LDC in S first by a spectral-projection linear controller (Lemma A.2) and then by a spectral controller on a lifted system (Lemma A.3), followed by an online convex optimization analysis. The empirical appendix reports small synthetic comparisons against GRC and LQG.
Significance. If the main theorem is correct, this is a notable advance in online nonstochastic control: the two-level spectral parameterization is an elegant way to avoid the polynomial dependence on γ^{-1} that plagues earlier partial-observation algorithms such as GRC, and the universal, system-independent basis is a genuine strength. The paper gives an explicit regret decomposition and clearly identifies the algorithmic operations needed for polylog runtime. However, the central proof currently depends on an unstated and unproved spectral-tail bound imported from a same-author preprint, the parameter choices in the main theorem are internally inconsistent, and a key closed-loop stability property is assumed rather than derived. Because these issues are load-bearing, the contribution cannot be considered established in its present form. No machine-checked proofs or reproducibility artifacts are provided; the theoretical claims rest entirely on the analytic argument.
major comments (3)
- [Appendix A, Eq. (14), Lemma A.16] The proof of Lemma A.2 (Eq. (14)) and Lemma A.16 invokes 'Lemma 7.4 of [7]' to bound all spectral truncation errors, but the lemma is not stated in this paper, and the decay lengthscale is written as log T. The Hankel matrices in Definitions A.1 and A.10 have size m+1 and m~, respectively, which are only polylogarithmic in T under the choices in Theorem 4.1, so it is not clear that the bound should be exp(−π^2 j/(16 log T)) rather than exp(−π^2 j/(16 log m)) or exp(−π^2 j/(16 log m~)). Since every approximation step in Lemmas A.2 and A.16, hence Lemma 4.2 and Theorem 4.1, is controlled by this inequality, the authors must state the lemma, prove it for the exact Hankel matrices used here, and verify that the constants and the regime h << m are compatible with the stated rates.
- [Theorem 4.1, item 2; Lemma A.2; Eq. (14)] The specified number of lifting filters is not a valid positive integer for large T. The argument of the logarithm in item 2 is C2 sqrt(m) / (γ^2 T^{3/2} log T log^{1/4}(2/γ)), which tends to 0 as T grows, so h = ceil(2 log T log(...)) is nonpositive for all sufficiently large T. Moreover, the lower bound on h stated in Lemma A.2 has T in the denominator through ε γ^2 T, whereas the derivation leading to Eq. (14) solves for h using δ1 with δ1 ~ ε γ / (... T), which puts a positive power of T in the numerator of the log argument when ε = 1/sqrt(T). These formulations are mutually inconsistent. The parameter choices in Theorem 4.1 must be corrected so that h is positive and satisfies the lower bound used in the proof of Lemma A.2.
- [Definition 3.4(4), Lemma A.5] Condition 4 of Definition 3.4 assumes that the lifted closed-loop matrix A~ + B~ K~ C~ for the spectral-projection controller constructed in Lemma A.2 is (κ,γ)-diagonalizably stable, but this is not derived from conditions 1–3 or from the construction itself. Lemma A.5 uses this condition through the statement 'By definition 3.4', and it is the only source of the bound on y_K_t that controls the trajectory differences in the proof of Lemma A.2. Because the condition refers forward to a controller that is not defined until the appendix, the comparator class S is not a standalone class of LDC policies. The authors should either prove the lifted stability from the standing assumptions or make it an explicit, carefully stated assumption on S, and should discuss how restrictive this assumption is relative to the natural notion of a diagonalizably stable LDC.
minor comments (4)
- [Theorem 4.1] The theorem statement says Regret_T(OSC, S) but the algorithm is called DSC; the acronym should be corrected.
- [Definition A.1 vs. Algorithm 1/Definition 3.6] Definition A.1 uses a Hankel matrix of dimension (m+1) × (m+1) with eigenvectors in R^{m+1}, while Algorithm 1 and Definition 3.6 use an m × m matrix; the dimensions and indexing should be aligned.
- [Definition 3.6] The symbol φ_i is used for both the lifting filters and the learning filters, which makes the two spectral stages hard to distinguish; separate notation, e.g., ϕ_i for lifting and φ_i for learning, would improve clarity.
- [Appendix C] The experiments use h = h~ = 5 and m = m~ = 10, which does not reflect the polylogarithmic parametric choices in Theorem 4.1; the appendix should state explicitly that the experiments are only illustrative and are not a test of the theorem's parameter regime.
Circularity Check
No fitted-parameter circularity; the proof is essentially self-contained except for one key spectral-tail lemma imported from the authors' own preprint [7].
-
self citation load bearing
[Appendix A.1, Eq. (14), and Appendix A.2, proof of Lemma A.16; both invoke 'Lemma 7.4 of [7]' ([7] = Brahmbhatt, Buzaglo, Druchyna, Hazan, 'A new approach to controlling linear dynamical systems'…]
"Using Lemma 7.4 of [7], we get that: ||u^{π_τ}_{τ−1} − u^{π_{τ−1}}_{τ−1}|| ≤ 2κ^6 κ_C W d√m/γ log^{1/4}(2/γ) ∫_h^∞ exp(−π^2 j/(16 log T)) dj ≤ ... [h ≥ 2 logT log(4κ^6κ_C W d√m/(δ_1 γ log T log^{1/4}(2/γ)))]."
This tail bound on the unrecovered spectral projections Σ_{i>h}|φ_i^T μ_α| is the mechanism that makes the approximation error in Lemma A.2 small, and the identical bound in Lemma A.16 is what makes Lemma A.3 and hence Lemma 4.2 go through. It is neither stated nor proved in this manuscript; it is imported from [7], an unpublished preprint by exactly the same four authors. The central regret theorem therefore depends on a same-author citation for its key decay estimate rather than on a proof contained in this paper. This is the load-bearing-self-citation pattern, though it is a technical lemma rather than a uniqueness theorem and does not reduce the result to a fitted value.
full rationale
The regret bound is not circular in the fitting sense: no parameter is fitted to data, the Hankel eigenbasis is universal and system-independent, and the online-gradient-descent analysis (Lemmas B.1-B.3 and Lemma 4.3) is proved in the paper. The main circularity-adjacent issue is the repeated import of 'Lemma 7.4 of [7]' in Eq. (14) and Lemma A.16; because [7] is an unpublished preprint by exactly the same four authors and the lemma's exact statement and regime are not reproduced, the approximation guarantee is conditional on that self-citation. That keeps the score at 2 rather than 0. Separate concerns raised in the proof—the possibly nonpositive h formula in Theorem 4.1 item 2 and the log T versus log m lengthscale for an (m+1)x(m+1) Hankel matrix—are correctness/validation issues, not circularity, and are not counted in this score. The Theorem 4.1 statement also says 'OSC' where the algorithm is named DSC; this is a naming typo, not a circular step.
Assumptions & free parameters
assumptions (6)
- domain assumption The system is marginally stable and diagonalizably so: ||A^i|| <= kappa (1-gamma)^i for all i, and B, C, W are bounded (Assumption 3.2).
- domain assumption Cost functions are convex and Lipschitz with respect to y and u (Assumption 3.3).
- domain assumption The comparator class S consists of (kappa, gamma)-diagonalizably stable LDCs, including the zero policy (Definitions 3.4 and 3.5).
- domain assumption Controllability of the LDS (Definition 3.1) is assumed.
- domain assumption The spectral-tail bound for the Hankel basis eigenvectors, imported as Lemma 7.4 of the same-authors' preprint [7], holds with the exact decay exp(-pi^2 h / (16 log T)).
- domain assumption The fast online convolution method of [2] can be applied to the streaming spectra of dense filters with polylogarithmic amortized cost.
Cite this review
Pith. "Pith review of Efficient Spectral Control of Partially Observed Linear Dynamical Systems." pith.science (2026). https://pith.science/paper/FNVHE36A
@misc{pith2026250520943,
author = {Pith},
title = {Pith review of: Efficient Spectral Control of Partially Observed Linear Dynamical Systems},
year = {2026},
howpublished = {\url{https://pith.science/paper/FNVHE36A}},
note = {Machine review of arXiv:2505.20943}
}
read the original abstract
We propose a new method for the problem of controlling linear dynamical systems under partial observation and adversarial disturbances. Our new algorithm, Double Spectral Control (DSC), matches the best known regret guarantees while exponentially improving runtime complexity over previous approaches in its dependence on the system's stability margin. Our key innovation is a two-level spectral approximation strategy, leveraging double convolution with a universal basis of spectral filters, enabling efficient and accurate learning of the best linear dynamical controllers.
Figures
Reference graph
Works this paper leans on
-
[7]
A new approach to controlling linear dynamical systems, 2025
Anand Brahmbhatt, Gon Buzaglo, Sofiia Druchyna, and Elad Hazan. A new approach to controlling linear dynamical systems, 2025
work page 2025
-
[1]
Naman Agarwal, Brian Bullins, Elad Hazan, Sham M. Kakade, and Karan Singh. Online control with adversarial disturbances, 2019
work page 2019
-
[2]
Futurefill: Fast generation from convolutional sequence models, 2024
Naman Agarwal, Xinyi Chen, Evan Dogariu, Vlad Feinberg, Daniel Suo, Peter Bartlett, and Elad Hazan. Futurefill: Fast generation from convolutional sequence models, 2024
work page 2024
-
[3]
Logarithmic regret for online control, 2019
Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control, 2019
work page 2019
-
[4]
Towards provable control for unknown linear dynamical systems, 2018
Sanjeev Arora, Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Towards provable control for unknown linear dynamical systems, 2018
work page 2018
-
[5]
Introduction to stochastic control theory, volume 70 of Mathematics in science and engineering
Karl Johan Åström. Introduction to stochastic control theory, volume 70 of Mathematics in science and engineering. Academic Press, United States, 1970
work page 1970
-
[6]
Lecture 10: Linear quadratic stochastic control with partial state observation
Stephen Boyd. Lecture 10: Linear quadratic stochastic control with partial state observation. https://web.stanford.edu/class/ee363/lectures/, 2009. Lecture notes for EE363: Convex Optimization I, Stanford University, Winter 2008–09
work page 2009
-
[8]
Prediction, Learning, and Games
Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games . Cambridge University Press, 2006
2006
Show all 27 references
-
[9]
Online control for meta-optimization
Xinyi Chen and Elad Hazan. Online control for meta-optimization. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY , USA, 2023. Curran Associates Inc
2023
-
[10]
Online linear quadratic control, 2018
Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control, 2018
2018
-
[11]
Logarithmic regret for adversarial online control
Dylan Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning , volume 119 of Proceedings of Machine Learning Research , pages 3211–3221. PMLR,...
2020
-
[12]
Jennifer Sun
Noah Golowich, Elad Hazan, Zhou Lu, Dhruv Rohatgi, and Y . Jennifer Sun. Online control in population dynamics, 2024
2024
-
[13]
Introduction to online convex optimization, 2016
Elad Hazan. Introduction to online convex optimization, 2016
2016
-
[14]
Spectral filtering for general linear dynamical systems, 2018
Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. Spectral filtering for general linear dynamical systems, 2018
2018
-
[15]
Introduction to online control, 2025
Elad Hazan and Karan Singh. Introduction to online control, 2025
2025
-
[16]
Learning linear dynamical systems via spectral filtering, 2017
Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering, 2017
2017
-
[17]
A new approach to linear filtering and prediction problems
Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82.1:35–45, 1960
1960
-
[18]
Logarithmic regret bound in partially observable linear dynamical systems, 2020
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Logarithmic regret bound in partially observable linear dynamical systems, 2020
2020
-
[19]
The general problem of the stability of motion.International journal of control, 55(3):531–534, 1992
Aleksandr Mikhailovich Lyapunov. The general problem of the stability of motion.International journal of control, 55(3):531–534, 1992
1992
-
[20]
Dimension-free regret for learning asymmetric linear dynamical systems, 2025
Annie Marsden and Elad Hazan. Dimension-free regret for learning asymmetric linear dynamical systems, 2025
2025
-
[21]
Online control of unknown time-varying dynamical systems, 2022
Edgar Minasyan, Paula Gradu, Max Simchowitz, and Elad Hazan. Online control of unknown time-varying dynamical systems, 2022. 10
2022
-
[22]
Improper learning for non-stochastic control, 2020
Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control, 2020
2020
-
[23]
Jennifer Sun, Praneeth Netrapalli, and Elad Hazan
Arun Suggala, Y . Jennifer Sun, Praneeth Netrapalli, and Elad Hazan. Second order methods for bandit optimization and control, 2024
2024
-
[24]
xπτ t − xπτ −1 t sπτ t − sπτ −1 t # = A B πC BCπ Aπ
Daniel Suo, Naman Agarwal, Wenhan Xia, Xinyi Chen, Udaya Ghai, Alexander Yu, Paula Gradu, Karan Singh, Cyril Zhang, Edgar Minasyan, Julienne LaChance, Tom Zajdel, Manuel Schottdorf, Daniel Cohen, and Elad Hazan. Machine learning for mechanical ventilation control, 2022. 11 A A...
2022
-
[25]
L is diagonal with nonnegative entries
-
[26]
The spectral norm of L is strictly less than one, i.e., ∥L∥ ≤1 − ˜γ
-
[27]
The controller and the transformation matrices are bounded, i.e., ∥K∥, ∥H∥, ∥H −1∥ ≤˜κ. We denote by ˜S = {K : K is (˜κ, ˜γ)-diagonalizably stable} the set of such policies, and, with slight abuse of notation, also use ˜S to refer to the class of linear policies ut = Syt where...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.