Toward Highly Efficient and Private Submodular Maximization via Matrix-Based Acceleration
This addresses efficiency and privacy concerns for applications like document summarization and sensor placement, representing a hybrid approach rather than a paradigm shift.
The paper tackles the computational bottleneck in submodular function maximization by proposing an integrated framework that accelerates function evaluations and provides privacy guarantees, achieving a theoretical complexity of O(ε⁻²(nd+kn+kd²)log(k/δ)).
Submodular function maximization is a critical building block for diverse tasks, such as document summarization, sensor placement, and image segmentation. Yet its practical utility is often limit by the $O(knd^2)$ computational bottleneck. In this paper, we propose an integrated framework that addresses efficiency and privacy simultaneously. First, we introduce a novel matrix-based computation paradigm that accelerates function evaluations. Second, we develop approximate data structures that further streamline the optimization process, achieving a theoretical complexity of $O(ε^{-2}(nd+kn+kd^2)\log(k/δ))$. Third, we integrate ($ε, δ$)-DP guaranties to address the privacy concerns inherent in sensitive optimization tasks.