Do Submodular Minimization Lower Bounds Bind in Practice?

Many problems in machine learning reduce to submodular function minimization. Examples include image segmentation, choosing a training subset, and clustering with a few labels. Each asks for the subset of items that minimizes a cost with diminishing returns: adding an item helps less the more you already have. The theory community measures difficulty by counting oracle queries, meaning how many times an algorithm must ask a black box "what is the cost of this subset?" On that measure the field has advanced quickly. Deterministic algorithms are now known to need about $n \log n$ queries on $n$ items. Cutting-plane methods solve the problem exactly in roughly $n^3$ time, and stochastic methods run in subquadratic time. Almost none of this has been implemented. Practitioners still use the Fujishige–Wolfe minimum-norm-point heuristic, which has no strongly polynomial guarantee. On some realistic instances its running time blows up to $n^5$–$n^7$. Nobody knows where real solvers sit between the lower and upper bounds, or whether the newer algorithms would ever win.

We propose to measure this directly. We will build an instrumented testbed that counts oracle queries, adaptive rounds and wall-clock time. It runs practical and theory-derived solvers on two kinds of instance. The first kind is realistic workloads. The second kind is executable versions of the adversaries used to prove the lower bounds. These adversaries are implemented as oracles that answer each solver's queries adaptively, as the proofs require, and evaluate in exact arithmetic so that floating-point rounding cannot quietly defeat them. The output is an empirical query-complexity curve for each solver on each instance family. It answers two questions. Do the lower-bound adversaries actually slow down the solvers people use? And at what problem size, if any, does an asymptotically better algorithm overtake Wolfe on realistic inputs?

Core Claim

The open theoretical problems and the missing empirical work in this area are the same problem viewed from two sides.

On the theory side, three questions are open. The first is the gap between the deterministic $\frac{n}{2}\log_2(n/4)$ query lower bound of Improved Lower Bounds for Submodular Function Minimization and the $O(n^3\log^2 n)$ cutting-plane upper bound of A Faster Cutting Plane Method. The second is whether randomization escapes $n\log n$. The third is whether bounds that depend on the value range $M$ are intrinsic.

On the empirical side, none of the algorithms behind those bounds has been run. The two sides are linked by something no one has measured: the query count, as a function of $n$, that each solver incurs on each instance family.

We claim this measurement is feasible, and that it is informative in both directions. It can show that a lower-bound construction is loose against every practical solver, which would suggest the true complexity is lower. It can show that a construction stops working in floating point at modest $n$, which says something about practical hardness. And it can locate a concrete crossover size for the subquadratic and sparse algorithms, or show that no crossover occurs below $10^5$ items.

Research Program

Adversarial oracles

The first component turns the lower-bound constructions into oracles.

Improved Lower Bounds for Submodular Function Minimization builds recursive layered functions with "indicator locks" and infinitesimal perturbations $\beta$. Its deterministic $\Omega(n\log n)$ query bound and $\Omega(n/\log n)$ parallel round bound rest on these. New Query Lower Bounds for Submodular Function Minimization proves bounds of $2n$, $3n/2-2$ (symmetric) and $\binom{n}{2}$ (asymmetric) using adversary arguments and a "cut dimension" notion.

A deterministic adversary argument does not specify one fixed hard function. It answers queries so as to stay consistent with many functions until the algorithm has paid enough queries. We will implement each construction in the form the papers give it, either an adaptive strategy or an explicit family. The oracle commits to answers lazily and records which candidate minimizers remain consistent. It is built on exact rational arithmetic, because the file notes that the $\beta$ perturbations need exponential integer scaling.

A second, float64 version of each oracle measures whether the hardness survives ordinary machine precision. Where a construction defines a distribution over functions rather than an adaptive strategy, we sample from it, which also lets us probe the open question of whether randomized solvers can beat the deterministic bound.

Instrumented solvers

The second component is a solver suite behind one shared oracle interface. That interface counts queries, rounds of parallel queries, and time spent inside the oracle versus outside it. The suite contains:

We will publish these implementations together with the oracles.

Analysis

The third component is analysis. For each pair of solver and instance family we fit the scaling exponent of queries against $n$. We separately fit the dependence of iteration count on the value range ($M$ or $F$) by rescaling instances. Provable Submodular Minimization using Wolfe's Algorithm reports that Wolfe's iterations look nearly independent of $F$, despite its $O((n^5 EO+n^7)F^2)$ bound. We test whether that holds on the adversarial families too.

Baselines

Naive reference. The do-nothing reference is plain Fujishige–Wolfe with default settings. It is what practitioners run, and Provable Submodular Minimization using Wolfe's Algorithm reports that it significantly outperforms the strongly polynomial Iwata–Orlin algorithm on Erdős–Rényi s-t mincut instances ($p=0.8$). No numerical table is given in the file, so that comparison has no reported figure for us to target. A theory-derived solver beats this reference if it uses fewer queries and less wall-clock time at the same exact-minimizer accuracy on some realistic family, at a size we can identify.

Strongest exact competitor. This is Wolfe wrapped with safe screening (IAES), which Safe Element Screening for Submodular Function Minimization reports as 11x–30.7x faster in wall-clock than the standalone minimum-norm solver on five GrabCut instances. That is the number to beat on GrabCut.

Strongest approximate competitor. This is the submodular-majorization method of On fast approximate submodular minimization, reported up to 100x faster than the minimum-norm algorithm on Switchboard subset selection. It scales empirically at about $O(n^{1.5})$, against $O(n^5)$ for minimum-norm. Because it is exact only for subclasses, we compare against it on bipartite and Switchboard-style instances and report its suboptimality alongside its speed.

Decomposable competitor. On decomposable instances the reference is ACDM warm-started with ten Wolfe iterations, the configuration Decomposable Submodular Function Minimization found effective. That paper quotes no wall-clock seconds, so the file has no reported result for it.

Fairness. Every solver uses the same oracle implementation, single-thread CPU (except for round-count experiments), and the same stopping rule. The stopping rule is a certified exact minimizer, obtained via the dual-gap or "robust Fujishige" criterion of Provable Submodular Minimization using Wolfe's Algorithm. Each method gets an equal hyperparameter-tuning budget of a fixed number of configurations on held-out instances of the same family.

Key ablation. The ablation that isolates our main ingredient compares each lower-bound family under three oracles: the adaptive exact-arithmetic adversary, a fixed function sampled once from the same family, and the float64 version of the adversary. If solvers slow down only under the first, the hardness lives in adaptivity. If they slow down under the first two but not the third, it lives in precision.

Why not just…?

Why not just implement the subquadratic algorithm and time it against Wolfe? That is one row of our study, and on its own it would answer a narrower question. A single timing result cannot say whether a loss comes from data-structure overhead, from the $M^3$ range dependence in Subquadratic Submodular Function Minimization, or from the instances simply being easy. Separating query counts from time spent outside the oracle, and including adversarial families, separates those causes. If a plain head-to-head would already settle things, the GrabCut row will show it. We would then report that row as the main finding rather than inflate the rest.

Why not just use Wolfe with screening everywhere, since it is already fast? This is a real threat. On image segmentation it may well remain unbeaten. But On fast approximate submodular minimization shows minimum-norm scaling as $O(n^5)$–$O(n^7)$ on bipartite neighborhood functions. Screening also has early-stage latency: it removes almost nothing until the dual gap shrinks, per Safe Element Screening. Our bipartite and adversarial experiments test whether screening rescues Wolfe there. If it does, that is a useful negative result for the theory-driven algorithms.

Why not just benchmark on real data and skip the lower-bound gadgets? Real data can only tell us that a solver is fast on that data. It cannot tell whether the $n\log n$ or $\binom{n}{2}$ constructions describe anything a solver actually encounters. Running the gadgets is the only way to learn whether the bounds are tight against practical algorithms. It also shows whether they collapse in floating point, a possibility the file flags because of the exponentially small $\beta$.

Why not use generic first-order convex solvers on the continuous relaxation? The Lovász extension is the standard convex relaxation of a submodular function. Generic solvers on it are a known failure mode. Quadratic Decomposable Submodular Function Minimization reports that PDHG and SGD failed to reach a $10^{-9}$ primal gap where its coordinate method needed 0.83 s. We still include projected subgradient descent as a cheap sanity row.

Proposed Experiments and Decisive Checks

Instance families

The realistic families are:

  • GrabCut segmentation with pairwise and $2\times2$ potentials. Potentials are quantized to integers so we can control $M$. Image-size sweeps are obtained by downsampling.
  • Two-Moons semi-supervised clustering from $p=200$ upward. Its minimizers are small, which makes it the natural test for sparse SFM.
  • Synthetic bipartite neighborhood functions and Switchboard-style subset selection.
  • Erdős–Rényi s-t mincut, path graphs and Iwata's "3 Groups" function from Provable Submodular Minimization using Wolfe's Algorithm.
  • The clustered hypergraph and UCI instances from Quadratic Decomposable Submodular Function Minimization, for decomposable solvers.

The adversarial families are the constructions of the two lower-bound papers, scaled from $n=16$ to the largest $n$ that exact arithmetic allows.

Decisive checks

Do the lower bounds bind? On the adaptive adversaries, we test whether Wolfe's query count grows at least as fast as $n\log n$, or whether some practical solver clearly beats the bound. Beating it would mean an implementation error in our oracle or a gap in our reading of the construction, and we would debug before reporting. We also record how close each solver comes to $\frac{n}{2}\log_2(n/4)$.

Does precision matter? We find the $n$ at which the float64 adversary stops forcing extra queries.

Is there a crossover? We fit the size at which the subquadratic and cutting-plane methods overtake Wolfe-with-screening, first in queries and then in wall-clock. We expect the query crossover to come well before the wall-clock one. A wall-clock crossover beyond $10^5$ items would mean the theoretical advance is currently of no practical use.

Does sparse SFM pay off? On Two-Moons and on synthetic instances where the minimizer has $k$ items, we test whether the sparse-certificate method's queries grow nearly linearly in $n$ at fixed $k$. Given its high powers of $k$, we expect any advantage only at very small $k$. Screening is the competitor that must lose for sparse SFM to matter.

All code, oracles and query logs will be released so that future theory papers can report counts on the same families.