Least Squares Theory Review

Error Bounds for Least Squares

Step 1. Framing the question

Without misspecification

With misspecification

Figure 1

Step 2. Abstracting away some of the details

Abstractly

In the Bounded Variation Model.

Figure 2

Step 3. Simplifying the problem

Implications of Convexity

Reduction to the sphere

Ignorability of misspecification

Figure 3

The Maximal Inner Product and ‘Crossing Picture’

Step 4. Thinking about what’s typical

Step 5. Thinking about how typical it is

The Good Version

An error bound based on the Borell-TIS inequality.

Figure 4: \[ \textcolor{blue}{\frac{s^2}{2\sigma}} \quad \text{ vs. } \quad \textcolor{red}{\operatorname{w}(\mathcal{M}_s) + \sqrt{\frac{2\log(1/\delta)}{n}}} \]

The Easy Version

An error bound based on the Efron-Stein inequality.

Figure 5: \[ \textcolor{blue}{\frac{s^2}{2\sigma}} \quad \text{ vs. } \quad \textcolor{red}{\operatorname{w}(\mathcal{M}_s) + \sqrt{\frac{1+2\log(2n)}{\delta n}}} \]

Rates of Convergence: The Bounds we get Varying \(n\)

The Good Version

Error bounds based on the Borell-TIS inequality.

\[ \text{The smallest $s$ satisfying} \quad \textcolor{blue}{\frac{s^2}{2\sigma}} \ge \textcolor{red}{\operatorname{w}(\mathcal{M}_s) + \sqrt{\frac{2\log(1/\delta)}{n}}} \]

The Easy Version

Error bounds based on the Efron-Stein inequality.

\[ \text{The smallest $s$ satisfying} \quad \textcolor{blue}{\frac{s^2}{2\sigma}} \ge \textcolor{red}{\operatorname{w}(\mathcal{M}_s) + \sqrt{\frac{1+2\log(2n)}{\delta n}}} \]