On Parallel Complexity of Nonsmooth Convex Optimization
On Parallel Complexity of Nonsmooth Convex Optimization
复制标题
非光滑凸优化的并行复杂度
DOI：
10.1006/jcom.1994.1025
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
A. Nemirovski
中科院分区：
文献类型：
--
作者：
A. Nemirovski
我们考虑标准的问题类别吗？（x）？最小，x？ BN与凸连续函数相关？将单位n维立方BN映射到0、1]。众所周知，在绝对常数因子（1/？）中，类相对于标准一阶甲骨文的信息复杂性是？ <12是所需的准确性（以？）。我们感兴趣的问题是，如果允许并行使用甲骨文的K副本，而不是单个甲骨文，则如何减少复杂性。我们证明“ K-Oracle复杂性”至少为O（1）（N/LN（2KN））1/3LN（1/？）。
We consider the standard class of problems ?(x) ? min, x ? Bn associated with convex continuous functions ? mapping the unit n-dimensional cube Bn into 0, 1]. It is known that the information complexity of the class with respect to the standard first-order oracle is, within an absolute constant factor, n ln (1/?), ? < 12 being the required accuracy (measured in terms of ?). The question we are interested in is how the complexity can be reduced if one is allowed to use K copies of the oracle in parallel rather than a single oracle. We demonstrate that the "K-oracle complexity" is at least O(1)(n/ln(2Kn))1/3ln(1/?).