Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

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 frac12-approximation due to irrevocable selections, Continuous Greedy (CG) attains the optimal bigl(1-frac1ebigr)-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 textitATCG (underlineAdaptive underlineThresholded underlineContinuous underlineGreedy), which gates gradient evaluations behind a per-partition progress ratio η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 τeff=maxτ,1-c, interpolating between the threshold-based guarantee and the low-curvature regime where textitATCG 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 textitATCG achieves objective values comparable to those of the full CG method while substantially reducing communication overhead through adaptive active-set expansion.