Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions
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 [28]), 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 [2,6,8,27]. 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 [3,29], 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.
Curvature and optimal algorithms for learning and 
      minimizing submodular functions This paper explores the impact of 
      a notion of function curvature on the approximability of problems 
      involving submodular functions. While it's not the first work to use this 
      notion of curvature to improve bounds for submodular functions (for 
      submodular maximization), this paper covers more settings. In particular, 
      the problems covered are: - efficiently finding (and representing) a 
      function f that approximates the submodular function - PAC-style 
      learning - constrained function minimization The paper makes 
      the case that many practically interesting functions have small curvature 
      and thus admit better approximations that previous bounds would indicate. 
      The main approach to solving the approximation problem is to 
      separately approximate the cured part of the underlying function. The 
      approach to the second problem is to use the Balcan-Harvey PAC-style 
      learning algorithm and apply the approximation result. The approach to the 
      third problem is less black-box than the previous two, but gives a means 
      of choosing an approximation of the original function to analyze; then 
      they can apply the previously mentioned results to understand how good an 
      approximation this gives. Finally, there is a brief experimental 
      section to demonstrate that for functions with small curvature (for the 
      "worst case" given that curvature), the empirical constrained minimization 
      closely tracks the approximation predicted. These are important 
      problems, with lots of different applications, and it's nice to see some 
      general tools for understanding what affects (in)approximability. 
      It would have been helpful to have more discussion of the 
      distinction between the notion of curvature used here and the 
      submodularity ratio (is there a way to compare their usefulness in 
      improving approximation ratios?) It is a bit difficult to digest 
      the new results, since the paper doesn't provide a succinct comparison 
      with existing worst-case bounds (for functions with maximum curvature). I 
      realize of course that there are a lot of other comparisons with previous 
      work one could make (for other specific classes of functions), but this 
      particular comparison seems that it would help the reader understand the 
      impact of taking curvature into account.