# Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

arXiv: https://arxiv.org/abs/2604.03419 · HTML: https://mlsanity.com/paper/2604.03419/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 3 Apr 2026.

## Builds on (most cited first, 10 of 10)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Between hard and soft thresholding: optimal iterative thresholding algorithms](https://mlsanity.com/paper/1804.08841/) (2018)
- [Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization](https://mlsanity.com/paper/1311.5750/) (2013)
- [Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings](https://mlsanity.com/paper/1802.03825/) (2018)
- [Distributed Strategy Selection: A Submodular Set Function Maximization Approach](https://mlsanity.com/paper/2107.14371/) (2021)
- [Federated Learning Using Variance Reduced Stochastic Gradient for Probabilistically Activated Agents](https://mlsanity.com/paper/2210.14362/) (2022)
- [ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization](https://mlsanity.com/paper/2505.13670/) (2025)
- [FedMPDD: Communication-Efficient Federated Learning with Privacy Preservation Attributes via Projected Directional Derivative](https://mlsanity.com/paper/2512.20814/) (2025)

## Abstract (arXiv)

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.