Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

arXiv:2604.03419v2 Announce Type: replace Abstract: Submodular maximization under matroid constraints is a fundamental problem in combinatorial optimization with applications in sensing, data summarization, active learning, and resource allocation. While the Sequential Greedy (SG) algorithm achieves only a frac{1}{2}-approximation due to irrevocable selections, Continuous Greedy (CG) attains the optimal igl(1-frac{1}{e}igr)-approximation via the multilinear relaxation, at the cost of a progressively dense decision vector that forces agents to exchange feature embeddings for nearly every ground-set element. We propose extit{ATCG} (nderline{A}daptive nderline{T}hresholded nderline{C}ontinuous nderline{G}reedy), which gates gradient evaluations behind a per-partition progress ratio eta_i, expanding each agent's active set only when current candidates fail to capture sufficient marginal gain, thereby directly bounding which feature embeddings are ever transmitted. Theoretical analysis establishes a curvature-aware approximation guarantee with effective factor au_{eff}=max{au,1-c}, interpolating between the threshold-based guarantee and the low-curvature regime where extit{ATCG} recovers the performance of CG. This shows that the problem structure, as captured by curvature, determines the amount of coordination and communication required to approach full-CG performance. Experiments on a class-balanced prototype selection problem over a subset of the CIFAR-10 animal dataset show that extit{ATCG} achieves objective values comparable to those of the full CG method while substantially reducing communication overhead through adaptive active-set expansion.

Source: arXiv cs.LG | 2026-05-20