The Power of Optimization from Samples
We consider the problem of optimization from samples of monotone submodular functions with bounded curvature. In numerous applications, the function optimized is not known a priori, but instead learned from data. What are the guarantees we have when optimizing functions from sampled data? In this paper we show that for any monotone submodular function with curvature c there is a (1 c)/(1 + c c 2 ) approximation algorithm for maximization under cardinality constraints when polynomially-many samples are drawn from the uniform distribution over feasible sets. Moreover, we show that this algorithm is optimal. That is, for any c < 1, there exists a submodular function with curvature c for which no algorithm can achieve a better approximation. The curvature assumption is crucial as for general monotone submodular functions no algorithm can obtain a constant-factor approximation for maximization under a cardinality constraint when observing polynomially-many samples drawn from any distribution over feasible sets, even when the function is statistically learnable.
Optimization from samples of monotone submodular functions with bounded curvature is studied. The authors provide and prove hard bounds on the approximation ratio for this problem. Specifically, using a probabilistic argument, they show that the approximation bounds are tight. They focus on the constrained case and consider the problem of maximizing the function with a cardinality constraint and provide a simple algorithm to solve the problem. Simulation study suggests that the algorithm is better than the best sample and a random set.
The paper is overall well written, in particular: section 1. sets up the problem well; intuition for the proofs were helpful in checking them and I think it should be accessible to readers with some basic understanding of submodular optimization literature. The references given by the authors are standard, good and popular which is good. In particular, I liked the hardness section where the idea is to classify elements of the ground set into two categories: good, bad and poor. Poor elements are only useful for making the constructed function monotone submodular whereas the good and bad are elements that carry very less "information". I am not sure if information is the right word here since usually it is related to entropy functions, it will be nice if the authors can describe why they call it that way.   One major concern that I have is the simulation experiments. In general, I think  that a single random set is not fair for comparison, if you are going to compare it with randomized selection, I think many draws should be conducted for evaluation (similar to boot strapping) and a confidence interval or bar would convey more than a single random draw. Secondly, while this seeme like a theoretical paper, nonetheless, I feel like it can/should be supplemented with some experiments using real datasets on problems that the authors mention in section 1. This is the main reason for my score for question 5, 7 (technical quality, Potential impact or usefulness).  While the analysis works for the special case of cardinality constrained problems, any thoughts on how to adapt the analysis to other constraints like cover or knapsack constraints? (I suppose that this is not simple as it sounds and can be highly nontrivial?)