PaperlayerView exact revision on arXiv

Source-linked AI summary

Gradient Descent Learns Linear Dynamical Systems

Moritz Hardt, Tengyu Ma, Benjamin Recht

arXiv:1609.05191v2cs.LGcs.DSmath.OCstat.ML

TL;DR

Linear dynamical-system learning has a non-convex likelihood objective despite its connection to linearized recurrent models. This paper uses stochastic gradient descent to learn unknown systems from noisy observations and establishes efficient convergence under stated assumptions.

  • Problem

    Linear systems offer a tractable recurrent-model special case, but their natural training objective remains non-convex.

  • Method

    The paper applies projected stochastic gradient descent and analyzes the objective through Fourier-domain transfer-function risk.

  • Results

    Gradient descent efficiently minimizes the maximum likelihood objective of an unknown linear system from noisy observations generated by that system.

  • Takeaways & Limitations

    The work provides a gradient-based route to learning linear dynamical systems despite non-convexity, under controllability and stability assumptions.

  • Takeaways & Limitations

    The analysis focuses on controllable, externally stable systems with bounded transformation norms and primarily studies single-input single-output systems.

Abstract

from arXiv · show

We prove that stochastic gradient descent efficiently converges to the global optimizer of the maximum likelihood objective of an unknown linear time-invariant dynamical system from a sequence of noisy observations generated by the system. Even though the objective function is non-convex, we provide polynomial running time and sample complexity bounds under strong but natural assumptions. Linear systems identification has been studied for many decades, yet, to the best of our knowledge, these are the first polynomial guarantees for the problem we consider.

1. Introduction

The paper studies learning unknown linear dynamical systems with stochastic gradient descent despite a non-convex maximum-likelihood objective. Under structural assumptions, it establishes polynomial-time and polynomial-sample guarantees, including benefits from over-parameterization.

  • Motivation: Linear dynamical systems provide a tractable special case for understanding gradient descent on non-convex recurrent sequence models.Their training objective remains non-convex because multiple linear operators are composed over time.
  • Main result: The paper proves that gradient descent efficiently minimizes the maximum likelihood objective for an unknown linear system from noisy observations.The observations come from a time-invariant system with hidden states and i.i.d. output noise.
  • Assumptions: The analysis focuses on controllable, externally stable systems, with bounded B, C, and D norms and varying unknown initial states across sequences.External stability is characterized by spectral radius ρ(A) strictly below 1.
  • Proper learning: Under the polynomial-based assumption, the transition parameters form a convex set and the objective is weakly quasi-convex, enabling stochastic gradient descent to make progress.The same assumption also ensures spectral radius below 1 through Rouché’s theorem.
  • The power of over-parameterization: Over-parameterization can weaken the structural assumption by extending the transfer function with an approximate inverse polynomial of degree O(n).The resulting order is n′ = O(n), and the equivalent input-output system can make the optimization geometry favorable.
  • Extensions: The work extends beyond SISO systems to a broad family of MIMO systems by introducing a generalized controllable canonical form.General MIMO systems lack the canonical forms available for SISO systems.
  • Related work: Compared with prior non-asymptotic identification results, the paper provides polynomial sample-complexity bounds together with algorithmic guarantees for minimizing empirical risk.Earlier results cited in the paper had sample-complexity bounds exponential in system degree and related quantities.

2. Gradient descent and quasi-convexity

The paper analyzes projected stochastic gradient descent under weak quasi-convexity and weak smoothness, extending standard convergence reasoning beyond convex objectives. Its guarantees rely on unbiased gradient estimates with bounded variance and a feasible global optimum.

  • Gradient descent and quasi-convexity: Weak quasi-convexity requires the negative gradient to correlate positively with the direction toward a global optimum.The paper uses a condition weaker than standard quasi-convexity, defined relative to the optimum.
  • Gradient descent and quasi-convexity: Weak smoothness bounds the squared gradient norm by the objective gap to the global minimum.
  • Gradient descent and quasi-convexity: An unbiased stochastic gradient estimator has expectation equal to the true gradient and variance at most V.
  • Gradient descent and quasi-convexity: Projected stochastic gradient descent updates parameters using a learning rate and Euclidean projection onto a closed convex set.
  • Gradient descent and quasi-convexity: Under weak quasi-convexity, weak smoothness, bounded estimator variance, feasible optimum, and bounded initialization, projected descent achieves an expected-error guarantee after K iterations.
  • Gradient descent and quasi-convexity: The analysis tolerates gradient-estimator bias of order exp(-Ω(n)); for inverse-polynomial target error, its effect is negligible.

3. Population risk in frequency domain

The analysis replaces population risk with an idealized frequency-domain objective tied to transfer-function error. Under a suitable parameter neighborhood, this objective is weakly quasi-convex and weakly smooth, while controlling the approximation requires additional structure.

  • Population risk in frequency domain: The proof first approximates population risk by idealized risk and then establishes weak quasi-convexity conditions.
  • Population risk in frequency domain: Idealized risk depends on the learned system’s impulse response, equivalently its transfer function, and measures transfer-function discrepancy in the frequency domain.
  • Population risk in frequency domain: For stable learned denominators, idealized risk admits a Fourier-domain representation derived from the transfer function and Parseval’s theorem.
  • Population risk in frequency domain: If the true and learned denominator polynomials have angle less than π/2 on the unit circle, idealized risk is weakly quasi-convex over the corresponding domain.
  • Population risk in frequency domain: The idealized risk is Γ-weakly smooth with Γ = O(n^2/τ^4).
  • Population risk in frequency domain: For i.i.d. zero-mean, unit-variance inputs and errors, population risk has the stated decomposition, while higher-order contributions require additional structure.

4. Effective relaxations of spectral radius

The paper introduces acquiescent parameter sets as convex relaxations that control spectral radius while preserving useful system behavior. These sets support stability, monotonicity, bounded impulse responses, and efficient projected optimization.

  • Effective relaxations of spectral radius: The acquiescence condition places q’s image of the unit circle inside a cone whose real part exceeds the absolute imaginary part.
  • Effective relaxations of spectral radius: An α-acquiescent polynomial maps the circle |z| = α into the prescribed complex cone, and Bα collects its coefficient vectors.
  • Effective relaxations of spectral radius: If a ∈ Bα, the roots of p_a have magnitudes at most α, giving the companion matrix spectral radius ρ(A) < α.
  • Effective relaxations of spectral radius: Acquiescent coefficient sets are convex, and Bα ⊂ Bβ whenever 0 < α < β.
  • Effective relaxations of spectral radius: The resulting no-blow-up property provides well-behaved impulse responses for systems in Bα.
  • Effective relaxations of spectral radius: Projection onto Bα can be represented by a semidefinite program, but the algorithm requires such a projection at every iteration.

5. Learning acquiescent systems

The paper proves convergence of projected stochastic gradient descent for acquiescent linear systems despite unknown initial states and a non-convex objective. The analysis establishes weak quasi-convexity, constructs an unbiased gradient estimator, controls its variance, and yields polynomial guarantees.

  • Learning acquiescent systems: Projected stochastic gradient descent learns an acquiescent system from N sample sequences of length T under the theorem's assumptions.The projection set contains the true system, and the algorithm returns learned parameters with a population-risk guarantee.
  • Convergence and variance: The gradient estimator's variance scales as 1/T, allowing 1/N convergence rather than 1/√N convergence for sufficiently long sequences and relatively small N.The bound separates a smoothness term from a gradient-estimator variance term; the variance contribution supplies the improved long-sequence scaling.
  • Computational complexity: Each iteration computes gradients in O(Tn) arithmetic operations, while projection can be solved in O(n^3.5) time, giving polynomial computational complexity.The projection step may be unnecessary in practice and may be an artifact of the analysis.
  • Long sequences: Breaking length-T sequences into Θ(T/n) sequences of length Θ(n) balances estimator variance and yields the long-sequence corollary.The resulting accounting treats TN as the effective number of samples for the sequence-to-sequence model.
  • Proof strategy: The proof combines weak quasi-convexity and weak smoothness of the idealized risk with an unbiased gradient estimator and variance bounds.These are identified as the three main parts of the proof; the smoothness parameter satisfies Γ = O(n^2/τ^4) and the quasi-convexity parameter satisfies τ = Ω(τ0τ1/τ2).
  • Handling unknown initial states: Unknown initial states prevent directly using the empirical gradient, so the algorithm initializes simulations at zero and ignores the first T1 = T/4 outputs in its partial loss.Discarding an initial portion reduces the effect of the missing initial state and also supports learning when early outputs are unobserved.

6. The power of improper learning

Improper learning exploits redundant transfer-function representations to weaken the assumptions needed for efficient projected stochastic gradient descent. The paper applies this framework to passive systems and derives polynomial-time learning guarantees, while showing linear regression requires stronger conditions and retains approximation bias.

  • 6. The power of improper learning: Redundant representations preserve identical system behavior while changing optimization geometry, enabling learning without recovering the minimum representation.For G(z)=s(z)/p(z), multiplying numerator and denominator by a monic polynomial u(z) yields an equivalent representation with n+d model states.
  • 6. The power of improper learning: Definition 6.1 calls p(z) α-acquiescent by extension of degree d when some degree-d monic u(z) makes p(z)u(z) α-acquiescent.The algorithm needs only the existence of u(z), not knowledge of the helper polynomial itself.
  • 6. The power of improper learning: Theorem 6.2 shows projected stochastic gradient descent learns systems with α-acquiescent-by-extension denominators using m=n+d states under bounded H2 norm.The resulting risk bound has polynomial dependence on τ0, τ1, τ2, and 1/(1−α).
  • 6.2 Examples: For distinct roots inside radius α, the extension degree is O(max{(1−α)^−1 log(√nΓ·∥p∥H2),0}), and random-root systems achieve degree eO((1−α)^−1n).The random-root guarantee holds with high probability over the polynomial construction.
  • 6. The power of improper learning: Polynomial extension degrees suffice for several system classes, including passive systems, for which learning is possible with n+d=Oτ,α(n) states.The passive-system result assumes strictly interior numerator roots, bounded root-separation quantity Γ(s), and bounded denominator H2 norm.
  • 6.3 Improper learning using linear regression: Linear regression learns finite-history input-output mappings with polynomial sampling complexity but requires extremely-acquiescent extensions and has bias that decreases only with feature length ℓ.Increasing the number of samples alone does not eliminate this bias.

7. Learning multi-input multi-output (MIMO) systems

The paper extends its learning framework to a class of MIMO systems whose transfer-function entries share a common denominator. Using a Brunovsky normal-form state-space representation, projected stochastic gradient descent retains a risk guarantee when that denominator is acquiescent by extension.

  • 7. Learning MIMO systems: The MIMO class uses an ℓin×ℓout polynomial numerator matrix S(z) and a shared scalar denominator p(z).Each numerator entry has degree at most n, with ℓin and ℓout denoting input and output dimensions.
  • 7. Learning MIMO systems: The model is parameterized by denominator coefficients a1,…,an and numerator coefficients collected into matrices C and D.D contains leading numerator coefficients, while C contains the remaining coefficients.
  • 7. Learning MIMO systems: The MIMO risk function is τ-weakly-quasi-convex on the specified domain, extending the corresponding scalar-system geometry.The proof relies on the numerator and denominator being linear in the parameterization and the denominator being scalar.
  • 7. Learning MIMO systems: A Brunovsky normal-form state-space realization provides the representation used to learn these transfer functions from example sequences.The representation is uniquely associated with transfer functions of the stated form.
  • 7. Learning MIMO systems: If the common denominator is α-acquiescent by extension of degree d and ∥G∥H2≤1, projected stochastic gradient descent returns a system with the stated risk bound.The theorem is presented as an extension of the earlier scalar-system guarantees to the MIMO setting.

8. Simulations

Synthetic experiments examine instability and stabilization mechanisms for stochastic gradient descent on linear dynamical systems. Plain SGD often blows up, projection enables convergence, and gradient clipping gives the strongest reported empirical performance.

  • 8. Simulations: Plain SGD tends to blow up even with relatively small learning rates, especially on hard instances.The experiments identify instability as a practical concern rather than only a theoretical possibility.
  • 8. Simulations: Projected SGD converges with reasonably large learning rates, and over-parameterization produces competitive final error.This finding corroborates the paper’s theoretical study.
  • 8. Simulations: Gradient clipping has the strongest performance for both convergence speed and final error.The paper interprets reduced batch noise as a possible contributor to this empirical advantage.
  • 8. Simulations: The experiments use synthetic systems with state dimension d=20 and characteristic-polynomial roots inside radius ρ=0.95, excluding systems with unusually large impulse-response norms.Systems with heavy-tailed impulse-response norms were difficult to learn, so the experiments selected systems with reasonable norms.

Appendix A. Background on optimization

The appendix develops convergence analysis for projected stochastic sub-gradient descent on weakly-quasi-convex objectives. It combines weak quasi-convexity with projection geometry, expectation over stochasticity, and step-size choices to obtain the stated bound.

  • Appendix A. Background on optimization: Weak quasi-convexity ensures that points with vanishing gradient are optimal and provides the gradient-correlation condition used in the analysis.The appendix applies this condition as the first step of the projected sub-gradient argument.
  • Appendix A. Background on optimization: Projection onto the closed convex set preserves the comparison needed between the iterate and the target because the target lies inside the set.The proof uses the non-expansive projection inequality in its distance recursion.
  • Appendix A. Background on optimization: Taking expectations and summing over iterations converts the one-step inequality into the convergence bound.The analysis conditions on the current iterate before averaging over the remaining randomness.
  • Appendix A. Background on optimization: The step size is selected according to the iteration count K and parameters R, Γ, and V to balance the terms in the bound.The proof assumes the initial distance satisfies ∥θ0−θ*∥≤R.
  • Appendix A. Background on optimization: For controllable canonical-form systems, the resolvent applied to the input vector is expressed through the inverse characteristic polynomial.The appendix derives this relation from the structure of I−wA and the characteristic polynomial pa.

C.1 Monotonicity of acquiescence: Proof of Lemma 4.3

The proof establishes that Bα is contained in Bβ whenever 0 < α < β. It uses the harmonic minimum principle to extend a boundary lower bound inward.

  • For 0 < α < β, Bα ⊂ Bβ.
  • Membership in Bα is characterized by qa(z) belonging to C for every z with |z| = 1/α.
  • The harmonic minimum principle carries the real-part lower bound from |z| = 1/α to the smaller-radius circle |z| = 1/β.

C.2 Proof of Lemma 5.4

The proof relates the expected partial empirical loss and its gradient to an idealized risk involving ˆA, ˆC, and ˆD. Stability and time truncation make the initial state negligible and the approximation error inverse exponentially small.

  • The proof controls the series tail using the no-blow-up property and shows that the incorrect initial state h0 does not disrupt the partial loss.
  • The expected partial empirical loss equals g(ˆA, ˆC) + (ˆD − D)^2 up to exp(−Ω((1 − α)T)).
  • After time T1 ≥ Ω(T), the initial-state contribution satisfies ∥CA^{t−1}h0∥ ≤ exp(−Ω((1 − α)T)).
  • The gradient of the expected partial loss is likewise within inverse exponentially small error of the gradient of g(ˆA, ˆC) + (ˆD − D)^2.

C.3 Proof of Lemma 5.5

The proof bounds the variance of the back-propagation gradient estimates by expanding them as quadratic forms and controlling their terms across several temporal-index cases. Independence, moment bounds, tail estimates, and Cauchy–Schwarz inequalities provide the needed concentration ingredients.

  • GA and GC are expressed as quadratic forms in the observations x1, …, xT and noises ξ1, …, ξT.
  • The coefficients are bounded using tail estimates for ∥zk∥ and the relation |ˆrk| ≤ ∥zk∥, with separate refinements when temporal gaps exceed Λ.
  • The analysis assumes independent mean-zero observations with unit variance and bounded fourth moments, together with independent mean-zero noises of variance σ2.
  • Independence and vanishing odd moments simplify the variance calculations, and the same strategy yields the corresponding bound for GC.

D.2 Proof of Theorem 6.9

The proof of Theorem 6.9 combines two polynomial-extension lemmas: one extends a denominator under root and transfer-function assumptions, and the other preserves membership in the relevant complex-value class.

  • Together, Lemmas D.3 and D.4 provide the two extension steps used to prove Theorem 6.9.
  • Lemma D.3 assumes the roots of s lie inside radius α < 1 and that G(z) = s(z)/p(z) belongs to Cτ0,τ1,τ2 or C+ on the unit circle.
  • Under those assumptions, Lemma D.3 constructs a polynomial u(z) of degree d = Oτ(…), with the transformed denominator retaining controlled class parameters.
  • Lemma D.4 starts from a monic degree-n polynomial p(z) in C+ on the unit circle and constructs u(z) so that p(z)u(z)/z^(n+d) belongs to Cτ′0,τ′1,τ′2.
  • The proof of Lemma D.4 uses a square-root representation, Taylor-series truncation, and multiplication by a power of z to obtain a polynomial.

Appendix E. Back-propagation implementation

The appendix describes back-propagation for computing gradients and a projected update for linear dynamical-system parameters. It also develops a grid-based approximation to the projection set, preserving the conditions needed for convergence.

  • Back-propagation implementation: Back-propagation computes hidden states, prediction errors, parameter gradients, and gradient updates for A, C, and D.The procedure runs forward through each sample, propagates errors backward, accumulates gradients, and applies learning-rate updates.
  • Back-propagation implementation: The algorithm projects the parameterization after each gradient update onto a constrained set based on the vector representation of A.The projection obtains a from A, applies Π_B, and reconstructs A through MCC(a).
  • Projection-set approximation: A grid GM of size M over the radius-α circle approximates the projection set, with M = Oτ(n) sufficient for convergence.The approximation uses polynomial constraints and can be solved by linear programming; the grid also forms a Fourier basis that may permit FFT acceleration.
  • Projection-set approximation: The algorithm chooses relaxed thresholds τ′0 = τ0/2, τ′1 = τ1/2, and τ′2 = 2τ2 for the approximating projection set.The construction is intended to keep iterates within the relaxed set so that the objective’s quasi-convexity continues to hold.
  • Projection-set approximation: Bernstein-based polynomial bounds show that controlling the polynomial on a sufficiently fine grid controls it around the entire circle.For m ≥ 20n, Lemma F.4 bounds the difference between values at any point on the circle and a nearby grid point by O(nατ/m).
Loading 1609.05191v2…