期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 63, 期 7, 页码 4709-4724出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2017.2701343
关键词
Convex optimization; oracle complexity; lower complexity bounds; randomized algorithms; distributional and high-probability lower bounds
资金
- NSF [CMMI-1232623, CMMI-1300144]
We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness. As a measure of complexity, we use distributional oracle complexity, which subsumes randomized oracle complexity as well as worst case oracle complexity. We obtain strong lower bounds on distributional oracle complexity for the box [-1, 1](n), as well as for the L-p-ball for p = 1 (for both low-scale and large-scale regimes), matching worst case upper bounds, and hence we close the gap between distributional complexity, and in particular, randomized complexity and worst case complexity. Furthermore, the bounds remain essentially the same for high-probability and bounded-error oracle complexity, and even for combination of the two, i.e., bounded-error high-probability oracle complexity. This considerably extends the applicability of known bounds.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据