Polynomial-Time Near-Optimal Estimation over Certain Type-2 Convex Bodies

Abstract

We develop polynomial-time algorithms for near-optimal minimax mean estimation under ${\ell }_2$-squared loss in a Gaussian sequence model under convex constraints. The parameter space is an origin-symmetric, type-2 convex body $K\subset {\mathbb{R}}^n$, and we assume additional regularity conditions: specifically, we assume $K$ is well-balanced, i.e., there exist known radii $r,R>0$ such that $r{B}_2\subseteq K\subseteq R{B}_2$, as well as oracle access to the Minkowski gauge of $K$. Under these and some further assumptions on $K$, our procedures achieve the minimax rate up to small factors, depending poly-logarithmically on the dimension, while remaining computationally efficient. We further extend our methodology to the linear regression and robust heavy-tailed settings, establishing polynomial-time near-optimal estimators when the constraint set satisfies the regularity conditions above. To the best of our knowledge, these results provide the first general framework for attaining statistically near-optimal performance under such broad geometric constraints while preserving computational tractability.

fixed some typos