TY - JOUR

T1 - Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory

AU - Braun, Gabor

AU - Pokutta, Sebastian

AU - Guzmán Paredes, Cristóbal Andrés

PY - 2017/7

Y1 - 2017/7

N2 - 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 highprobability oracle complexity. This considerably extends the applicability of known bounds.

AB - 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 highprobability oracle complexity. This considerably extends the applicability of known bounds.

U2 - 10.1109/tit.2017.2701343

DO - 10.1109/tit.2017.2701343

M3 - Article

SP - 4709

EP - 4724

JO - IEEE transactions on information theory

JF - IEEE transactions on information theory

SN - 0018-9448

ER -