CS Paper Radar

Learning Graded Sparse Mechanisms: A Representation Theorem and Certified Generalization

Mark Kozdoba, Shie Mannor

cs.LG cs.MAstat.ML ·submitted 2026-10-12 10:24 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Networks for Agentic Information Aggregation

cs.LG cs.GTecon.TH ·2026-09-28 ·MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Shayan Taherijam
similarity 0.60
Abstract

We study information aggregation in the networked learning model introduced by Kearns, Roth, and Ryu (SODA 2026). There is a fixed distribution over $d$ features and a common label. Agents learn in topological order on a directed acyclic graph. Each observes a subset of the features and its parents' predictions, fits a linear predictor to minimize mean squared error, and passes only its prediction forward. The global predictor is the best linear predictor using all features. Kearns, Roth, and Ryu show that the output agent's error approaches the global predictor's error along sufficiently deep paths with suitable feature coverage, while insufficient depth can prevent aggregation even in large networks. In contrast to their main focus on a given graph and feature allocation, we consider the limits of the model under two settings. In the adaptive designer setting, a designer chooses the graph, feature allocation, and output agent knowing the distribution. In the oblivious designer setting, the designer fixes all three before an adversary chooses the distribution. Each agent observes one feature and receives predictions from a limited number of parents. We call the aggregation exact when the output agent matches the global predictor exactly. For $d\ge3$, we show that no finite depth guarantees exact aggregation for every distribution with one parent per agent, even when the designer knows the distribution. In contrast, two parents per agent suffice for exact aggregation even in the oblivious designer setting. A fixed graph, feature allocation, and output agent achieve this for every distribution at depth $O(d\log d)$. Knowing the distribution reduces the depth to $O(d)$. Both constructions use $O(d^2)$ agents, with a very large constant for two parents. We show the bounds on the depth and number of agents are all optimal up to constant factors.

0.36

Finite-Sample and Communication-Efficient Networked Information Aggregation

cs.LG cs.AIcs.GT ·2026-11-08 ·Mohammadhossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Shayan Taherijam
top venue similarity 0.59
Abstract · Accepted at the 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

Building on SODA 2026 work Kearns et al. (2026), we study learning in directed acyclic graphs in which each agent observes only a subset of the input coordinates and may use the predictions of its parents as additional features. In the finite-sample protocol, the message sent along each edge is the agent's prediction vector on a shared sample, so the communication cost is linear in the sample size $m$. In this paper we study this model under communication constraints. First, we revisit the finite-sample analysis of the full-message protocol. We identify a gap in the finite-sample proof of Kearns et al. (2026) and develop a different argument that establishes a finite-sample population-risk guarantee along paths satisfying deterministic $M$-coverage. Second, we introduce a shared-sketch protocol in which each agent sends a $k$-dimensional linear sketch of its prediction vector instead of the full $m$-dimensional message, where $k\ll m$. We analyze this protocol through a reduction to least squares on the compressed sample together with an oblivious subspace embedding argument. The resulting bound separates statistics from communication: the statistical term is still governed by the original sample size $m$, while the additional error due to compression is controlled by the sketch dimension $k$. For Gaussian sketches, we obtain an explicit high-probability population-risk bound, showing that row subsampling is not the only possible communication-statistics tradeoff for networked information aggregation.

0.42

Best of Both Worlds in Federated LSA: Speedup When Possible, Personalization Always

cs.LG ·2026-10-08 ·Safwan Labbi, Paul Mangold, Eric Moulines
theory similarity 0.56
Abstract

We study personalized federated linear stochastic approximation (LSA), a framework which notably encompass personalized temporal difference learning. In this setting, heterogeneous agents collaborate to solve distinct linear fixed-point equations, each corresponding to an agent-specific learning problem. A central open question in personalized learning is whether a single method can adapt to an unknown level of heterogeneity by converging to each agent's personalized solution in all regimes while achieving a linear speedup in the number of agents when their learning problems are sufficiently similar. We answer this question affirmatively by introducing PF-LSA, a minimalist algorithm that mixes each agent's local stochastic update with the average update across agents, at no additional computational cost relative to standard federated methods. We prove that PF-LSA, achieves best-of-both-worlds guarantees without any prior knowledge on the level of heterogeneity. Our analysis is based on a sharp decomposition of the error into consensus and disagreement components. The consensus error decays rapidly, whereas the disagreement error decays more slowly but becomes negligible in low-heterogeneity regimes.

0.24

A Large-Dimensional Analysis of Least-Squares Federated Learning via Generalized Total Variation Minimization

cs.LG stat.ML ·2026-10-14 ·Ekkehard Schnoor, Malik Tiomoko, Alexander Jung
similarity 0.56
Abstract · 21 pages, 9 figures

Federated learning over decentralized networks inherently trades off the suppression of local finite-sample noise through collaboration against the bias that collaboration introduces between heterogeneous nodes. We study this tension by performing a large-dimensional analysis of Generalized Total Variation Minimization with least-squares models. Using tools from random matrix theory, we show that Lipschitz observations of the global GTVMin solution concentrate in large dimensions, universally for any underlying network structure. We provide exact analytic expressions for the asymptotically precise performance under both i.i.d. and non-i.i.d. Gaussian mixture distributions on a fixed network. For the latter, these expressions quantify how regularization balances local adaptation against collaboration. Our theoretical results are confirmed by experiments on synthetic and real-world data.

0.25

Graphon Design for Human-Machine Coordination under Bounded Rationality: Optimality of Stochastic Block Models

eess.SY cs.GT ·2026-08-28 ·Zhewei Wang, Vu Anh Phi, Marcos M. Vasconcelos
published similarity 0.55
Abstract · Accepted for presentation at the IEEE Conference on Decision and Control 2026

Coordination is a desirable feature in multi-agent systems, ranging from robotic swarms to socioeconomic networks. This paper is concerned with promoting coordination among heterogeneous agents, e.g., machines and humans, interacting in a stag-hunt game. In our model the agents exhibit bounded rationality at different levels, which leads to uncertainty and a propensity for errors during learning and decision-making processes. This paper addresses the problem of designing a network topology that maximizes a global metric of coordination under such constraints. While optimizing over the discrete space of finite graphs is generally computationally intractable, we employ a mean-field approach to lift the problem into the space of graphons. Within this framework, we analyze agents following a logit learning dynamics. Using calculus of variations, we show that for systems with a bimodal rationality profile, it suffices to search for optimal graphons in the ensemble of stochastic block models. We then propose a water-filling algorithm to find a locally optimal graphon. Finite graphs can then be sampled from the optimized graphon, bypassing the inherent combinatorial complexities of discrete graph optimization.

0.26

Euclidean Crowding-Driven Adaptive Euclidean-Hyperbolic Graph Learning

cs.LG ·2026-10-27 ·Hao Chen, Jian Sun, Chuan Shi, Hongying Zhang
benchmark similarity 0.55
Abstract

Hyperbolic graph representation learning has emerged as a powerful paradigm for modeling hierarchical data. Unlike Euclidean space, which exhibits polynomial volume growth, hyperbolic space grows exponentially with radius, naturally accommodating tree-like structures without the geometric distortion known as Euclidean crowding. Despite strong empirical performance, the theoretical mechanisms underlying hyperbolic embeddings remain poorly understood. In this work, we provide a geometric quantifcation research for Euclidean crowding, a generalization-theoretic explanation for the superiority of hyperbolic space on hierarchical data, and further develop an adaptive Euclidean-hyperbolic fusion learning framework toward bridging this gap. Specifically, we \textbf{first} establish a geometric quantification of Euclidean crowding by analyzing layer-wise minimum separation in node embeddings, proving that fixed-dimensional Euclidean embeddings of tree-like graphs inevitably exhibit layer-wise crowding that leads to weaker margin-based generalization bounds. \textbf{Second}, we provide a generalization-bound for the superiority of hyperbolic geometry on hierarchical data. \textbf{Third}, we propose EH-Fusion, a geometry-adaptive framework that lifts Euclidean GNN representations into hyperbolic space via exponential mapping and adaptively fuses both geometries based on node-level neighborhood expansion patterns. Extensive experiments validate our theoretical insights and demonstrate the effectiveness of EH-Fusion on benchmark datasets.

0.21

Test-Time Collaborative Classification over Multi-Agent Networks

cs.MA ·2026-08-25 ·Ping Hu, Mert Kayaalp, Ali H. Sayed
similarity 0.54
Abstract

The increasing heterogeneity of multi-agent systems poses significant challenges for jointly training a global model across agents. At the same time, cooperative inference between agents has long been recognized as a powerful mechanism for distributed decision making over networks. Motivated by these observations, we propose a collaboration framework for distributed binary classification over multi-agent networks, where a set of independently trained agents, potentially differing in architecture, feature space, or modality, coordinate their actions during test time to form collective predictions. This coordination is achieved by exchanging local decision statistics through a distributed learning protocol. We develop a theoretical and experimental study of this independent training and cooperative inference paradigm, and examine its performance under different communication budgets and distributed learning rules. We establish classification error guarantees under sufficient, finite-round, and finite-precision communication, together with PAC-style generalization bounds. These results capture the influence of model heterogeneity, network topology, combination policy, and communication constraints on prediction accuracy. Taken together with the experimental results, they reveal both the price of independent training and the benefit of collective prediction for the proposed distributed decision making framework with models learned from data.

0.30

Towards Scaling Reinforcement Learning to Massive Populations: Learning Mean-Field Representations

cs.MA cs.LGstat.ML ·2026-08-26 ·Aditya Makkar, Benjamin Unger, Jeongyeol Kwon, Mathieu Laurière, Eugene Vinitsky +1 more
similarity 0.54
Abstract · 33 pages, 3 figures

Modern multi-agent systems are increasingly deployed at scale over large populations of agents in settings such as ad-auctions, traffic routing, and recommendation systems. The dominant approach in such settings is to optimize each agent's policy independently, treating the other agents as part of a fixed single-agent environment rather than modeling the population dynamics. In many large-population systems, the dynamics depend on an aggregate summary of the population rather than the identity of any individual. Mean-field RL exploits such structure, providing a principled framework that models each agent's environment as an explicit function of the population distribution. However, in large state-action spaces or high-dimensional control problems, modeling the population distribution is itself intractable. How can we design a scalable framework for high-dimensional control problems with large populations? This work explores this question from the perspective of representation learning. We introduce a mean-field RL framework in which the rewards and transition dynamics depend on the population only through an unknown low-dimensional aggregate statistic. We then study this framework in the offline setting and design a provable approach that learns a near-optimal policy by learning a low-dimensional representation. Motivated by real-life supply-chain optimization problems, we design a one-step routing game to test the hypothesis that learning a low-dimensional population representation improves reward prediction and Nash gap estimation relative to baselines that don't exploit this structure. We show that under a fixed neural-network parameter count and optimization budget, learning a low-dimensional population representation improves reward prediction and the equilibrium quality of the resulting policies.

0.19