提出自适应阈值连续贪心法,显著降低通信开销同时保持近似最优性能。
Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization

- 根据进度比率动态控制梯度计算,仅在收益不足时扩展活跃集
- 在CIFAR-10动物子集上达到与全量连续贪心相当的优化目标值
- 适用于高维特征需高效通信的资源分配与数据摘要场景
带拟阵约束的子模最大化是组合优化中的基础问题,广泛应用于传感、数据摘要、主动学习和资源分配。尽管序列贪心(SG)算法因不可逆选择仅能实现1/2近似比,连续贪心(CG)通过多线性松弛可达到最优的(1−1/e)近似比,但其决策向量逐渐稠密,导致每个基元素都需交换特征嵌入。本文提出ATCG(自适应阈值连续贪心),通过每部分的进度比率η_i控制梯度评估,仅当当前候选无法获得足够边际收益时才扩展代理的活跃集,从而直接限制特征嵌入的传输范围。理论分析表明,该方法具有基于曲率的近似保证,有效因子τ_eff=max{τ,1−c},在低曲率情况下可恢复CG性能。实验在CIFAR-10动物子集上的类别平衡原型选择任务中显示,ATCG在接近全量CG目标值的同时,大幅降低通信开销。
原文摘要 · Abstract (English)
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 $\bigl(1-\frac{1}{e}\bigr)$-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 \textit{ATCG} (\underline{A}daptive \underline{T}hresholded \underline{C}ontinuous \underline{G}reedy), 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 $τ_{\mathrm{eff}}=\max\{τ,1-c\}$, interpolating between the threshold-based guarantee and the low-curvature regime where \textit{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 \textit{ATCG} achieves objective values comparable to those of the full CG method while substantially reducing communication overhead through adaptive active-set expansion.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。