Unsolved

Sharp minimax behavior as contamination approaches the breakdown boundary $\epsilon\uparrow 1/2$

Sourced from the work of Akshay Prasadan, Matey Neykov

§ Problem Statement

Setup

Let d,NNd,N\in\mathbb N, let KRdK\subseteq\mathbb R^d be a nonempty star-shaped set with respect to some center cKc\in K (that is, for every xKx\in K and t[0,1]t\in[0,1], c+t(xc)Kc+t(x-c)\in K; the origin-centered condition is the special case c=0c=0 used in the cited paper), and let $\epsilon\inPrasadan & Neykov (2024).

The clean sample is Y1,,YNY_1,\dots,Y_N with Yii.i.d.N(μ,Id)Y_i\overset{i.i.d.}{\sim}\mathcal N(\mu,I_d), where IdI_d is the d×dd\times d identity matrix. An adversary is allowed to choose a (possibly data-dependent and randomized) index set O{1,,N}\mathcal O\subseteq\{1,\dots,N\} with OϵN|\mathcal O|\le \epsilon N and replace {Yi:iO}\{Y_i:i\in\mathcal O\} by arbitrary vectors in Rd\mathbb R^d, producing observed data X1,,XNX_1,\dots,X_N. An estimator is any measurable map μ^:(Rd)NRd\hat\mu:(\mathbb R^d)^N\to\mathbb R^d. The squared-error minimax risk is

RN(ϵ,K):=infμ^supμKsupadversaries A:OAϵNEμ,A ⁣[μ^(X1,,XN)μ22].\mathcal R_N(\epsilon,K) := \inf_{\hat\mu} \sup_{\mu\in K} \sup_{\text{adversaries }A:\,|\mathcal O_A|\le \epsilon N} \mathbb E_{\mu,A}\!\left[\|\hat\mu(X_1,\dots,X_N)-\mu\|_2^2\right].

Unsolved Problem

For multivariate constrained classes KK, determine the sharp asymptotic behavior of RN(ϵ,K)\mathcal R_N(\epsilon,K) as ϵ1/2\epsilon\uparrow 1/2. In particular, obtain matching (up to universal constants, and ideally exact) upper and lower bounds that identify the correct dependence on the boundary parameter 12ϵ1-2\epsilon, and characterize how this boundary dependence interacts with local metric-entropy geometry of KK (for example through covering numbers of localized sets KB2(μ,r)K\cap B_2(\mu,r)).

See Prasadan & Neykov (2024), discussion around the boundary-contamination regime, for context.

§ Discussion

Loading discussion…

§ Significance & Implications

Open as of June 12, 2025: the cited work proves sharp rates under separation from the boundary (ϵ1/2κ\epsilon\le 1/2-\kappa for fixed κ>0\kappa>0), but does not establish the sharp multivariate constrained behavior as ϵ1/2\epsilon\uparrow 1/2. Resolving this would pin down robustness limits near maximal contamination and clarify constrained-geometry effects in the hardest regime.

§ Known Partial Results

  • Prasadan et al. (2025): The paper gives sharp rates for fixed separation from 1/21/2 (i.e., ϵ1/2κ\epsilon\le 1/2-\kappa). In discussion, the authors reference prior one-dimensional boundary-regime results and indicate possible extensions to multivariate constrained settings, but do not establish the sharp 12ϵ1-2\epsilon boundary behavior for those classes.

§ References

[1]

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

Akshay Prasadan, Matey Neykov (2025)

Annals of Statistics (to appear; as listed in arXiv v2 metadata)

📍 Problem context: Section 6 (Discussion and Future Work), paragraph beginning “We now comment on the i.i.d. Gaussian case…”, p. 27. Publication-status metadata (“Annals of Statistics, to appear”) is taken from the arXiv v2 abstract/metadata page.

Primary source where this open problem is discussed. Year convention: 2025 corresponds to the cited arXiv version (v2); initial posting was in 2024 (identifier 2412).

§ Tags