Timezone: »

 
Oral
Learning to Optimize Combinatorial Functions
Nir Rosenfeld · Eric Balkanski · Amir Globerson · Yaron Singer

Wed Jul 11 08:00 AM -- 08:20 AM (PDT) @ K11
in Optimization (Combinatorial) 2 »

Submodular functions have become a ubiquitous tool in machine learning. They are learnable from data, and can be optimized efficiently and with guarantees. Nonetheless, recent negative results show that optimizing learned surrogates of submodular functions can result in arbitrarily bad approximations of the true optimum. Our goal in this paper is to highlight the source of this hardness, and propose an alternative criterion for optimizing general combinatorial functions from sampled data. We prove a tight equivalence showing that a class of functions is optimizable if and only if it can be learned. We provide efficient and scalable optimization algorithms for several function classes of interest, and demonstrate their utility on the task of optimally choosing trending social media items.

[ PDF]  [ Video] 

Author Information

Nir Rosenfeld (Harvard University)
Eric Balkanski (Harvard)
Amir Globerson (Tel Aviv University, Google)
Yaron Singer (Harvard)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors