{"id":"6aa22c6b-399b-47f9-be59-6a753826a507","arxiv_id":"2505.20943","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Double Spectral Control achieves O~(sqrt(T)/gamma^11) regret against stable linear dynamical controllers with only polylog(T/gamma) per-step runtime, exponentially improving the stability-margin dependence of prior work.","lead":"This paper proposes Double Spectral Control (DSC), a new algorithm that controls partially observed linear systems under adversarial disturbances while keeping per-step computation time polylogarithmic in the horizon and the stability margin. If correct, it removes a major computational bottleneck in online control and makes spectral online control practical for longer-horizon problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The approximation proof hinges on an imported spectral-tail bound whose decay lengthscale (log T vs. log m) is not justified for the m×m Hankel matrix used, and the h formula in Theorem 4.1 appears nonpositive for large T.","rationale":"The central claim is a chain of approximation results: LDCs in S are first approximated by spectral-projection linear controllers (Lemma A.2), and those are then approximated by the DSC parameterization (Lemma A.3/A.16). Both links rely on the same imported eigenvector tail lemma from [7]. The paper neither states nor proves that lemma, and it is from a same-author preprint, so the reader cannot verify constants or regime. More concretely, the eigenvectors are of an (m+1)×(m+1) Hankel matrix, and standard finite-matrix spectral bounds would have decay governed by the matrix dimension m, not the horizon T. Since m=O(γ^{-1} log T), replacing log T by log m changes the tail from roughly T^{-c} to roughly exp(-c log T/log log T), which may not suffice for the chosen h. This is not a stylistic objection: Eq. (14) is the only mechanism that makes the spectral tail negligible, and the same bound is reused in Lemma A.16. The h formula in Theorem 4.1 is also problematic as written: with ε=1/√T, the denominator contains γ^2 T^{3/2} log T, so for large T the argument of the outer logarithm tends to 0, making the specified h nonpositive. The proof's Eq. (14) instead requires a logarithm whose argument grows like T/ε = T^{3/2}. That is a concrete inconsistency between the theorem statement and the proof, though likely fixable by a corrected formula. I do not see an internal contradiction that forces rejection; the high-level two-level spectral construction is plausible and the runtime claim is interesting. But the current manuscript does not fully justify the central regret bound, because the h parameter as stated cannot satisfy the approximation lemma for large T, and the imported spectral-tail lemma is not verifiable in the regime used. Conditional acceptance is therefore appropriate, requiring the authors to state and prove the tail bound for the m×m Hankel matrix and to correct the h formula so that it matches the proof's requirement.","tokens_in":21961,"tokens_out":14475,"duration_ms":157513,"concrete_test":"Restate and prove the spectral-tail bound of [7, Lem. 7.4] for the exact Hankel matrix H∈R^{(m+1)×(m+1)} used in Definition A.1, then recompute Eq. (14) with the stated m and h of Theorem 4.1 for T=10^6 and γ=0.1. Separately evaluate the outer-log argument in Theorem 4.1 item 2; if the tail no longer yields the required δ1, or if the h formula is nonpositive, then Lemma 4.2 and Theorem 4.1 fail as written.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma A.2 and Lemma A.16 control the error of truncating the eigen-expansion of geometric sequences μ_α to the top h eigenvectors of the Hankel matrix H∈R^{(m+1)×(m+1)} (Definition A.1) by invoking 'Lemma 7.4 of [7]' and writing Σ_{i>h}|φ_i^T μ_α| ≤ O(log^{1/4}(2/γ)) ∫_h^∞ exp(−π^2 j/(16 log T)) dj (Eq. 14). The decay lengthscale is stated as log T, the horizon, but the eigenvectors come from a matrix of size m+1, where in Theorem 4.1 m = O(γ^{-1} log(T^{3/2}/γ^3)). If Lemma 7.4's rate is exp(−π^2 h/(16 log N)) with N the matrix dimension, then the correct tail is exp(−π^2 h/(16 log m)), which decays much more slowly when m≪T, and the stated h need not make Eq. (14) ≤ δ1. This tail bound is used in every approximation step of Lemmas A.2 and A.16, hence in Lemma 4.2 and Theorem 4.1, so the central regret bound is not established unless the authors restate and prove the lemma in this exact regime. Separately, the h chosen in Theorem 4.1 item 2 is h = ⌈2 logT log(C2√m/(γ^2 T^{3/2} logT log^{1/4}(2/γ)))⌉; for large T the outer-log argument is <1, so the formula specifies a nonpositive number of filters, while the proof of Lemma A.2 requires h ≥ 2 logT log(C T^{3/2}) with T^{3/2} in the numerator. Thus the stated parameter choice is inconsistent with the proof. Definition 3.4(4) also assumes without proof that the lifted closed-loop matrix for the spectral-projection controller is (κ,γ)-diagonalizably stable, and Lemma A.5 depends on that assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22332,"tokens_out":9181,"duration_ms":98712,"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":[{"comment":"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.","section":"Appendix A, Eq. (14), Lemma A.16"},{"comment":"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.","section":"Theorem 4.1, item 2; Lemma A.2; Eq. (14)"},{"comment":"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.","section":"Definition 3.4(4), Lemma A.5"}],"minor_comments":[{"comment":"The theorem statement says Regret_T(OSC, S) but the algorithm is called DSC; the acronym should be corrected.","section":"Theorem 4.1"},{"comment":"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.","section":"Definition A.1 vs. Algorithm 1/Definition 3.6"},{"comment":"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.","section":"Definition 3.6"},{"comment":"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.","section":"Appendix C"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on 'Lemma 7.4 of [7]', an unpublished same-author preprint, for the central spectral-tail estimate. For a journal submission, the proof should be self-contained or the lemma should be stated and proved in the exact Hankel-matrix regime used here. The parameter inconsistencies in Theorem 4.1 and the forward-referential condition in Definition 3.4(4) also need to be resolved before the main claim can be evaluated. The approach is plausible and the contribution is potentially significant, so I do not recommend rejection at this stage, but the revision must address these load-bearing points."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis is a serious attempt at an important problem: a controller for partially observed linear dynamical systems under adversarial disturbances and convex costs, claiming O~(sqrt(T)/gamma^11) regret and polylog(T/gamma) per-step runtime. The two-level spectral approximation (spectral lifting followed by spectral filtering) is a genuinely new idea in online control, and the analysis is ambitious. If the main theorem is correct, it is a real subfield advance.\n\nBut the paper is not yet trustworthy as written, and I see three specific problems.\n\nFirst, the load-bearing spectral-tail bound is imported as 'Lemma 7.4 of [7]', a same-author preprint, and used in every approximation step (Lemmas A.2 and A.16). The paper does not state the lemma or its precise regime. The decay lengthscale appears as log T while the Hankel matrix has dimension m+1; if the true lengthscale is log m, the stated h may or may not suffice. That needs to be settled and the lemma proved in this paper.\n\nSecond, the parameter choice in Theorem 4.1 is internally inconsistent: the h formula has T^{3/2} in the denominator of the inner logarithm, making h negative for large T. Lemma A.2 has the same expression with T^{3/2} in the numerator, so this looks like a typo, but as written the theorem statement is vacuous.\n\nThird, Definition 3.4 item 4 simply assumes that the lifted closed-loop matrix for the spectral-projection controller is (kappa,gamma)-diagonalizably stable. That is not a consequence of items 1-3, and it restricts the comparator class S in a way the paper does not quantify. The footnote says it is for analysis tractability only, but that does not justify claiming to compete with general stable LDCs.\n\nOn the positive side, the convex parameterization, the OGD reduction, the Lipschitz bounds, and the memoryless-loss approximation are standard and structurally sound. The experiments are too preliminary to add evidence.\n\nThe three issues are addressable: fix the typo, restate and prove the spectral-tail lemma, and either prove item 4 or clearly state the narrower comparator class and its cost. That makes this a conditional accept rather than a reject. I would send it to a careful referee.\n\nVerdict: worth serious peer review, with a strong expectation of revision.","headline":"Novel two-level spectral method with a plausible but incomplete proof: parameter typo, unproved imported tail bound, and a narrower-than-claimed comparator class.","tokens_in":22922,"tokens_out":5402,"would_cite":false,"duration_ms":53219,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93C05","93B05","68Q32","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["online nonstochastic control","partial observation","linear dynamical systems","regret minimization","spectral filtering","convex relaxation","improper learning","adversarial disturbances"],"falsifier":"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.","tokens_in":21701,"feed_emoji":"🎛️","tokens_out":17097,"duration_ms":154321,"temperature":0.7,"pith_summary":"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.","feed_headline":"Partially observed control gets sqrt(T) regret at polylog speed","feed_subtitle":"DSC matches the best known regret for partially observed LDS while cutting per-step runtime to polylog(T/gamma).","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Provides Lemma 7.4, the spectral-tail decay bound on projections of geometric sequences onto Hankel eigenvectors, which controls every approximation error in the proof.","marker":"[7]"},{"why":"Introduces the online nonstochastic control setting, defines linear dynamical controllers as the comparator class, and motivates the convex relaxation.","marker":"[15]"},{"why":"Introduces spectral filtering for learning linear dynamical systems from observations, the technique that DSC extends to two levels.","marker":"[16]"},{"why":"Defines GRC, the prior method with polynomial runtime dependence on the inverse stability margin, against which the runtime gain is measured.","marker":"[22]"},{"why":"Supplies the fast online convolution method used to implement each control step in polylog(T/gamma) time.","marker":"[2]"},{"why":"Provides the standard online gradient descent regret bound used to turn the convex parameterization into a regret guarantee.","marker":"[13]"}],"fun_headline_variants":["DSC speeds partial LDS control with polylog runtime and sqrt(T) regret","Double spectral filtration gives polylog-per-step control of partially observed LDS","Exponential runtime cut: Double Spectral Control for partial LDS","Polylog runtime for partial LDS control with sqrt(T) regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["DSC speeds partial LDS control with polylog runtime and sqrt(T) regret","Double spectral filtration gives polylog-per-step control of partially observed LDS","Exponential runtime cut: Double Spectral Control for partial LDS","Polylog runtime for partial LDS control with sqrt(T) regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000585,"raw_usage":{"total_tokens":2686,"prompt_tokens":815,"completion_tokens":1871,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":431,"completion_tokens_details":{"reasoning_tokens":1790}},"tokens_in":431,"tokens_out":1871,"duration_ms":14504,"temperature":1.0,"reasoning_tokens":1790,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T13:42:53.476566+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"A new approach to controlling linear dynamical systems, 2025","cited_arxiv_id":null,"evidence_quote":"Provides Lemma 7.4, the spectral-tail decay bound on projections of geometric sequences onto Hankel eigenvectors, which controls every approximation error in the proof."},{"cited_title":"Introduction to online control, 2025","cited_arxiv_id":null,"evidence_quote":"Introduces the online nonstochastic control setting, defines linear dynamical controllers as the comparator class, and motivates the convex relaxation."},{"cited_title":"Learning linear dynamical systems via spectral filtering, 2017","cited_arxiv_id":null,"evidence_quote":"Introduces spectral filtering for learning linear dynamical systems from observations, the technique that DSC extends to two levels."},{"cited_title":"Improper learning for non-stochastic control, 2020","cited_arxiv_id":null,"evidence_quote":"Defines GRC, the prior method with polynomial runtime dependence on the inverse stability margin, against which the runtime gain is measured."},{"cited_title":"Futurefill: Fast generation from convolutional sequence models, 2024","cited_arxiv_id":null,"evidence_quote":"Supplies the fast online convolution method used to implement each control step in polylog(T/gamma) time."},{"cited_title":"Introduction to online convex optimization, 2016","cited_arxiv_id":null,"evidence_quote":"Provides the standard online gradient descent regret bound used to turn the convex parameterization into a regret guarantee."}],"review_version":1}