Timezone: »

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

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #19
in Tuesday Posters »

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.

Keywords: Learning Theory · Combinatorial Optimization
[ PDF] 

Author Information

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

More from the Same Authors