Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions

Abstract

We investigate three related and important problems connected to machine learning: approximating a submodular function everywhere, learning a submodular function (in a PAC-like setting [53]), and constrained minimization of submodular functions. We show that the complexity of all three problems depends on the 'curvature' of the submodular function, and provide lower and upper bounds that refine and improve previous results [3, 16, 18, 52]. Our proof techniques are fairly generic. We either use a black-box transformation of the function (for approximation and learning), or a transformation of algorithms to use an appropriate surrogate function (for minimization). Curiously, curvature has been known to influence approximations for submodular maximization [7, 55], but its effect on minimization, approximation and learning has hitherto been open. We complete this picture, and also support our theoretical claims by empirical results.

21 pages. A shorter version appeared in Advances of NIPS-2013

References in corpus (6)

• Near-optimal Nonmyopic Value of Information in Graphical Models
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Non-monotone submodular maximization under matroid and knapsack constraints
• Fast Semidifferential-based Submodular Function Optimization
• On the Approximation of Submodular Functions

Cited by in corpus (15)

• Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints
• Guarantees for Greedy Maximization of Non-submodular Functions with Applications
• Robust Maximization of Non-Submodular Objectives
• Structural Systems Theory: an overview of the last 15 years
• Influence Minimization Under Budget and Matroid Constraints: Extended Version
• Optimal approximation for unconstrained non-submodular minimization
• Reconfiguration Problems on Submodular Functions
• A Unified Framework of Constrained Robust Submodular Optimization with Applications
• On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
• On Maximization of Weakly Modular Functions: Guarantees of Multi-stage Algorithms, Tractability, and Hardness
• On the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functions
• Competitive Algorithms for Online Weighted Bipartite Matching and its Variants
• Training Data Subset Selection for Regression with Controlled Generalization Error
• Subquadratic Submodular Function Minimization
• Subadditive Load Balancing