我们提出了第一个针对一组约束下最大化非负单调可分解子模函数 $F=\sum_{i=1}^N f^i$ 的小批量算法。我们考虑两种采样方法：均匀采样和加权采样。我们首先证明了加权采样的小批量算法在理论和实践上都优于最先进的稀疏化方法。 令人惊讶的是，我们的实验结果表明均匀采样优于加权采样。然而，无法用最坏情况分析来解释这一点。我们的主要贡献是使用平滑分析为我们的实验结果提供理论基础。我们证明了在非常温和的假设下，均匀采样在小批量和稀疏化方法中都更优。我们通过实验证明了这些假设对我们的数据集成立。均匀采样易于实现，其复杂度与 $N$ 无关，使其成为处理海量现实世界数据集的完美选择。