Information theoretic limits of robust sub-Gaussian mean estimation under star-shaped constraints

This paper establishes the minimax rates for robust mean estimation under star-shaped constraints in the presence of adversarial corruption and Gaussian or sub-Gaussian noise, characterizing the optimal error bounds in terms of the local entropy of the constraint set, the noise variance, and the corruption fraction.

The Gist

Here is an explanation of the paper "Information theoretic limits of robust sub-Gaussian mean estimation under star-shaped constraints," translated into everyday language with creative analogies.

The Big Picture: Finding the Center of a Storm

Imagine you are trying to find the exact center of a city (the mean) based on reports from 1,000 weather stations scattered around it.

In a perfect world, every station reports the temperature accurately, and you just take the average. But in the real world, things are messy:

1. Noise: Even good stations have slight errors (like a thermometer being off by a degree).
2. Sabotage: A mischievous hacker (the adversary) has hacked some of the stations. They are sending fake, wild reports (e.g., "It's 500 degrees!") to confuse you.
3. The Shape: You don't know the city is a perfect circle. Maybe it's a star-shaped district, or a long, thin strip. You know the center must be somewhere inside this specific shape (star-shaped constraint).

The goal of this paper is to answer: How accurately can you find the true center, given that some data is noisy, some is sabotaged, and the city has a weird shape?

---

Key Concepts Explained

1. The "Star-Shaped" City

Usually, statisticians assume the city is a perfect circle (convex). But real-world constraints are often weirder.

• The Analogy: Imagine a star-shaped park. If you stand at the center of the star, you can draw a straight line to any point in the park without leaving the grass. However, if you stand at the tip of one of the star's points, a straight line to another tip might cut through the lake (outside the park).
• Why it matters: The authors prove that even if the "allowed area" for the center is a weird, non-convex star shape, you can still find the center almost as well as if it were a perfect circle. They generalized a math trick that usually only works for circles to work for these weird stars.

2. The Saboteur (Adversarial Corruption)

The hacker isn't just making random mistakes; they are smart. They know your algorithm and will try to trick it specifically.

• The Analogy: Imagine a game of "Hot and Cold." The hacker knows you are looking for the treasure. If you ask, "Is it north?" they might lie and say "Yes," even if it's south, just to lead you in circles.
• The Result: The paper calculates the Minimax Rate. Think of this as the "worst-case score." It tells you the best possible accuracy you can guarantee, even if the hacker is playing perfectly against you.

3. The "Smooth" vs. "Rough" Noise

The paper looks at two types of background noise:

• Gaussian (The Bell Curve): This is "nice" noise. Most errors are small, and huge errors are extremely rare. It's like a gentle breeze.
• Sub-Gaussian (The Unknown Wind): This is "rougher" noise. It behaves like a bell curve mostly, but we aren't 100% sure of the rules. It could be slightly windier or gustier.
• The Discovery: The authors found a surprising difference. If you know exactly how the wind blows (the distribution), you can find the center faster. If you only know it's "windy" but don't know the specific pattern, your accuracy drops slightly. It's the difference between having a weather forecast vs. just guessing "it might rain."

4. The Algorithm: The "Tournament" Tree

How do you actually find the center without getting tricked?

• The Old Way: Just take the average. (Fails immediately if the hacker sends 500-degree reports).
• The New Way (The Paper's Method):
  1. Build a Tree: Imagine a giant family tree where every branch represents a possible location for the center. The tree gets finer and finer, zooming in on the city.
  2. The Tournament: Instead of averaging, the algorithm pits two locations against each other. It asks: "Which location is closer to more than half of the data points?"
  3. The Pruning: If a branch of the tree is clearly wrong (too far from the majority), it gets cut off.
  4. The Winner: The algorithm keeps playing this "tournament" until it zooms in on the true center.

The Catch: This method is mathematically perfect (it achieves the theoretical limit), but it is computationally expensive. It's like using a supercomputer to solve a puzzle that a human could solve with a pencil. The authors admit their algorithm is too slow for real-time use, but it sets the "gold standard" for what is theoretically possible.

The Main Takeaways

1. Shape Doesn't Matter (Much): Whether the city is a circle, a star, or a weird blob, as long as it has that "star property" (you can draw lines from a center point to anywhere), the math works the same way.
2. Knowledge is Power: If you know the exact nature of the noise (the wind), you can estimate the center faster. If you are flying blind about the noise, you have to settle for being slightly less accurate.
3. The "Star" Limit: The paper provides a precise formula for the error. It says your error will be the larger of two things:
   • How much the "star shape" makes it hard to distinguish points (Local Entropy).
   • How many hackers are in the crowd (Corruption Rate).
4. Sparse Examples: They tested this on "Sparse Mean Estimation" (finding a center where most coordinates are zero). This is like finding a needle in a haystack where the haystack is huge, but the needle is very thin. Their method works perfectly here too.

In a Nutshell

This paper is a theoretical blueprint. It doesn't give you a fast app you can download today. Instead, it tells us the absolute limit of human knowledge for this problem.

It says: "No matter how smart your algorithm is, you cannot beat this level of accuracy if the data is this corrupted and the shape is this weird. But, if you use this specific (slow) method, you can hit that limit."

It's like a physicist calculating the maximum speed of a car on a specific track. They might not build the car, but they prove that nothing can go faster than 200 mph, and they show you the theoretical design that would get you there.

Technical Summary

Here is a detailed technical summary of the paper "Information theoretic limits of robust sub-Gaussian mean estimation under star-shaped constraints" by Akshay Prasadan and Matey Neykov.

1. Problem Formulation

The paper addresses the fundamental statistical problem of robust mean estimation in high dimensions under adversarial corruption and geometric constraints.

• Model: The authors consider a corrupted Gaussian (or sub-Gaussian) location model. We observe $N$ data points $X_1, \dots, X_N \in \mathbb{R}^n$.
  • Ideally, $\tilde{X}_i = \mu + \xi_i$, where $\xi_i$ are i.i.d. sub-Gaussian noise vectors with parameter $\sigma$.
  • An adversary corrupts a fraction $\epsilon \leq 1/2 - \kappa$ of the observations arbitrarily. The corruption scheme $C$ can depend on the true mean $\mu$, the noise, and the constraint set.
• Constraint: The true mean $\mu$ is known to lie within a star-shaped set $K \subseteq \mathbb{R}^n$.
  • A set $K$ is star-shaped with center $k^*$ if for any $k \in K$ and $\alpha \in [0, 1]$, the point $\alpha k + (1-\alpha)k^* \in K$.
  • This generalizes convex constraints (where the center can be any point in the set) and includes non-convex sets like sparse vectors (unbounded) or bounded non-convex shapes.
• Goal: Construct an estimator $\hat{\mu}$ that minimizes the minimax risk under squared $\ell_2$ loss:
  $$\inf_{\hat{\mu}} \sup_{\mu \in K} \sup_{C} \mathbb{E} \| \hat{\mu}(C(\tilde{X})) - \mu \|^2$$
  The authors focus on statistical optimality (minimax rates) rather than computational efficiency, acknowledging that their proposed algorithms are computationally intractable but serve as information-theoretic benchmarks.

2. Methodology

The authors develop a novel framework combining local metric entropy, tournament-style selection, and iterative tree construction to derive tight upper and lower bounds.

A. Lower Bounds

The paper establishes minimax lower bounds for three distinct noise settings:

1. Gaussian Noise: Uses Fano's inequality and properties of local metric entropy to bound the difficulty of distinguishing between points in $K$.
2. Known/Symmetric Sub-Gaussian Noise: Adapts the Gaussian proof but accounts for the specific tail behavior of sub-Gaussian distributions.
3. Unknown Sub-Gaussian Noise: This is the most challenging case. The authors construct a mixture distribution (Gaussian + point mass) to show that without knowledge of the noise distribution, the adversary can force a slower convergence rate. They utilize a specific construction involving the trimmed mean estimator (from Lugosi and Mendelson, 2021) to handle the lack of symmetry.

B. Upper Bounds (The Algorithm)

The core of the upper bound proof relies on a data-independent directed tree construction and a tournament selection process:

1. Tree Construction (Algorithm 1):
   • The authors construct an infinite directed tree where nodes represent points in $K$.
   • Levels of the tree correspond to progressively finer local packing sets of $K$.
   • Pruning: A crucial innovation is a "pruning" step. When constructing level $k$, if a new node is too close to an existing node in the same level, edges are redirected to ensure the tree remains a valid packing while maintaining coverage properties. This resolves technical issues found in prior work (Neykov, 2022) regarding non-convex sets.
2. Tournament Selection (Algorithm 2):
   • Instead of simply minimizing distance (which fails under adversarial corruption), the algorithm traverses the tree using a tournament test.
   • Given two candidate points $\nu_1, \nu_2$, the test checks if more than half of the data points are closer to $\nu_2$ than $\nu_1$.
   • Adaptation for Unknown Noise: In the unknown sub-Gaussian case, the standard median-based test is insufficient. The authors switch to a trimmed mean estimator on the projected distances when the scale $\delta$ is small, leveraging the robustness of the trimmed mean to outliers.
3. Convergence: The algorithm iteratively selects the "winner" of the tournament among offspring nodes. The sequence of selected points forms a Cauchy sequence converging to the true mean.

3. Key Contributions

1. Generalization to Star-Shaped Sets:

   • This is the first work to establish minimax rates for robust mean estimation under star-shaped constraints (which include non-convex sets).
   • They prove that the non-increasing property of local metric entropy, previously known for convex sets, also holds for star-shaped sets (Lemma 1.4).

2. Information-Theoretic Limits for Sub-Gaussian Noise:

   • Known/Symmetric Noise: The minimax rate is $\max(\eta^{*2}, \sigma^2 \epsilon^2) \wedge d^2$.
   • Unknown Noise: The authors uncover a phenomenon where unknown noise distribution leads to a strictly slower rate: $\max(\eta^{*2}, \sigma^2 \epsilon^2 \log(1/\epsilon)) \wedge d^2$. The $\log(1/\epsilon)$ factor is unavoidable when the noise distribution is unknown, even if it is sub-Gaussian.
   • They provide the first definitive minimax rates for sub-Gaussian noise under constraints, covering both bounded and unbounded cases.

3. Unbounded Sets:

   • The results are extended to unbounded star-shaped sets (e.g., sparse vectors).
   • For unbounded sets, the diameter $d$ is removed from the rate (as it is infinite), and the requirement for knowing the corruption fraction $\epsilon$ becomes necessary even for Gaussian noise.

4. Expected Risk Bounds:

   • Unlike many recent works in robust statistics that provide high-probability bounds, this paper derives bounds on the expected error ($\mathbb{E}\|\hat{\mu} - \mu\|^2$), which is a stronger and more standard measure of statistical optimality.

4. Key Results

The minimax rate is characterized by two competing terms:

1. Statistical Complexity Term ($\eta^{*2}$): Determined by the local metric entropy of the set $K$.
   $$\eta^* = \sup \left\{ \eta \geq 0 : \frac{N\eta^2}{\sigma^2} \leq \log M_K^{\text{loc}}(\eta, c) \right\}$$
   This term captures the difficulty of estimation in the absence of corruption.
2. Robustness Term:
   • Gaussian / Known Symmetric Sub-Gaussian: $\sigma^2 \epsilon^2$.
   • Unknown Sub-Gaussian: $\sigma^2 \epsilon^2 \log(1/\epsilon)$.

Summary Table of Rates (Bounded Case):

Noise Model	Corruption Rate Assumption	Minimax Rate
Gaussian	$\epsilon$ unknown	$\max(\eta^{*2}, \sigma^2 \epsilon^2) \wedge d^2$
Known/Symmetric Sub-Gaussian	$\epsilon$ unknown	$\max(\eta^{*2}, \sigma^2 \epsilon^2) \wedge d^2$
Unknown Sub-Gaussian	$\epsilon$ known	$\max(\eta^{*2}, \sigma^2 \epsilon^2 \log(1/\epsilon)) \wedge d^2$

Example Application: Sparse Mean Estimation
For the set of $s$-sparse vectors (unbounded), $\log M_K^{\text{loc}} \asymp s \log(n/s)$.

• Gaussian/Known Noise Rate: $\max\left( \frac{\sigma^2 s \log(n/s)}{N}, \sigma^2 \epsilon^2 \right)$.
• Unknown Noise Rate: $\max\left( \frac{\sigma^2 s \log(n/s)}{N}, \sigma^2 \epsilon^2 \log(1/\epsilon) \right)$.

5. Significance and Future Work

• Theoretical Benchmark: The paper provides the "gold standard" for what is statistically possible in robust estimation with constraints. It clarifies that computational tractability often comes at the cost of statistical optimality (e.g., polynomial-time algorithms often achieve suboptimal rates like $\epsilon$ instead of $\epsilon^2$).
• Role of Symmetry: The work highlights a critical distinction: if the noise distribution is known (or symmetric), one can achieve the optimal $\epsilon^2$ rate. If the distribution is unknown, the $\log(1/\epsilon)$ penalty is unavoidable.
• Star-Shaped Geometry: By moving beyond convexity, the authors open the door to analyzing more complex, realistic constraints (like unions of subspaces or non-convex manifolds) in robust statistics.
• Future Directions: The authors suggest exploring computationally efficient algorithms that match these rates, extending results to heavy-tailed noise (where tail bounds are weaker), and investigating the behavior as $\epsilon \to 1/2$.

In conclusion, this paper resolves the information-theoretic limits of robust mean estimation under a broad class of geometric constraints, revealing the precise cost of unknown noise distributions and providing a rigorous framework for future algorithmic developments.