Stochastic Intermediate Gradient Method for Convex Problems with Stochastic Inexact Oracle
Stochastic Intermediate Gradient Method for Convex Problems with Stochastic Inexact Oracle
复制标题
DOI：
10.1007/s10957-016-0999-6
复制
发表时间：
2016-10-01
影响因子：
1.9
通讯作者：
Gasnikov, Alexander
中科院分区：
文献类型：
--
作者：
Dvurechensky, Pavel;Gasnikov, Alexander
本文对具有随机不精确预言的凸优化问题提出了新的求解方法。我们的第一种方法是由Devolder，Glineur和Nesterov提出的中间梯度方法的扩展确定性不精确的预言的问题。我们的方法可以应用于复合目标函数的问题，确定性和随机不精确的预言，并允许使用非欧几里德设置。我们估计的非最优差距的期望方面的收敛速度，并提供了一种方法来控制从这个速度的大偏差的概率。对于强凸问题，我们还介绍了该方法的两个修正。对于第一个修改，我们估计的收敛速度的非最优差距的期望，第二，我们提供了一个绑定的概率大偏差的收敛速度的非最优差距的期望。所有的速率导致所提出的方法的复杂性估计，其中乘法常数符合所考虑的一类凸复合优化问题的随机不精确预言的复杂性下界。
In this paper, we introduce new methods for convex optimization problems with stochastic inexact oracle. Our first method is an extension of the Intermediate Gradient Method proposed by Devolder, Glineur and Nesterov for problems with deterministic inexact oracle. Our method can be applied to problems with composite objective function, both deterministic and stochastic inexactness of the oracle, and allows using a non-Euclidean setup. We estimate the rate of convergence in terms of the expectation of the non-optimality gap and provide a way to control the probability of large deviations from this rate. Also we introduce two modifications of this method for strongly convex problems. For the first modification, we estimate the rate of convergence for the non-optimality gap expectation and, for the second, we provide a bound for the probability of large deviations from the rate of convergence in terms of the expectation of the non-optimality gap. All the rates lead to the complexity estimates for the proposed methods, which up to a multiplicative constant coincide with the lower complexity bound for the considered class of convex composite optimization problems with stochastic inexact oracle.