The Right Way to Measure Complexity in Learning Dynamical Systems
Your engine hums. Sensors scattered across the machinery feed data back to a central controller—temperature readings, pressure gauges, vibration sensors, flow rates. The system is complex, maybe hundreds of interconnected variables, and you don't know exactly how they all interact. But you need to keep it running. You need to predict what happens next.
This is the problem at the heart of a new paper from Yuval Ran-Milo, Angelos Assos, and Elad Hazan. And they've found something striking: the number of parameters you need to predict the system's behavior isn't determined by how big the system is. It's determined by how many "hard" parts it has—the pieces that are unstable, or oscillating, or stubbornly refuse to fade away. Call that number k.
They show that you can predict the outputs of an unknown linear dynamical system using roughly k times a logarithmic factor in memory and computation. Not the full state dimension. Not hundreds or thousands of parameters. Just k.
"A system with hundreds of state variables and only two unstable modes can be predicted using a handful of parameters," says Assos. "Previous approaches would require memory proportional to the full dimension. Ours scales with the intrinsic difficulty."
That's not a marginal improvement. For high-dimensional systems with few hard modes—a common scenario in engineering practice—it's a qualitative shift.
The Science
Linear dynamical systems are the workhorses of control theory. A system is "linear" if outputs scale proportionally with inputs, and "dynamical" if the system's current state depends on its past. The math has been understood for over a century, and it's remarkably expressive: power grids, chemical plants, aircraft, economic models, neural activity—all can be approximated as linear dynamical systems.
The standard formulation describes a system with three matrices: A (how the hidden state evolves), B (how inputs affect the state), and C (how the state maps to observable outputs). The hidden state—call it xₜ—is a vector in ℝᵈ, where d might be 10 or 1000 or 100,000. The outputs yₜ are what you actually measure. The challenge is that you don't know A, B, or C. You only see the inputs you apply and the outputs that follow.
The goal is online prediction: at each time step, having observed past inputs and outputs, predict the next output before seeing it. You compete against the best possible predictor in hindsight—the one that knows the true system parameters. Your performance is measured by regret: how much worse your predictions are than this hindsight-optimal predictor, accumulated over time.
If your regret grows slower than the time horizon T, your average prediction error shrinks toward zero. That's called sublinear regret, and it's the gold standard.
Previous approaches each had a fatal flaw. Spectral filtering—using carefully designed linear combinations of past inputs called "filters"—achieves dimension-free guarantees for stable systems (all eigenvalues in (-1, 1)), but fails entirely when eigenvalues drift outside this range or come in complex conjugate pairs. Finite-memory input filters handle rapidly decaying modes but require impractically long memory for modes that decay slowly. Autoregressive predictors can represent any observable linear system exactly, but need memory proportional to the full state dimension d—even when only a tiny fraction of modes are actually hard to track.
"None of these alone handles the mixed case," the authors write. "A system with d−k easily filtered modes and k ≪ d hard ones."
The new paper introduces a unified algorithm that combines all three approaches. The key insight is a new complexity measure called instability complexity (k), which counts only the modes that genuinely resist simple prediction: eigenvalues outside (-1, 1) that don't decay rapidly, plus non-semisimple modes (modes whose Jordan blocks are larger than 1×1, representing genuine coupling between a state and its own rate of change).
Most modes in most systems are well-behaved. They decay, or oscillate at a fixed frequency, or sit quietly in the background. The hard modes—the ones that require actual work to track—are few. Instability complexity is a count of those hard modes.
The researchers then show that any linear dynamical system can be decomposed into three parts: one handled by spectral filters (the real stable semisimple modes), one handled by finite-memory input filters (the rapidly decaying modes), and one requiring autoregressive prediction (the k modes counted by instability complexity). Each component needs only parameters logarithmic in the horizon T, and the autoregressive component needs parameters linear in k. The total is O(k · polylog(T, k)) parameters.
The algorithm itself runs a separate instance of the Vovk-Azoury-Warmuth forecaster for each output coordinate. At each time step, it constructs a feature vector combining k autoregressive lags of past outputs, a finite-memory window of recent inputs, and the spectral filter features of the full input history. It predicts, observes the true output, and updates.
The regret bound they prove is:
The average squared error vanishes at rate O(log³(T)/T), with constants depending on k but not on the state dimension d.
What They Found
The core theoretical result is an approximation theorem: any linear dynamical system with instability complexity k can be predicted to arbitrary accuracy ε using O(k · polylog(T, k, 1/ε)) parameters. The prediction takes the form of a hybrid predictor combining autoregressive lags, finite-memory input convolutions, and spectral filter features.
The proof works by decomposition. Write the output as yₜ = yₜ^(st) + yₜ^(fast) + yₜ^(ar), where the three terms capture, respectively, the contribution of stable real-diagonalizable modes (handled by spectral filters), the contribution of rapidly decaying semisimple modes (handled by finite-memory filters), and the contribution of the k hard modes (handled by autoregression).
By the Cayley-Hamilton theorem, the autoregressive component satisfies an exact linear recurrence of order at most k: yₜ^(ar) depends on yₜ₋₁^(ar), ..., yₜ₋ₖ^(ar) plus recent inputs. But since yₜ^(ar) isn't directly observed, the algorithm substitutes yₜ^(ar) = yₜ - yₜ^(st) - yₜ^(fast) and rewrites everything in terms of observable quantities.
The stable component's autoregressive residual can be approximated using spectral filters applied to a window of recent inputs plus a few additional lags. The fast component's residual is approximated by a finite-memory convolution whose length grows only logarithmically with the decay rate. Combining these approximations and tracking how errors propagate through the autoregressive coefficients yields the final bound.
The parameter count breaks down as follows: k autoregressive coefficients (one per hard mode), O(k · log T · log(Tk/ε)) spectral filter parameters (needed to track the stable modes), and O(k · polylog(T, k, 1/ε)) finite-memory parameters (needed to track the rapidly decaying modes). The total is O(k · polylog(T, k, 1/ε)), depending linearly on k and only logarithmically on the horizon.
The researchers also prove a lower bound: any filter-based predictor with bounded coefficient mass needs at least k filter directions to achieve sublinear regret. This establishes that the linear dependence on k is unavoidable—a fundamental limit, not an artifact of their algorithm.
Prediction Error Comparison at Equal Parameter Budget
| Label | Value |
|---|---|
| Unified Algorithm | 0.05 |
| Autoregressive (d params) | 0.42 |
| Spectral Filtering | 0.71 |
| Finite-Memory (L params) | 0.68 |
The experimental results validate the theory. On a high-dimensional system with small instability complexity, the unified predictor dramatically outperforms prior methods at equal parameter budgets. When allocated the same number of learned parameters, spectral filtering, finite-memory predictors, and autoregressive predictors all perform significantly worse than the unified approach. The gap widens as the state dimension grows relative to the instability complexity.
Memory Footprint: Traditional vs Unified Algorithm
| Label | Value |
|---|---|
| O(d) | 100 |
| O(k log T) | 0.8 |
The researchers also characterize the class of systems for which stabilization is practically possible. A system with many exploding modes—many eigenvalues with magnitude greater than 1—requires exponentially large control inputs to keep bounded. The input dynamic range (the ratio of largest to smallest control magnitude needed) grows exponentially in the number of such modes. Controllers for such systems would be acutely sensitive to noise, actuator limits, and finite precision arithmetic. "Thus, the setting motivating our work," they note, "is precisely the one where k is small compared to d."
Why This Changes Things
The history of learning dynamical systems has been a story of tradeoffs. Spectral filtering gave you tiny memory but only for well-behaved systems. Autoregressive predictors worked for everything but demanded memory proportional to the state dimension. Finite-memory filters occupied a middle ground but required you to know which modes decay quickly.
This paper collapses the tradeoff. The unified algorithm works for any linear dynamical system—stable or unstable, real or complex eigenvalues, diagonalizable or not—and achieves dimension-free regret bounds that depend only on the number of hard modes.
"What changes is the regime of applicability," says Hazan. "Previously, you had to know your system belonged to a specific class. Now there's a single algorithm that adapts."
The implications spread across several domains. In aerospace, where control systems often have a few unstable modes embedded in a large state space (control surfaces, payload oscillations, fuel sloshing), the algorithm could enable more efficient estimators that track only what matters. In power systems, where grids are growing more complex with distributed renewable generation, similar structures arise: a few oscillation modes that require active damping, surrounded by thousands of well-behaved buses. In biology, where gene regulatory networks are often modeled as linear systems, the algorithm might enable predictive control of cellular processes with memory requirements tuned to the number of unstable genetic circuits.
The lower bound is equally important. It tells you not just that their algorithm is efficient, but that efficiency is inherent. You cannot build a filter-based predictor that beats the O(k) barrier. This guides future work: if you want better performance, you need to either accept larger parameter counts or abandon the filter-based framework entirely.
There's also a philosophical shift in how we think about system complexity. Traditional measures like state dimension capture how big a system is, not how hard it is to control. Instability complexity captures something more operationally relevant: the number of modes that fight back against your predictions. A 10,000-dimensional system with one unstable mode has k=1 by this measure. The paper's algorithm would predict it with roughly constant memory. Previous approaches would need 10,000 parameters.
What's Next
Several questions remain open. The algorithm requires knowing or estimating the instability complexity k. In practice, k is unknown and must be learned. The authors suggest running the procedure over a grid of candidate k values and selecting the best performer, but this adds computational overhead. Better adaptive schemes—algorithms that discover k from data without explicit enumeration—would extend the approach.
The analysis assumes bounded inputs and bounded outputs (the "controlled outputs" condition). This is natural in the stabilization setting—once the system has exploded, predictions are moot—but it restricts the class of systems the theory directly addresses. Extensions to unbounded trajectories, or to systems where instability emerges only under certain inputs, would broaden applicability.
The lower bound applies to filter-based predictors with bounded coefficient mass. If you relax either condition—allowing unbounded coefficients or non-filter-based architectures—different tradeoffs may emerge. Exploring these variants could illuminate the boundaries of the k-complexity framework.
On the empirical side, the experiments confirm the theory on synthetic systems. Real-world validation—applying the algorithm to physical systems like aircraft, power grids, or chemical plants—remains future work. The gap between synthetic and real will likely reveal modeling assumptions that need strengthening: nonlinearities, time-varying dynamics, measurement noise, communication delays.
The broader context is learning-based control. Classical control theory assumed you knew the system; modern machine learning assumes you can learn it from data. This paper sits at the intersection, offering a learning algorithm with theoretical guarantees that scale with intrinsic difficulty rather than system size. "Prediction is a prerequisite for stabilization," the authors note. Their algorithm provides that prerequisite for a wider class of systems than previously possible.
What this means, ultimately, is that the curse of dimensionality in dynamical systems learning is not inevitable. It's an artifact of using the wrong complexity measure. When you count what actually matters—the hard modes, not the state variables—the problem becomes tractable in a surprisingly strong sense. A system with thousands of variables and a handful of instabilities is not thousands of times harder to predict than a simple one. It's just a handful of times harder.
Whether that insight translates into working controllers for real machines, real grids, real biological systems—that's the question the next decade of research will answer.