Universal Mini-Batch Consistency for Set Encoding Functions

Jeffrey Willette, Andreis Bruno, Juho Lee, Sung Ju Hwang

TL;DR

This paper introduces a new framework called Universal Mini-Batch Consistency (UMBC) that allows existing, powerful set encoding models (like Set Transformers) to be used in settings where data arrives in chunks or streams. It also proposes an efficient training method that uses a constant amount of memory regardless of the input set size, making it practical for very large datasets.

What Problem Does This Paper Address?

Deep learning models often struggle with processing data that arrives in pieces, like streaming data or large datasets that don't fit into memory all at once. For set-based data (where the order of elements doesn't matter, like words in a document or patches in an image), this is a significant challenge. Previous approaches to handle this, known as Mini-Batch Consistency (MBC), were limited by restrictive architectures that sacrificed expressive power. Additionally, training these models on large sets required computing gradients over the entire dataset, which is computationally prohibitive. This paper aims to bridge this gap by enabling flexible, powerful set models to be used in MBC settings and by developing a scalable training approach.

Methods

The core contribution is the Universal Mini-Batch Consistent (UMBC) framework. UMBC allows arbitrary non-MBC set functions (like Set Transformers) to be combined with MBC components, effectively making the entire composition MBC. This is achieved by relaxing the strict architectural constraints of previous MBC models and allowing for more flexible attention mechanisms, including softmax attention.

Furthermore, the authors propose an unbiased full set gradient approximation algorithm. This algorithm allows training with large sets by processing subsets and using a "stop gradient" trick. This ensures that the gradient is unbiased (unlike previous biased approximations) while maintaining a constant memory overhead, regardless of the total set size.

Datasets

The paper evaluates their approach on several datasets:

  • Image Completion: CelebA dataset.
  • Long Document Classification: Inverted EURLEX dataset.
  • Multiple Instance Learning (MIL): Camelyon16 dataset.
  • Amortized Clustering: A synthetic dataset generated from Mixtures of Gaussians (MoGs).

Key Insights and Ideas

  • Flexibility is Key: Restrictive architectures for MBC models limit their expressiveness. UMBC shows that by allowing the integration of powerful non-MBC components, we can achieve both MBC and high performance.
  • Softmax Attention is MBC: Contrary to prior assumptions, the authors demonstrate that softmax attention, when used within their UMBC framework, can satisfy the MBC property. This opens up a wider range of attention mechanisms for MBC models.
  • Scalable Training is Achievable: The proposed unbiased gradient approximation method is crucial for training on massive datasets. It achieves performance comparable to full-set gradient training but with constant memory usage, a significant advantage.
  • UMBC + Set Transformer is Powerful: Combining UMBC with a Set Transformer consistently outperformed other MBC and non-MBC models across various tasks, highlighting the synergy between their approaches.

Key Results

  • Image Completion: UMBC+Set Transformer achieved the best performance (lowest NLL) on the CelebA dataset, outperforming baselines like DeepSets, SSE, and Set Transformer alone.
  • Long Document Classification: UMBC+BERT achieved the highest micro F1 score, outperforming non-MBC models like Longformer and ToBERT, while using significantly less GPU memory.
  • Multiple Instance Learning (MIL): UMBC achieved the best accuracy and competitive AUROC score on the Camelyon16 dataset.
  • Amortized Clustering: The unbiased gradient estimation method was nearly indistinguishable from full-set gradient training, while the biased estimation showed a significant gap. UMBC+ST also showed superior performance.
  • Memory Efficiency: UMBC models, when trained with the unbiased gradient approximation, exhibit constant memory overhead for any set size, enabling processing of extremely large datasets.

Limitations and Future Work

  • Time Complexity: The proposed unbiased gradient approximation has a higher time complexity during mini-batch training compared to simpler biased methods. However, this is traded for better performance and constant memory overhead.
  • Fixed Slot Parameters: The UMBC model uses fixed parameters for its "slots" in the attention mechanism. Future work could explore making these slot parameters dependent on the input set to potentially increase model expressivity.

Summary updated

Abstract

Recent work on mini-batch consistency (MBC) for set functions has brought attention to the need for sequentially processing and aggregating chunks of a partitioned set while guaranteeing the same output for all partitions. However, existing constraints on MBC architectures lead to models with limited expressive power. Additionally, prior work has not addressed how to deal with large sets during training when the full set gradient is required. To address these issues, we propose a Universally MBC (UMBC) class of set functions which can be used in conjunction with arbitrary non-MBC components while still satisfying MBC, enabling a wider range of function classes to be used in MBC settings. Furthermore, we propose an efficient MBC training algorithm which gives an unbiased approximation of the full set gradient and has a constant memory overhead for any set size for both train- and test-time. We conduct extensive experiments including image completion, text classification, unsupervised clustering, and cancer detection on high-resolution images to verify the efficiency and efficacy of our scalable set encoding framework. Our code is available at github.com/jeffwillette/umbc
BibTeX
@inproceedings{willette2023universal,
  author = {Jeffrey Willette and Andreis Bruno and Juho Lee and Sung Ju Hwang},
  title = {{Universal Mini-Batch Consistency for Set Encoding Functions}},
  booktitle = {International Conference on Machine Learning},
  year = {2023},
  url = {https://openreview.net/forum?id=VnsST4dDlu},
}
Figure