Submodular Maximization via Taylor Series Approximation
This work addresses optimization efficiency for researchers in machine learning and operations research, but it is incremental as it builds on existing continuous greedy algorithms with a new approximation technique.
The paper tackles submodular maximization with matroid constraints for analytic and multilinear functions, showing that a continuous greedy algorithm achieves a ratio arbitrarily close to 0.63 using deterministic Taylor series approximation, which drastically reduces execution time compared to prior sampling-based methods.
We study submodular maximization problems with matroid constraints, in particular, problems where the objective can be expressed via compositions of analytic and multilinear functions. We show that for functions of this form, the so-called continuous greedy algorithm attains a ratio arbitrarily close to $(1-1/e) \approx 0.63$ using a deterministic estimation via Taylor series approximation. This drastically reduces execution time over prior art that uses sampling.