Certified Capacity Search on Channels You Can Only Probe

Picture an engineer with a new optical link, a molecular signaling device, or a sensor with an unusual noise profile. She wants the best way to use it: which input levels to send, and how often, so that each transmission carries as many reliable bits as possible. That best rate is the channel's capacity. The input distribution that reaches it is often a small set of discrete levels rather than a smooth curve. Textbook algorithms find it only when the channel's noise law is written down exactly. Deep-learning methods such as CORTICAL find it from data, but they need thousands of gradient steps over large sample batches. Neither fits the common situation where each probe of the channel is slow or costly and the engineer gets perhaps a few dozen input settings. She also needs to know when to stop.

This note proposes a small-budget, adaptive search that treats the problem through its dual. The quantity it models is not "how good is this whole input distribution?", which is a jagged function whose optimum jumps between discrete and continuous shapes. It models "how much information would a single input level $x$ carry against the current output statistics?" That one-dimensional function is smooth for the channels in question, which suits a Gaussian-process surrogate. Its maximum also gives a certified upper bound on capacity. Each probe therefore improves the signaling scheme and tightens a stopping certificate at the same time. The central test is empirical: how many probes the certificate needs before it becomes non-vacuous, measured on channels whose true capacity is known.

Core Claim

Two standard facts bracket capacity $C$ for a channel $W$, which gives the probability of output $y$ given input $x$. For any input distribution $P$ and any output distribution $Q$,

$$I(P; W) \;\le\; C \;\le\; \max_{x \in \mathcal{X}} D\big(W(\cdot\mid x)\,\|\,Q\big),$$

where $I(P;W)$ is the mutual information achieved by $P$, $\mathcal{X}$ is the allowed input set (for example $[-A,A]$ under a peak constraint), and $D$ is the Kullback–Leibler divergence. The right-hand function of $x$ is the information density. At the optimum it equals $C$ exactly on the support points and lies below $C$ elsewhere. This is Smith's Karush–Kuhn–Tucker (KKT) characterization summarized in the file.

The claim has two parts. First, when the channel is a black box, you can place a probabilistic surrogate over the conditional output law as a function of $x$. You then choose probes with an upper-confidence rule on the information density evaluated against the current output mixture. This yields a two-sided, finite-budget interval on $C$ that narrows faster than grid probing or search over distribution parameters. Second, the discreteness of the optimal input causes no trouble in this formulation. The phase transitions studied for peak- and cost-constrained channels change which $x$ values touch the level $C$. They do not make the information density itself non-smooth.

The second point directly addresses the smooth-surrogate-versus-phase-transition mismatch that the file identifies as a gap. For the uniform-noise channel, Capacity-Achieving Input Distribution of the Additive Uniform Noise Channel With Peak Amplitude and Cost Constraint shows that the optimum jumps from discrete support to full support as the cost exponent crosses $\alpha = 1$. That discontinuity lives in $P$. In our formulation it shows up only as whether the information density touches $C$ at isolated points or along an interval.

The claim also respects the negative result that constrains this whole area. Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions proves that capacity is computable but the optimal distribution is not. It also shows that Blahut–Arimoto has no computable stopping rule for the distribution. Our certificate is a stopping rule for the rate, not for the distribution, so it is consistent with that result. We do not claim to recover $P^*$ to guaranteed accuracy. For finite alphabets with polyhedral constraints, The Mutual Information in the Vicinity of Capacity-Achieving Input Distributions proves that $I(p;W) \le C - \gamma\,\mathrm{dist}(p,\Pi)^2$. A rate gap $\varepsilon$ then implies a distance of at most $\sqrt{\varepsilon/\gamma}$ from the optimal set $\Pi$. However, the constant $\gamma$ depends on the channel and is not known in advance. We therefore treat distribution recovery as something to measure, not something to certify.

Research Program

The algorithm keeps four things. It keeps a set of probed input levels, each with a batch of observed outputs. It keeps a surrogate for $W(\cdot\mid x)$ over the continuous input range. It keeps a current finite-support input distribution $P_t$ and its output mixture $Q_t$.

We build two surrogate variants. The first is a Gaussian process over $x$ on the log-probabilities of binned outputs, used for counting channels such as Poisson. The second is a Gaussian process on output quantiles, used for continuous-noise channels such as AWGN and Cauchy. Posterior samples of the conditional law give posterior samples of the information density $x \mapsto D(W(\cdot\mid x)\|Q_t)$.

Each round has three steps. The algorithm first re-solves for $P_t$ on the probed levels, using Blahut–Arimoto on the estimated conditionals. This is cheap because it involves no channel uses. It then computes an upper confidence band on the information density over the whole interval. It probes the level where that band is highest. This is the analogue of GP-UCB from Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design. The difference is that the target function is re-anchored to $Q_t$ every round, and its maximum is itself the quantity being certified.

The lower end of the interval is a held-out estimate of $I(P_t;W)$: we transmit under $P_t$ and apply a plug-in estimate with a finite-sample confidence correction. The upper end is the band's maximum. The algorithm stops when the two meet within $\varepsilon$.

The constant-factor question sits in the band width. Gaussian Process Optimization in the Bandit Setting: No Regret and Experimental Design reports that its theoretical confidence multiplier $\beta_t$ was too conservative and had to be scaled down by hand. A certificate built on that $\beta_t$ would be valid but useless at small budgets. A hand-scaled one would be useful but uncertified.

We will derive a band from two pieces. One is a posterior-sampling or bootstrap maximum over the input interval. The other is an explicit finite-sample term for estimating each conditional law in KL. The rates in Nearly Minimax Discrete Distribution Estimation in Kullback-Leibler Divergence with High Probability give the right scaling, $(K + \ln K \ln(1/\delta))/n$ for $K$ output bins and $n$ samples, but leave the constants unoptimized. We will measure those constants empirically. The reported quantity is the ratio of certified gap width to true gap. This turns direction 2 into a measurable outcome: we report how far the certificate is from the truth, not only whether it holds.

Baselines

The naive reference points are fixed signaling schemes. We use equally spaced amplitude levels with uniform weights and, where the peak is small, on–off keying. For Poisson channels with $A + \lambda < e$, on–off keying is exactly optimal by Improved Bounds on the Number of Support Points of the Capacity-Achieving Input for Amplitude Constrained Poisson Channels, which gives a built-in sanity check. These baselines cost only the channel uses needed to evaluate them. Any adaptive method must beat them at small $A$ to justify its probes.

The strongest simple competitor is grid-probe-then-Blahut–Arimoto. It spreads the same budget of input levels and channel uses evenly over $[-A,A]$, estimates each conditional law, and solves on the grid. It gets the identical channel-use budget, the same output binning, and the same plug-in estimator as our method. The only difference is where probes go. Beating it means reaching a given true capacity gap, computed from the known simulator, with fewer channel uses. It also means producing a valid upper bound that grid-only methods cannot give, since they say nothing about inputs between grid points.

The strongest existing learned method is CORTICAL from Cooperative Channel Capacity Learning and Discriminative Mutual Information Estimators for Channel Capacity Learning. It trains a generator of inputs against a density-ratio discriminator. It is the only method in the file demonstrated on black-box channels, including the peak-constrained AWGN bifurcation, Cauchy noise, Rayleigh fading and MIMO. We will run it with its published architecture, capped at the same total channel uses and given the same hyperparameter-search budget.

We found no reported numeric result on Lacuna for CORTICAL's capacity gap at any channel-use budget. The file states only that it "converges to theoretical capacity" and reproduces the 2-to-3-point transition as $A^2$ grows. We will therefore produce CORTICAL's budget-versus-gap curve ourselves.

A third baseline is standard GP-UCB on the parameters of a $k$-point distribution (locations and weights), with $k$ tuned. This is the reviewer's natural Bayesian-optimization default.

Two ablations isolate the proposal's key ingredients. The first keeps our surrogate but probes on a uniform grid, which removes adaptivity. The second keeps adaptive probing but uses the theoretical $\beta_t$ in place of our calibrated band, which shows what the constant factor costs.

Why not just…?

Why not just probe a fine grid and run Blahut–Arimoto? This is the real threat. For small peak amplitudes it may match us, because the optimum has two or three points and a coarse grid already brackets them. The argument for adaptivity is that the number of support points grows with amplitude: at least order $\sqrt{A}$ and at most order $A$ for Poisson channels per Properties of the Support of the Capacity-Achieving Distribution of the Amplitude-Constrained Poisson Noise Channel and Improved Bounds on the Number of Support Points of the Capacity-Achieving Input for Amplitude Constrained Poisson Channels. A fixed grid must resolve all of these points uniformly, while an adaptive probe concentrates near the information-density peaks. The sweep over $A$ will show whether the advantage widens with $A$. If it does not, the contribution shrinks to the certificate alone. Grid methods cannot supply that certificate without a surrogate between grid points, and we will say so plainly.

Why not just train CORTICAL? Its design assumes abundant samples. It trains a neural encoder and discriminator by stochastic gradient descent over many iterations and large batches, and it provides no finite-sample interval on the rate. The matched-budget comparison will show where it stops being competitive. The honest outcome may be that it wins once budgets reach tens of thousands of channel uses. That would be a useful result that locates the crossover.

Why not just run off-the-shelf Bayesian optimization over the input distribution? The search space changes dimension with the unknown number of support points. Its landscape also has the discrete-to-continuous jumps shown in Capacity-Achieving Input Distribution of the Additive Uniform Noise Channel With Peak Amplitude and Cost Constraint, which stationary kernels model poorly. Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spaces documents a related failure: box-constrained search in high dimensions misses where the mass actually lies. The uniform-noise sweep across $\alpha$ near 1 is the experiment designed to expose this failure. Our method's surrogate stays one-dimensional, or low-dimensional for small MIMO, regardless of support size.

Proposed Experiments

All benchmark channels are simulators from the file with computable ground-truth capacity. They are the scalar peak-constrained AWGN channel, the amplitude-constrained Poisson channel with and without dark current, the uniform-noise channel with cost exponent swept through $\alpha = 1$, additive Cauchy noise, noncoherent Rayleigh fading, and a two-antenna MIMO channel. Ground truth comes from Blahut–Arimoto on a very fine grid of the known law, a computation hidden from every method under test.

We measure three quantities against total channel uses and against the number of distinct input levels, since each can be the costly resource. The first is the true capacity gap $C - I(P_t;W)$. The second is the certified interval width and its empirical coverage over repeated runs. The third is the ratio of certified width to true gap, which is the empirical constant factor. We also report how often the recovered support size matches ground truth. For Poisson channels we check it against the exact two-point result below $A + \lambda = e$ and the lower bound $\lceil e^{C}\rceil$.

Three checks decide the project. The first is coverage: the certified upper bound must sit above true capacity in at least the nominal fraction of runs, with the calibrated band, at budgets under a few hundred input levels. The theoretical-$\beta_t$ ablation should also show whether it is vacuous there. The second is the scaling of the advantage over grid-then-Blahut–Arimoto as $A$ grows on Poisson and AWGN. The third is behavior across the $\alpha = 1$ transition in the uniform-noise channel. There our method should track the capacity gap smoothly, while parametric Bayesian optimization should degrade.

As a secondary output, running the certified solver on Poisson channels at large $A$ produces empirical support-size curves. These address the unresolved question of whether support size grows like $\sqrt{A}$ or like $A$, a question the bounding papers leave open and test only with toy plots. If a low-cost optical intensity setup is available, the final experiment transfers the unchanged pipeline to measured data. Wall-clock time per probe will be reported, since no capacity-learning method in the file has been timed on real hardware.