Research map / Learning theory and algorithms / Sample complexity
Monotone and Separable Set Functions: Characterizations and Neural Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes monotone-and-separating (MAS) multiset-to-vector functions, shows they don't exist for infinite ground sets, and proposes MASNet (weakly MAS, Hölder-separable DeepSets-style models with hat or ReLU activations) for set containment tasks.
Problem
Designing set-to-vector functions that preserve the subset partial order (S ⊆ T iff F(S) ≤ F(T)) so that vector comparison serves as an exact containment test, especially over infinite ground sets such as R^d.
Approach
Establishes dimension bounds for MAS functions over finite ground sets, proves non-existence over infinite ground sets, and relaxes separability to a weak, parameter-existential form realized by DeepSets-style models with non-negative hat activations or two-layer ReLU networks, with an asymmetric EMD-based Hölder separability guarantee.
Key results
- On text datasets with a 1:1 class ratio, Relu-MAS reaches 0.98 (Bedding), 0.98 (Feeding), 0.99 (MSWEB), 0.97 (MSNBC), versus best baseline Set Transformer 0.77/0.79/0.90/0.94 and FlexSubNet 0.88/0.85/0.92/0.91.
- On the synthetic dataset with |S|=10 and |T|=100, M-Hat reaches 0.99 accuracy versus 0.54 for DeepSets and 0.57 for Set Transformer.
- On monotone function approximation, Hat-MAS achieves the lowest MAE (0.00959 ± 0.00016) versus DeepSets 0.01024 and Set Transformer 0.01026.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MAS variants instead of the strongest listed standard baseline | Set-containment models · Synthetic set containment | accuracy: 0.59 -> 0.99 | Helped |
| Use MAS variants instead of the strongest listed standard baseline | Set-containment models · Bedding | accuracy: 0.88 -> 0.98 | Helped |
| Use MAS variants instead of the strongest listed standard baseline | Set-containment models · Feeding | accuracy: 0.85 -> 0.98 | Helped |
| Use MAS variants instead of the strongest listed standard baseline | Set-containment models · MSWEB | accuracy: 0.92 -> 0.99 | Helped |
| Use MAS variants instead of the strongest listed standard baseline | Set-containment models · MSNBC | accuracy: 0.94 -> 0.97 | Helped |
| Use ReLU-MAS instead of FlexSubNet | Point-cloud containment models · ModelNet40 point-cloud containment (|S|=128) | accuracy: 0.84 -> 0.98 | Helped |
| Use ReLU-MAS instead of FlexSubNet | Point-cloud containment models · ModelNet40 point-cloud containment (|S|=256) | accuracy: 0.75 -> 0.94 | Helped |
| Use ReLU-MAS instead of FlexSubNet | Point-cloud containment models · ModelNet40 point-cloud containment (|S|=512) | accuracy: 0.60 -> 0.72 | Helped |
| Use Hat-MAS instead of DeepSets | Monotone function approximation models · Monotone set-function approximation | MAE: 0.01024 ± 0.00030 -> 0.00959 ± 0.00016 | Helped |
| Use a one-layer hat-activation pointwise model rather than a one-layer ReLU pointwise model (ablation) | One-layer set-containment model · Synthetic set containment | accuracy | Helped |
| Increase target-set size while keeping query-set size fixed (ablation) | M-ReLU and M-Hat · Synthetic set containment | accuracy: 0.99 -> 0.98 | Hurt |
| Increase target-set size while keeping query-set size fixed (ablation) | DeepSets and Set Transformer · Synthetic set containment | accuracy: 0.89 -> 0.54 | Hurt |
Surprising findings
- Scalar (one-dimensional) MAS set functions do not exist, and MAS functions do not exist at all over infinite ground sets for cardinality k≥2.
- Standard monotone activations such as ReLU in a one-layer DeepSets model cannot achieve weak separability; Set Transformers with sum pooling are not even pointwise monotone.
Limitations
- Separability guarantees for the parametric models hold only in the randomized setting (at initialization-like sampling) and do not carry over to gradient-trained models.
- Universality of monotone set functions via MAS composition is established only for finite ground sets.
- Extension to subgraph isomorphism is not addressed.
Experimental setup
Datasets: MSWEB MSNBC Amazon Registry Amazon Feeding Amazon Bedding ModelNet40 synthetic Gaussian sets
Benchmarks: synthetic set containment MSWEB MSNBC Amazon Feeding Amazon Bedding ModelNet40 point-cloud containment monotone function approximation
Metrics: accuracy mean absolute error
Baselines: DeepSets Set Transformer FlexSubNet Neural SFE
Builds on: DeepSets Set Transformer Erdős–Szekeres theorem
Closest papers by meaning
- On the Limitations of Representing Functions on Sets (ICML 2019 · similarity 0.86)
- Polynomial Width is Sufficient for Set Representation with High-dimensional Features (ICLR 2024 · similarity 0.83)
- Variance Reduced Halpern Iteration for Finite-Sum Monotone Inclusions (ICLR 2024 · similarity 0.82)
- Robustly Learning Monotone Single-Index Models (NeurIPS 2025 · similarity 0.82)
- Decomposition Polyhedra of Piecewise Linear Functions (ICLR 2025 · similarity 0.81)
- Learning Set Functions with Implicit Differentiation (AAAI 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.