Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions

Abstract

Submodular optimization is widely used in large datasets. In order to speed up the problems solving, it is essential to design low-adaptive algorithms to achieve acceleration in parallel. In general, the function values are given by a value oracle, but in practice, the oracle queries may consume a lot of time. Hence, how to strike a balance between optimizing them is important. In this paper, we focus on maximizing a normalized and strictly monotone set function with the diminishing-return ratio $\gamma$ under a cardinality constraint, and propose two algorithms to deal with it. We apply the adaptive sequencing technique to devise the first algorithm, whose approximation ratio is arbitrarily close to $1-\mathrm{e}^{-\gamma }$ in $O(\log n \cdot \log (\log \frac{k}{\gamma }))$ adaptive rounds, and requires $O(n^2\cdot \log (\log \frac{k}{\gamma }))$ queries. Then by adding preprocessing and parameter estimation steps to the first algorithm, we get the second one. The second algorithm trades a small sacrifice in adaptive complexity for a significant improvement in query complexity. With the same approximation and adaptive complexity, the query complexity is improved to $O(n\cdot \log (\log \frac{k}{\gamma }))$. To the best of our knowledge, this is the first paper of designing adaptive algorithms for maximizing a monotone function using the diminishing-return ratio.