Unsolved

Information-theoretic limits under heavy-tailed (non-sub-Gaussian) noise

Sourced from the work of Akshay Prasadan, Matey Neykov

§ Problem Statement

Setup

Fix integers d1d\ge 1 and N1N\ge 1, and fix contamination parameters κ(0,1/2]\kappa\in(0,1/2] and ϵ[0,1/2κ]\epsilon\in[0,1/2-\kappa] (equivalently, one may consider the boundary regime ϵ1/2\epsilon\le 1/2). Let p>2p>2, ν>0\nu>0, and let KRdK\subseteq\mathbb R^d be a known constraint set for the unknown mean vector μ\mu (in the motivating framework, KK is star-shaped with respect to 00). Define

Pp,ν={P on Rd: EP[ξ]=0, EPξ2pνp}.\mathcal P_{p,\nu}=\left\{P\ \text{on }\mathbb R^d:\ \mathbb E_P[\xi]=0,\ \mathbb E_P\|\xi\|_2^p\le \nu^p\right\}.

For (μ,P)K×Pp,ν(\mu,P)\in K\times\mathcal P_{p,\nu}, let Xi=μ+ξiX_i^\star=\mu+\xi_i with ξ1,,ξNi.i.d.P\xi_1,\dots,\xi_N\stackrel{i.i.d.}{\sim}P. Under Huber contamination, an adversary replaces at most ϵN\lfloor\epsilon N\rfloor observations arbitrarily, yielding X1,,XNX_1,\dots,X_N. For measurable estimators μ^:(Rd)NRd\hat\mu:(\mathbb R^d)^N\to\mathbb R^d (or KK), consider

R(N,ϵ,p,ν;K)=infμ^supμKsupPPp,νsupOϵNE ⁣[μ^(X1,,XN)μ22].\mathfrak R^\star(N,\epsilon,p,\nu;K) = \inf_{\hat\mu} \sup_{\mu\in K} \sup_{P\in\mathcal P_{p,\nu}} \sup_{|\mathcal O|\le \lfloor\epsilon N\rfloor} \mathbb E\!\left[\|\hat\mu(X_1,\dots,X_N)-\mu\|_2^2\right].

Unsolved Problem

Determine sharp minimax upper/lower bounds (rates, and if possible constants) for this heavy-tailed setting, including dependence on N,ϵ,p,νN,\epsilon,p,\nu and on geometry of KK (e.g., heavy-tail analogues of local complexity).

§ Discussion

Loading discussion…

§ Significance & Implications

Heavy-tailed robustness is explicitly posed as a future direction in the source paper. Clarifying minimax limits here would test how much of the star-shaped, geometry-driven theory persists beyond sub-Gaussian tails and which additional complexity terms are unavoidable.

§ Known Partial Results

  • Prasadan et al. (2025): The paper establishes minimax characterizations for several sub-Gaussian regimes (including unbounded star-shaped sets) but does not provide a full heavy-tailed minimax characterization. Based on the source framing, this heavy-tailed formulation should be treated as a proposed extension and remains open.

§ References

[1]

Information Theoretic Limits of Robust Sub-Gaussian Mean Estimation Under Star-Shaped Constraints

Akshay Prasadan, Matey Neykov (2025)

Annals of Statistics (accepted; final volume/issue/pages/DOI pending)

📍 Section 6 (Discussion and Future Work), first paragraph: "Another avenue for future research is to understand the case when the noise can be heavy tailed."

Primary source paper; Section 6 frames heavy-tailed noise as future work rather than a completed characterization.

§ Tags