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 additional conditions guaranteeing an efficient approximate quadratic-form-maximization oracle on $K$, our procedures achieve the minimax rate up to factors that depend polylogarithmically 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.

the manuscript underwent a major revision; fixed multiple typos and errors; added additional results; main story remains the same