acceptodds
Under review as a conference paper at ICLR 2027

Learning Graded Sparse Mechanisms: A Representation Theorem and Certified Generalization

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, generalization bounds, sample complexity, sparsity, multi-agent systems, permutation invariance, Deep Sets, optimal transport, representation theorem, flocking

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_94oBOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper provides a new representation class with guarantees for modelling sparse interacting particle systems and similar settings. The authors provide analyses for classes of interaction functions and their axioms, which are transformed into a representation based on measures. The analysis is rigorous and the contribution is mainly theoretical. A Vicsek swarm example is given as an example of such a system, and the derived certificate is measured.

Critical strengths
  • The direction seems promising and potentially useful: New representation models for sparsely-interacting systems.
  • The presentation of the work is technical and rigorous.
  • The representation is exact for the given axioms.
Critical weaknesses
  • The experiments are limited to simulating a Vicsek flock, for which the interaction rules are fixed as known and not learned. Importantly, no training or learning is performed.
  • The significance of this work remains limited to me, as potential applications are discussed too little and no examples for learning control or dynamics are given. Moreover, no alternative representations are compared against in terms of bounds and rates.
  • Sparsity is assumed, not learned here, and it doesn't seem to be a key element for the proposed certificates.
  • Regarding related work, I believe the work is also related to the area of learning in mean field games and control [A], or general sparse mean field theory [B], which analogously considers anonymous agents through their empirical distribution (but not with separate weights per sample) and could be compared for the case with uniform weights.
  • Presentation-wise, it may be helpful for understanding to add some visualizations of the discussed empirical distributions, configurations etc. Additionally, I felt many sentences are difficult to parse or understand due to their length / slightly vague. Here are some examples I would try to revise:
Its proof is a routing: the axioms bound f along three moves, one value
at fixed weights, one weight at fixed values, a permutation, so f is Lipschitz for the path metric
the moves generate, and the theorem computes that metric in closed form as (4) by moving each
matched value at the smaller of its two heights, before the weight move where the height rises and
after it where it falls, at exactly the matching’s cost

...

For one chosen learner on one target a holdout
estimate on half B is tighter by definition, and the certificate does not compete with it: what it gives
is uniformity at no labels, over every target on the design and every predictor in the class at once,
in hand before a learner is chosen or a label seen, so that a choice made after seeing the data costs
nothing (Theorem B.1(ii)).

[A] Laurière et al. "Learning in Mean Field Games: A Survey." arXiv 2205.12944

[B] Lacker et al. "Local weak convergence for sparse networks of interacting processes." Ann. Appl. Probab. 33 (2) 843 - 888, April 2023. https://doi.org/10.1214/22-AAP1830

Questions for authors
  1. Is it necessary to work with configurations (x, \mu) instead of directly working with the lifted objects from the beginning? What examples would necessitate this?
  2. Can the theory be applied to obtain stronger guarantees for learning control or dynamics than in existing literature?
  3. Regarding the discussion of related works on graph networks, how does this work represent these graphs? For example, given the anonymous interaction, can you consider Vicsek flocking agents interacting on a static graph through your selector? Alternative, is it possible to represent states on a discrete graph?
4 comments
AuthorsOpenReview ↗

Reply to Reviewer 94oB, part 1 of 2

Thank you for your feedback and questions!

We were glad to learn that the framework introduced in this paper was found to be promising and potentially useful, that the exactness of the representation was listed among the strengths.

We believe that the main concern in this review is that the theory we present is not sufficiently connected to applications.

Our goal in this paper was indeed to develop the theoretical framework in which one can formally discuss functions with a varying number of arguments, where the influence of each argument is also controlled. In the Introduction we discussed how such functions appear in multi-agent systems and robotics, including situations with known selectors. We believe such situations are fairly common.

That said, following the notes in this and the other reviews, we have added an example to illustrate the framework. It is the dam break, a simulation of liquid particles in which each particle's next state depends on its current state and the states of the other particles. Please see the dam break comment above for the details.

In particular, in relation to several concerns raised in this review, in this example we show how a selector can be learned in some situations, we evaluate the implied dimension of the data, and we learn the mechanism itself under different selectors. We find that learning the mechanism with the learned selector performs better than the same learning with several heuristically chosen selectors. We also show that the performance is comparable to or better than that of a known GNN-based model on the same data, although that comparison is initial.

We hope that this example helps address the concerns raised in weaknesses 1 to 3 of the review. Please let us know whether the example clarifies the situation. We do believe that the notions we discuss in the paper address a modelling need in practical situations, and we would be glad to discuss this further.

We now address the questions in the review.

Q1. Is it necessary to work with configurations (x, μ) instead of directly working with the lifted objects from the beginning? What examples would necessitate this?

Our understanding is that the question asks why we use the pair (x, μ) as the configuration, where x is the set of states of all the particles and μ are the weights. Please let us know if that was not the intention.

As mentioned above, the basic problem we try to solve is this: how do we formalize the notion of a function (a mechanism) that depends on few elements? We want it to depend on few elements because this often happens in nature, due to locality in space. Another reason is that the total number of elements may be huge, and some restriction is needed to control overfitting.

The classical approach is simply to limit the elements: one chooses the elements within a radius, or the k closest elements, and discards everything outside. Note that in our terminology this is a hard uniform selector, which is not learned, and which is already broadly used in a large share of GNN and multi-agent models.

The obvious downside of this approach is that a hard threshold is unrealistic and loses information. The natural solution is to allow dependence on all elements, but to introduce weights that control the strength of the dependence. Without the weights, we would have the complexity problem mentioned above.

This explains why we use weights.

We note that while the original Vicsek flock has a hard selector, there has been considerable follow-up work studying weighted flock dynamics, for instance (Olfati-Saber, 2006; Cucker and Smale, 2007; Degond and Motsch, 2008; Motsch and Tadmor, 2011). Those are natural candidates where the weights are required.

Another example is the dam break. There the influence of a particle on another decays with distance, with no sharp cutoff: the solver's own kernel radius holds only 46% of the influence on a particle's next state, and 99% is reached only at about 18 particle spacings (Appendix F.2, Table 5).

We also note that while introducing weights is natural, how to do this in a general way is not obvious. For instance, there are whole lines of work that analyze the complexity of weighted linear sums (Lu, Maggioni, Tang and Zhong 2019, Lu, Maggioni and Tang 2021). However, linear sums are restrictive. For instance, the dam break mechanism cannot be described by linear sums (Appendix F.1).

Our framework is a way to incorporate weights in a general way, starting from axioms.

AuthorsOpenReview ↗

Reply to Reviewer 94oB, part 2 of 2

Q2. Can the theory be applied to obtain stronger guarantees for learning control or dynamics than in existing literature?

Strictly speaking, there are no guarantees in the literature that cover our setting in general.

For hard selectors of constant size, one could derive complexity bounds from existing results relatively quickly. In that case the results would give the same rates as ours. In that sense our results are stronger, in that they cover much more general selectors.

As mentioned above, there also exist results for weighted linear sums. Those can be viewed as having (somewhat) general selectors, but a restricted type of function. In that case their sample complexity bounds are better than ours. This is to be expected, however, since our class is much bigger than theirs.

Q3. Regarding the discussion of related works on graph networks, how does this work represent these graphs? For example, given the anonymous interaction, can you consider Vicsek flocking agents interacting on a static graph through your selector? Alternative, is it possible to represent states on a discrete graph?

In flocks the behavior of a bird is influenced by a set of birds that are close to it in some sense. Because the relative positions change over time, this set is different at each time step. We are not sure there is a way to represent this with a static graph, except as a full graph, but then the weight information would be lost.

To allow the dynamic behaviour, the selector determines the weights from the whole configuration. However, dependence through a static graph can also be expressed via the selector. The selector knows the identity of a particle, and can always choose a fixed set of other particles for it.

We are not completely sure whether we have answered the question. Please let us know if we can clarify more.

Literature.

Thank you for bringing the references to our attention. Both [A] and [B] consider permutation invariant mechanisms with uniform weights, where all the elements can have influence ([A]) or only the neighbours on a fixed graph ([B]). Both papers have been added to the references and to the literature discussion (Appendix E).

The question we ask in this paper is different from the ones in these works. We are interested in the complexity of all possible mechanisms (the functions F in [B]) given a certain selector, which has implications for how difficult it is to learn such a mechanism. In contrast, [A] and [B] assume that the mechanism is given: [A] computes equilibrium policies, and [B] studies the dynamics of the system under that mechanism.

Presentation.

We take the suggestions on presentation in the review seriously. We will proofread the paper for clarity and add illustrations for the flock and the dam break experiments.

We hope we have been able to clarify some of the points raised in the review. We would be very glad to discuss any follow-up questions.

Thank you for the extensive response to W1 and Q1-3. It seems the selector is fitted to a known simulator rather than learned from data, and the learned result is not better than a tuned exponential. I remain a little bit concerned about significance and presentation of the revised manuscript. Due to its length and density, I think a more clear presentation would greatly enhance the work. However, I think the structural results of the theory are of potential interest to the audience. Given the authors' additions as well as commitment to improving the work and its presentation, I will increase my score in favor of acceptance.

Thank you for the reply and for raising the score!

We will continue working on improving the presentation, including the illustrations for the two experiments, and on a more detailed comparison of methods on the dam break example.

Reviewer_4afkOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies permutation-invariant interaction mechanisms with given influence weights. It defines a function class through coordinate-wise influence and weight-stability constraints, identifies this class with a Lipschitz ball under a matching metric, and derives generalization bounds depending on the weight-tail profile rather than the ambient number of elements. It also constructs an empirical transport-based certificate and demonstrates non-vacuous bounds in a simulated Vicsek flocking setting.

Critical strengths
  1. The exact identification between the axiomatic mechanism class and the matching-metric Lipschitz class is useful. It connects local influence constraints to a global geometry without losing the Lipschitz constant.

  2. The analysis accommodates continuously weighted, full-support interactions rather than only hard sparsity. The lower bounds and non-vacuous empirical certificates strengthen the theoretical contribution.

Critical weaknesses
  1. The mathematical novelty appears relatively narrow after accounting for existing results on multiset transport, Kantorovich–Rubinstein duality, and empirical Wasserstein convergence. Appendix E appropriately acknowledges these connections, including earlier rates of the same exponential-square-root-log form. The remaining contribution is therefore the specific class identification and the extension to mean weight-tail assumptions. While these are legitimate contributions, I am not yet convinced that they provide a sufficiently substantial advance beyond the existing framework.

  2. The learning implications remain limited in the current demonstration. The selector and weights are supplied, and the empirical result primarily establishes a class-wide generalization certificate in a controlled flocking setting. Non-vacuity is valuable, but it remains unclear how much the new profile-dependent analysis changes our understanding of learning these mechanisms beyond what the transport formulation already provides.

Questions for authors
  1. Could you give a concrete example covered by the mean-tail result but not by the closest existing convergence theorems, and identify the additional proof ingredient needed to handle it?

  2. In the existing flocking experiments, what conclusion about generalization depends specifically on the graded-sparsity analysis, beyond the availability of a computable transport certificate?

2 comments
AuthorsOpenReview ↗

Reply to Reviewer 4afk, part 1 of 2

We thank the reviewer for the feedback.

We were glad to read that the framework itself, allowing full-support interactions, the exact representation theorem, the lower bounds and the data-driven certificates were listed as strengths of the paper.

Following the notes in this and the other reviews, we have added an example to illustrate the framework. It is the dam break, a simulation of liquid particles in which each particle's next state depends on its current state and the states of the other particles. Please see the dam break comment above for the details.

In particular, in this example we show how a selector can be learned in some situations, we evaluate the implied dimension of the data, and we learn the mechanism itself under different selectors. We find that learning the mechanism with the learned selector performs better than the same learning with several heuristically chosen selectors. We also show that the performance is comparable to or better than that of a known GNN-based model on the same data, although that comparison is initial.

We hope that the example helps address this part of weakness 2:

The learning implications remain limited in the current demonstration. The selector and weights are supplied, and the empirical result primarily establishes a class-wide generalization certificate in a controlled flocking setting.

We would be glad to answer any follow-up questions on this topic.

Before we address the questions in the review, we would like to make a few notes on weakness 1, "The mathematical novelty appears relatively narrow".

In addition to the representation theorem (Theorem 3.2), which was named as a strength in this and the other reviews, we believe the following are new with respect to the literature.

(a) The framework. Conceptually, we believe the framework we suggest is not a straightforward extension of hard sparsity. Once there is no sparsity to control complexity, it is natural to assume that some weighting should be involved. However, how to incorporate this weighting in a general way is not clear a priori.

For instance, there are whole lines of work which introduce weighting just by considering weighted sums (Lu, Maggioni, Tang and Zhong 2019, Lu, Maggioni and Tang 2021). As with ours, their bounds do not depend on the cardinality of the support, but their function class is a small and very specialized subclass of ours.

We would be glad to know whether the reviewer agrees with this perspective.

(b) The cone space (eq. 2), its relation to existing results, and its novelty. While related constructions did appear in the literature, in the context of transport between multisets, our approach differs in two ways.

(i) In the literature this space was introduced directly, to solve a specific problem, a matching between sets of different cardinalities. In this paper we arrive at the space from the axioms. It is the unique space on which the functions we are interested in are a Lipschitz ball. That view of the cone space is new, and we use it for a new purpose.

(ii) Our version of the space is weighted by the cap function (the u/v coordinates), with a corresponding metric.

(c) The empirical convergence theory. Here we indeed build on the existing convergence results for empirical measures in Wasserstein distance, which in turn build on Dudley's arguments from the 1960s. As noted in the review, we extend these results to our weighted-support case. We would like to emphasize that, to begin with, the whole connection of the transport results to the problem of mechanisms with set-like inputs is only possible because of our identification.

(d) The lower bounds. The lower bounds we prove, in particular those of Theorems 4.4 and 4.5, were mentioned as a strength in this and the other reviews. These results, we believe, also contribute to the mathematical novelty.

AuthorsOpenReview ↗

Reply to Reviewer 4afk, part 2 of 2

Q1. Could you give a concrete example covered by the mean-tail result but not by the closest existing convergence theorems, and identify the additional proof ingredient needed to handle it?

Technically speaking, there are no existing convergence theorems that could be applied directly to obtain our sample bounds, simply because there are no results that consider this class of functions.

Existing results can treat directly only unweighted configurations, where the number of points is the only parameter. However, at the level of the arguments, most of the material we use for the statistical part of the upper bounds is known. For instance, Proposition 10 of Weed and Bach (2019) provides general bounds on any metric space, in terms of covering numbers and the probability of a residual set on that space. Our Theorems 4.4 and 4.5 can then be viewed as supplying the connection. The space is the cone space (eq. 2), and the statistical profile T_k of the mechanism is translated, via the axioms (Definition 3.1), into the above covering numbers and residual probabilities, plus an additional approximation term.

The use of the axioms, in particular axiom (W), is essential here. It is what allows the comparison of function values at different sparsity levels, that is, what happens when we cut off to zero all the particles of low influence.

Since this question is specifically about the technical novelty in the proofs of the upper bounds, we would like to note again that, as discussed above, there are several arguments in this paper that, at least in our opinion, are more novel than this one: the representation theorem (Theorem 3.2), where the metric is derived from the axioms, and the lower bounds (Theorems 4.4, 4.5 and D.5).

Q2. In the existing flocking experiments, what conclusion about generalization depends specifically on the graded-sparsity analysis, beyond the availability of a computable transport certificate?

As we understand this question, it asks what we can learn from the class-level bounds, such as Theorems 4.4 and 4.5, and especially what they give beyond the data-driven bound (the certificate) of Theorem 4.6. Please let us know if this was not the intention of the question.

Given the data and the sample count n, the data-dependent bound will usually be much better than a data-independent bound, since the latter is at least the worst case over all data distributions. On the other hand, the data-dependent bound can only be computed for those n for which we have the data. As such, it provides less information about the function class. For instance, we cannot ask in advance for which n we should expect a given risk level. Data-independent bounds, on the other hand, do not use the data and make no assumptions about distributions, but have asymptotic rates in n.

Our profile-dependent bounds are in a sense a middle ground. They do not require the samples themselves, but they do require knowledge of the profile distribution. While that distribution can be postulated, usually it will be beneficial to estimate it from data. Note, however, that estimating the profile may require some n₀ samples (a moderate number, since this is a one-dimensional quantity), while the result then yields bounds for any n, which could be much larger than n₀.

Both types of bounds can also be used to gain some intuition about the data, such as its intrinsic dimension, which is derived from the rate of decay of the bounds and is a rough measure of the true complexity of the data.

We hope we have been able to clarify some of the points raised in the review. We would be very glad to discuss any follow-up questions.

Reviewer_8SG8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper looks at mechanisms where an element's update depends on a set of other elements, each with a weight that the environment provides (for example, the neighbors inside the interaction radius of a Vicsek flock, or neighbors weighted by a distance kernel). The weights are treated as observed inputs, and the goal is to learn the mechanism.

The authors define the class of such mechanisms through three axioms: each element's influence is capped by its weight, the output changes regularly with the weights, and the elements are interchangeable. The main structural result (Theorem 3.2) shows that this class is exactly the set of Lipschitz functions under a partial-matching distance between weighted multisets, lifted to a cone. Two versions are considered, one with mean-like semantics (the main text) and one with sum-like semantics (the appendix).

Using this representation, the generalization gap of the class becomes a Wasserstein distance between the empirical and true distributions of configurations. The paper bounds it through the "sparsity profile", that is, how much weight remains beyond the k heaviest elements. For exactly sparse designs the rate is polynomial, with an exponent that gets worse as the sparsity level grows. Under exponentially decaying profiles the rate is quasi-polynomial. Neither bound depends on the total number of elements, and lower bounds match the exponents in several cases, including a lower bound for learners at fixed sparsity.

Separately, the paper gives a label-free certificate computed from the data. It is the exact transport distance between two halves of the sample, found by an assignment problem, plus a concentration term.

The experiments compute this certificate on a simulated Vicsek flock with four interaction rules (hard ball, bump, Gaussian, Cauchy) at two noise levels. Each sample is one view from an independent simulation run, which makes the samples i.i.d.

Critical strengths

1. The exact representation gives the whole framework a solid base. Theorem 3.2 is not just "this model is Lipschitz for some convenient metric". It shows the axiomatic class is exactly a Lipschitz ball, with the same constant in both directions. The proof explains nicely how each axiom contributes a piece of the matching cost. The weight axiom is also well justified: Proposition A.4 shows it is the tightest weight condition that does not look at the values and still keeps every bounded Lipschitz weighted sum in the class. The mean versus sum versions give a clean way to talk about influence that gets diluted as more elements join versus influence that adds up. This matters to my assessment because everything after it, both the rates and the certificate, is built on this characterization.

2. The worst-case theory is sharp, and the certificate makes the geometry usable in practice. Cropping each configuration to its heaviest elements ties the weight tail to low-dimensional strata. This gives bounds that do not depend on the number of elements, and the lower bounds show that the dependence on effective sparsity cannot be removed for the full class (for sparsity at least 2 on interval values, with Theorem D.5 giving a lower bound for any learner). The exponential-profile lower bound shows the slow rate is real and not an artifact of the analysis.

The certificate then turns the same geometry into an actual number from the data. Its transport term is the exact empirical discrepancy of the class on the two halves, and it is never worse than the cell-based bounds of Proposition B.5. The statistical ingredients are classical, which the paper acknowledges (maximum discrepancy, as in Bartlett et al. 2002 and von Luxburg & Bousquet 2004). What is new is that the representation makes it exactly computable for this class. The flock experiments show it is clearly non-vacuous for the unit class on every rule tested.

Critical weaknesses

1. It is not shown that the full class is needed in practice. All four mechanisms in the experiments compute the direction of the weighted mean heading, so they depend on the configuration only through two weighted sums. Where polarization is bounded away from zero, the update is a Lipschitz function of those two numbers. The paper's own Proposition B.20 and Remark B.21 explain that this kind of fixed, low-dimensional feature avoids any dependence on the number of elements, and so does not need the profile theory at all. So the running example does not show that the richer class is the right model for the motivating problems. A certificate computed on the two-dimensional mean-heading features would show how much is lost by certifying the whole class. A real example that needs richer dependence on individual weights would make the motivation much stronger.

The role of the profile in the experiments is also not isolated. Appendix C.1 (p. 45) says the bound "reads the profile" and that "the certificate follows the profile, slowly". However, the bandwidth sweep changes the dynamics and the polarization along with the weight tails, so the effect of the profile on its own cannot be read off. I do not see a contradiction with the theory here: matching the tail at ten atoms does not match the whole profile, and the theory already treats free and uniform weights differently. The issue is only that the experiments do not separate the profile from everything else that changes.

2. The headline numbers are for the class, not for the actual flock update. The abstract's claim that the certificate is non-vacuous is correct for the unit class. The normalized Vicsek update, though, only belongs to the class when polarization is bounded below, and then with a larger Lipschitz constant; samples outside that region need a separate correction. Appendix C.1 does this translation for the ball rule and gets bounds of about 0.16 and 0.51, against a range of 2, at the two noise levels. The same translation is not given for the graded rules. So the headline numbers alone do not show useful guarantees for every physical update. It would also help to clearly separate three quantities: deviation of the class, the generalization gap of the loss, and the actual population risk (which also needs the training error).

On scope: using independent simulation runs is a legitimate way to meet the i.i.d. assumption. However, the guarantee does not cover correlated views from recorded trajectories, which is what most of the motivating applications would provide. I see this as a limit on applicability rather than a flaw in the theorem.

Questions for authors
  1. Which practical mechanism needs more than a Lipschitz function of a fixed number of weighted sums? Is there a setting where the richer class is actually required, and not just allowed?
  2. What certificate do you get on the two-dimensional mean-heading features, with the right Lipschitz constant? This would show the price of certifying the full class in your own running example.
  3. Could you report the update-specific bounds for every rule and noise level, with justified polarization thresholds, the cost of the excluded region, and how the confidence levels are combined? Please keep class deviation, loss generalization gap, and population risk separate.
  4. Can you vary the weight-tail decay while keeping the heading distribution and other geometry fixed? This would support the profile reading of the bandwidth sweep in Appendix C.1.
2 comments
AuthorsOpenReview ↗

Reply to Reviewer 8SG8, part 1 of 2

Thank you for a detailed and constructive review. We were glad to see the exactness of the representation highlighted as a strength, together with the sharpness of the worst-case theory and the data-driven certificate.

We believe the main concern in the review is that in our leading example, the flock, the true mechanism is the direction of a weighted average, which does not illustrate the need for the full Lipschitz class. Accordingly, and following the notes in the other reviews as well, we have added a second example, the dam break, whose mechanism is demonstrably not a function of a fixed number of weighted sums. In this example we also show the learning of the selector, the effective dimension as a function of the selector, the learning of the mechanism itself by Lipschitz regression, and an initial comparison with the GNN model trained on these data. Please see the general comment above for a summary and Appendix F of the updated PDF for the details.

We would be glad to hear whether this example illustrates the need in practice for the full Lipschitz class.

We now address the specific questions.

Q1. Which practical mechanism needs more than a Lipschitz function of a fixed number of weighted sums? Is there a setting where the richer class is actually required, and not just allowed?

The dam break is one such practical mechanism. Its target is not a function of any fixed number of weighted sums, and this is measured rather than assumed: for a function of p weighted sums the matrix of second derivatives between two disjoint groups of particles has rank at most p, and the dam break target has rank at least 38 (Appendix F.1). The reason is intrinsic. A single solver step is already not a function of a few weighted sums. And the target mechanism which we are to model composes 100 such steps, with the neighborhoods changing from step to step, which compounds this.

Q2. What certificate do you get on the two-dimensional mean-heading features, with the right Lipschitz constant? This would show the price of certifying the full class in your own running example.

We computed it for all four rules and both noise levels (Appendix G, Table 11), at 32,000 samples per half, in the same units as Table 2 (a fraction of the diameter).

two-dimensional featurefull classratio
η = 1.2, ball0.0120.0342.9
η = 1.2, graded rules0.012 to 0.0130.11 to 0.138.5 to 10.5
η = 2.4, ball0.0140.0503.6
η = 2.4, graded rules0.012 to 0.0130.15 to 0.1612 to 13.5

Thus in this case the price of not knowing that the update depends on the configuration only through the mean heading is a factor of 3 to 13.

Q3. Could you report the update-specific bounds for every rule and noise level, with justified polarization thresholds, the cost of the excluded region, and how the confidence levels are combined? Please keep class deviation, loss generalization gap, and population risk separate.

Please see Appendix G, Table 12 for these bounds.

For every noise level η and selector type, we report:

  • the threshold,
  • the percentage of samples above the threshold,
  • the generalization gap of the class, already multiplied by the update's Lipschitz constant 1/ϖ₀,
  • the threshold correction term, which is the cost of the samples below the threshold,
  • and the resulting bound (the sum of the two terms above).

We also show what the bound would be if a different threshold were chosen. We used the threshold yielding the best bound.

Please note that we do not report a population risk. A population risk is the risk of a specific function, and would depend on the noise in the labels, while our bounds are for the class itself as a whole, with no relation to label noise.

AuthorsOpenReview ↗

Reply to Reviewer 8SG8, part 2 of 2

Q4. Can you vary the weight-tail decay while keeping the heading distribution and other geometry fixed? This would support the profile reading of the bandwidth sweep in Appendix C.1.

We agree there is a confound, where the bandwidth h determines both the dynamics and the weights computed on the resulting flock. Thank you for pointing this out!

We did the computation at fixed dynamics (Appendix G.3, Table 13 and Figure 6). We took the Gaussian flock (η = 1.2, h = 0.5) and recomputed the weights on the same 64,000 state views, under the Gaussian kernel at the four other bandwidths of the sweep and under the ball of radius 1. The positions and headings are fixed and only the weights change.

For each selector, Table 13 reports:

  • the mean number of atoms per view that receive weight,
  • the number of heaviest atoms that carry 99 % of the weight,
  • the polarization under the selector's weights,
  • the transport W₁ between the two halves and the certificate, at 16,000 samples per half, in units of κ,
  • the implied dimension, read from the decay of W₁ with the sample size.

We reproduce part of the table here:

selectoratoms per viewimplied dimensioncertificate
Gaussian, h = 0.533.712.00.133
h = 0.3518.19.30.122
h = 0.2510.27.00.100
h = 0.185.95.30.073
h = 0.1253.44.20.049
ball, r = 111.73.20.043

With the geometry fixed, the certificate follows the weight tail. As the bandwidth narrows from 0.5 to 0.125, the atoms per view go from 34 to 3.4, the implied dimension falls from 12 to 4.2, and the certificate from 0.133κ to 0.049κ.

Remarkably, however, the ball is not on this trend. It gives weight to about 12 atoms per view, close to the Gaussian at h = 0.25, but its implied dimension is 3.2 against 7.0. It is also below the narrowest Gaussian, which has 3.4 atoms per view and reads 4.2.

The reason, we believe, is that under the ball all the atoms of a view have the same weight, so two views (states) differ only in their headings and in their number of atoms. Under a graded kernel each atom also carries its own weight, which changes from view to view and has to be matched as well. In a well-aligned flock (polarization 0.94) the headings vary little, so the weights account for most of the difference between views.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General comment to all reviewers, the Dam Break example

We would like to thank the reviewers again for the detailed feedback. Following the feedback, we have added a second example which illustrates the framework.

The example is a physics simulation: a column of water at rest behind a gate is released and collapses under gravity along a dry floor. This is the standard SPH dam break (the 2D dam break dataset of LagrangeBench, Toshev et al. 2023, the SPH scheme of Adami et al. 2012). Previously, graph network simulators of the GNS type (Sanchez-Gonzalez et al. 2020) were trained on this dataset. Each particle's next state (position, velocity) is determined by its current state and the states of the other particles, a typical interaction mechanism. The dataset is well known and stores every 100th step of a smoothed-particle (SPH) simulation of the weakly compressible Navier–Stokes equations.

What we have shown:

  • This dataset does not come with a "built-in" selector.

    We show that the selector can be learned, at least when a simulator is available, and we learn an exponential-type selector. The environment's obvious candidates, the solver's own kernel and the depth of the GNN trained on the data, do not produce good predictions (nearly twice the error of the learned selector).

  • Under the learned selector, the effective dimension the certificate implies (4 to 6) is far below the ambient dimension (thousands).

  • Given the selector, we learn the interaction mechanism as a Lipschitz regression, and we study the effect of different selectors on prediction accuracy.

    • On the same one-step task (the next stride of the same 250 test configurations) the pretrained LagrangeBench GNS (see above) has a position error of 0.0067 dx per coordinate, the trivial predictor 0.0072, and our Lipschitz regression under the learned selector 0.0020 dx, after learning from 500 examples.

    We note however that the GNS was trained with input noise for rollout stability, so one-step accuracy is not necessarily what it optimizes. A more detailed comparison will be presented in the final version of the paper.

Full details are in the revised version of the paper, Appendix F. The code for this example is included in the updated supplementary material.

We believe this example addresses several concerns raised in the reviews.

  • Reviewer 8SG8:

    It is not shown that the full class is needed in practice.

    For the dam break it is needed: the mechanism is not a function of a fixed number of weighted sums, and this is measurable. For a function of p weighted sums, the matrix of second derivatives between two disjoint groups of particles has rank at most p. For the flock rules p = 2. For the dam break target the measured rank is at least 38 (Appendix F.1).

  • Reviewer 4afk:

    The selector and weights are supplied, and the empirical result primarily establishes a class-wide generalization certificate in a controlled flocking setting.

    This provides an additional example, and here the selector is learned rather than supplied. It also shows where the complexity analysis enters the choice of a selector: the certificate is about the same for every selector that reaches all the particles the mechanism depends on, but the Lipschitz constant of the mechanism is 179 under a uniform ball and 27 under the learned exponential selector, so the generalization bound (the constant times the certificate) is seven times smaller under the learned selector.

  • Reviewer 94oB:

    The experiments are limited to simulating a Vicsek flock, for which the interaction rules are fixed as known and not learned. Importantly, no training or learning is performed.

    no examples for learning control or dynamics are given.

    The dam break is a dynamics-learning task, the one the GNS is trained on, and learning is performed: the mechanism is learned by Lipschitz regression. Under the learned selector the prediction error is a quarter of the trivial predictor's error, and under the selector given by the GNN's own ten message-passing rounds it is 0.44 of it.

Although our paper concentrated on building the theory (the representations, lower bounds and data-driven certificates were mentioned as strengths), we agree with the reviews that an example beyond the flocks of the original submission could be useful to illustrate the framework. We hope the dam break provides such an example.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.