Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
Accelerated, Optimal, and Parallel: Some Results on Model-Based Stochastic Optimization
复制标题
DOI：
--
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Karan N. Chadha;Gary Cheng;John C. Duchi
中科院分区：
文献类型：
--
作者：
Karan N. Chadha;Gary Cheng;John C. Duchi
我们将近似近点 (aProx) 系列基于模型的方法（包括随机次梯度、近点和束方法）扩展到小批量和加速设置，用于解决随机凸优化问题。为此，我们提出了特定的基于模型的算法和加速方案，为其提供非渐近收敛保证，这些保证在所有与问题相关的常数中都是顺序最优的，并在小批量大小中提供线性加速，同时保持 aProx 系列所需的鲁棒性特征（例如步长）。此外，我们还展示了收敛速度的提高和匹配下界，从而确定了“插值”问题的新基本常数，“插值”问题在统计机器学习中的重要性正在不断增长；例如，这给出了交替投影的并行化策略。我们通过实证测试证实了我们的理论结果，以证明精确建模、加速和小批量处理所提供的收益。
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.