Many image-labeling problems ask for a small answer inside a large image: a thin crack, a small object, a few pixels that change label in the late rounds of an iterative solver. When the labeling cost includes "higher-order" terms, meaning costs defined on whole patches or superpixels of pixels rather than on pairs, the best exact solvers still sweep every patch in the image on every pass. They do this even when the true answer touches only a few hundred pixels out of a million. Recent theory on submodular function minimization (SFM) points to a way out. Submodular functions are set functions with diminishing returns, the discrete counterpart of convex functions. That theory shows that when the minimizing set has size $k \ll n$, a solver can find it with a number of function evaluations that grows almost linearly in $n$ and polynomially in $k$ (Sparse Submodular Function Minimization). The key device is a sparse dual certificate: a short proof that every element outside a candidate set can be safely excluded.
We propose to carry this certificate idea into sum-of-submodular vision energies, where it becomes much stronger than in the black-box setting because the energy is a sum of small, local pieces. The core claim is this. In a broad and common class of these energies, patches far from the answer can be certified inactive at zero cost. We can therefore grow an active region from the unary evidence, run an existing polyhedral solver only on patches that touch that region, and stop with an exact, checkable certificate of global optimality. The number of expensive patch evaluations then scales with the size and boundary of the answer, not with the image.
Core Claim
We write the energy as $f(S) = \sum_{i \in S} u_i + \sum_{r=1}^{R} f_r(S \cap c_r)$. Here $S$ is the set of pixels labeled foreground (or flipped, in a move), $u_i$ is the per-pixel cost, and each $f_r$ is a submodular cost on patch $c_r$ with $f_r(\emptyset)=0$. By Edmonds' min-max theorem, a set $A$ is a global minimizer if there are vectors $y_r$ in each patch's base polytope $B(f_r)$ such that the combined dual $y = u + \sum_r y_r$ is nonpositive on $A$ and nonnegative off it. The base polytope is the set of vectors that lie below $f_r$ on every subset and sum to $f_r(c_r)$, and the condition is
$$ y_e = u_e + \sum_{r:\, e \in c_r} (y_r)_e \;\le 0 \ \ \text{for } e \in A, \qquad y_e \ge 0 \ \ \text{for } e \notin A . $$
The observation that makes locality possible comes from the same min-max theorem. A nonnegative vector exists in $B(f_r)$ exactly when $\emptyset$ minimizes $f_r$, and when in addition $f_r(c_r)=0$ the zero vector itself lies in $B(f_r)$. We call such a patch silent. Silent patches include the symmetric "all-or-nothing" consistency terms of the $P^n$ Potts family (P3 & Beyond) and most learned smoothing priors normalized so that uniform patches cost nothing. A silent patch with no element in $A$ can be assigned $y_r = 0$ without ever being evaluated. The certificate outside the active region then reduces to checking the sign of the cheap unary terms plus the duals of the few patches that straddle the region's boundary.
The resulting algorithm has four steps. It seeds $A$ with pixels whose unary cost is negative. It runs block coordinate descent with Wolfe's minimum-norm-point routine only on patches meeting $A$. It checks the certificate condition on boundary pixels. It then expands $A$ where the check fails, and stops when it passes. The algorithm is exact whenever it terminates, which it always does, in the worst case at $A=V$. The question is how small $A$ stays.
Research Program
The work has a theoretical half and a systems half, joined by a single quantity: the number of patch-oracle evaluations. We count separately the $O(n)$ unary reads, which are unavoidable and cost one arithmetic operation each, and the evaluations of higher-order patch functions, which dominate runtime in practice.
On the theory side, the first goal is an upper bound on patch evaluations of the form $\mathrm{poly}(k, |c|, d) \cdot \log(1/\delta)$. Here $k$ is the minimizer size, $|c|$ the maximum patch size, $d$ the maximum number of patches per pixel, and $\delta$ a margin by which background unaries exceed the most negative boundary marginal. We will reuse subgradient truncation and coordinate sampling from Graur, Jiang and Sidford, but confine them to the active region. Their black-box guarantee pays $\tilde{O}(n \cdot \mathrm{poly}(k))$ because it has no notion of locality. Ours is intended to drop the $n$ factor for patch evaluations at the cost of a structural assumption, namely silence plus margin.
The second goal is a separation result. An algorithm that sees only the aggregate energy $f(S)$, as in the lower-bound models of New Query Lower Bounds for SFM and the deterministic $\Omega(n\log n)$ bound of Graur et al., needs $\Omega(n)$ aggregate queries even on silent sparse instances. Each such query internally touches all $R$ patches, so the total cost is $\Omega(nR)$, whereas patch-level access allows $\mathrm{poly}(k,|c|,d)$. This answers a narrow but concrete piece of the open question of what decomposition buys in query complexity, a question that the maximum-flow reduction of Axiotis et al. leaves untouched because it bounds running time, not information.
The third goal is a negative example: an instance with non-silent patches on which the active region must grow to size $\Omega(n)$ even though $k=1$. This tells practitioners exactly when to expect locality to fail.
On the systems side, we will build the local solver on top of the SoS-MinNorm block coordinate descent of Shanu, Arora and Singla. That solver already handles patches of hundreds of pixels but processes all of them. We supply the method that decides which patches to process and when to stop. Wolfe's routine lacks worst-case guarantees, and Chakrabarty et al. show such heuristics need $\Omega(n)$ subgradient calls on a monolithic polytope. We therefore treat it as an inner solver whose dimension is bounded by $|A|$. Bounding the active region is what makes that lower bound harmless here.
The most useful application may be multi-label inference. In α-expansion, each step solves a binary problem in which pixels either switch to label α or stay. After the first few steps, the set that switches is typically tiny, so each move is a sparse binary problem, and for consistency-style patches the current labeling tends to make them silent. MLHybrid (Shanu et al.) solves each such move over the whole image. We will measure how much of its 28-second Middlebury runtime is spent on patches that a local certificate would never have evaluated.
Baselines
The naive reference point is the do-nothing version of the strongest solver. We run SoS-MinNorm (Shanu et al.) on the full image to a matched duality gap. It is the right reference because our method changes only which patches are visited, so any gain is attributable to locality. On synthetic grids with 24-pixel patches, the file reports SoS-MinNorm finishing in about 0.02 seconds while Generic Cuts failed to compute. No reported result was found on Lacuna for SoS-MinNorm energy or runtime on the image benchmarks we use, so we will rerun it ourselves with identical energies, stopping tolerance, and hardware. Beating it means reaching the same certified energy with fewer patch evaluations and less wall-clock time, with the gap widening as $n$ grows at fixed $k$.
For multi-label problems, the strongest existing method is MLHybrid (Shanu et al.). It reports 28 seconds to effective convergence on Middlebury stereo, where SOS-MNP failed to converge within 50 minutes, and mIoU 0.579 on Pascal VOC against 0.544 for DeepLabv3+ alone. We will replace its per-move binary solve with our local certified solve, keeping its handling of invalid states and its expansion schedule unchanged. Beating it means matching 0.579 mIoU and the final energy while cutting total runtime, with the savings concentrated in late expansion moves.
For hypergraph and cardinality-based energies, the strongest competitor is SparseCard (Approximate DSFM for Cardinality-Based Components). It reports finding solutions on smallplant in seconds where exact continuous methods took roughly 20 minutes. SparseCard is approximate, at a $(1+\epsilon)$ factor, and limited to cardinality-based patches. We will compare on smallplant and octopus at equal wall-clock budgets. To beat it, our method must be exact and no slower on those components, and it must also run on general learned patch functions where SparseCard does not apply.
Two ablations isolate the key ingredient. The first keeps our region-growing schedule but removes the certificate, stopping when the region stops changing. This shows whether certification costs much and whether uncertified growth ever stops at a wrong answer. The second keeps the certificate but forbids zero duals for silent patches, so that every patch must be evaluated once. This measures how much of the saving comes from silence specifically.
Why not just…?
Why not just crop a box around the object and solve there? This is the most practical threat, and it will often give the right answer. However, it needs a detector, it has no way of telling when the object leaks out of the box, and the energy inside the box differs from the full energy because border patches are cut. We will sweep crop margins on Gulshan interactive segmentation (where S3SVM reports 7.3% error against GrabCut's 10.6% in Fix et al.) and on small Pascal objects. We will report how often a cropped solution has strictly higher full-image energy than the certified optimum, and at what margin cropping becomes as slow as our method. If cropping at a modest margin is almost always exact and faster, our contribution reduces to providing the certificate, and we will say so.
Why not just reduce to a graph cut and use a fast max-flow solver? Max-flow on pairwise or gadget-reduced graphs is near-linear in practice. However, exact gadgets for general submodular patches grow exponentially with patch size: Generic Cuts failed at 24-pixel patches in Shanu et al.. Cardinality gadgets grow quadratically (SparseCard). Even the theoretically efficient route of Axiotis et al. carries a quadratic per-patch overhead and still processes all $n$ pixels. On pairwise or small-patch energies, a max-flow solver may well win, and we will include that regime and report it.
Why not just use local hypergraph clustering? Seeded local cut methods already do work proportional to the output on cardinality-based hyperedges. That is essentially SparseCard on StackOverflow, where hyperedges exceed 60,000 nodes. Our method generalizes this to arbitrary learned submodular patches and adds an exact global-optimality certificate. On cardinality-only instances, the two should behave similarly, and we expect no advantage there beyond exactness.
Proposed Experiments
The decisive experiment is a scaling test on synthetic lattices. We fix the minimizer size $k$ and patch size, from 16 to roughly 230 pixels as in SoS-MinNorm, and grow the image from $10^4$ to $10^7$ pixels. We plot patch evaluations and wall-clock time to a certified optimum. The method succeeds if its curve is flat in $n$, apart from the unary scan, while the full SoS-MinNorm curve grows linearly. A companion test lowers the margin $\delta$ and introduces non-silent patches, checking whether active-region growth follows the predicted dependence and whether our constructed hard instance forces linear growth.
On real data, we use Gulshan images, smallplant and octopus, Pascal VOC with MLHybrid-style patch energies, and Middlebury stereo with α-expansion. For each, we report final energy relative to the certified optimum, the fraction of patches ever evaluated, the size of the active region as a fraction of the image and of the true answer, runtime, and task accuracy: pixel error for segmentation and mIoU for Pascal.
For the expansion-move study, we additionally log the size of the switching set at each move. This tests directly whether late moves are sparse and silent in practice. If moves stay large, or patches are rarely silent on real learned energies, the application claim fails and only the synthetic and binary-segmentation results remain.
References
- Sparse Submodular Function Minimization
- P3 & Beyond: Solving Energies with Higher Order Cliques
- New Query Lower Bounds for Submodular Function Minimization
- Improved Lower Bounds for Submodular Function Minimization
- Decomposable Submodular Function Minimization via Maximum Flow
- Min Norm Point Algorithm for Higher Order MRF-MAP Inference
- Subquadratic submodular function minimization
- An Inference Algorithm for Multi-label MRF-MAP Problems with Clique Size 100
- Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components
- Structured Learning of Sum-of-Submodular Higher Order Energy Functions