The approximation-radius gap conjecture for centrally symmetric convex bodies

Let XRnX\subseteq\mathbb{R}^n be a centrally symmetric convex body, let R(X,σ)R(X,\sigma) denote its minimax risk, and let zc,k(X)z_{c,k}(X) denote the approximation-radius quantity defined in the paper for 0<c10<c\leq 1 and dimension kk. The approximation-radius gap conjecture. For every 0<c10<c\leq 1, there exists a constant f(c)>0f(c)>0 such that

R(X,σ)lognf(c)maxkmin(zc,k(X)2,kσ2).R(X,\sigma)\leq\sqrt{\log n}\,f(c)\max_k\min\bigl(z_{c,k}(X)^2,k\sigma^2\bigr).

The conjecture would show that the approximation-radius lower bound loses at most a factor of order logn\sqrt{\log n}; the authors motivate it from the known gap for p\ell_p balls with 1p<21\leq p<2, while the supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

Adel Javanmard and Li Zhang, “The minimax risk of truncated series estimators for symmetric convex polytopes”, arXiv:1201.2462 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.