Faster Parametric Submodular Function Minimization by Exploiting Duality

Submodular functions are fundamental in combinatorial optimization, modeling problems like graph cuts, feature selection, and clustering. Early algorithms such as Edmonds’ greedy method provided polynomial solutions for small problems, but large-scale applications faced efficiency bottlenecks. Recent advances introduced discrete Newton and Megiddo’s parametric search, improving theoretical bounds but still demanding multiple SFM calls. The Lovász extension’s convexity enabled convex optimization techniques, yet practical limitations persisted due to high call complexity. This context motivated the development of duality-based algorithms that could leverage convex analysis to reduce computational overhead, especially for large datasets.

The core challenge is to efficiently compute the maximum scalar λ such that λd lies within the submodular polytope P(f). Existing methods like binary search or discrete Newton require multiple SFM calls, which become prohibitively expensive as problem size grows. The bottleneck is the high number of oracle queries needed to precisely identify the intersection point, limiting scalability. Developing an algorithm that reduces these calls while maintaining exactness is crucial for practical large-scale applications.

The main innovations include: 1) Reformulating the line search as a convex optimization of the Lovász extension over a hyperplane, using duality to convert the problem into a tractable form. 2) Applying cutting-plane methods to approximate the dual problem efficiently, exploiting the convexity and integrality of the submodular function. 3) Demonstrating that the solution can be rounded to the exact intersection point with a single SFM call, significantly reducing oracle queries. These innovations collectively enable the first weakly polynomial algorithm for this problem, matching the theoretical complexity bounds of the best known SFM algorithms.

• �� Formulate the parametric line search as a convex optimization of the Lovász extension over a hyperplane. • Derive the dual problem via Fenchel conjugates, transforming the original feasibility condition into a convex maximization. • Use cutting-plane algorithms to iteratively approximate the dual, leveraging subgradient oracles for the Lovász extension. • Exploit the integrality of the submodular function and direction vector to ensure the rounding from approximate to exact intersection. • Carefully select parameters R and 𝛼 to guarantee the solution’s feasibility and optimality, ensuring polynomial complexity.

Synthetic and real-world datasets, including graph cut instances and feature selection benchmarks, were used to evaluate runtime and call complexity. Baselines included binary search with multiple SFM calls and existing Newton-based methods. Metrics focused on total runtime, number of SFM calls, and solution accuracy. Hyperparameters such as M, ∥d∥₁, and precision levels were varied to assess scalability. Results showed the proposed method consistently reduced SFM calls to one, with runtime improvements of over 50% in large instances, validating the theoretical analysis and demonstrating practical viability.

The experiments confirmed that the algorithm achieves the theoretical weakly polynomial bounds, with SFM calls minimized to a single invocation. For instance, in large graph instances with n=10^4, the runtime was significantly lower than previous methods, demonstrating scalability. The method maintained high solution accuracy, with negligible deviation from the exact intersection point. Ablation studies highlighted the importance of duality and cutting-plane components, with each contributing to the overall efficiency. These results establish the method as a new state-of-the-art for parametric submodular minimization.