Probabilistic Invariant Learning with Randomized Linear Classifiers

Leonardo Cotta, Gal Yehuda, Assaf Schuster, Chris J. Maddison

Introduction

In machine learning, achieving invariance—ensuring a model's output remains unchanged under transformations like permuting elements in a set or nodes in a graph—is a fundamental requirement for many tasks. However, traditional deterministic architectures often face a steep trade-off between expressivity and resource efficiency. For instance, Deep Sets require hidden layers proportional to the input size to achieve universality, while Graph Neural Networks (GNNs) are bounded by the Weisfeiler-Lehman test, leaving them unable to solve basic topological problems like graph connectivity regardless of parameter count.

This paper introduces Randomized Linear Classifiers (RLCs), a novel class of models that leverage external randomness to break these constraints. By relaxing the requirement for deterministic invariance and instead guaranteeing it with high probability, RLCs achieve universal approximation using significantly fewer parameters and memory than standard models.

Methodology: Randomness as a Computational Resource

The core innovation of RLCs is the shift from a single complex deterministic function to a distribution of linear classifiers. The process involves three primary steps:

  1. Random Weight Generation: A neural network $f_\theta$ takes external randomness as input and outputs the weights and bias for a linear classifier.
  2. Linear Inference: This sampled classifier is applied to the input data.
  3. Amplification: The process is repeated $m$ times, with the final prediction determined by a majority vote.

The authors utilize classical representation theorems from probability theory to design these weight distributions. Specifically, they employ de Finetti’s theorem for set invariance, the Aldous-Hoover theorem for graph exchangeability, and Freedman’s theorem for spherical data. These foundations allow RLCs to remain invariant to specific group transformations by construction.

Experimental Evaluation

The effectiveness of RLCs was evaluated on three synthetic tasks designed to highlight the theoretical and practical limitations of existing architectures:

  • Sorting Task: A set-based task where the label depends on the sorted order of elements.
  • Sign Task: A set-based task requiring the model to predict the sign of the sum of signs of input elements.
  • Connectivity Task: A graph-based task where the model determines if a graph (sampled from a $G(n, p)$ model) is connected. This is a known "blind spot" for standard GNNs.

Key Results and Insights

Universal Approximation and Efficiency

The authors prove that RLCs can approximate any binary classification problem with a smooth boundary. Crucially, the resource requirements for Randomized Set Classifiers (RSetCs) depend on the task's complexity (smoothness) rather than the input sequence length, effectively decoupling parameter count from input size.

Generalization and Robustness

In the Sorting Task, RSetCs demonstrated superior generalization compared to Deep Sets, particularly in "Size OOD" (Out-of-Distribution) scenarios where the model is tested on sets larger than those encountered during training. RSetCs achieved these results while using smaller hidden layers, confirming their parameter efficiency.

Bypassing GNN Limitations

In the Connectivity Task, RGraphCs maintained high accuracy even as graph sizes increased. In contrast, standard GNN performance plummeted toward the level of a constant classifier. This confirms that RLCs can solve tasks that are theoretically "unsolvable" for traditional message-passing architectures by tying expressivity to whether a decision can be tested via an inner product.

Practical Implications and Future Work

RLCs offer unique advantages for edge computing. Because the heavy lifting (generating weights) can be done server-side, a low-power device only needs to perform simple linear computations. This preserves battery life and enhances data privacy.

Despite these strengths, the current framework is limited to binary classification. Future research is needed to extend RLCs to multi-class problems and regression. Additionally, while synthetic tests are promising, evaluating RLCs on large-scale real-world datasets—such as molecular graphs or 3D point clouds—remains a critical next step. Exploring broader invariances, such as 3D rotation ($SO(n)$), could further expand the utility of this randomized approach.

Summary updated

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.
BibTeX
@inproceedings{cotta2023probabilistic,
  author = {Leonardo Cotta and Gal Yehuda and Assaf Schuster and Chris J. Maddison},
  title = {{Probabilistic Invariant Learning with Randomized Linear Classifiers}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=WwP2JaXAtB},
}
Figure