Research map / Learning theory and algorithms / Submodular and game algorithms

Difference-of-submodular Bregman Divergence

ICLR 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Monotone submodular maximization

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a difference-of-submodular generalization of the discrete Bregman divergence, extending submodular-generated Bregman divergences on discrete domains.

Problem

Bregman divergences are well defined for continuous spaces, but defining an analog for discrete spaces is nontrivial; prior discrete versions (Iyer & Bilmes 2012) use submodular generating functions.

Approach

Generalizes the submodular-based discrete Bregman divergence by using difference-of-submodular functions as generators, providing a broader discrete analog of the Bregman divergence.

Experimental setup

Builds on: Bregman divergence submodular Bregman divergence (Iyer & Bilmes 2012)

Closest papers by meaning

• A scaled Bregman theorem with applications (NeurIPS 2016 · similarity 0.89)
• Neural Bregman Divergences for Distance Learning (ICLR 2023 · similarity 0.89)
• Learning to Approximate a Bregman Divergence (NeurIPS 2020 · similarity 0.89)
• Deep Divergence Learning (ICML 2020 · similarity 0.88)
• Learning Bregman Divergences with Application to Robustness (NeurIPS 2024 · similarity 0.84)
• Discrete and Continuous Difference of Submodular Minimization (ICML 2025 · similarity 0.83)