Disintegration Theorem for Multifunctions, with Applications to Empirical Wasserstein Distances and Average-Case Statistical Bounds
2025 · Preprint · arXiv:2507.01236
Why do deep learning models perform well outside of their training sample? We lack a comprehensive theory of why this happens, or of how the implicit bias of training—the preference for some fitted functions over others—affects this performance. I take a geometric perspective on this problem, seeking to understand the geometry underlying data, dynamics and statistics.
Classical (uniform) generalisation bounds control performance over an entire model class, independently of the data population. Their dependence on the size of that class typically make the bounds worse as an architecture grows. In practice, however, larger architectures perform better, and the amount of data required to achieve a given test performance depends strongly on the population. The scaling experiments of Rosenfeld et al. and Bahri et al. illustrate this: out-of-sample performance improves at a faster rate as sample size is increased for simpler data populations, and scaling models larger also improves performance.
If classical bounds are worst-case in population but sensitive to architecture size, perhaps one should instead consider the opposite extreme: bounds which are worst-case in architecture size but sensitive to population. Let \((\mathfrak{X},d,\mu)\) be a compact metric probability space, let \(X_1,\ldots,X_n\) be i.i.d. observations from \(\mu\), and write \(\widehat\mu_n=n^{-1}\sum_{i=1}^n\delta_{X_i}\). For a function \(g\), the generalisation gap is the discrepancy between its population and sample averages; in a learning problem, \(g\) can be the loss of a fitted model on an observation. Kantorovich–Rubinstein duality gives
This can be viewed as a generalisation bound, bounding the gap between the empirical loss \(\frac{1}{n}\sum_{i=1}^ng(X_i)\) and the true population loss \(\int_{\mathfrak{X}}g\,d\mu\). The Wasserstein distance measures the discrepancy between the population and its empirical sample, while \(\|g\|_{\mathrm{Lip}}\) measures the function’s sensitivity to changes in its input. Importantly for generalisation theory, the inequality holds simultaneously for all Lipschitz functions, including functions chosen using the training sample. There is precedent for this approach in Buchanan, Gilboa and Wright’s work on separating curves with deep networks, and in Ma and Ying's work on the implicit regularisation of input-smoothness by SGD. The intuition that models which vary more smoothly in inputs generalise better also drove my prior work with Sameera Ramasinghe, Moshiur Farazi, Hemanth Saratchandran and Simon Lucey. The Kantorovich-Rubinstein bound makes this intuition rigorous.
There is an obvious problem with this perspective, however, namely the use of the global Lipschitz constant in the bound. Increasing a network’s fitting capacity can increase its steepest input variation even when its behaviour over most of the population remains well controlled. The below animation of a sine-activated network fitting a step function illustrates this: as the represented frequency increases, the global Lipschitz quantity grows, while the average local quantity is much less sensitive to the increasingly sharp transition.
My paper with James Allen Fill addresses this issue directly by replacing the global Lipschitz constant in the transport bound by an average of local Lipschitz constants. The idea which led me to this problem was geometric: could one construct a probability-theoretic partition of unity?
Suppose the population measure could be patched together from equal-mass pieces, each concentrated near a sample point. More precisely, given \(r>0\) and samples \(X_1,\dots,X_n\) from \(\mu\), suppose one had probability measures \((\mu_i)_{i=1}^n\) such that
where \(B(X_i,r)\) denotes the \(r\)-ball centred at \(X_i\). Such a family is a measure-theoretic analogue of a partition of unity, commonly used in differential geometry for patching locally defined data into a global object. Just like a partition of unity, such a family of measures also patches local geometric data into a global object, in this case the desired bound in terms of the average local Lipschitz constant.
Given a family \((\mu_i)_{i=1}^n\) satisfying \eqref{eq:partition}, one has
The right-hand side averages local Lipschitz constants \(\|g\|_{\mathrm{Lip},B_i}\) over the sample, instead of applying the single worst constant to the entire population; the radius \(r\) stands in for the Wasserstein distance seen in the Kantorovich-Rubinstein bound. The remaining question is geometric and probabilistic: is there \(r\equiv r(n)\rightarrow0\) such that families of this form can be found with increasing probability over independent samples \(X_1,\dots,X_n\) as \(n\rightarrow\infty\)?
It is first necessary to uncover the conditions for the existence of such a family of measures. It turns out that such families may be described as disintegrations along multi-valued functions. Classically, a measure \(\mu\) on a space \(\mathfrak{X}\) disintegrates along the fibres of a measurable map \(f:\mathfrak{X}\rightarrow\mathfrak{Y}\) according to the formula
The conditions \eqref{eq:partition} and \eqref{eq:disint} can be brought under a single concept by considering disintegrations along multi-valued functions. Specifically, in the setting of \eqref{eq:partition}, define the random multifunction \(F(x)=\{i:x\in B(X_i,r)\}\), with the uniform probability measure on the index set \(\{1,\ldots,n\}\). Its fibres are the random balls \(F^{-1}\{i\}=B(X_i,r)\), and the decomposition in \eqref{eq:partition} is exactly a disintegration along this multifunction. The first contribution of our paper is the provision of conditions of existence of such a disintegration in a fairly general setting; our proof combines Strassen’s coupling theorem with classical disintegration.
Let \(\mathfrak{X},\mathfrak{Y}\) be Polish spaces with Borel probability measures \(\mu,\nu\), and let \(F:\mathfrak{X}\to2^{\mathfrak{Y}}\) be a measurable multifunction with closed graph. Then \(\mu\) admits a disintegration along \(F\), i.e. a family of measures \((\mu_y)_{y\in\mathfrak{Y}}\) satisfying
if and only if \(\mu(F^{-1}U)\geq \nu (U)\) for every open \(U\subseteq\mathfrak{Y}\).
For the sample-centred balls of \eqref{eq:partition}, this says that the desired family of measures exists if and only if \(\mu\) assigns measure at least \(1/n\) to \(B(X_i,r)\). It may then be asked whether such a disintegration exists with probability \(\mathbb{P}(n)\to 1\) at radii \(r(n)\to0\) as \(n\rightarrow\infty\); if this is the case, we say that the the space \((\mathfrak{X},\mu,d)\) is asymptotically disintegrable. We give some strong counterexamples showing asymptotic disintegrability does not always hold, however we also demonstrate a number of examples for which asymptotic disintegrability does hold; for such spaces,
For any \(c>0\):
For 1-dimensional examples, our rate \(r(n)\) is thus the same as the rate of concentration of empirical measures around their mean in Wasserstein distance, so our average-case bound \eqref{eq:avgcase} gives a genuine improvement over the Kantorovich-Rubinstein bound for sufficiently spiky functions.
Applied to generalisation, the decay rates \(\tilde{O}(n^{-1/D})\) in sample size of our bounds are more pessimistic than the rates we measure in practice. On the other hand, the rates we see in practice are worse than the \(\tilde{O}(n^{-1/2})\) rates supplied by uniform generalisation theory. This suggests that a middle ground is desirable, one which which synthesises data structure, dynamics and architecture in a non-worst-case fashion. Contributing to the development of this middle ground is one of the goals of my research program.
2025 · Preprint · arXiv:2507.01236
2023 · ICML · PMLR 202, 28637–28655