- 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
- 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?
- Can the theory be applied to obtain stronger guarantees for learning control or dynamics than in existing literature?
- 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
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.
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.