Research map / Learning theory and algorithms / Submodular and game algorithms
Deep Submodular Peripteral Networks
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.
Introduces deep submodular peripteral networks (DSPNs), a submodular-by-construction set function family trained with a graded-pairwise-comparison "peripteral" loss on sampled set pairs, distilled from an expensive facility location target.
Problem
Learning practical, scalable submodular set functions from data, and learning scalar scorings from graded pairwise preference oracles (GPC), where existing methods use binary comparisons or non-submodular set networks.
Approach
A DSPN stacks per-element neural pillars, a submodularity-preserving weighted matroid rank aggregator, and a deep submodular function roof; it is trained with a graded-ratio hinge-like peripteral loss on (E,M) set pairs scored by the target's score difference, with passive and active (submodular feedback) pair sampling.</12idea>
Key results
- DSPN trained with peripteral loss outperforms margin and regression losses and random sets in normalized FL evaluation across budgets and datasets.
- On Imagenet100 size-100 ablation, full DSPN reaches 0.92 FL eval, 67.8% offline accuracy and 65.9% online accuracy, versus Deep Set at 0.56, 9.2% and 3.5%.
- Graded comparisons beat binary pairwise comparisons (PC rather than GPC: 62.8 offline / 63.4 online vs 67.8 / 65.9).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Remove target feedback (ablation) | DSPN · Imagenet100, size-100 | FL Eval: 0.93 -> 0.92 | No clear effect |
| Add active feedback (ablation) | DSPN · Imagenet100, size-100 | Online Acc: 30.1 -> 65.9 | Helped |
| Add type-II sampling (ablation) | DSPN · Imagenet100, size-100 | Offline Acc: 13.1 -> 67.8 | Helped |
| Use graded GPC instead of non-graded pairwise comparisons (ablation) | DSPN · Imagenet100, size-100 | FL Eval: 0.90 -> 0.92 | Helped |
| Learn the pillar instead of freezing it (ablation) | DSPN · Imagenet100, size-100 | Offline Acc: 39.1 -> 67.8 | Helped |
| Enforce submodularity instead of using a Deep Set (ablation) | DSPN · Imagenet100, size-100 | Offline Acc: 9.2 -> 67.8 | Helped |
| Enforce submodularity instead of using a Set Transformer (ablation) | DSPN · Imagenet100, size-100 | FL Eval: 0.34 -> 0.92 | Helped |
Surprising findings
- Removing target (facility location) feedback leaves performance essentially unchanged, so the target need not be optimizable.
- DSPN outperforms random sets even at budgets above 100, which were never seen in training.
Limitations
- Open theoretical question whether DSPNs can represent all monotone submodular functions.
- Aggregators are fixed rather than learned; matroid structure is not trained.
- Target FL does not generalize to held-out data, so distillation is required.
Experimental setup
Datasets: Imagenette Imagewoof CIFAR100 Imagenet100
Benchmarks: Imagenette Imagewoof CIFAR100 Imagenet100
Metrics: normalized facility location evaluation linear-probe accuracy in offline and online experimental des
Baselines: Deep Sets Set Transformer CRAIG K-centers reservoir sampling VeSSAL random subset selection
Builds on: deep submodular functions deep sets max-margin structured prediction triplet loss
Closest papers by meaning
- As Simple as Fine-tuning: LLM Alignment via Bidirectional Negative Feedback Loss (ICLR 2025 · similarity 0.84)
- Bridging and Modeling Correlations in Pairwise Data for Direct Preference Optimization (ICLR 2025 · similarity 0.84)
- Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options (NeurIPS 2025 · similarity 0.84)
- Distributional Preference Learning: Understanding and Accounting for Hidden Context in RLHF (ICLR 2024 · similarity 0.83)
- 3D-Properties: Identifying Challenges in DPO and Charting a Path Forward (ICLR 2025 · similarity 0.83)
- Proximalized Preference Optimization for Diverse Feedback Types: A Decomposed Perspective on DPO (NeurIPS 2025 · similarity 0.83)
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.