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.

通过利用随机性设计的随机线性分类器 (RLCs) 类别的二元分类模型，可以在使用较少资源的同时近似任何 (光滑的) 函数并保持对紧凑群转换的不变性。