arXiv preprint ·
Learning Graded Sparse Mechanisms: A Representation Theorem and Certified Generalization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
Dream2Discern: Learning from Hard Latent Variants for Runtime Failure Prediction in Multi-Agent Systems
Collective Benefits and Efficiency in Coupled Echo State Networks
GUIDE: Computationally Augmented Consensus for Trustworthy Clinical Practice Guidelines
Mobility-Budget-Constrained Submodular Maximization for Distributed Semantic Multi-Robot Exploration
Beyond Perfect Teammates: Multi-Agent Collaboration with Unreliable Colleagues
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.