  Permutation invariant neural networks are a promising tool for making
predictions from sets. However, we show that existing permutation invariant
architectures, Deep Sets and Set Transformer, can suffer from vanishing or
exploding gradients when they are deep. Additionally, layer norm, the
normalization of choice in Set Transformer, can hurt performance by removing
information useful for prediction. To address these issues, we introduce the
clean path principle for equivariant residual connections and develop set norm,
a normalization tailored for sets. With these, we build Deep Sets++ and Set
Transformer++, models that reach high depths with comparable or better
performance than their original counterparts on a diverse suite of tasks. We
additionally introduce Flow-RBC, a new single-cell dataset and real-world
application of permutation invariant prediction. We open-source our data and
code here: https://github.com/rajesh-lab/deep_permutation_invariant.
