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

Gabor Braun, Sebastian Pokutta, Cristóbal Andrés Guzmán Paredes

Research output: Contribution to journalArticleAcademicpeer-review

7 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)4709 - 4724
JournalIEEE transactions on information theory
DOIs
Publication statusPublished - Jul 2017
Externally publishedYes

Fingerprint

Dive into the research topics of 'Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory'. Together they form a unique fingerprint.

Cite this