Regularized Unconstrained Weakly Submodular Maximization
<|reference_start|>Regularized Unconstrained Weakly Submodular Maximization: Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form $h = f-c$, where $f$ is a monotone, non-negative, weakly submodular set function and $c$ is a modular function. We design a deterministic approximation algorithm that runs with ${{O}}(\frac{n}{\epsilon}\log \frac{n}{\gamma \epsilon})$ oracle calls to function $h$, and outputs a set ${S}$ such that $h({S}) \geq \gamma(1-\epsilon)f(OPT)-c(OPT)-\frac{c(OPT)}{\gamma(1-\epsilon)}\log\frac{f(OPT)}{c(OPT)}$, where $\gamma$ is the submodularity ratio of $f$. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of $f$. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function $f$, and Bayesian A-Optimal design for weakly submodular $f$. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.<|reference_end|>
@article{zhu2024regularized,
    title={Regularized Unconstrained Weakly Submodular Maximization},
    author={Yanhui Zhu and Samik Basu and A. Pavan},
    journal={Proceedings of the 33rd ACM International Conference on
  Information and Knowledge Management (CIKM 2024)},
    year={2024},
    doi={10.1145/3627673.3679651},
    archivePrefix={arXiv},
    eprint={2408.04620},
    primaryClass={cs.DS}
}