Learning Graded Sparse Mechanisms: A Representation Theorem and Certified Generalization

Mark Kozdoba; Shie Mannor

cs.LGOct 12, 2026

Learning Graded Sparse Mechanisms: A Representation Theorem and Certified Generalization

Authors: Mark Kozdoba, Shie Mannor

Organizations: Technion, IIT · Technion, IIT and NVIDIA

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.

Figures & tables

Panel of Figure 1 — Figure 1: The flock at $\eta=1.2$ , $64{,}000$ independent replicas per flock, one sample each. (a) The profile: the mean tail $T_{k}$ , the weight beyond the $k$ heaviest atoms, under the four selectors, the dashed line the tail of one sample at the mean count $\bar{m}+1$ . (b) The certificate of Theorem 4.6 for half $A$ at $\delta=0.05$ , in units of $\kappa$ , on samples after the burn-in of $3000$ steps, by which the flock has ordered.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

mechanism	form	class	$L$
weighted mean	$h\bigl(\sum_{i}\mu_{i}x_{i}\bigr)$	conservative	$\left\\|h^{\prime}\right\\|_{\infty}$
value aggregation	$\sum_{i}\mu_{i}\,\varphi(x_{i})$ , $\varphi\in\mathcal{S}$	conservative	$1$
attention pooling	$h\bigl(\sum_{i}\mu_{i}\,v(x_{i})\bigr)$ , $\mathrm{Lip}v\leq 1$ , $\lvert v\rvert\leq R$	conservative	$\mathrm{Lip}(h)$
top weight	$R\,\mu_{\max}$	conservative	$1$
flocking update	direction of $\sum_{i}\mu_{i}\,e^{\mathrm{i}\theta_{i}}$	conservative	$1/\varpi_{0}$ at polarization $\varpi\geq\varpi_{0}$
count	$R/\mu_{\max}=R\sum_{i}s_{i}$	accumulative	$1$

Appendix

Table 1: Common aggregations, the class they belong to and the constant. Values in

[-R,R]

where a value bound is used. The starred row is the mechanism of the first row read against the share cap. The flocking row is Section C.1 , the rest is Proposition A.14 . No constant depends on

d

or on the number of selected coordinates.

Figure 2: The count law of the ball flock after the burn-in: the number

m

of particles inside the ball

r=1

other than the self, per sample, on the

64{,}000

replicas at (left)

\eta=1.2

, those of Figure 1 , and (right)

\eta=2.4

, those of Figure 3 .

	$\eta=1.2$			$\eta=2.4$
flock	$W_{1}$	cert.	cell cert.	$W_{1}$	cert.	cell cert.
ball, $r=1$	0.0272	0.0340	0.681	0.0435	0.0503	0.881
bump, $r_{b}=1.4$	0.1057	0.1125	1.005	0.1386	0.1454	1.004
Gaussian, $h=0.5$	0.1152	0.1238	1.006	0.1498	0.1583	1.004
Cauchy, $h=0.9$ , $a=3$	0.1205	0.1292	1.006	0.1555	0.1643	1.005

Appendix

Table 2: The two-sample transport

W_{1}(\hat{\Gamma}_{A},\hat{\Gamma}_{B})

and the certificate of Theorem 4.6 for half

A

\delta=0.05

, in units of

\kappa

, at

n=64{,}000

samples (

32{,}000

per half), each flock through the selector of its own rule, after the burn-in of

3000

steps, in both regimes, with the cell certificate of Proposition B.5 on the same halves at the same

\delta

, its shells, resolution and cutoff optimized on the data (the covering script of the supplementary material). The trivial value is

\kappa

, and the mean distance

D

between two random samples is

0.56

0.68\kappa

Panel of Figure 3 — Figure 3: The flock at $\eta=2.4$ , the twin of Figure 1 : $64{,}000$ independent replicas per flock, one sample each. (a) The profile, the mean tail $T_{k}$ under the four selectors. (b) The certificate of Theorem 4.6 for half $A$ at $\delta=0.05$ , in units of $\kappa$ , after the burn-in of $3000$ steps.

Figure 4: The implied dimension, the reciprocal of the local slope of

\ln W_{1}(\hat{\Gamma}_{A},\hat{\Gamma}_{B})

against

\ln n

over three consecutive doublings, at the middle

n

, after the burn-in: (a) on the replicas of Figure 1 at

\eta=1.2

and (b) on those of Figure 3 at

\eta=2.4

. The curves are the transports behind panel (b) of the two figures.

$4{,}000$ samples per half
$h$	$k(1\%)$	$k(0.1\%)$	decay	$\varpi$	dim	cert.
$0.125$	9	16	0.33	0.78	5.8	0.109
$0.18$	11	19	0.29	0.85	5.9	0.127
$0.25$	12	21	0.26	0.90	7.2	0.142
$0.35$	20	33	0.18	0.93	7.2	0.155
$0.5$	32	53	0.11	0.94	9.7	0.157

Appendix

Table 3: The bandwidth sweep of the Gaussian rule at

\eta=1.2

, each flock under its own rule, read at

4{,}000

samples per half (the pilot sets of

8{,}000

replicas) and at

16{,}000

per half (the full sets of

32{,}000

replicas),

h=0.5

the flock of Section 5.1 at the same prefixes: the atoms carrying all but

1\%

and

0.1\%

of the mean weight and the decay rate per atom between them, the mean local polarization within

r=1

, the implied dimension of the transport over the last three doublings, and the certificate of Theorem 4.6 in units of

\kappa

$\eta$	$k(1\%)$	$k(0.1\%)$	$\beta$	count	pol.	gate	dim.	cert A	$\varpi_{0}$
$1.2$	24	34	0.23	10.7	0.94	1.00	2.5	0.070	0.8
$2.4$	24	34	0.23	10.9	0.78	0.94	3.5	0.088	0.6
$3$	26	39	0.18	10.8	0.66	0.69	4.0	0.107	0.6
$4$	15	20	0.46	7.5	0.47	0.27	4.4	0.101	0.6
$5$	12	15	0.77	6.5	0.37	0.13	4.9	0.106	0.6

Appendix

Table 4: The noise sweep of the ball rule at

4{,}000

samples per half: the paper’s regimes at that prefix and the pilots above the transition (

8{,}000

replicas each). The columns of Table 3 , with the mean count of neighbors other than the self and the share of samples at the polarization gate

\varpi_{0}

of Proposition C.7 .

Structured Sparsity

Structured sparsity organizes zeros into meaningful groups, blocks, channels, or patterns to simplify models and computation.

See all 62 papers

Oct 11, 2026

Matched Specialization, Different Adaptation: Second-Moment Structure in Shared Representations

Small Adam-trained shared-representation networks can reach equivalent selected mean readout measurements yet respond differently to the same further learning. We use state interventions to separate second-moment scale and coordinate-pattern effects, then examine their formation and time dependence. In the central two-target experiment, the more precisely readable target switches within ten updates in 67.5% of acquisition-formed checkpoints and 0% of update-formed checkpoints. First-moment exchange leaves the ten-update contrast change within its pre-specified margin, whereas second-moment exchange reverses the contrast. A coordinate-pattern effect remains at common mean adaptive scale. Layer and movement controls locate an effect beyond overall update size. Formation records connect small encoder second moments with stronger cancellation between task gradients. A prospective gradient-projection experiment changes this retained state; transferring the resulting second moment alone reduces the ten-update adaptation response in a fixed recipient. The matched comparison extends to three Gaussian targets, while a room-sensor extension retains component effects but fails endpoint matching. Across tested regimes, component effects survive more widely than reversal or reset equivalence. Effect magnitude and duration depend on learning conditions.

Toru Takahashi

Human Informatics and Systems Lab, Doshisha University · Linked Open Data Initiative, NPO · Keio Research Institute at SFC +1

Multi-Task Learning

Ask PDF

Oct 5, 2026

Who Bears the Burden? Learning Responsibility for Shared Constraints in Multi-Agent Reinforcement Learning

When multiple agents share a cost budget, a common Lagrange multiplier can enforce the aggregate constraint but does not determine how its penalty should be allocated across agents. Uniform penalties ignore heterogeneity in the rewards agents sacrifice, while agent-specific multipliers may still rely on the same aggregate cost signal. We introduce Lagrangian Responsibility Allocation (LiRA), which learns each agent's share of a common multiplier by optimizing social welfare over a finite training horizon. The multiplier enforces the aggregate budget, while responsibility shares redistribute its influence without modifying the original rewards or constraints. For convex games under standard regularity conditions, varying these shares induces a smooth family of normalized generalized Nash equilibria in which active constraints remain at their budgets while welfare varies. To optimize responsibility before convergence, we derive a welfare gradient that accounts for both learning updates and the induced change in data distribution. Across CityLearn, MABIM, Harvest, and MetaDrive, spanning 3 to 400 agents, LiRA improves average social welfare by up to 29% over uniform and agent-specific multiplier baselines. Grid and driving costs remain within budget, inventory violations decrease, and Harvest makes more effective use of available budget.

Xiaoyang Cao, Jingqi Li, Zhe Fu +1

Massachusetts Institute of Technology · The University of Texas at Austin · Stanford University +1

Game Theory Constrained MARL Constrained RL Cooperative MARL Multi-Agent Reinforcement Learning

Ask PDF

Jun 26, 2026

Dangerous Liaisons of Convex Learning and Non-Affine Aggregation

Last-iterate convergence and generalization guarantees in first-order convex learning hinge on the monotonicity of the update operator. While linear averaging preserves the monotonicity of gradient updates, this property is often violated when gradients are aggregated non-affinely, as in modern pipelines enforcing constraints like adaptivity, privacy, robustness or fairness. Whether it is possible to design non-affine aggregation rules that maintain monotonicity has remained an open question. We answer this question negatively: we prove that the monotonicity of aggregated gradients is preserved if and only if the aggregation rule is positively affine. Consequently, non-affine aggregation prevents steady convergence and substantially degrade algorithmic stability. We quantify these drawbacks and propose a path forward by identifying sufficient conditions under which monotonicity can be restored. Our results provide a unified theoretical framework explaining the disparate failure modes observed in modern learning systems.

Thomas Boudou, Batiste Le Bars, Nirupam Gupta +1

PreMeDICaL team, Inria, Idesp, Inserm, Universit´e de Montpellier, Montpellier, France · Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189, CRIStAL, F-59000 Lille, France · Department of Computer Science, University of Copenhagen, Copenhagen, Danemark

Optimization Convergence Analysis Algorithmic Stability

Ask PDF

Abstract

Structured Sparsity

Explore similar work

Matched Specialization, Different Adaptation: Second-Moment Structure in Shared Representations

Who Bears the Burden? Learning Responsibility for Shared Constraints in Multi-Agent Reinforcement Learning

Dangerous Liaisons of Convex Learning and Non-Affine Aggregation