Amin Karbasi
Probabilistic Submodular Maximization in Sub-Linear Time"

Abstract: In this talk, we consider optimizing submodular functions that are
drawn from some unknown distribution. This setting arises, e.g., in
recommender systems, where the utility of a subset of items may depend
on a user-specific submodular utility function. In modern
applications, the ground set of items is often so large that even the
widely used (lazy) greedy algorithm is not efficient enough. As a
remedy, we introduce the problem of sublinear time probabilistic
submodular maximization: Given training examples of functions (e.g.,
via user feature vectors), we seek to reduce the ground set so that
optimizing new functions drawn from the same distribution will provide
almost as much value when restricted to the reduced ground set as when
using the full set.