有限和（finite sum）优化问题,也被称为经验风险最小化,是机器学习领域的关键问题,它可以帮助学习模型获得令人满意的性能,因而需要进行深入研究。为了解决这样一个问题,许多研究者设计出了各种不同的随机增量梯度方法（randomized incremental gradient methods）,包括SAG（Stochastic Average Gradient）、SVRG（Stochastic Variance Reduced Gradient）和Katyusha等等,并给出了这些算法在不同条件下的上界复杂度的分析。尽管如此,研究清楚这些算法在某些情况下是否可以具有更小的复杂度,以及是否存在其他一些具有更高性能的方法仍然很重要。为了回答这些问题,一些研究者提出了不同条件下算法的下界复杂度。然而,这些下界依赖于特定的条件:确定性的优化算法,或者是分量函数（component function）的选择遵从某个固定的概率分布。同时,在某些情况下一些下界复杂度并没有与已知算法的上界复杂度相匹配。为了打破这些限制,本文在两种经典的有限和优化问题类别上,得到了随机增量梯度方法的紧的下界复杂度。证明技巧是建立一种通用的证明框架,首先分别在两种情况下构造相应的对抗函数（adversarial function）,并根据当前迭代点到有限和函数的最优点的距离,得到该距离的一个下界;然后根据有限和函数的凸性,得到当前函数值与最优函数值差值的下界;接着得到迭代次数的一个下界,并运用不等式的技巧估计其中的关键参数,最终得到下界复杂度。得到的结果是:当分量函数是强凸和光滑的时候,得到的下界收敛复杂度与Katyusha算法的上界复杂度紧密匹配;当有限和函数本身是强凸函数,且分量函数序列是平均光滑的时候,其下界复杂度与SDCA without duality和Katyusha X算法的上界复杂度紧密匹配。同时,两种情况下解的精度参数与条件数和函数个数无依赖性。