STOCHASTIC MODEL-BASED MINIMIZATION OF WEAKLY CONVEX FUNCTIONS
STOCHASTIC MODEL-BASED MINIMIZATION OF WEAKLY CONVEX FUNCTIONS
复制标题
DOI：
10.1137/18m1178244
复制
发表时间：
2019-01-01
影响因子：
3.1
通讯作者：
Drusvyatskiy, Dmitriy
中科院分区：
文献类型：
--
作者：
Davis, Damek;Drusvyatskiy, Dmitriy
我们考虑了一种算法家族，该算法连续采样并最大程度地减少了目标函数的简单随机模型。我们表明，在合理条件下，模型的近似质量和规律性，任何此类算法都以o（k（-1/4））为零的自然平稳性量度降至零。结果，我们获得了随机近端，近端亚速度和正规高斯 - 牛顿方法的首次复杂性，以最大程度地减少具有光滑图的凸函数的组成。指导原则是基本的复杂性保证，即所有正在考虑的算法都可以解释为莫罗（Moreau Chemvelope）的隐性平滑平滑的近似下降方法。专门针对经典环境，我们获得了随机投影梯度方法的长期收敛速率，而无需分组，以最大程度地减少封闭凸组的平滑函数。
We consider a family of algorithms that successively sample and minimize simple stochastic models of the objective function. We show that under reasonable conditions on approximation quality and regularity of the models, any such algorithm drives a natural stationarity measure to zero at the rate O(k(-1/4)). As a consequence, we obtain the first complexity guarantees for the stochastic proximal point, proximal subgradient, and regularized Gauss-Newton methods for minimizing compositions of convex functions with smooth maps. The guiding principle, underlying the complexity guarantees, is that all algorithms under consideration can be interpreted as approximate descent methods on an implicit smoothing of the problem, given by the Moreau envelope. Specializing to classical circumstances, we obtain the long-sought convergence rate of the stochastic projected gradient method, without batching, for minimizing a smooth function on a closed convex set.