May, 2016
优化复合目标的紧密复杂度界
Tight Complexity Bounds for Optimizing Composite Objectives
TL;DR通过使用分量函数的梯度和prox oracles提供了最小化m个凸函数平均值的复杂性的严格上下界；我们表明决定性和随机优化之间存在显着差距。对于光滑函数，我们表明在确定性和随机设置中，加速梯度下降(AGD)和SVRG的加速变体分别是最优的，并且梯度Orcale足以获得最佳速率。对于非光滑函数，通过接入prox oracles可降低复杂度，因此，我们提出基于平滑的最优方法，以改进仅使用梯度访问的方法。