We extend the Approximate-Proximal Point (aProx) family of model-based methods for solving stochastic convex optimization problems, including stochastic subgradient, proximal point, and bundle methods, to the minibatch and accelerated setting. To do so, we propose specific model-based algorithms and an acceleration scheme for which we provide non-asymptotic convergence guarantees, which are order-optimal in all problem-dependent constants and provide linear speedup in minibatch size, while maintaining the desirable robustness traits (e.g. to stepsize) of the aProx family. Additionally, we show improved convergence rates and matching lower bounds identifying new fundamental constants for "interpolation" problems, whose importance in statistical machine learning is growing; this, for example, gives a parallelization strategy for alternating projections. We corroborate our theoretical results with empirical testing to demonstrate the gains accurate modeling, acceleration, and minibatching provide.

我们扩展了 Approximate-Proximal Point 方法，在随机凸优化问题中应用包括随机次梯度、近端点和束方法，同时提出了更快的模型算法和加速方案，保持了 Approximate-Proximal Point 算法的鲁棒性，同时提供了更快的收敛速度和更低的界限。我们通过实证测试证实了理论结果的可行性。

基于模型的随机优化：加速、优化和并行计算的若干结果