Poster
The Power of Optimization from Samples
Eric Balkanski · Aviad Rubinstein · Yaron Singer

Tue Dec 6th 06:00 -- 09:30 PM @ Area 5+6+7+8 #19 #None

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.

Author Information

Eric Balkanski (Harvard University)
Aviad Rubinstein (UC Berkeley)
Yaron Singer (Harvard University)

More from the Same Authors