SECTION 01Introduction to Non-Asymptotic Theory
Non-asymptotic theory studies estimation error at finite sample sizes.
Asymptotic vs. Non-Asymptotic Analysis
- Asymptotic: Let the sample size n tend to infinity and study the estimation error in the limit. For example, the central limit theorem describes convergence of the distribution of a properly standardized sample mean to a normal distribution.[1]
- Non-asymptotic: Fix the sample size n at a finite value and study the estimation error at that value. Specifically, (1) how large is the error? (2) With what probability does the error guarantee hold?[2]
Why It Matters
- It is particularly useful in high-dimensional statistics, where we care about both the sample size n and the dimension d.
- Non-asymptotic does not mean small-sample: the bounds apply to finite n and can also be used to study behavior as n → ∞.
SECTION 02Why Study Non-Asymptotic Theory in High-Dimensional Statistics?
We study (1) non-asymptotic theory in (2) high-dimensional statistics.
- In modern science & engineering, datasets are extremely large, often with the dimension of the same order or possibly even larger than the sample size.
- Classical asymptotic theory often fails to provide useful predictions, and standard methods may break down in dramatic ways.
SECTION 03How to Study
I assume readers come from an engineering background and have some basic mathematical knowledge, but not a comprehensive grounding in mathematics. We can therefore approach mathematics in a familiar way, much as we read a research paper. In the notes that follow, I will try to explain the material from the four perspectives below to make it easier to understand:
1. Setting: What Problem Are We Studying?
Clarify (1) the problem we study, (2) what we aim to achieve, and (3) why studying it matters in practice.
2. Definition / Formulation: How Is It Expressed?
Understand (1) the precise mathematical form, (2) its physical meaning, and (3) its intuitive interpretation.
3. Theorem / Claim: What Does It Tell Us?
Understand (1) the main insight, (2) its physical meaning, and (3) the explanation or proof, especially the key steps.
4. Example: How Is It Useful in Practice?
Use examples to deepen our understanding of (1) the definitions and (2) the theorems, especially how they apply to real-world problems.
When a formula looks complicated or a definition seems strange, remember that there is a clear logic behind it. Its form comes from a motivation and the tradeoffs made along the way. Understanding that logic often reveals a simple, elegant idea. Remembering the idea is usually more useful than memorizing the formula. This is quite like how we read a research paper: we follow the logic behind its results.
Also, we do not need to understand every detail. Some formulas and theorems can be used as black boxes: it is enough to know their meaning and when they apply. In other cases, we need to understand their derivations deeply because the derivation method itself is a general tool. We may encounter it in many other settings or use it to develop our own theory. We can view formulas, theorems, and derivations as tools and choose how deeply to understand each one based on what we can learn from it.
For those of us with an engineering background, learning mathematics means learning to make these choices. First build a clear framework and understand how the ideas connect. Then study the details that matter. A few days spent building this overall understanding can be far more valuable than a long detour through a complicated derivation we may never use. The aim of this post is to offer a self-contained learning path for readers with an engineering background and an average level of mathematical knowledge. I hope you can follow these ideas easily without having to look anything up elsewhere.