# Provable Submodular Minimization using Wolfe's Algorithm

arXiv: https://arxiv.org/abs/1411.0095 · HTML: https://mlsanity.com/paper/1411.0095/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2014.

## Built on by (most cited first, 10 of 10)

- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case](https://mlsanity.com/paper/2306.05865/) (2023)
- [Efficient Vertex-Oriented Polytopic Projection for Web-scale Applications](https://mlsanity.com/paper/2103.05277/) (2021)
- [Reusing Combinatorial Structure: Faster Iterative Projections over Submodular Base Polytopes](https://mlsanity.com/paper/2106.11943/) (2021)
- [A Family of Distributions of Random Subsets for Controlling Positive and Negative Dependence](https://mlsanity.com/paper/2408.01022/) (2024)
- [Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles](https://mlsanity.com/paper/2510.15257/) (2025)
- [Client Selection in Federated Learning with Data Heterogeneity and Network Latencies](https://mlsanity.com/paper/2504.01921/) (2025)
- [A Policy Efficient Reduction Approach to Convex Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/2108.12916/) (2021)
- [Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems](https://mlsanity.com/paper/2505.17443/) (2025)
- [Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization](https://mlsanity.com/paper/2606.14764/) (2026)

## Abstract (arXiv)

Owing to several applications in large scale learning and vision problems, fast submodular function minimization (SFM) has become a critical problem. Theoretically, unconstrained SFM can be performed in polynomial time [IFF 2001, IO 2009]. However, these algorithms are typically not practical. In 1976, Wolfe proposed an algorithm to find the minimum Euclidean norm point in a polytope, and in 1980, Fujishige showed how Wolfe's algorithm can be used for SFM. For general submodular functions, this Fujishige-Wolfe minimum norm algorithm seems to have the best empirical performance. Despite its good practical performance, very little is known about Wolfe's minimum norm algorithm theoretically. To our knowledge, the only result is an exponential time analysis due to Wolfe himself. In this paper we give a maiden convergence analysis of Wolfe's algorithm. We prove that in t iterations, Wolfe's algorithm returns an O(1/t)-approximate solution to the min-norm point on em any polytope. We also prove a robust version of Fujishige's theorem which shows that an O(1/n2)-approximate solution to the min-norm point on the base polytope implies em exact submodular minimization. As a corollary, we get the first pseudo-polynomial time guarantee for the Fujishige-Wolfe minimum norm algorithm for unconstrained submodular function minimization.