Probabilistic Invariant Learning with Randomized Linear Classifiers
Authors: Leonardo Cotta
Gal Yehuda
Assaf Schuster
Chris J. Maddison
Venue: NeurIPS 2023 poster (2023)
Keywords: Invariant Learning
Geometric Deep Learning
Set Representations
Graph Representations
Expressive Power
Randomized Algorithms
TL;DR: We combine insights from randomized algorithms and probability theory to devise resource-efficient invariant models.

Abstract: Designing models that are both expressive and preserve known invariances of tasks is an increasingly hard problem. Existing solutions tradeoff invariance for computational or memory resources. In this work, we show how to leverage randomness and design models that are both expressive and invariant but use less resources. Inspired by randomized algorithms, our key insight is that accepting probabilistic notions of universal approximation and invariance can reduce our resource requirements. More specifically, we propose a class of binary classification models called Randomized Linear Classifiers (RLCs). We give parameter and sample size conditions in which RLCs can, with high probability, approximate any (smooth) function while preserving invariance to compact group transformations. Leveraging this result, we design three RLCs that are provably probabilistic invariant for classification tasks over sets, graphs, and spherical data. We show how these models can achieve probabilistic invariance and universality using less resources than (deterministic) neural networks and their invariant counterparts. Finally, we empirically demonstrate the benefits of this new class of models on invariant tasks where deterministic invariant neural networks are known to struggle.

Probabilistic Invariant Learning with Randomized Linear Classifiers
Leonardo Cofta
Gal Yehuda
Vector Institute
Technion, Haifa, Israel ygal@cs. technion ac
leonardo. www.ta@veerrrrriiittttte..eee
Assaf Schuster Technion, Haifa, Israel assaf@technion ac.
Chris Maddison
University of Toronto and Vector Institute cmaddis@cs toronto.... edu
Abstract
Designing models that are both expressive and preserve known invariances of tasks is an increasingly hard problem. Existing solutions tradeoff invariance for compu- tational or memory resources. In this work, show how to leverage randomness and design models that are both expressive and invariant but use less resources. Inspired by randomized algorithms, key insight is that accepting probabilis- tic notions of universal approximation and invariance can reduce our resource requirements. More specifically, propose class of binary classification models called Randomized Linear Classifiers (RLCs). We give parameter and sample size conditions in which RLCs can, with high probability, approximate any (smooth) function while preserving invariance to compact group transformations. Lever- aging this result, we design three RLCs that are provably probabílistic invariant for classification tasks over sets, graphs, and spherical data. We show how these models can achieve probabilistic invariance and universality using less resources than (deterministic) neural networks and their invariant counterparts. Finally, we empirically demonstrate the benefits of this new class models on invariant tasks where deterministic invariant neural networks are known to struggle.
Introduction
modern challenge in machine learning designing model classes for invariant tasks that are both universal and resource-efficienn Consider designing an architecture for graph problems that is invariant under graph isomorphism. Ensuring that this class universal is at least as hard as solving the graph isomorphism problem [5). Similarly, permutation invariance universality comes at the cost of memory-the the number of parameters scales with the sequence size 332
Using randomness as a computational resource for algorithms a fundamental idea in computer science. In their essence, randomized algorithms often provide simple solutions that use less memory or run in less time than their deterministic counterparts [30]. Since there is no free lunch, these gains come the cost of accepting probabilistic notion of correctness, i.e.. while deterministic algorithms always output correct answers, their randomized versions will be right only with high probability: Inspired by this, the key insight in our paper is using an external source of randomness reduce time and space resources when learning an invariant task. To benefit from that, just as in randomized algorithms, we also need introduce probabilistic notion invariance and expressive power. By guaranteeing invariance and universal approximation only with high probability, we show when it is possible to avoid the invariance-resource tradeoff.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

We introduce a class of models for binary classification tasks named Randomized Linear Classifiers (RLCs). In an RLC the external source of randommess is input neural network that generates a random linear classifier classifier-indppeee -ndeependenlly from the input- which is then used to make prediction. To guarantee correctness with high probability, we need to repeat this process for a sufficient number of times, ie., take multiple samples, and predict the majority of their output- this is called amplification. The key features of RLCs are both i) randomness independent from input and ii) linear transformation of the input. Combined, these features provide both theoretical and practical simplicity. On the practical side, RLCs can offload computation and preserve privacy resource-constrained devices. We highlight the benefits of RLCs in such applications below.
Online computation. Suppose that our goal is to answer classification queries quickly as possible, or that the queries arrive in an "online" fashion. By using RLCCs, we can sample several linear classifiers "offline" (before observing new inputs), and then in the online phase simply take the majority of few (different) linear classifiers for each input. This way, the majority of computations can be done oflline rather than online -a usual in existing online learning settings.
b. Private computation. Suppose that we wish to peform inference with an RLC, but we only have low-rew oow-resource computer (e.g., smartwatch). A practical way of doing so to perform the sampling remote server, then retrieve the answer. In our approach, the server can send the randomness, i.e, the sampled linear classifier coefficients. There no communication between the client and the server at all, and the client never sends the input -retaining its privacy. Moreover, since the client only needs to perform a few linear computations, it can be a low-resource computer.
The theoretical advantages of RLCs' features explored in this work. We consider the required resources of an RLC to be universal and invariant for a given task as the number of parameters used by its neural network and the sufficient number of samples (amplification size). Then, focus on establishing upper-bounds for these resources in different scenarios. More specifically, our contributions are three-fold:
i) We introduce the general class of Randomized Linear Classifiers (RLCs), presenting universal approximation theorem coupled with a resource consumption characterization (Theorem [ In specific, show that any binary classification problem with a smooth boundary can be approximated with high probability by RLCs with at most the same number of parameters as a deterministic neural network. This is result of general purpose and holds for any invariant or non-imvariant task.
ii) We show how the problem of designing RLCs invariant to compact group transformations can be cast designing invariant distributions of linear classifiers. As result, we can leverage representation theorems in probability theory, such as de Finetti's (9]. Aldous-Hoover 's[Il and Friedman's 's [13] design invariant RLCs for tasks with set and graph data. Moreover, in Appendix B we also show a simple invariant model for spherical data using these ideas.
iii) Finally, we show both theoretically and empirically how invariant RLCs can succeed in tasks where deterministic architectures, such as Deep Sets and GNNs, cannot efficiently approximate. By introducing probabilistic notions of universality and invariance, our work establishes the first alternative avoid the invariance-resource tradeoff with theoretical guarantees and empirical success.
1.1 Related Work
Here, we briefly review Coin-Flipping Neural Networks (CFNNs) and invariant representation learning -two core concepts that we build upon. Finally, we explain how Bayesian neural networks and RLCs belong to different learning paradigms.
Coin-flipping neural networks. CFNNs were presented by 127. where the authors pro- pose several deep learning architectures using randomness as part of their inference. A few (constructive) examples were shown in which randomness can help by reducing the number of parameters or the depth the network. In this paper we focus on the case of learning randomized linear classifiers and its use in invariant learning. The invariant models were not explored in [27).

---

and to the best of our knowledge this is the first work studying randomized models for invariant learning. One specific CFNN model proposed in [27] is the Hypernetwork CFNN. In this model, the weights of a model are first randomly generated. Then, the computation of deterministic neural network using these random weights takes place. this work, we focus on the "extreme" case of this paradigm: we allow our model to use arbitrarily complex distributions to generate our final weights, but we insist that the deterministic part -using such weights- would be linear function. That is, we push the computational complexity to the random part of the model. This gives rise to the class of models we study: Randomized Linear Classifiers (RLCs). The work of [27] considered a first version of RLCs, but did not provide any empirical results and their theoretical results hold only for single dimensional input (i.e., in R). Hence, to the best of our knowledge our work also establishes the first (general purpose) universal approximation theorem of (non- moon-invrriant) RLCs (cf. Section
Invariant representation learning. Over the last years, there has been growing interest in designing G-invariant architectures 4 18 335. In summary, we can often leverage an a priori knowledge that the function to be learned is invariant the action of group G by forcing our model to also be invariant to it. That is, G-invariant architectures incorporate a known propriety of the target. Such a reduced model space is known to both empirically and theoretically achieve better generalization 4 6 19]. Existing works study the G-invariant function space and how to parameterize it with neural networks. Despite some empirical success, invariance guarantees often come at unreasonable prices. For instance, CNNs are guaranteed to be invariant to translations only with infinite grids (images) 19 Regarding permutation invariance, Deep Sets is always invariant, but to remain universal it requires a hidden layer as large as the input set [32. Finally, GNNs, as any other computationally efficient graph isomorphism-invarinn architecture, cannot achieve universal approximation. More specifically, achieving graph isomorphism invariance and universal approximation is at least as hard as solving the graph isomorphism problem [5]. In contrast to these results, our work shows that such tradeoff's are usually restricted to the design of deterministic architectures. By accepting probabilistic notions of invariance and universality, we show that under mild data generation conditions we can circumvent these invariance-resource tradeoffs.
Bayesian neural networks. Bayesian Neural Networks (BNNs) incorporate Bayesian in- ference into both training and inference of neural networks. In short, BNNS explicitly assign a prior to the parameters and perform inference with a posterior. BNNs differ from RLCss in how randomness is used. BNNs explicitly model prior and posterior distributions over the weights. This is usually leveraged in the context of confidence estimation. On the other hand, RLCs do not model prior or a posterior distribution over the parameters. Rather, RLCs take samples from a model that uses external randomness. In their essence, BNNs and RLCs trying to achieve different goals. While BNNs are modeling uncertainty over decisions, RLCs are trying to output the correct target with the highest probability they can.
2 Randomized Linear Classifiers
We start by introducing the general class of Randomized Linear Classifiers. Due to universal approximation result, this can be seen as the analogous of a multi-layer perceptron in the context of randomized linear models. In the next sections will introduce the analogous of G-invariant models.
For notation simplicity, we denote the random variable of value with bold letters, e.g., a random variable x would have realization x. We consider binary classification tasks where the input data x is supported on X' = supp(x) C Rd and labeled according to a true labeling function y: X (-1, 1). Therefore, a binary classification task can be summarized by the tuple (x,
Given source of randomness supported U4 supp(u) C Rdd,, and neural network fo: dd... + pd+1 parameterized by 0 E Rdd, an RLC predicts y(x) for E X according
sgu( (ao, x) ba) (gg((fo(w)) lnd a)) So (o(
From above, one can see the coefficients (ao: bo) of the linear classifier given by the pushforward measure fu Finally, unless otherwise stated, we assume so to be a multi-layer perceptron with ReLU activations.
3

---

Analogously to randomized algorithms for decision problems, we can take multiple samples using Equation (T) and make final prediction using their majority. To simplify notation, let define the function of our final prediction taking m samples as
Yo (m) (x) maj({sgn( (aag) .²) b bb )(),)) =
)1.dd x) -aoce)-fffuuu fo
(2)
where each u iid P(u). Note that as take more samples, we approach the mode of the distribution of linear predictions for a given x. We define this value as the limiting classification of xr
which implies the existence of the limiting classifier Fg: I (-1.1] with
Fx) == lim maj({sgu( ((a))((())) ( x) bg )1ار = argmax P P(sgn( (a).z) - -bo) = 9). m 100
(3)
At this point, it is worth noting that although the random prediction (Equation (T) is a linear function, its limiting classifier (Bquation (3)) can induce an arbitrarily non-linear boundary. In fact, we leverage this notion to define the probabilistic version of universality. We say that an RLC is universal in a probabilistic sense if its limiting classifier (Equation (3) universal. It is easy to see that models making deterministic predictions collapse the notions of probabilistic and exact universality. On the other hand, for RLCs to be probabilistic universal it suffices to produce predictions that are biased towards the desired answer on every input, i.e., P(yg (m)) (x) = v(z)) > 0.5, Vz E X.
(x)
In practice we will make random predictions and therefore we need to capture a sufficient sample size m such that we are close to the limiting classifier with high probability. An important measure to understand how large m needs to be is what we call the minimum bias of the RLC. We denote it by and define as the infimum of the total variation distances between the random predictions of every input and random variable with Radamacher distribution. That is.
inf (y (m)) r): E 2).
Put into words, E captures a lower-bound on how close to a random prediction the RLC can be. And, naturally, the closer it is to a random prediction the larger m needs to be such that the majority converges to the limiting prediction. Therefore, our universal approximation result needs to capture how many parameters to m, it does. Before we proceed with our results on m, p and the universality property, we need to define the general class of binary classification tasks consider.
RLC needs to converge to correct answers and how fast, i.e. with respect
Assumption 1 (Tasks with smooth separators). We say that a binary classification task (x, y) admits a smooth separator if there exists a neural network 8: IRd + R. such that y(x) = sgn(( (x))), Vo E supp(X).
Note that due to the universal approximation ability of neural networks, the set of tasks satisfying Assumption 1 is quite large. Moreover, Assumption is sufficient but not necessary condition. We will later prove universality for a wide class of graph problems and we believe many others exist. For now, let us finally state result on the resource consumption and universal approximation of RLCs in tasks with smooth separators.
Assumption 2 (Absolutely continuous randomness source). We say that the randonness source is absolutely continuous if at least one of its coordinates u; S i < dy has an absolutely continuous marginal distribution.
Theorem 1 (Resource consumption of universal RLCs). Let u) be a binary classification task Then, there exists an RLC with newral network
that admits a smooth separator as in Assumption 7 for and absolutely contimuous randomness source u (Assumption ( that is universal in the limit, i.e.,
For = y(æ), Vx E X
and makes random predictions that are correct with probability
P(maj((sgn((aa)) .)) b b ))))))))>>)))))))))))))) = v(x)) 1 1 eexp(=22222
where E is the minimum bias of Fg..
Further, p' is the number of parameters used by a deterministic neural network with one hidden layer to achieve zero-error in the task, So has at most
p pt + O()) parameters.

---

The complete proof is in Appendix|A]Noo Note that Theorem T does not assume or explore any invariance the task. It is a general universality result that we will leverage in our study of invariant RLCs, but of independent interest. One way to interpret Theorem is as a probabilistic version of the classical universal approximation theorem of multi-layer perceptrons [8]. The result on the number of parameters is important to make it clear that RLCs do not need to find a solution more complex than one given by a deterministic model in the supervised learning task.
Until now, we have established the expressive power of RLCs, i.e., that, under mild assumptions, they can be as expressive and resource-eficieen as deterministic neural networks. But, there still the general question: When are RLCs more resource-efficiee than deterministic neural networks? In [27] was constructed an specific task where an RLC (although the authors do not name it as such) uses a constant number of parameters, while a deterministic neural network would need number of parameters that grows with the input dimension. Here, we are interested in more general settings. In the next section we will show a large class of invariant tasks where invariant RLCs are more resource-efficient than their invariant deterministic neural network counterparts.
3 G-invariant Randomized Linear Classifiers
Now, we turn our focus to binary classification tasks that are invariant to compact group transforma- tions. That is, let G' be a compact group with action of g E G' on a E X denoted by g A task (x, 3) is G-invariant if y(x) - y(g 2), Va E X, Vy E G.
easy to see that an RLC that perfectly classifies the task in the probabilistic notion, iee, Fa. (x) y(z), Vz X, will also be probabilistic G-invariant, i... Fe- (z) = Fo. (g z). Yx E X. Vg E G. Thus, if we know that a task G-invariant, can restrict our model class to G-invariant RLCs? At first, the answer is not obvious. We need design principle that guarantees a search space with only G-invariant solutions while at least one of them has zero error. In Theorem 2 we present the result that guides our design of invariant RLCs.
Theorem 2 (G-invariant RLCs). Let (x,z) be G-invariant task with smooth separator in Assumption 7 Then, the set of RLCs with a G-invariant distribution in the classifier weights, i.e.,
ag 9- a,, Vg E G,
and absolutely continuous randommess source (cf. Assumption 2 is both probabilistic G-invariant and universal in (x. y). That is,
Fo(x) = Folg V2 Ve Vg E G.
and
30t E Rp: Fo. y Vo X
The complete proof is in Appendix [A From above, invariant tasks can be cast to the problem of designing universal G-invariant distributions -together with separate (possibly dependent) bias distribution. This design principle differs fundamentally from deterministic invariant representation learning. Here, instead of designing architectures that are G-invariant, we wish to design architectures that induce G-invariant distribution. That is, the RLC neural network fe is not itself G- G-invariantt.
know that designing universal RLCs for
Next, we will define very useful assumption about the data generation process. It will allow to leverage representation results in probability theory to both design universal and efficient G-invariant distributions and allow for variable-size set and graph data.
Assumption 3 (Infinitely G-invariant data). Let Goo be homomorphism of G into the composition of homormophisms of G all finite dimensions, e.g., if G is the set of permutations of (1,.... . d). Go is the set of permutations of N. We say that a task (x, has infinitely G-invariant data if there exists an infinite sequence of random variables (x4) = 9o0 (xx) Vgoo E G where x (x:)ies for S E (a) with (2) being the set of all d-size subsets of N.
Although the above might seem unintuitive, the representation theorems also help us make sense of them. The data generation process will take the same form as our linear weights distribution. As we will see, for sets it means that items are sampled i.i.d. given a common latent factor of the set [9] In graphs edges are also generated i..d. given latent factors of their endpoints and the graph [
5

---

Proposition (Infinitely G-invariant RLCs). Let (x. y) be a G-invariant task with infinitely G- invariant data (Assumption 3
with a smooth separator as Assumption [ Then, the set of RLCs
with infinitely G-invariant distribution in the linear classifier weights, L.e., as in Assumption 3 (as,)== = 9oe [m 4g E Go., where ag _ (ass)ves.for S (a), and absolutely continuous probabilistic G-invariant and universal for (x. y) as in
randomness source (cf. Assumption
Theorem 2
The complete proof is Appendix A Next, we design G-invariant RLCs drawing from results in the representation theory of probability distributions. We consider tasks with set and graph data. In Appendix B we also consider spherical data. For each, we derive conditions for G-invariance and universality, highlighting their resource gain when compared to their deterministic counterpart.
3.1 RLCs for set data
Here we consider tasks that are invariant to permutations, ie., our input is a set of vectors. More formally, we let our input be supported on X' := (I²* y and G := Sym[[d] be the group of permutations of [d] ;= {I..... d}. Then, for an input æ E I' the action g x is given by permuting the d vectors of size k according to
The key insight to design RLCs for set data is leveraging the classic de Finetti's 's theorem 99. In summary, de Finetti showed how any infinite sequence of exchangeable random variables can be expressed as an infinite sequence of i.i.d. random variables conditioned on common latent measure. Now, when Assumption 3 is true, de Finetti tells us that we can sample our weights an by first sampling common noise and use it as input the same function, which generates the linear weights together with an independent noise in an i..dd manner. Note that the bias does not have the exchangeability property. Thus, needs to receive the same shared noise as the set but use different function, since it is not necessarily sampled in the same way. Next, we formalize these notions by defining the class of Randomized Set Classifiers (RSetCs) and characterizing its universal approximation power together with resource consumption.
Definition (Randomized Set Classifiers (RSetCs)). A Randomized Set Classifier (RSetC) uses two neural networks fo,= IR2 + R and 90,- : IR? - R. together with d +2 sources of randomness: (u,) and ut, The random linear classifier coefficients are generated with
d (k) for (u, u.) and be 90, (u,
a8;
(k), is the 7th chunk of k random linear weights, i.e., the weights multiplying the 8th vector. where ae;
Proposition (Universality and resource consumption of RSeCCs). Let (x, y) be a permutation- invariant task with a smooth separator in Assumption Aan infinitely
iintuutationiivariint data as in Assumption 3 Then, RSerCs as in Definition [ with absolutely continuous randomness source (cf. Assumption 2 are probabilistic G-invariant and universal for (x,y) (as in Theorem 2 Further, the number of parumeters needed by RSeICs in this task will depend only on the smallest finite absolute moments of the weight and bias distributions in the zero-error solution, i.e., the ones given by Soy (u, u:) and goy (u, ub).
The complete proof is in Appendix A We highlight that Proposition 2 is combining de Finetti's theorem (9. Kallenberg's noise transfer theorem [16] and recent results on the capacity of neural networks to generate distributions from noise 34
What is the practical impact of Assumption in set tasks? Assumption 3 implies that input set x is generated by first sampling some latent variable e ~ 1/ which is then used to sample items in an i.i.d. manner X1, X..... (eLLi. Pe. We make sense of this with an example in e-commerce systems. If the set represents items in a shopping cart, the latent factor O can be thought of as a summary of the user's shopping behavior. Overall, this assumption is not appropriate if there could be mutually exclusive items in the set.
When are RSetC's better than Deep Sets? We contrast the results of RSetCs with Deep Sets [35] due to its universality and computational efficiency [32]. Overall, other deterministic set models
If the support is discrete we shall consider multisets instead. Note that this does not change the reference d in previous results.

---

are either variations of Deep Sets that inherent the same properties [20 24 or are computationally inefficient [23] Apart from universality. it important to note from Proposition hlow the number of parameters used by the RSetC. does not depend on the set size. Instead, its resource consumption is related to how smooth the distribution of linear classifiers weights and bias are. Since all the weights have the same distribution (conditioned on u), the set size is not relevant. This comes in contrast to Deep Sets, which as shown in (32 only achieves universality when the hidden-layer and the input set have the same size.
Moreover, Deep Sets is known to have poor set size generalization abilities, L.e. when the test set contains larger sets than the training set [3T] In RSetCs, although the number of parameters does not depend on the set size, the distribution of linear coefficients can use this information. Overall, the gain in robustness to set size might come from RSetCs performing simple linear transformations of the input. That is, for small changes the set size, the output is not expected to change abruptly. This opposes to Deep Sets, where the representations of the items are aggregated and input to a neural network. Thus, any small addition to the set can arbitrarily change the output. Although we cannot always guarantee size generalization for RSetCs, we give empirical evidence in Section 4 that they do seem to be a lot more robust than Deep Sets.
3.2 RLCs for graph data
Here we consider tasks that take graphs as input. Given (possibly weighted) graph G (V, with d vertices and M edges, we take as input vector of size de representing the vectorized adjacency matrix of G. Our invariance is then to graph isomorphism. That is, we again have the permutation group G Sym(ld), but now with different action. Here g x jointly permutes the rows and columns of the adjacency matrix corresponding to x. This way, z and z represent isomorphic graphs. We will then assume that our graph tasks are G-invariant, i.e., two isomorphic graphs x, g will always have the same label.
Hoover's theorem, the analogous of de Finetti's theorem for joint exchangeability in 2-dimensional arrays. It gives us a model, invariance and universality results analogous the ones for RSetCs.
Now, can leverage
Definition 2 (Randomized Graph Classifiers). A Randomized Graph Classifier (RGraphC) uses two neural networks foy: R + R. and go, - IR together with d2 + d 1 sources of randomness: u.
(u (1) d
(e) )=rr (u Jaje(ay and us- The random linear classifier coefficients are generated with
d fey u,
(e)
and ba c fo, (u, Mb).
abij
, . "ij
where assz is the random linear weight multiplying the entry of that corresponds the entry in row i and column j of the graph's 's adjacency matrix.
Note that we can use the same proof of Proposition 2 and have an equivalent result for RGraphCs. However, since graphs are discrete objects the smooth separator assumption (ef. Assumption I might not be so easily satisfied. To address this, we define a sufficiently large class of graph models that RGraphCs can approximate.
Definition 3 (Inner- product decision graph problems). Let G = (V,E) be a graph over d vertices with vectorized adjacency matrix x E X == supp(x) S I.d. We say that a graph property y: X - 1-1,1} is an inner product verifiable property if there exists a set of vectors S C d.d and a constant E R such that:
For all graphs x+ E X satisfying the property y(x*) = 1, there exists E S, such that (8, x+) 2 b:
For all graphs x= E not satisfying the property u(x = 1, we have (x", < b, Vo S.
As an example of such property, consider connectivity. The set S above is defined to be the set of all binary vectors representing adjacencies of spanning trees. The threshold in this case would be d 1. If G is connected, then there exists spanning tree for G. When taking the inner product of x and the vector s E representing the spanning tree, the result would be the number of edges in the tree, which is d --11 1. In contrast, if G is not connected, it does not have a spanning tree. This means that for all vectors in S, the inner product (s',x) is less than d - 1. We can use the same logic to show that properties arising from NP-complete problems such independent set, or simple ones that GNNs
7

---

cannot approximate, such as diameter, girth and connectivity are all encompassed by Definition 3 We are now ready state the probabilistic invariance and universality result for RGraphCs.
Theorem 3. Let (x. y) be a graph isomorphism-inven iiniiiiiinni task that either i) has a smooth separator as in Assumption orr ūi) is an inner-product decision graph problem as in Definition [ Further, the task has infinitely graph isomorphism-inven invariant data as in Assumption 3 Then, there exists an RGraphC as in Definition 2 with absolutely continuous randomness source (cf. Assumption 2 that is probabilistic G-invariant and universal for (x. y) (as in Theorem 2). Further, the number of parameters of this RGraphC will depend only on the smallest finite absolute moments of its weight and bias distributions, i.e. the ones given by fe, (u, U;) and 9o, (u, Uv).
The complete proof is in Appendix A The main insight behind Theorem 3 is using techniques from randomized algorithms to derive the universality of RLCs in the graph tasks from Definition 3 The other results follow the same line as Proposition 2 while replacing de Finetti's with Aldous-Hoover's
theorem.
What is the practical impact of Assumption 3 in graph tasks? Janson and Diaconis 15] showed that Assumption is equivalent to having the input graphs sampled from graphon model. For the reader unfamiliar with graphons, this class encompasses from simple random graph models like G(n, p) 112) to modern matrix factorization methods in recommender systems [29]. Moreover, this assumption has been recently used to design representations that are invariant to graph size, see
When are RGraphCs better than GNNs? We contrast the results of RGraphCs with GNNs
22 26
due its widespread use, empirical success and computational efficiency. A known issue with GNNs is its inability to approximate simple tasks such as graph connectivity [14]. This comes from the fact that GNNs cannot distinguish simple non-isomorphic graphs such as any pair of d-regular graphs. As such, GNNs cannot universally approximate tasks that assign different labels to any of such pairs. In contrast, RGraphCss can approximate any problem that either has smooth boundary or can be tested with an inner product as in Definition 3
Note that can always define task following Definition Ijtnt distinguishes between specific graph and any other non-isomorphic input. Thus, unlike deterministic models, the set of tasks RGraphCs can solve is not attached to solving the graph isomorphism problem. It is simply attached to whether the decision problem can be tested with an inner product. Note that this does not imply that our model solves the graph isomorphism problem. To do so, we would need to test on an exponential number of tasks. The main implication of this observation is that the expressive power of probabilistic graph models is not attached to the ability distinguish nom-osomopphic graphs, but to the task's 's complexity. Thus, we are not doomed to fail at simple tasks like GNNs. Finally, note that GNNs aggregate messages using Deep Sets (or some variation of it). Thus, its approximation power, even for graphs that it can distinguish, requires number of parameters that grows with the graphs' number of vertices.
Finally, we highlight that there exist more expressive, but still non-universal, models such as higher- order GNNs (22 and subgraph GNNs 7 However, they suffer from heavy use of computational resources and are restricted to smaller, but existent, set of non- non-isomoiphic graphs it cannot distinguish. As such, they suffer from the same aforementioned problems as GNNs.
Experiments
Until now, our theory characterized the model space of invariant RLCs. It is natural to wonder whether such guarantees translate into practice. Concretely, we focus on investigating three questions related to our theoretical contributions.
Q1. Are RSetCss more parameter-efficiient than Deep Sets in practice? (cf. Proposition 2
Q2. Are RSetCs more robust than Deep Sets with out-of-distribttion data? (cf. discussion in Section 3.1]
Q3. Can RGraphCs efficiently solve tasks that GNNs struggle in practice? (cf. Theorem 3)
Sorting task. To address Q1 and Q2, we consider the sorting task proposed in [32]. Our input is
given by x, supp(x) = Rd x; ~ NO, 1) for some odd number of dimensions and the labeling function by y(x) = if for vector w, w; == (-1)++1 we have w" soortxx) 2 0 or -1 otherwise. We chose this task since it was shown in 32 that Deep Sets needs a hidden-layer least as large as the input set (d) to approximate it with zero error. Thus, to showcase the parameter efficiency of
8

---

RSetCs in practice (cf. Proposition 2 we test both models in this task, while fixing the hidden layer at on both. To make the results comparable, we train RSetC's with a single hidden layer (in both networks) and Deep Sets with a single hidden layer in each of its networks as well. Finally, to answer Q2 we test both models on sets twice as large as the ones used in training.
Sign task. We would also like to investigate Q1 in a setting where Deep Sets is not supposed to struggle. That is, we would like to know whether RSetCs can be more parameter--fficient in tasks that are (supposedly) easy for Deep Sets. For this, we consider the sign task y(x) == sgn Di= (x.()x)) with X, ~ (0, 1). Note that the networks in Deep Sets would need to simply learn the sign function and thus its parameters should not depend on the set size. To showcase the parameter efficiency of RSetCs, we consider Deep Sets with one and two hidden layers (in both networks) while keeping RSetCs with a single hidden layer. The rest of the experimental setup follows the sorting task verbatim.
Connectivity task. We chose the task of deciding whether graph sampled from a G(n, p) model with 1.1- log(n)/ / is connected or not. Unlike RGraphCs, GNNs provably cannot approximate this simple task [14]. By comparing the performance of GNNs and RGraphCs in this task, we can empirically verify Theorem 3 Moreover, in contrast to GNNs, Theorem 3 tells us that the required number of parameters
RGraphCs is not attached to the graph size. Hence, we also test the performance of both models in this task while increasing the size of the input graphs and keeping hidden layer sizes fixed to 2 in both models. To make results comparable, we use a GNN with 3 layers and an RGraphC with 3 hidden layers of size in each network. Since in each GNN layer there are two network layers, the parameter sizes in the GNN and in the RGraphC are comparable.
Experimental setup. We used the Deep Sets architecture as proposed in the original paper [35]. For the GNN, we used the GIN [33 architecture, which completely captures the GNN properties mentioned in Section 3.2 Finally, to give perspective on how bad model is performing, we also contrast the results with a constant classifier, ie., how a classifier that always predicts the most common class performs. All models were trained with Pytorch (25) using Adagrad [10] for maximum of 1000 epochs with early stopping. The reported results in Figures [ and 2b are with respect to five runs. The training sets consisted of 1000 examples, while the the validation and test sets contained 100 examples. We detail the hyperparameters and their search in Appendix C
A1 (RSetC parameter efficiency). In Figure Ta we see the (test set) results for RSetCs and Deep Sets when varying the size of the input for fixed hidden layer. We note that even in the first task, d = 5, when Deep Sets is supposed to approximate the task well it fails to generalize. Overall, for all input sizes we can see RSetCs consistently outperforming Deep Sets. On the other hand, most of the tasks Deep Sets performs similarly or even worse than a constant classifier. Finally, in the sign task from Figure 2a we see that the performance of a single hidden-layer RSeIC is closer to a two lidden-layer Depe Sets, showing its parameter efficiency even in tasks where Deep Sets is supposed to efficiently succeed. Thus, we can verify Theorem 2
and Proposition in practice.
2
A2 (RSetC out-of-distribution robustness). We can see in Figure Ib how RSe(Css provide consis- tently better results than Deep Sets when tested in sets twice the size as the ones used in training. This provides evidence to the size generalization discussion in Section We can see that RSetCs perform even similarly to the in-distribution case, while Deep Sets is consistently worse than a constant classifier. Moreover, the high variance in Deep Sets' results confirm our observation in Section about its sensitivity.
A3 (RGraphC universality and parameter efficiency). In Figure 2b we can see the results for RGraphC's vs. GNNs in the connectivity task. We note how the lack of expressive power coupled with the parameter inefficiency of GNNs is reflected in its poor performance, that decreases as the input size increases. In contrast, Theorem is confirmed by RGraphCss better performance even when the input size is increased (and the number of parameters is fixed). Finally, just as in Deep Sets we note a very high variance in the GNN results. This is often observed in tasks where there is no continuous features in the input, see e.g., 77
5 Conclusions
Our work established the first class of models that leverages randomness to achieve universality and invariance binary classification tasks. We combined tools from randomized algorithms and probability theory in our results. By leveraging this new principle, we were able to present resource-
9

---

f
0.-
Teep Sete Gondaee chudftr
Dora Docatiant cimite
50
100
Set aco
Boc
(b) Results using test set containing sets twice the size of the ones used in training.
(a) Results with in-distribution test
Figure I: Results for the sorting task. We use a fixed hidden layer size of in both models, while varying the training input size. The mean accuracy, together with standard deviation values, is reported using five runs.
GNY Conteet cheitte
0.
0.6
Dherp Sette (1 Lipee)
Dhepp Srie 22 liever
0.4
12
(a) Results for the sign We fixed hidden layer size of in both models, while varying the training input size. The mean accuracy. together with standard deviation values, is reported using five
(b) Results for the connectivity task. We use a fixed hidden layer size of 2 in both models, while varying graph size. We report mean accuracy and standard deviation five
Figure 2: Results for the sign (set) and the connectivity (graph) tasks.
efficient models that, under mild assumptions, are universal and invariant in a probabilistic sense. This work can be extended in many different ways, e.g., designing architectures for other group invariances, such as SO(n) or designing specific optimization procedures for RLCs. It is also interesting to understand the practical benefit RLCs and their invariant counterparts in real-world tasks.
Acknowledgements
We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), RGPIN-2021-03445 and of the Hasso Plattner Institute. L. Cotta is funded in part, by postdoctoral fellowship provided by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. This work was done in part, when G. Yehuda was visiting the Simons Institute for the Theory of Computing.
References
[I] Aldous. D. J. (1981). Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11(4):581-59) -98..
10

---

[2] Bevilacqua, B., Frasca, F, Lim, D., Srinivasan, B., Cai, C., Balamurugan, G.. Bronstein, M. M.. and Maron, 1. (2022). Equivariant subgraph aggregation networks. In International Conference Learning Representations.
[3] Bevilaequa, B., Zhou, Y., and Ribeiro, B. (2021). Size-invariant graph representations for graph classification extrapolations. arXiv preprint arXiv:2103.0504.
[4] Bronstein, M. M., Bruna, J., Cohen, T., and Veličković, P. (2021). Geometric deep learning: Grids, groups. graphs, geodesies, and gauges. arXiv preprint arXiv:2 13478.
[5] Chen, Z., Villar, S., Chen, L.. and Bruna, J. (2019). On the equivalence between graph isomorphism testing and function approximation with GNNs. In Advances in Neural Information Processing Systems, pages
[6] Cohen, T. and Welling, M. (2016). Group equivariant convolutional networks. In International conference machine learning, pages 2990-2999, Pmir.
[7] Cotta, L.., Morris, C., and Ribeiro, B. (2021). Reconstruction for powerful graph representations. Advances in Neural Information Processing Systems, 34.
[8] Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4))303-314
[9] De Finetti, B. (1929). Funzione caratteristica di un fenomeno alcatorio. In Arri del Congresso Internazionale dei Matematici: Bologna del 3 al 10 de settembre di 1928, pages 179-190.
[10] Duchi, J., Hazan, E., and Singer, Y. 12011)).. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7).
[11] Elesedy, B. (2022). Group symmetry in pac learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning.
[12] Erdos, P., Renyi, A., et al. (1960). On the evolution of random graphs. Publ, Math. Inst. Hung. Acad. Sci, 5(1):17-60.
[13] Freedman, A. (1962). Invariants under mixing which generalize finetti's theorem. The Annals of Mathemutical Statistics, 33(3):916-923.
[14] Garg, V., Jegelka, S., and Jaakkola, (2020). Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419 -430. PMLR.
[15] Janson, S. Diaconis, P. (2008). Graph limits and exchangeable random graphs Rendiconti di Matematica e delle sue Applicazioni. Serie VII, pages 33-61.
[16] Kallenberg, O. (1997). Foundations modern prohability, volume 2. Springer.
[17] Kipf. T. N. and Welling, M. (2016). Variational graph auto-encoders. NIPS Workshop Bayesiun Deep Learning.
[18] Kipf, T. and Welling, M. (2017). Semi-supervised classification with graph convolutional networks. In International Conference Learning Representation.
[19] Kondor, R. and Trivedi, S. (2018). On the generalization of equivariance and convolution neural networks to the action of compact groups. In International Conference on Machine Learning, pages 2747-2755. PMLR.
[20] Lee, J., Lee. Y., Kim, J., Kosiorek, A., Choi, S., and Teh, Y. W. (2019). Set transformer: A framework for attention-based vermutation-invarian neural networks. In International conference on machine learning. pages 3744-3753 PMLR.
[21] Leshno, M., Lin, V. Y., Pinkus, A., and Schocken, S. (1993). Multilayer feedforward networks with a nonpolynomial activation function approximate any function. Neural networks, 6(6):861-867,
[22] Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, J. E., Rattan, G., and Grohe, M. (2019). Weisfeiler and Leman go neural: Higher-order graph neural networks. In AAAI Conference Artificial Intelligence, pages 4602-4609.
[23] Murphy, R. L., Srinivasan, B., Rao, V., and Ribeiro. B. (2019). Janossy pooling: Learning deep permutation- invariant functions for variable-size inputs. International Conference on Learning Representations.
(24] Ong, E. and Veličković, P. (2022). Learnable commutative monoids for graph neural networks. arXiv preprint 2rXiv:22/2.0884///
[25] Paszke, A., Gross, S., Massa, F,, Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, I.., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. In Advances in neural information processing systems, pages 8026-8037.
[26] Scarselli, F., Gori, M.. Tsoi, A. C., Hagenbuchner. M., and Monfardini, G. (2009). The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80 808
11

---

[27] Sieradzki, Y.. Hodos, N., Yehuda, G.. and Schuster. A. (2022). Coin flipping neural networks. In International Conference Machine Learning, pages 20195-20214. PMLR.
[28] Simon, B. (1996). Representations of finite and compact groups. American Mathematical Soe.
[29] Srinivasan, B. and Ribeiro, B. (2020). On the equivalence between positional node embeddings and structural graph representations. Iclr.
[30] Upfal, E. and Mitzenmacher, M. (2005). Probability and computing.
[31] Velickovic, P., Buesing, Overlan, C., Pascanu, R., Vinyals, O., and Blundell, C. (2020). Pointer graph networks. stat, 1050:11.
[32] Wagstaff, E., Fuchs, F. B.. Engelcke, M., Osborne, M. A., and Posner. I. (2022). Universal approximation of functions on sets. Journal of Machine Learning Research, 23(15)):1-55.
[33] Xu, K., Hu, W., Leskovec, J. and Jegelka, S. (2019). How powerful are graph neural networks? In International Conference Learning Representations.
[34] Yang. Y., Li, Z., and Wang. (2022). On the capacity of deep generative networks for approximating distributions. Neural Networks, 145:1444155.
[35] Zaheer, M., Kottur, S., Ravanbakhsh, S., Poczos, Salakhutdinov, R. and Smola, J. (2017). Deep scts. Advances in neural information processing systems, pages 3391-3401.
12

---

A Proofs
Theorem 1 (Resource consumption of universal RLCs). Let (x. y) be a binary classification task that admits smooth separator as in Assumption [ Then, there exists RLC with neural network for and absolutely continuous randomness source (Assumption
2 that is universal in the limit, i...
Fe. (2) v(œ), Vx X,
and makes random predictions that are correct with probability
P(maj( (rmaj([sgn((ee) (sgn((a 2)) // ))=))>>>>> v(z)) > ex
where is the minimum bias of Fer.
Further, if is the number of parameters used by deterministic neural network with one hidden layer achieve zero-error the task, fo has most
p PSp' + ((1) parameters.
Proof Theorem Since Assumption holds there exists single hidden-layer neural network N that, in this task 8
like 8, achieves linearity of this network (21). Putting it all together, there exists a number hidden units and parameters by, E R, wy E 12d for l,..., M such that
Further, since sgn is nonpolynomial, we it the non-
N(x) = Σ og sgn((g b₂);
N(x) =gg=s))ns()))) X.
Note that this means we can achieve zero-error in classification, ((x) = y(z), Ve E X. Having this in mind, we will now show that for network N constructed as such, we can build a limiting classifier Fo equal to it. Let first note that we force positivity in the output weights of N by doing
ds os sgn(a;)
w/y wy sgn(o;)
without changing the classification
(ysgn((w5, b;)) sgn
dfsgu(luus b;)), Vx E X.
Further, note that we can also multiply the output weights by the constant EØ= of without changing the sign thus classification, Overall, we can define network N* equivalent classification with
N*)x)
d'sgn((w// b,).
Now, note that the limiting classifier can be written Fo(x) ([ by sgn( (ao. ba)). We then define its distribution as one samples from the weights and bias w/. by with probabilities according to DdL of oj. This implies that (x) N (z) (xx, making Fa achieve zero-error in the task. Note that pt : M is the number of parameters in can generate the lincar coefficients in Fo Fo(x) with at most + O(1) simply take the external noise from uniform distribution and map it to the probabilities in the output layer pick the coefficients.
Finally, note that we have to also characterize the probability that y (m) outputs different answer from Fa. The common tool for this is Hoeffding's inequality, which lets upper-bound it for some x E X with
P(y!" (m)) + Fo()) S exp 2s 2
where c p(y!")) Fo(=)) - 0.5. Note that e depends on xr and our definition the minimum bias the main text is precisely the lowest of all such E.. Thus, as stated we finally have that for æ
P(y!") Fz))
exp(-2=²m2
Note that the above is true for any Fo, including the universal and invariant ones later discussed the main text.
Further taking the usual assumption that X' is compact.
13

---

Theorem 2 (G-invariant RLCs), Let (x. y) be G-invariant lask with smooth sepurutor in Assumption Then, the of RLCs with G-invariant distribution the classifier weights, i...
ag d 9 ag. Vgg E G,
and absolutely continuous randomness source (cf. Assumption 2 is both probabilistic G-invariant and universal in (x, y). That is,
Fo(x) = Folg 2) Vor G
and
30 RP: Fa- (1) ((x), Vo E.
Proof of Theorem Let us start with Proposition B a central observation needed in Theorem Put words Proposition Sasays that we can transfer the action of G to the weights of the linear classifier. For the reader more familiar with group representation theory, the result follows immediately from noting that compact groups admit unitary representations, see (28) for a good resource on the matter.
Proposition 3. If a compact group and g x is an action of Gnnn x E RR, there exists a bijective mapping a: - such that
(g w) = (1r, a(g) w)) VX, R E.
finite-dimensional vector space, the action of g can be associated with linear representation p of G. iee. p(g) E Rdxd That is, if [xr] is the column vector of x, we have that [z))[z) z. Now, since G is compact and R is dimensoimessinnl,, G also admits a unitary linear representation Pu. with associated action -u- Then, it is easy see that
Proof. Since we are dealing with actions
6g u w) = (p=()) w) = (z, (o) [w]) = (x, [w]>, Vi E IR..
Thus, since inversion defines bijection on G. Proposition 3 hoolds for the unitary representation action. Now. note that any other group action- "u defines a homomorphism between and the symmetric group of R Then, for any other action there exists a bijective function 8: G G such that g B(g) " 2, Va E Rd Henee, we can write
(g x. w) = (B(g) 'u I. w) = (B(g) "n ". w) = (8- (B(g)-1) x, ws. Va. w E R Vg E G. Finally, since 8 and group inversion are bijective, we finish the proof by defining the bijective mapping a(g) = 10 (8(g)=1 for every g G.
Now, we can proceed to prove the universality part of Theorem 2 Since the task admits smooth separator, there exists a universal limiting classifier Fo for it. That is, for every x E X
Fo(z) = y(*).
Since the task is G- --iivariant, we know that for every 9 E
Fo(x) = vlg xx).
Note that since G is compact, it admits unique normalized Haar measure considering random group action g ~ X. By Fubini's theorem and Proposition we have
Then, the insight comes from
Fo(x) = F. (o x:] = sgn (ggnTT (Tgay, by [sgn( (z, (g) ao) bo)])-
Now, we define limiting classifier Fgr that samples coefficients according to b - bo and From ahove, we know that Fo- (œ) = (a)), Var X. Since Fø is universal, For is also universal. Finally, since g sampled according to the Haar measure, we have that
d g ag-
ag- as- Vg E G.
At last, it is easy to see from Proposition Iatittioonnhaa that the action on the weights can be transferred to the input as well, meaning that every model is probabilistic invariant, i.e., Fo(x) = Folg u), Vr E X, Vy E G, vo e R", which finalizes the proof.
O
Proposition (Infinitely G-invariant RLCs). Let (x, y) be G-invariant task with infinitely G-invariant data
(Assumption By with smooth separator as in Assumption 7 Then, the set of RLCs with an infinitely G-imvariant
distribution in the linear classifier weights, i.e., as in Assumption 3 (ae:) d 9:0 (as:) Vg Goe.
where as & (as.)iEs, for E (a), and absolutely continuous randomness source (ef. Assumption probabilistic G-invariant and universal for (x. y) as in Theorem
'The reader can think of X uniform distribution over G.
14

---

From Proposition it also follows that the model is G-invariant. Let us proceed to prove is universal. Since the task admits smooth separator, from Theorem there exists RLC Fa such that
0, for 5' E [N(I,.....)) Proef of Proposttio 1
E (F x(x) =0 Since the data infinitely G-invariant, we have that for the infinite G-invariant sequence (xi)
N d
[xF((x) - vx)] = (Fo())es(Fo(())eeeee -ip0-----oe v((x))i=s) = 0, for S E
with (a) being the set of all d-size subsets of N. Let À he the unique normalized Haar measure of G. As in
the proof of Theorem 2 we can take random group action g ~ X and have from Proposition 3 and Fubini's
theorem that
( v((x))ess) = Eeiseeehee eFolg ((x))es)))
0, for S E
Now, let us define task (x', y) on higher dimension d' 2 d, supp(x) C supp(x') C Rd where y(x') v(x(p..4) (...)) Further, g' is a random group action (sampled from the Haar measure) from G", the homomorphism of G into the dimension d'. From above, together with Proposition 3 we have that
Eis (Fo((x))ess)) - u((xx)<es=) = (r( (F ((x))eSs))
B((s))ccs) ses (sgn (Eag, (2), bb)])
d'
Now, from above, since the lower dimensions (1...., n G-invariant if all higher dimensions G-invariant, is easy to see that there is an infinitely G-invariant sequence weights (as,)?= 1 that achieves zero error.
Proposition 2 (Universality and resource consumption of RSetCs). Let (x. y) be a permutation invariant task with a smooth separator in Assumption [and infinitely conuutaationinvariin data Assumption 3 Then, RSetCs as in Definition] [ with absolutely continuous randomness source (cf. Assumption 2) are probabilistic G-invariant and universal for (x, y) (as in Theorem 2}. Further, the number of parameters needed by RSetCs in this task will depend only on the smallest finite absolute moments of the weight and bias distributions in the zero-error solution, i.e, the ones given by for (u, u.) and goz (u, ub).
Proof of Proposition 2 The result follows directly from the combination of de Finetti's 's theorem 99, Kallen- berg's 's noise transfer theorem [16] and the recent results the capacity of neural networks generate dis- tributions from noise (34). Let us outline it in more detail. From de Finetti's 's theorem ( we know that any infinite sequence exchangeable random variables can be expressed by i..dd. random variables conditioned on a common latent measure. Combining this with Kallenberg's noise transfer theorem we have that the weights and biases can be written as fu, u:) and g(u, us) where f.g measureable maps and the noises are sampled from replace the uniform noise with absolutely continuous noise and f.g g with sufficiently expressive ReLU Malli-layer perceptron. Moreover, Theorem 2.1 (34] says that the number of parameters depends only on the output dimension and the smallest finite absolute moments of the distributions. Since the output dimension l is constant for us, it depends solely on the latter and we finalize the proof.
uniform distribution. Finally, the work of [4] showed that
Theorem 3. Let (x, y) graph isomorphism-imvane invariant task that either i) has a smooth separator as in Assumption 7 or ii) is an inner-product decision graph problem as in Definition 3 Further, the task has infinitely graph isomorphism-
iirriiiiii--miiiatttttt invoriant data as in Assumption 3 Then, there exists an RGraphC in Definition 2 with
absolutely continuous randonness source (cf. Assumption 2 that is probabilistic G-invariant and universal for (x, u) (as in Theorem[). Further, the number of parameters of this RGraphC will depend only on the smallest finite absolute moments of its weight and bias distributions, i.e., the ones given by Jo, (u, u.) and ge, (u, un).
Proof of Theorem 3 Note that it suffices to show that there exists an RLC that takes as input graphs of size d and decides correctly tasks in Definition 3 with probability > 0.5 this implies universal limiting classifier
15

---

Fe. Then, can replace the smoothness assumption in Theorem and Proposition I with Definition B and we will have that there exists infinitely jointly exchangeable sequence that universal for tasks in Definition Finally, we follow Proposition 2 proof by simply replacing Finetti's is with Hoover's theorem. Thus, let us now proceed to prove the main part of this thcorem, í.e., there cxists an RLC that takes as input graphs of size d and decides correctly tasks in Definition 3 with probability >> 0.5.
Define an RLC that samples the lincar coofficients as follows.
Let al be a random variable such that (app(ab) = S. It is important to note that we do not require that this random vector to have the same distribution the input, or any other distribution on S. We simply need it be supported on S.
Now, let t ~ Bernoulli + y) for some > O. We define ag == t aa and and ba = t b. Our random prediction can then be rewritten as sgn(t- ((#6) 2) b)).
Let us now calculate our probability of success. For convenience, let define sgn(0) of a positive graph xt i.e. y(x*t = 1, being classified correctly is
Then, the probability
Pasgn((as, x*) bo) 1) P(sgn(t- ((ab, x b))
0.5 7 + P((ab. x) 2 b) (0.5 + 7).
while the probability of a negative graph x i..., y( = - being classified correctly is bo) = =1 P(sgn(t ((ab) x. b))
P(sgn((a0,
0.5 +
Then, since X is finite set for any imput distribution there exists a constant y where < 7/ + P( æ) 2 6) for all x E X. Given such gamma, every input has a probability of success greater than 0.5. which implies that Fo(z) = y(ø), Var E X' as we wanted to show.
B RLCs for spherical data
Here we want to show how the same ideas presented in Sections and 3.2 can be applied to spherical data using Freedman's 's theorem 13). More specifically, we let our input be d- dimensioonal vectors, i.e., supp(x) C R' and task invariant to the orthogonal group, i.e. v(z) v(g 2²), Ve supp(x), Vy G. where G = O(d).
and
We refer tasks like this tasks over spherical data since it invariant rotations and reflections.
Just as de Finetti, Aldous and Hoover informed ahout and graphs, Freedman did for spherical data [ follows from his work that an infinite sequence invariant to the action the orthogonal group can be represented as a random scalar multiplying a sequence of i.i.d. standard Gaussian distrihutions. Leveraging this, we can define the following very simple invariant model for spherical data (assuming Assumption 3
Definition (Randomized Sphere Classifiers). A Randomized Sphere Classifier (RSphereC) uses 2 neural networks fo, I2² - R and ga, R² - I2 together with 3 sources of randomness: u, un and us. The random linear classifier coefficients are generated with
d fo, u.) (N(0, (),0..(((,, 1),, and by go, ub).
where [N(0, .(0,
1)] is a vector of i.i.d. standard Gaussians.
Proposition 4 (Universality and resource consumption of RSphereCss. (x, v) be O(d))-nvariin task with a smooth separator as A Assumption Ma and infinitely spherical data as in Assumption 3 Then, RSphereCs as in Definition with absolutely continuous randomness source (cf. Assumption ( are probabilistic G-invariant and universal for (x, y) (as in Theorem 2 Further, the number of parameters needed by RSphereCss in this task will depend only on the smallest finite absolute moments of the weight and bias distributions in the zero-error solution, ie., the ones given by foz (u, u:) and goz (u, un).
Proof. The proof is exactly the one from Proposition 2 but replacing de Finetti's theorem with Freedman's 's [33. For clean and more accessible material on Freedman's thenrem, we refer the reader to the lectures by Kallenberg in mtthttss////mittii
acience uottava. ca/ wwt..aaa/aaaa... givaanfffff/////gooooomo......aa / wwwpanffwwwaaalleeerrrraee pdf
Finally, we note that tasks invariant Onn) are not that common. However, tasks invariant to SO(n) are extremely relevant in computer vision, see 6 Therefore, think this model is first step towards probabilistic invariance for SO(n
"This can done by always adding sufficiently small constant to the input. 'Note that (O(n) is the connected component of O(n).
16

---

C Implementation Details
As mentioned in the main text, all models were trained for maximum of 1000 epochs using a cosine annealing scheduler for the learning. We tuned all the hyperparameters
Deep Sets models found better learning rate of 0.001 and batch the validation set using patience of 30. The of 250. The GNN model found better learning rate of 0.01 and batch size 100. The RSetC model used a batch size of 250 and learning rate 0.5. The RGraphC model used batch size of 100 and a learning rate of 0.5. Finally, we also note that RLCs can out put different answers given the same weights (due to the random input). Thus, we amplify each mini-batch with 1000 samples for each model we noted that this reduces the variance and helps convergence. The amplification size used test was m 10. Finally, for all RLCs we used a single dimensional standard normal distribution each of their noise sources.
Source code available at: http:///hhhh...ooooo/oocc//////t
17


Reviews:
[{"review_id": "q2GWcn5rXv", "reviewer": "Reviewer_EYc5", "summary": "This work proposes a framework called Randomized Linear Classifiers (RLCs) that leverages external randomness to build models that are expressive and can encode invariance in the input space. The authors establish probabilistic versions of universal approximation theorem and invariance for several types of RLCs. The key insight from the theory is that by maintaining probabilistic universal approximation and invariance, RLCs can be more parameter-efficient than their deterministic counterparts. Numerical experiments verify the theoretic properties.", "questions": "It would be interesting to see how the external randomness affects the generalization performance of RLCs.", "limitations": "NA", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well-written and explains the implications of the assumptions and theorems clearly.\n- RLCs extend the idea of Coin-Flipping Neural Network with stronger theoretic backgrounds and more general formulations and invariant extensions.\n- The probabilistic notions of universal approximation and invariance potentially open up a new direction.", "weaknesses": "- I am not so sure about the benefits of \"Online computation\" and \"Private computation\". What is the difference between standard online inference and RLCs? In the inference phase, the client downloads the model and computes the prediction without sending the inputs, so it is already private.\n- I am not sure how the external randomness would affect the generalization performance of RLCs. From the theorems, it seems that the only requirement for the randomness source is to be absolutely continuous, thus MLPs can universally approximates? In the experiments, the external randomness was fixed as standard normal. I assume that the distribution of the external randomness would greatly affect sample complexity? For example, RLCs may require more restarts to amplify the probability if a bad external randomness is used? I think this part needs some further discussion.\n- In the numerical experiments, the performance of DeepSets looks pretty bad, even worse than using a constant predictor. Is this normal? It would be more convincing if RLCs was examined on tasks that DeepSets performs good.  \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. Please, refer to our feedback summary where we address your questions about the randomness distribution and the deep sets comparison. If you have any extra input, we would be very happy to discuss.\n\n>I am not so sure about the benefits of \"Online computation\" and \"Private computation\". [...] What is the difference between standard online inference and RLCs?\n\nThe benefits are in terms of resource consumption. In standard online inference, one can ideed send (or store) the model, but this can be arbitrarily large. In our case, we simply need to send (or store) the pre-sampled linear coefficients. As we say in the private computation paragraph, this can be very useful in settings with low-resource computers, e.g., smartwatches."}, {"review_id": "yRk68Husaz", "reviewer": "Reviewer_2JHn", "summary": "The authors introduce Randomized Linear Classifiers, which are a way to randomly represent the weights of a linear classifier. Because there is a random reconstruction of the network, a sample majority of which is used to determine the actual inference of the network. The authors show a universal representation theorem for such a classifier, and show that the representation is quite efficient in some cases (for instance, sometimes the number of parameters needed does not scale with a relevant quantity, in which a deterministic network would scale).", "questions": "Typos in line 219, 287.\n\nAs a sanity check that I have understood this, you dont have access to the true gradients for $\\theta$ until $m \\to \\infty$ right?\n\nIs this similar to learning a one layer NN in which during training and inference some random subset of neurons is used each time (for forward and backward passes)?", "limitations": "None", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The notion that the number of parameters needed for $f_\\theta$ can be much smaller than the number of parameters needed for a classifier that is a deterministic neural network is nice.", "weaknesses": "From what I can tell, the paper only considers the expressivity of RLCs, and the number of parameters needed. Is there a result about learning $f_\\theta$? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for reviewing our paper. Next, we address your comments. Please, let us know of any additional feedback you might have. We would be very happy to discuss.\n\n> \"From what I can tell, the paper only considers the expressivity of RLCs, and the number of parameters needed. Is there a result about learning $f_{\\theta}$?\n\nOur work address the well known computational resources vs. model capacity tradeoff in invariant models. We note that even in deterministic invariant learning the question of generalization/learnability is still to be understood, see for instance https://openreview.net/forum?id=HxeTEZJaxq\nWe believe that our probabilistic view on the problem can, in a future work, shed new light into the generalization capabilities of invariant models.\n\n> \"As a sanity check that I have understood this, you dont have access to the true gradients for $\\theta$ until $m \\to \\infty$ right?\"\n\nYes, we have gradient samples.\n\n> \"Is this similar to learning a one layer NN in which during training and inference some random subset of neurons is used each time (for forward and backward passes)?\"\n\nYes, this is precisely the idea behind the proof of Theorem 1 as you can see in the appendix."}, {"review_id": "NUUTx8TrOm", "reviewer": "Reviewer_QYFX", "summary": "This work presents a very interesting method for training efficient invariant classifiers by leveraging randomness. More precisely, it proposes to train a neural network to sample linear classifier weights, by pushing forward some data-independent distribution, and using the majority vote over sampled classifiers to make predictions. It is rather a theoretical paper which proves universal approximation and G-invariance theorems for this class of classifiers (adapted to the probabilistic setting). The special cases of set and graph invariance are studied (with relaxed assumptions). Spherical data is also addressed in the appendix. A few toy experiments illustrate the theoretical results proved.", "questions": "See questions above.", "limitations": "A few limitations are discussed throughout the paper, but not very thoroughly. A major limitation for now is that this is a very preliminary study showcasing the new method only on toy binary classification problems. Although one cannot expect it to address all research questions in a single paper, some directions on how the proposed approach could have practical use would be welcome.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "### Originality\n\nAlthough the paper borrows some ideas from CFNNs, it is largely original in its restriction to linear classifiers and focus on invariant representation learning.\n\n### Clarity\n\nThe paper is clearly written and well-structured.\n\n### Quality\n\nI read two out of three proofs from the supplementary material and they look fine to me. Toy experiments are well-designed.\n\n### Significance\n\nThis work addresses the important question of invariant representation learning with a very original method that has some benefits compared to existing methods.", "weaknesses": "### Originality\n\n1. The only remark I would have here is that there are a few references missing from the invariant representation learning paragraph of the related work section. Namely, there are methods which are quite different from the proposed one but which also make use of randomness to obtain invariant representations, such as Augerino (https://arxiv.org/abs/2010.11882) and AugNet (https://arxiv.org/abs/2202.02142).\n\n### Clarity\n\n2. The only remark I have is that the error bars on the figures are difficult to associate to each dot as they are not color-coded.\n\nTypos:\n\n- l.126: supp(x)\n- l. 297: “$u_b$, and $u_b$” ($u_b$ twice)\n\n### Quality\n\nI only have two remarks/questions regarding the method and experiments:\n\n3. I realize that the paper contribution is rather theoretical, but the experiments are very very toy. I realize the value of the experiments carried out, but I wonder whether it would be possible to showcase the method in a more realistic setting.\n4. As far as I understood, the model invariance relies on underlying theorems specific to each setting (de Finetti for sets, Aldous-Hoover for graphs and Freedman for spherical data). Is that right? It would be interesting if you could discuss to which extent your framework can be adapted to arbitrary symmetry groups and whether this is a limitation.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your feedback. We refer the reviewer to our feedback summary for an additional experiment. We will also take in your suggested references in the final version. If you have any other input we'd be happy to discuss.\n> \"As far as I understood, the model invariance relies on underlying theorems specific to each setting (de Finetti for sets, Aldous-Hoover for graphs and Freedman for spherical data). Is that right? It would be interesting if you could discuss to which extent your framework can be adapted to arbitrary symmetry groups and whether this is a limitation.\"\n\nTheorem 2 shows that our framework can be adapted to any compact group transformation. That is, there is an equivalence between designing invariant distributions and designing invariant RLCs. Any result characterizing distributions invariant to a compact group transformation, such as the ones you cited, can be used to design invariant RLCs. We will highlight this in the final version, thank you for bringing this up."}, {"review_id": "GRh6eZzFoW", "reviewer": "Reviewer_4yWn", "summary": "The paper introduces a novel approach for achieving universality and invariance in binary classification tasks, while minimizing computational requirements. Instead of relying on deterministic neural networks such as DeepSet, which have parameterization complexity proportional to the set size, the paper proposes using randomised linear classifiers (RLCs). These RLCs can maintain invariance to compact group transformations and provide a universal approximation. Importantly, the parameterization complexity of RLCs remains independent of the set size. Building upon this finding, the paper extends the design of RLCs to ensure invariance in classification tasks involving sets, graphs, and spherical data. Experimental results demonstrate that the proposed RLCs outperform DeepSet and GNN approaches in certain invariant tasks.", "questions": "•\tWhat impact does the hyperparameter $m$ have on the model's performance? It appears that a larger value of $m$ is necessary to achieve highly confident predictions. This suggests that increasing $m$ allows the model to gather more evidence and make more precise decisions. It would be valuable to investigate how different values of $m$ influence the model's accuracy and confidence levels across various tasks and datasets.\n\n•\tThe impact of random distribution on model performance is a noteworthy aspect to consider. I am curious about whether different randomness would affect the model performance. What kind of randomness do you use in the experiment?\n", "limitations": "The paper presents some notable limitations despite its promising theoretical results:\n\n•\tScalability: The applicability of the proposed RLCs appears to be challenging in large-scale scenarios compared to deterministic methods. Further investigations and enhancements are needed to improve scalability and address potential computational complexities.\n\n•\tUnclear impact of $m$ and randomness: The paper would benefit from additional discussions and experiments to explore the effects of the hyperparameter $m$ and the selection of randomness sources. This would provide better insights into the optimal choices and their influence on model performance.\n\n•\tLack of real-world tasks: The evaluation of the proposed method is limited to synthetic tasks, and it would be valuable to extend it to real-world datasets. This would allow for a more comprehensive understanding of the method's capabilities and potential applications.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "•\tThe paper makes a notable theoretical contribution by presenting a novel approach that utilizes randomness to achieve universality and invariance in binary classification tasks. As far as my knowledge extends, this is the first approach of its kind to utilize randomness in this context.\n\n•\tThe incorporation of de Finetti's, Aldous-Hoover's, and Freedman's theorems is a significant contribution of the paper. These theorems play a crucial role in making RLCs applicable and practical for dealing with set, graph, and spherical data. By leveraging these theoretical foundations, the paper provides valuable insights into achieving invariance and universality across various data domains. This expands the scope of invariance and opens up new possibilities for addressing similar challenges in different contexts.\n", "weaknesses": "My main concern pertains to the scalability of the proposed approach. While deterministic neural networks only require a single feed-forward process to produce an output, RLCs necessitate the sampling of multiple randomnesses to compute the linear weights. This introduces computational complexity during both training and testing phases. Consequently, I am particularly interested in understanding how RLCs perform on real-world tasks compared to deterministic models like DeepSet and GNN. It remains to be seen whether RLCs can deliver competitive results in practical scenarios, considering the additional computational demands imposed by their inherent stochastic nature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! In the feedback summary we address your questions about $m$ and the choice of randomness source. Please, let us know if you have any extra input, we'd be interested in discussing.\n"}, {"review_id": "g971SGnjcm", "reviewer": "Reviewer_iRPF", "summary": "The authors propose probabilistic linear classifiers (RLCs) that are able to solve relatively general binary classification problems. They derive a trade-off between the probability that sampling of RLCs leads to an accurate prediction and the number of samples to obtain the majority vote of an RLC.\nFurthermore, there discuss more detailed results for three invariant learning problems related to inputs in form of sets, graphs, or spherical data.\n", "questions": "- How many samples m did RsetC and RgraphC use in the experiments? This seems to be quite an important parameter to determine the maximum achievable accuracy and the required computational resources for the evaluation of RsetC and RgraphC.\n\n- Experimental set-up in support of story:\nI would like to understand the required computational resources in an experimental context that directly supports the theoretical claims. 1) Start from good baselines that have enough neural network capacity to actually solve the discussed problems. 2) Then design RLCs that achieve a similar accuracy and compare the used computational resources. In this context: How many FLOPS does the evaluation of RLCs cost? How many trainable parameters do they use?\n", "limitations": "The limitations have been pointed out under weaknesses and were partially discussed by the authors. I do not foresee a major or immediate negative societal impact of this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- **Clarity:** The paper is well written and well understandable despite a strong theoretical component.\n\n- **Originality:** The authors propose to use probabilistic binary classifiers instead of deterministic ones to trade-off the number of required trainable parameters with prediction accuracy. A similar idea has been put forth by Sieradzki et al. (ICML22) for a number of interesting examples. This work seems to be the first to use randomized models for invariant learning (and relatively general binary classification problems).\n\n- **Significance:** The idea is significant because it discusses a novel problem solution perspective to overcome some computational barriers of the deterministic setting.\n\n- **Quality:** Mathematically rigorous analysis and exposition of the main idea. As a highlight, Theorem 1 gives a practically relevant estimate of the trade-off between required samples and the probability of accurate predictions.\nThe experiments could be designed in better support of the theory but still point out some potential benefits of RLCs for binary classification problems on sets and graphs.\n\n**Detailed points of strengths:**\n\n- The number of parameters used by RSetC does not depend on the set size, in contrast to DeepSets. Yet, the resource consumption depends on the smoothness of the distribution of linear classifier weights and bias. (Note that this might also imply disadvantages over DeepSets in some settings.)\n\n- RGraphCs can approximate any problem that either has a smooth boundary or can be tested with an inner product as in Definition 3. This includes the classification of graph connectivity (which cannot be solved by simple GNN architectures).\n\n", "weaknesses": "- The analysis is limited to binary classification problems.\n\n- The claimed computational resource savings are not obvious from the exposition and not directly covered by the theorems. According to the theory, the number of required parameters of RLCs could be higher than the ones of a deterministic solution (by a constant that could be very large). The theory does not establish that a smaller number of samples m (leading to potentially lower accuracy) would work in combination with fewer neural network parameters.\n(Some potential benefits for invariant learning are established based on reduced input dependence. But the changed criteria related to the smoothness of decision boundaries could also lead to worse results for RLCs in some situations.)\n\n- The experiments were not designed clearly to highlight computational advantages but to show accuracy improvements on small scale tasks, in which the baselines cannot perform reasonably well because of an unrealistic computational resource constraint.\nIt is likely that the baselines would actually achieve much higher accuracy with sufficient model capacity. Could RLCs actually perform at least on par if equipped with the same capacity that allow the baselines to work well?\n\n- The statement in Line 338: \"This comes from the fact that GNNs cannot distinguish simple non-isomorphic graphs such as any pair of d-regular graphs. As such, GNNs cannot universally approximate tasks that assign different labels to any of such pairs. In contrast, RGraphCs can approximate any problem that either has a smooth boundary or can be tested with an inner product...\"\nis not entirely correct. This limitation only applies to simple GNN architectures. Modern architectures that use attention and suitable node labels do not suffer from this problem. Experiments that compare with such stronger baselines would be more informative regarding the practical implications of the proposed work.\n\n- Conceptually, RLCs might require fewer trainable parameters in some cases, which could lead to advantageous memory requirements. Yet, they are not necessarily computationally more efficient at inference, which is not discussed at all in the paper. The fact that each inference needs to evaluate the trained neural network m times could increase the associated FLOPS significantly. \n\n- For the same reason, the experiments might not be fair, as the baselines are allowed fewer computational resources at inference than the RLCs.\n\n- **Reproducibility:** No code has been shared.\n\n\n**Points of minor critique:**\n\n- Line 297: $u_b$ is listed twice instead of once.\n\n- Figures: It would help to color also confidence intervals because it currently is impossible to distinguish them when they are overlapping.\n\n- The size of the validation set is not mentioned (neither in the main paper nor the Appendix). Only the size of the training and test set is given.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the valuable comments. We are glad the reviewer appreciated our contributions. In the feedback summary we address your questions about i) settings where the deterministic models succeed and how it can be compared to RLCs in terms of resources and ii) how the number of samples $m$ can impact our resources. We will also take in your suggestion about color coding in the plots for the final version.\n\n>  According to the theory, the number of required parameters of RLCs could be higher than the ones of a deterministic solution (by a constant that could be very large).\n\nIn the proof of Theorem 1 we can see that the constant cannot be arbitrarily large. If $p^\\dagger$ is the number of parameters that an MLP with 1 hidden layer needs to solve the task, the constant will be at most 2. We thank the reviewer for pointing out this is not clear in the main text and we will make it explicit in the final version.\n\n> The statement in Line 338: [...] is not entirely correct.\n\nThanks, we will clarify that we refer to GNNs with expressiveness bounded by the Weisfeiler Leman test. Note, however, that the mentioned node labeling (e.g., random features) methods do not have the invariance property, the main theme of our work.\n\n> \"How many samples m did RsetC and RgraphC use in the experiments?\n\n10, we will add to the main paper in the final version."}]

Author rebuttal:
### **_Feedback summary_**
We thank all the reviewers for the valuable feedback on our manuscript. In general, reviewers found the paper to be well written and appreciated the novel direction given by our theoretical contributions. Here we address three common points raised across reviews. Then, we discuss specific comments separately in each reviewer's thread.
1. **Choice of external randomness:** Reviewers asked about the impact of the choice of randomness source. We highlight that our theory shows the suffiency of absolutely continuous sources. As in models such as GANs or VAEs, due to their capacity, neural networks can transport simple distributions, e.g., Gaussian, to arbitrarily complex ones. Our experiments do confirm that this also seems to be the case in RLCs ---note that RLCs solve supervised learning, a task easier than data generation (tackled by GANs and VAEs). Moreover, if there's a form of prior knowledge about the solution, i.e., the linear coefficients ideal distribution, one should leverage it. In fact, this is precisely what our invariant models are doing (through parameter-sharing), see Theorem 2.
2. **Number of samples ($m$):** Some reviewers asked about the impact of the number of samples $m$ in the computational complexity of the model. We point them to Theorem 1, where we show that we need only a few samples to output the model's true prediction with arbitrarily high probability. For instance, if the model outputs 1 with probability 2/3, with 3 samples we will output 1 with probability $>0.95$. This result is only possible due to the independence between input and randomness source.
4. **Experiments:** Reviewers raised two interesting points regarding our experiments. How do RSetCs compare to tasks when Deep Sets are supposedly good? Can we compare the resource consumption of RSetCs vs. Deep Sets when both are performing well in a task? To address them, we consider the task of deciding whether the majority of a set of random numbers is positive or negative. This task is essentially removing the sorting operation from the task in the paper ---where deep sets struggles. We then consider Deep Sets with one and two hidden layers vs an RSetC with a single hidden layer. The results are in the image attached. We see that the single layer RSetC has a performance more similar to the Deep Sets with two hidden layers, showcasing our parameter efficiency. The experimental setup was the same as the sort task in the main paper. We will add this experiment to the final version, thank you for the input!

Meta-review: An interesting paper, which saw its ratings increase at discussion phase. I am inclined to remove the bottom review of 2JHn, which was short and without any follow-up.

We end up with a paper with globally positive ratings, and that could reasonably be considered for acceptance.
Decision: Accept (poster)