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

Discrete and Continuous Difference of Submodular Minimization

ICML 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 full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends difference-of-submodular (DS) minimization from set functions to discrete and continuous domains by reducing to a DC program over a convex continuous extension and proposing a DCA variant with local search (DCA-LS), tested on integer least squares and integer compressed sensing.

Problem

Minimizing difference-of-submodular functions over discrete (integer lattice) and continuous domains, which is NP-hard and inapproximable, so only local minima are targeted.

Approach

Relaxes DS minimization on bounded integer lattices to a DC program via the Bach convex continuous extension, then applies a DCA variant whose subgradient choice uses a local-search step over neighboring points, giving convergence directly to an approximate local minimum; continuous domains are handled by discretization.

Key results

• On integer least squares with n=100, DCA-LS matches the optimal Gurobi solution in recovery from m/n = 1.2 and outperforms ADMM and relax-and-round on all metrics.
• On integer compressed sensing (n=256, SNR 8 dB), DCA-LS and DCA-LS-LASSO significantly outperform OMP, LASSO and FISTA in recovery probability.
• DCA-LS converges to an (epsilon + epsilon_x)-local minimum in at most (F(x0) - F*)/epsilon iterations.

Measured effects reported in the paper

Surprising findings

• Any function on a discrete domain and any smooth function on a continuous domain admits a DS decomposition, but DS functions on continuous domains are not necessarily DC.
• The natural DS decomposition of sparse learning objectives with ||x||_q^q regularizers is not a discrete DC decomposition.

Limitations

• Finding tight decomposition constants (alpha, beta, L_F) is exponential in general, and loose bounds slow optimization.
• Local minimality only, no global guarantee; the problem is inapproximable in general.
• Continuous domains are handled via discretization, whose grid size grows with the Lipschitz constant over epsilon.

Experimental setup

Benchmarks: integer least squares (synthetic) integer compressed sensing (synthetic)

Metrics: recovery probability bit error rate relative objective gap support error estimation error

Baselines: ADMM Optimal Brain Quantizer relax-and-round Babai nearest plane Gurobi OMP LASSO with box constraint FISTA

Builds on: DCA Bach continuous extension of submodular functions pairwise Frank-Wolfe SubSup method

Closest papers by meaning

• Difference of submodular minimization via DC programming (ICML 2023 · similarity 0.91)
• Optimal approximation for unconstrained non-submodular minimization (ICML 2020 · similarity 0.90)
• Decomposable Submodular Function Minimization: Discrete and Continuous (NeurIPS 2017 · similarity 0.89)
• Fast Decomposable Submodular Function Minimization using Constrained Total Variation (NeurIPS 2019 · similarity 0.89)
• Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (NeurIPS 2025 · similarity 0.87)
• The Multi-Block DC Function Class: Theory, Algorithms, and Applications (NeurIPS 2026 · similarity 0.87)