Pith. sign in

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 →

arxiv 2505.20943 v1 pith:FNVHE36A submitted 2025-05-27 cs.LG cs.SYeess.SYmath.OCstat.ML

classification cs.LGcs.SYeess.SYmath.OCstat.ML MSC 93C0593B0568Q3290C25
keywords onlinenonstochasticcontrolpartialobservationlineardynamicalsystemsregretminimizationspectralfilteringconvexrelaxationimproperlearningadversarialdisturbances
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

This paper claims that a partially observed linear dynamical system with known dynamics can be controlled almost as well as the best stable linear dynamical controller chosen in hindsight, even when an adversary picks both the disturbances and the convex losses, and that each control step can be computed in time polylogarithmic in the horizon and the inverse stability margin. The proposed algorithm, Double Spectral Control (DSC), achieves regret $O~(\sqrt{T}/\gamma^{11})$ under a controllability assumption and a diagonalizable-stability assumption on the comparator class. It works by expressing the comparator as a double spectral convolution of the natural observation sequence with a universal filter bank built from the top eigenvectors of a Hankel matrix. If the theorem is correct, DSC is the first method for this adversarial partial-observation setting with this regret order and polylogarithmic runtime, improving on the previous GRC method. Small synthetic experiments are reported in which DSC matches or outperforms GRC and LQG baselines.

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.

Watch

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

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

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)
  1. [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.
  2. [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.
  3. [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)
  1. [Theorem 4.1] The theorem statement says Regret_T(OSC, S) but the algorithm is called DSC; the acronym should be corrected.
  2. [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.
  3. [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.
  4. [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

1 steps flagged · score 2.0 of 10

No fitted-parameter circularity; the proof is essentially self-contained except for one key spectral-tail lemma imported from the authors' own preprint [7].

  1. 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 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard online-control assumptions (known bounded marginally stable dynamics, convex Lipschitz costs, a restricted diagonalizably stable comparator class) and on two external results: the spectral-tail bound from the authors' own prior work [7] and the fast-convolution algorithm from [2]. No free parameters are fitted to data; all hyperparameters are set by closed-form formulas. No new physical entities are introduced. The main burden is the unproved spectral-tail bound, which is a self-citation and is not verified within this document.

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).
    This assumption is stated in Section 3.2 and is used throughout the analysis to bound impulse responses and lifted-system norms.
  • domain assumption Cost functions are convex and Lipschitz with respect to y and u (Assumption 3.3).
    Stated in Section 3.2; used to bound cost differences and to apply online gradient descent.
  • domain assumption The comparator class S consists of (kappa, gamma)-diagonalizably stable LDCs, including the zero policy (Definitions 3.4 and 3.5).
    Stated in Section 3.2; the regret benchmark and the analysis are both restricted to this class. Item 4 of Definition 3.4 (closed-loop diagonalizability) is asserted for tractability of analysis only, as acknowledged by the authors.
  • domain assumption Controllability of the LDS (Definition 3.1) is assumed.
    Stated in Section 3.2 and invoked in the main theorem statement, although it is not used in the provided proof lemmas.
  • 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)).
    Invoked in Lemmas A.2 and A.16 to bound the tail of the spectral expansion. This is a load-bearing analytic fact that is not proved in the present paper.
  • domain assumption The fast online convolution method of [2] can be applied to the streaming spectra of dense filters with polylogarithmic amortized cost.
    Used in Corollary 4.4 to claim per-step runtime polylog(T/gamma); no detailed adaptation argument is provided in this paper.

how reviews work

0 comments
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

Figures reproduced from arXiv: 2505.20943 by the authors.

Figure 1
Figure 1. Entries of the first six eigenvectors of [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Illustration of the Double Spectral Control (DSC) method. The learner receives the observed [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Comparison of Controllers: LQG, GRC, and DSC with 95% Confidence Intervals over 100 [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 24 canonical work pages

  1. [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

  2. [1]

    Kakade, and Karan Singh

    Naman Agarwal, Brian Bullins, Elad Hazan, Sham M. Kakade, and Karan Singh. Online control with adversarial disturbances, 2019

  3. [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

  4. [3]

    Logarithmic regret for online control, 2019

    Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control, 2019

  5. [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

  6. [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

  7. [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

  8. [8]

    Prediction, Learning, and Games

    Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games . Cambridge University Press, 2006

Show all 27 references
  1. [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

  2. [10]

    Online linear quadratic control, 2018

    Alon Cohen, Avinatan Hassidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control, 2018

  3. [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,...

  4. [12]

    Jennifer Sun

    Noah Golowich, Elad Hazan, Zhou Lu, Dhruv Rohatgi, and Y . Jennifer Sun. Online control in population dynamics, 2024

  5. [13]

    Introduction to online convex optimization, 2016

    Elad Hazan. Introduction to online convex optimization, 2016

  6. [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

  7. [15]

    Introduction to online control, 2025

    Elad Hazan and Karan Singh. Introduction to online control, 2025

  8. [16]

    Learning linear dynamical systems via spectral filtering, 2017

    Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering, 2017

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [22]

    Improper learning for non-stochastic control, 2020

    Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control, 2020

  15. [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

  16. [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...

  17. [25]

    L is diagonal with nonnegative entries

  18. [26]

    The spectral norm of L is strictly less than one, i.e., ∥L∥ ≤1 − ˜γ

  19. [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...

Pith tools

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