Shrinking Parameter Sets as Rate Certificates for Adaptive Control over Zero-Error Networks

An unstable physical system controlled over a digital link needs a minimum bit rate. Roughly, the link must carry information as fast as the system's instability creates uncertainty. For worst-case guarantees, the right measure of what a noisy link can carry is its zero-error capacity: the highest rate at which the receiver never misdecodes, not merely rarely. The existing theorems that pair this capacity with a system's instability, measured by its topological entropy (the sum of log-magnitudes of its unstable eigenvalues), assume two things. The system's dynamics are known exactly, and the network is either one link or a star with a central receiver. Real deployments such as vehicle platoons, sensor meshes, and building networks violate both assumptions. Their dynamics are only known to lie in some range, and the data must cross several hops of an irregular network.

This note proposes treating the parameter set used for projection as the object that sets how many bits are needed. In online learning, projection means clipping each new parameter estimate back into a bounded set of plausible values. In our scheme, each controller keeps a shrinking set of plant parameters that are still consistent with the data, and projects its running estimate into that set. The worst-case instability over the set then becomes a bit-rate requirement that both ends of the link can compute. As the set shrinks, the requirement falls, and capacity is freed on shared links of the network. This only works because zero-error links let the sensor and the remote controller keep bit-identical copies of the set and the estimate without any return channel. We aim to show that the smallest link capacity at which control succeeds tracks the true plant's entropy rather than the worst case over the prior set. We also aim to show that this holds on arbitrary multi-hop graphs, with a cut-based condition replacing the star-network condition.

Core Claim

Consider a linear plant with unknown matrix $A$ known only to lie in a compact convex prior set $\Theta_0$, with bounded disturbances. Its information must reach a remote controller across a graph whose edges are finite-state noisy channels. Each edge $e$ has a known zero-error capacity $C_0(e)$. Define the certified entropy at time $t$ as

$$\bar h_t = \max_{A' \in \Theta_t} \sum_i \max(0, \log|\lambda_i(A')|),$$

where $\Theta_t \subseteq \Theta_0$ is the set of parameter values consistent with all data decoded up to time $t$, and $\lambda_i(A')$ are the eigenvalues of $A'$.

The controller runs a projected least-mean-squares estimator, a simple online regression whose output is clipped into the set; here the estimate $\hat A_t$ is clipped into $\Theta_t$. It drives a zooming quantizer whose range is sized from $\bar h_t$ and the diameter of $\Theta_t$. The projection plays two roles. First, it keeps the model-mismatch term $(A-\hat A_t)x_t$ bounded by the diameter of $\Theta_t$ times the state bound, which keeps the quantizer range finite. Second, it keeps $\hat A_t$ inside the certificate, so the rate actually used is never below what the current set requires.

With $M$ such loops sharing the graph, our conjecture is that bounded stabilization of every loop is achievable whenever, eventually, every cut of the graph satisfies

$$\sum_{k \in \mathcal{F}(S)} \bar h_{k,t} < \sum_{e \in \partial S} C_0(e).$$

Here $S$ is any set of nodes, $\partial S$ is the set of edges leaving it, $\mathcal{F}(S)$ is the set of loops whose sensor is in $S$ and whose controller is outside, and $\bar h_{k,t}$ is loop $k$'s certified entropy. A separate transient budget must also cover the excess $\bar h_{k,t} - h(A_k)$ during learning, where $h(A_k)$ is loop $k$'s true entropy. The new content has two parts. One is the set-as-certificate mechanism, which gives a rate schedule that adapts to the true $A$ while keeping worst-case guarantees. The other is the replacement of the star-network capacity region with a time-varying cut condition on native, irregular graphs.

Relation to Prior Work

Three papers supply the information-theoretic base, and all three assume known, fixed dynamics.

We keep their quantizer and coding constructions. We add online learning, which turns the fixed $h_{lin}$ into the shrinking $\bar h_t$. We replace the star with arbitrary multi-hop graphs.

The projection literature supplies the estimator and constrains the design.

- Adaptive Economic Model Predictive Control uses projected least-mean-squares inside a fixed plausible set on a centralized building model with perfect measurements.

We differ from both by making the set shrink and by having the set's worst-case entropy decide communication. Their open problem matters here as a constraint. A misspecified projection set biases the estimate permanently, and in our setting it would also under-provision bits. Robustness to a misspecified $\Theta_0$ is therefore an explicit experiment.

Topology work motivates the graph-level question.

These results are why we test across graph families rather than on one stylized topology.

Research Program

The first piece is the single-link mechanism. The sensor sees $x_t$ exactly. The controller sees only decoded quantizer symbols. Because the link never misdecodes, the sensor can rerun the controller's set-membership update and projected estimator on the same decoded data. It therefore holds bit-identical copies of $\Theta_t$, $\hat A_t$ and the quantizer range without any return channel. This is the precise reason the zero-error constraint is load-bearing rather than decorative. We will prove that $\Theta_t$ stays consistent with the true $A$ and that $\bar h_t$ is non-increasing. We will also bound the transient: the number of extra bits spent before $\bar h_t$ gets within $\delta$ of $h(A)$, as a function of excitation and disturbance size. Sets will be kept tractable as polytopes or ellipsoid outer bounds. Computing $\bar h_t$ is a non-convex maximum of spectral radii over a set, so we will use vertex enumeration for small sets and certified upper bounds otherwise. Using an upper bound only over-provisions bits, so safety is preserved.

The second piece is the network. Relays forward bits only. Since forwarding over zero-error links is exact, synchronization survives any number of hops. At each re-planning epoch, the flows are assigned capacity by a multi-commodity flow linear program over the edge capacities $C_0(e)$, with demands $\bar h_{k,t}$ plus a transient margin. Capacity released by a loop whose set has shrunk is reassigned to loops still learning. A change of allocation must itself be announced without error. Because allocations are deterministic functions of synchronized sets, every node can compute the new allocation locally, and no announcement is needed.

We will prove that the cut condition is necessary, using the single-link converse applied across each cut. We will prove it is sufficient for unicast flows by routing. For coupled plants we only conjecture it, and test it empirically.

Baselines

The naive reference point is certainty-equivalent rate selection. The controller fits an unprojected least-mean-squares estimate and provisions bits from the entropy of the point estimate alone. Whenever the estimate understates the true instability, this under-provisions. We expect it to diverge in a measurable fraction of runs. It is run with the same channels, graphs, plants and estimator step size as our method.

The strongest classical competitor is robust worst-case provisioning. It applies the zero-error constructions of Zero-Error Feedback Capacity for Bounded Stabilization and Uniformly Bounded State Estimation Over Multiple Access Channels with $h_{lin}$ replaced by $\max_{\Theta_0} h$, with no learning. It is guaranteed safe whenever capacity suffices, so it is the method to beat. For it, the file reports only qualitative results: errors "remain bounded" inside the capacity region and "grow exponentially" outside it on the binary adder channel. No reported numerical result was found on Lacuna for its error bounds or rate thresholds. We will reimplement it on identical channels and graphs.

Beating it means stabilizing at link capacities strictly between $h(A)$ and $\max_{\Theta_0} h$, where robust provisioning cannot operate. A second test is whether freed capacity lets more loops share a fixed graph. If capacity exceeds the worst case, robust provisioning should match us. Reporting that tie honestly delimits where the proposal helps.

The Shannon-style competitor pairs unbiased dithered quantization in the style of Q-GADMM with ordinary error-correcting codes of small error probability on each link. It is given the same learning and projection, so the only difference is the error model. That paper reports 90% MNIST accuracy at 8 bits per parameter, but that is a learning benchmark, and no reported result was found on Lacuna for it in control loops.

The topology baseline overlays a GADMM-style logical chain and routes along it, instead of solving the flow program on the native graph.

Three ablations isolate the ingredients:

  • shrinking sets with the projection removed, so the point estimate may leave the set;
  • projection onto a fixed $\Theta_0$ without shrinking;
  • shrinking sets with static rather than re-planned routing.

All methods get the same estimator hyperparameter search budget, the same horizons, and the same 50 disturbance seeds per configuration.

Why not just…?

Why not just provision for the worst case and skip learning? This is the real competitor, and when capacity is plentiful it wins on simplicity. The proposal matters only when link capacity lies below $\max_{\Theta_0} h$, which is common when the prior set is wide. The capacity sweep below locates exactly where the two methods separate. If the gap is negligible for realistic prior sets, we will report that the mechanism has limited practical value.

Why not just use strong error-correcting codes with tiny error probability? Bounded Estimation Over Finite-State Channels and the binary adder channel results in Uniformly Bounded State Estimation Over Multiple Access Channels show that average-error guarantees do not give uniform boundedness. In our scheme the failure is sharper. One misdecoded symbol desynchronizes the sensor's and controller's copies of $\Theta_t$, and every later quantizer range is wrong. We will measure the time to desynchronization and the divergence that follows, against code strength. The fair version of this alternative adds periodic resynchronization over a return channel, and we will include that variant too.

Why not just use variable-length feedback coding on each link? Error-Free Communication Over State-Dependent Channels with Variable-Length Feedback shows zero-error transmission can reach Shannon capacity on average with variable-length feedback. This is a genuine threat, because it raises every edge's usable rate. Its cost is unbounded worst-case delay. An unstable plant grows during each delay, so variable-length links can wreck worst-case boundedness. We will run it as a link-layer option inside our scheme, measuring peak state against delay. If it stabilizes reliably, it complements set certificates rather than replacing them, and we will say so.

Why not just use weight decay instead of projection? Regularization keeps estimates small but provides no set. Without a set there is no certified worst-case entropy and no bound on the mismatch term. The ablation without projection tests whether keeping the estimate inside $\Theta_t$ matters in practice.

Proposed Experiments

Channels are the (3,1) sliding-window erasure channel from Bounded Estimation Over Finite-State Channels, finite-state additive noise channels with zero-error capacity $C_0 = \log q - h_{ch}$, and the binary adder channel for shared edges. Plants are scalar and two-dimensional unstable systems with interval priors, plus the vehicle platooning benchmark of Towards safe control parameter tuning in distributed multi-agent systems. The platoon setting is 4 and 8 vehicles at a 100-meter reference gap, with unknown actuation lags, now over noisy links. That paper reports zero safety violations across 50 episodes with noiseless links. Matching that zero-violation record over zero-error links is our platoon target.

Graph families are paths, rings, two-dimensional grids, random geometric graphs and scale-free graphs with up to 64 nodes. These are the families on which the topology papers above report guarantees breaking. Metrics are:

  • fraction of seeds with bounded state over long horizons;
  • peak state norm;
  • the empirical capacity threshold, meaning the smallest uniform $C_0$ at which all seeds stay bounded;
  • total and peak bits;
  • the number of loops a fixed graph can support.

Three checks decide the claim. First, on single links, the empirical capacity threshold of our method should approach $h(A)$ as the horizon grows, while robust provisioning stays at $\max_{\Theta_0} h$. Second, the Shannon-style and certainty-equivalent baselines should fail at capacities where our method succeeds, with failures traceable to desynchronization and under-provisioning respectively. Third, across graph families, the boundary between success and failure should line up with the cut condition rather than with degree or spectral-gap statistics. The native-graph flow program should support more loops than the chain overlay on loopy and scale-free graphs.

If the third check fails for coupled plants, the cut condition is not sufficient there. That would be a useful negative result pointing to coordination effects like those in Empirical Coordination Over Triangular Networks.