The approximation-radius gap conjecture for centrally symmetric convex bodies

About 14 years old · traced to

Let X⊆RnX\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<c≤10<c\leq 1 and dimension kk. The approximation-radius gap conjecture. For every 0<c≤10<c\leq 1, there exists a constant f(c)>0f(c)>0 such that

R(X,σ)≤log⁡n f(c)max⁡kmin⁡(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 log⁡n\sqrt{\log n}; the authors motivate it from the known gap for ℓp\ell_p balls with 1≤p<21\leq p<2, while the supplied text gives no resolution.

References

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.