Some facts about the optimality of the LSE in the Gaussian sequence model with convex constraint

This paper characterizes the necessary and sufficient conditions for the least squares estimator to be minimax optimal in a convex constrained Gaussian sequence model by linking optimality to the Lipschitz property of the local Gaussian width, while providing algorithms to compute worst-case risk and demonstrating these results across various geometric sets.

The Gist

Imagine you are trying to find the location of a hidden treasure (the true data, $\mu$) in a vast, foggy field. You have a compass that gives you a rough direction, but it's covered in static noise ($\xi$). Your goal is to guess the treasure's location as accurately as possible.

In the world of statistics, the Least Squares Estimator (LSE) is like a very intuitive, "common sense" strategy: Just walk straight toward the compass reading until you hit the edge of the allowed area.

In this paper, the authors ask a simple but profound question: "Is this 'walk straight' strategy always the best we can do, or are there situations where a smarter, more complex map would help us find the treasure faster?"

Here is a breakdown of their findings using everyday analogies.

1. The Setting: The Foggy Field and the Fence

Imagine the "allowed area" (the constraint set $K$) is a fenced-in garden.

• The Treasure ($\mu$): Somewhere inside the garden.
• The Compass ($Y$): A noisy signal that points near the treasure but might be off due to fog (noise).
• The LSE Strategy: You look at the compass, walk in that direction, and stop the moment you hit the fence. You assume the treasure is the closest point on the fence to where the compass is pointing.

This strategy is popular because it's easy to calculate and works great for simple shapes like circles or squares. But the authors wanted to know: Does it work for every shape?

2. The "Shape" Matters: The Gaussian Width

To figure out if the LSE is optimal, the authors looked at the shape of the garden. They used a concept called Gaussian Width.

Think of Gaussian Width as the "wiggle room" or the "complexity" of the garden's shape when viewed through a foggy lens.

• Simple Shapes (Optimal): If your garden is a perfect circle or a flat square, the "wiggle room" is predictable. The LSE works perfectly here. It's like walking straight to a wall; you know exactly where you'll stop.
• Complex Shapes (Suboptimal): If your garden is a weird, spiky pyramid or a twisted solid, the "wiggle room" changes drastically depending on where you are standing. In these cases, the LSE might walk you to a "dead end" on the fence, while a smarter strategy could have cut through the fog to find the treasure much faster.

3. The Golden Rule: Lipschitz Continuity

The paper's biggest discovery is a condition for when the LSE is the best possible guess. They call this the Lipschitz property.

The Analogy: Imagine the "Gaussian Width" is a terrain map showing how hard it is to find the treasure from any point.

• The LSE is Optimal if this terrain map is smooth. If you take a small step, the difficulty of finding the treasure changes only a little bit. It's like walking on a gentle hill; you can trust your intuition.
• The LSE is Suboptimal if the terrain is jagged. If a tiny step changes the difficulty from "easy" to "impossible," your simple "walk straight" strategy fails. You need a more complex algorithm to navigate the cliffs and valleys.

4. Examples: When to Trust Your Gut (and When Not To)

The authors tested their theory on various shapes to see if the LSE wins or loses.

🏆 The Winners (LSE is Optimal)

• The $\ell_1$ Ball (The Diamond): Imagine a diamond shape. The LSE works great here.
• The $\ell_2$ Ball (The Circle): A perfect circle. The LSE is perfect.
• Isotonic Regression (The Staircase): Imagine data that must always go up (like a staircase). If the total height is known, the LSE is the best guess.
• Linear Subspaces (The Flat Plane): If the treasure is guaranteed to be on a flat sheet of paper, walking straight to the paper is the best move.

🏳️ The Losers (LSE is Suboptimal)

• The Pyramid: Imagine a pyramid with a very sharp tip. The LSE might get stuck near the base, thinking the treasure is there, while a smarter estimator realizes the treasure is likely near the sharp peak. The "jaggedness" of the pyramid tricks the LSE.
• The Solid of Revolution: Think of a vase shape. If the noise is high, the LSE might project the signal onto the wide base of the vase, missing the narrow neck where the treasure actually is.
• $\ell_p$ Balls (The Squashed Sphere): For shapes between a circle and a square (where $1 < p < 2$), the LSE is actually too slow. It's like trying to navigate a city with a map that only shows straight lines, while the actual streets are diagonal.

5. The Takeaway

The paper provides a mathematical "checklist" (algorithms and formulas) to determine if your specific problem has a "smooth" shape (where the LSE is king) or a "jagged" shape (where you need a more sophisticated, computationally expensive method).

In simple terms:

• If your data constraints form a smooth, predictable shape, the simple "Least Squares" method is the best tool you have.
• If your constraints form a spiky, complex, or jagged shape, the simple method will fail to find the best answer, and you need a more advanced algorithm to avoid getting lost in the fog.

The authors didn't just say "it depends"; they gave us the tools to measure the "jaggedness" of the problem and decide exactly when to switch strategies.

Technical Summary

Here is a detailed technical summary of the paper "Some facts about the optimality of the LSE in the Gaussian sequence model with convex constraint" by Akshay Prasadan and Matey Neykov.

1. Problem Statement

The paper investigates the Gaussian sequence model under a convex constraint. The setup is as follows:

• Observation: $Y = \mu + \xi$, where $\xi \sim \mathcal{N}(0, \sigma^2 I_n)$ is Gaussian noise and $\mu$ is an unknown vector.
• Constraint: The true parameter $\mu$ lies in a known, closed, convex set $K \subset \mathbb{R}^n$.
• Estimator: The primary focus is the Least Squares Estimator (LSE), defined as the Euclidean projection of $Y$ onto $K$:
  $$\hat{\mu} = \arg\min_{\nu \in K} \|Y - \nu\|^2$$
• Goal: To characterize the worst-case risk (expected squared $\ell_2$ loss) of the LSE, denoted as $\varepsilon_{K, LS}^2 = \sup_{\mu \in K} \mathbb{E}_\mu \|\hat{\mu} - \mu\|^2$, and determine when this estimator is minimax optimal.
• Minimax Benchmark: The optimal rate is characterized by the information-theoretic lower bound $\varepsilon^*$, defined via the local metric entropy of $K$:
  $$\varepsilon^* \asymp \sup \{ \varepsilon : \varepsilon^2/\sigma^2 \leq \log M_{loc}^K(\varepsilon) \}$$
  where $M_{loc}^K(\varepsilon)$ is the local packing number.

The central question is: Under what geometric conditions on $K$ does the LSE achieve the minimax rate $\varepsilon^*$ (up to constants)?

2. Methodology

The authors employ a geometric analysis approach, moving beyond simple entropy bounds to utilize the local Gaussian width and its behavior across the set $K$.

• Local Gaussian Width: For a point $\mu \in K$ and radius $\varepsilon$, the local Gaussian width is defined as $w_{K, \mu}(\varepsilon) = \mathbb{E}[\sup_{t \in B(\mu, \varepsilon) \cap K} \langle \xi, t \rangle]$.
• Variational Characterization: Building on Chatterjee (2014), the paper utilizes the quantity $\varepsilon_{\mu, w}(\sigma) = \arg\max_{\varepsilon} [\sigma w_{K, \mu}(\varepsilon) - \varepsilon^2/2]$. The risk of the LSE at a specific $\mu$ is shown to be proportional to $\varepsilon_{\mu, w}^2$.
• Lipschitz Property of Width Mapping: A core methodological insight is analyzing the mapping $\mu \mapsto w_{K, \mu}(\varepsilon)$. The authors prove that the optimality of the LSE is intimately tied to whether this mapping is Lipschitz continuous with respect to the geometry of $K$.
• Algorithmic Search: The paper proposes theoretical algorithms (Local and Global Packing Algorithms) to compute or bound the worst-case LSE rate by searching for the "worst-case" point $\mu$ where the local Gaussian width behaves most unfavorably.

3. Key Contributions

A. Necessary and Sufficient Conditions for Optimality

The paper provides a rigorous characterization of LSE optimality:

• Sufficient Condition: The LSE is minimax optimal if the local Gaussian width mapping $\mu \mapsto w_{K, \mu}(\varepsilon)$ is Lipschitz continuous with a constant proportional to $\varepsilon/\sigma$ for all $\varepsilon$ above the minimax rate.
• Necessary Condition: Conversely, if the LSE is minimax optimal, this Lipschitz property must hold.
• Counterexamples to Folklore: The authors demonstrate that simple conditions based solely on global entropy or simple width bounds (like those in Corollary 2.6) are not necessary. They construct examples (e.g., specific hyper-rectangles) where the LSE is optimal despite failing these simpler sufficient conditions.

B. Characterization of Worst-Case Risk

The authors derive variational formulas that bound the worst-case LSE risk $\varepsilon_{K, LS}$ in terms of the supremum of the difference in local Gaussian widths between points in $K$. Specifically, they show that the risk is controlled by the maximum variation of the width function over the set.

C. Theoretical Algorithms

Two algorithms are introduced to bound the worst-case rate for bounded sets $K$:

1. Local Packing Algorithm: Uses a hierarchical tree of local packings to detect where the width function varies significantly.
2. Global Packing Algorithm: Uses global packings to search for the worst-case risk based on the variational formulas derived in Section 2.2.

4. Key Results and Examples

The paper applies these theoretical tools to a wide variety of convex sets, categorizing them into Optimal and Suboptimal cases.

Optimal Cases (LSE achieves minimax rate)

• Isotonic Regression: Both univariate (with known total variation) and multivariate isotonic regression (up to logarithmic factors).
• Subspaces (Linear Regression): The LSE is optimal for any fixed design matrix (linear regression), recovering the standard result that projection onto a subspace is optimal.
• $\ell_1$ and $\ell_2$ Balls: The LSE is optimal for both the $\ell_1$ ball (sparsity) and the $\ell_2$ ball (bounded norm).
• Hyperrectangles: Despite the complexity of the geometry, the LSE is optimal for hyperrectangles.

Suboptimal Cases (LSE fails to achieve minimax rate)

The paper identifies specific geometric structures where the LSE is strictly worse than the minimax rate:

• Pyramids: Sets formed by the convex hull of a base $K$ and a vertex $v$ far away. The LSE suffers from high bias in the direction of the vertex.
• Multivariate Isotonic Regression (High Noise): When the noise level $\sigma > 1/\sqrt{n}$, the LSE becomes suboptimal for dimensions $p > 2$, whereas block estimators can achieve the optimal rate.
• Solids of Revolution: Sets generated by rotating a concave function. The LSE fails to adapt to the "flat" regions of the solid.
• Ellipsoids: The LSE is suboptimal for certain ellipsoids, particularly when the eigenvalues decay in specific ways (e.g., Sobolev ellipsoids with smoothness parameter $\alpha < 1/2$).
• $\ell_p$ Balls for $p \in (1, 2)$: This is a significant new result. While $\ell_1$ and $\ell_2$ are optimal, the LSE is suboptimal for $\ell_p$ balls when $1 < p < 2$. The paper proves that for specific noise levels, the LSE risk is constant (order of diameter), while the minimax rate decays with$n$.

5. Significance and Impact

• Resolution of Open Questions: The paper settles the question of LSE optimality for $\ell_p$ balls with $p \in (1, 2)$, showing they are a distinct class where the LSE fails, unlike the $p=1$ and $p=2$ cases.
• Geometric Insight: It shifts the focus from purely metric entropy (counting points) to the local geometry of the Gaussian width. The Lipschitz continuity of the width mapping emerges as the fundamental geometric property governing estimator performance.
• Practical Implications: The results suggest that for certain convex constraints (like pyramids or specific ellipsoids), computationally tractable alternatives to the LSE (such as block estimators or shrinkage methods) are theoretically necessary to achieve optimal rates.
• Algorithmic Framework: The provided algorithms offer a theoretical blueprint for numerically investigating the worst-case risk of the LSE for arbitrary convex sets, bridging the gap between abstract theory and computational verification.

In summary, Prasadan and Neykov provide a comprehensive geometric theory explaining when and why the intuitive Least Squares Estimator succeeds or fails in high-dimensional convex constrained problems, moving beyond simple entropy bounds to a nuanced analysis of local Gaussian width variations.