Learning Graded Sparse Mechanisms: A Representation Theorem and Certified Generalization

In a variety of multi-agent and physical environments, an element's update depends strongly on a few other elements and weakly on many, and both the identity and the number of the elements that matter change with the state of the system. Such graded sparse mechanisms are common, for instance, in flocks, crowds, learned particle simulators and the neighborhood aggregation of graph networks, yet they have received little systematic study as a class of functions with the grading given. In this paper we study the supervised learning of the mechanism when the grading is provided by the environment, as a weight on every element. First, we define the class by axioms, where each element's influence is capped by its weight, the dependence on the weights is regular, and no element is distinguished, and prove a representation theorem: the class is exactly the Lipschitz ball of a transport metric on weighted multisets, and the metric is forced by the axioms. Next, the geometry of the representation gives generalization bounds that depend on the data in two ways. One is via the sparsity profile of the data—the law of how many elements matter and by how much—which bounds the rate over all designs with that profile, with an exponent from the profile and no dependence on the number of elements. In a number of natural cases we also show matching lower bounds, up to constants in the exponent. The other is empirical: due to the representation result, classical empirical discrepancy bounds apply to the class as they stand, and the resulting bound is the transport distance between the two halves of the sample in the class's own metric, computed exactly by a matching, with an additional concentration term. Finally, we study a simulated Vicsek flock under four interaction rules at two noise levels, and show that the certificate is non-vacuous, a small fraction of the trivial value on every rule.