{"ID":2824891,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.22714","arxiv_id":"2512.22714","title":"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 \u003e 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.","short_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 assu...","url_abs":"https://arxiv.org/abs/2512.22714","url_pdf":"https://arxiv.org/pdf/2512.22714v2","authors":"[\"Matey Neykov\"]","published":"2025-12-27T22:06:32Z","proceeding":"math.ST","tasks":"[\"math.ST\",\"stat.ME\"]","methods":"[]","has_code":false}