Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
This addresses fundamental algorithmic challenges in machine learning for researchers and practitioners dealing with submodular optimization, though it is incremental as it builds on existing work.
The paper tackles the problems of approximating, learning, and minimizing submodular functions by showing that their complexity depends on curvature, providing refined lower and upper bounds that improve previous results.
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.