Fast Semidifferential-based Submodular Function Optimization

Abstract

We present a practical and powerful new framework for both unconstrained and constrained submodular function optimization based on discrete semidifferentials (sub- and super-differentials). The resulting algorithms, which repeatedly compute and then efficiently optimize submodular semigradients, offer new and generalize many old methods for submodular optimization. Our approach, moreover, takes steps towards providing a unifying paradigm applicable to both submodular min- imization and maximization, problems that historically have been treated quite distinctly. The practicality of our algorithms is important since interest in submodularity, owing to its natural and wide applicability, has recently been in ascendance within machine learning. We analyze theoretical properties of our algorithms for minimization and maximization, and show that many state-of-the-art maximization algorithms are special cases. Lastly, we complement our theoretical analyses with supporting empirical experiments.

This work appeared in Proc. International Conference of Machine Learning (ICML, 2013)

References in corpus (1)

• Non-monotone submodular maximization under matroid and knapsack constraints

Cited by in corpus (8)

• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
• Submodular Hamming Metrics
• Batch greedy maximization of non-submodular functions: Guarantees and applications to experimental design
• The Lovasz-Bregman Divergence and connections to rank aggregation, clustering, and web ranking
• On Unconstrained Quasi-Submodular Function Optimization
• Maximizing submodular functions using probabilistic graphical models
• Approximation Guarantees of Local Search Algorithms via Localizability of Set Functions