Minibatch Stochastic Approximate Proximal Point Methods
Minibatch Stochastic Approximate Proximal Point Methods
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Hilal Asi;Karan N. Chadha;Gary Cheng;John C. Duchi
中科院分区：
文献类型：
--
作者：
Hilal Asi;Karan N. Chadha;Gary Cheng;John C. Duchi
我们扩展的近似邻近点（A P ROX）家庭的基于模型的方法来解决随机凸优化问题，包括随机次梯度，邻近点，束方法，minibatch设置。要做到这一点，我们提出了两个minibatched算法，我们证明了收敛速度的非渐近上界，揭示了minibatch大小的线性加速。与标准的随机梯度方法相比，即使对于非光滑函数，这些方法在小批量设置中也可以具有线性加速。我们的算法保持了所需的性状特性的A P ROX家族，如鲁棒性初始步长的选择。此外，我们显示了改进的收敛速度“插值”问题，这（例如）提供了一个新的并行化策略交替投影。我们证实了我们的理论结果与广泛的实证测试，这表明了准确的建模和minimizations提供的收益。
We extend the Approximate-Proximal Point ( A P ROX ) family of model-based methods for solving stochastic convex optimization problems, including stochastic subgradient, proximal point, and bundle methods, to the minibatch setting. To do this, we propose two minibatched algorithms for which we prove a non-asymptotic upper bound on the rate of convergence, revealing a linear speedup in minibatch size. In contrast to standard stochastic gradient methods, these methods may have linear speedup in the minibatch setting even for non-smooth functions. Our algorithms maintain the desirable traits characteristic of the A P ROX family, such as robustness to initial step size choice. Additionally, we show improved convergence rates for "interpolation" problems, which (for example) gives a new parallelization strategy for alternating projections. We corroborate our theoretical results with extensive empirical testing, which demonstrates the gains provided by accurate modeling and minibatching.