Day 1 - Introduction
Canada/USA Mathcamp 2026
The Estimation Problem
Formally we start with the so called estimation problem. We are given a set of data points: (x_i, y_i) \text{ for } i = 1, 2, \ldots, n. Think of x_i as inputs and y_i as the corresponding outputs.
In general, we can have multiple inputs and outputs i.e. x_i and y_i can be vectors. In the Ceres example, there is one input - the time of observation - and two outputs - the right ascension and declination of the asteroid (coordinates describing its position in the sky). For this class, for simplicity, we will assume that both x_i and y_i are real numbers.
Our goal is to estimate the output y for a new input x. In the Ceres example, we want to estimate the position of the asteroid at a future time.
Regression
One method to solve the estimation problem is using regression. In regression analysis, we assume that there is some function f such that
y_i = f(x_i)
Notice that there is no restriction on what f can be. Data scientists have to make a choice of what f should be based on their expertise and the data they have. Probability theoreticians and statisticians have developed a number of methods to make this choice in a principled way. In this class, we will learn about one such method - the method of least squares.
A Motivating Example
Consider the following simple example. Suppose we have the following set of points
(-1, 0), (0, 1), (1, 2), (2, 3)
Our goal is to estimate the value of y at x = 3. In this case there is a simple natural choice - we can fit the line y = x + 1 to the data points and use it to estimate the value of y at x = 3. This gives us an estimate of y = 4.
But now suppose the last data point was actually (2, 3.5) instead of (2, 3). The linear model y = x + 1 is no longer a perfect fit for the data. What should we do?
One option is to fit a cubic polynomial that passes through all four points exactly. The figure below shows both the original line (which no longer fits) and the cubic polynomial fit. The cubic gives us an estimate of y = 6 for x = 3.
Notice something troubling: a small change in one data point (from 3 to 3.5) caused a large change in our prediction (from 4 to 6). This is a hint that exact polynomial fits might not be the best approach. We’ll see that simpler models tend to be less sensitive to small changes in the data, which makes them more robust when our measurements contain errors.
Exact Polynomial Fits
Let’s analyze the sensitivity problem more carefully. Given n data points, we can always find a polynomial of degree n-1 that passes through all of them exactly.
Sensitivity Analysis
NoteExercises: Cubic Polynomial Fit
The following exercises analyze the sensitivity of cubic polynomial fits.
Exercise 1: Find the cubic polynomial p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 fitting the data (-1, 0), (0, 1), (1, 2), (2, z). That is, find the coefficients a_0, a_1, a_2, a_3 (in terms of z) such that p(-1) = 0, p(0) = 1, p(1) = 2, and p(2) = z.
Exercise 2: Compute p(3) (in terms of z).
Exercise 3: Compute \dfrac{dp(3)}{dz}. Call this \kappa_{2 \to 3} (kappa).
The constant \kappa_{2 \to 3} represents the sensitivity of the estimate at x=3 to the value of the data point at x=2. One can similarly calculate the sensitivity \kappa_{x_i \to 3} for each data point. These constants tell us how much the estimate at x=3 will change if we change the value of one of the data points.
In practice, our data is often noisy and we do not know the true values. Any error in the data points will be amplified by the sensitivity constants. The larger the sensitivity, the more our estimate is affected by errors in the data. On the other hand, too small a sensitivity means that our estimate might neglect important information. So we want to find a model that balances these two competing goals.
Lagrange Interpolation
We can extend the above analysis to polynomial fits of any degree. Consider data points (i, y_i) for i = 1, 2, \dots, n, and suppose our goal is to estimate y at x = n+1.
We can fit a degree n-1 polynomial, i.e., find coefficients a_0, a_1, \dots, a_{n-1} such that
y_i = a_0 + a_1 \cdot i + a_2 \cdot i^2 + \dots + a_{n-1} \cdot i^{n-1}
for all i = 1, 2, \dots, n. We call a_i the parameters of our model. We will sometimes denote the estimates by \widehat{a}_i to emphasize that they are computed from data.
The cleanest way to construct this polynomial is through Lagrange interpolation.
NoteExercises: Lagrange Interpolation
Exercise 4: Suppose you fit a degree n-1 polynomial to the data points (1, y_1), (2, y_2), \dots, (n, y_n). Call this polynomial p(x).
Imagine slightly tweaking the value of y_1 (the first data point) versus slightly tweaking y_n (the last data point). Which tweak do you think would affect the estimate p(n+1) more?
Now consider the two extreme sensitivities \kappa_{1 \to {n+1}} = \dfrac{\partial p(n+1)}{\partial y_1} and \kappa_{n \to {n+1}} = \dfrac{\partial p(n+1)}{\partial y_n}. Based on your intuition, which one do you think is larger?
Exercise 5: Let j be an integer between 1 and n. Find the degree n-1 polynomial p_j(x) satisfying
p_j(i) = \begin{cases} 1 & \text{if } i = j, \\ 0 & \text{if } i \neq j. \end{cases}
Such a polynomial is called a Lagrange basis polynomial. (Hint: What are the roots of p_j(x)?)
The plots below show the four Lagrange basis polynomials for n = 4. Each polynomial equals 1 at exactly one node (green) and 0 at the others (red).
Exercise 6: Use the Lagrange basis polynomials to find the degree n-1 polynomial p(x) satisfying
p(i) = y_i, \text{ for } i = 1, 2, \dots, n.
Exercise 7: Now calculate the two extreme sensitivities \kappa_{1 \to {n+1}} = \dfrac{\partial p(n+1)}{\partial y_1} and \kappa_{n \to {n+1}} = \dfrac{\partial p(n+1)}{\partial y_n}. Does your answer match your intuition from Exercise 4?
Overfitting
You should find that the sensitivity of the estimate at x = n+1 to nearby data points increases with n. This means that as we increase the degree of the polynomial, our estimate becomes more sensitive to errors in the data.
In fact, our example is especially nice since the input coordinates are evenly spaced. In general, the sensitivity can be much worse when coordinates are uneven or when the target is far from the data. This is called Runge’s phenomenon.
The fact that sensitivity increases with model complexity is an example of a general phenomenon called overfitting. Overfitting occurs when we fit a model that is too complex for the data—such a model captures noise rather than signal and will not generalize well to new inputs.
Approximate Fits
This brings us to approximate fits. Instead of requiring the polynomial to pass through all data points exactly, we can find a polynomial that is “close” to the data in some sense. There are many ways to define “closeness.”
The figure below shows three approaches to fitting the perturbed data (-1, 0), (0, 1), (1, 2), (2, 3.5):
Cubic polynomial (green): Passes through all four points exactly, gives estimate f(3) = 6.
Quadratic polynomial (orange): Uses only the three closest points (0,1), (1,2), (2,3.5), gives estimate f(3) = 5.5.
Linear least squares (purple): Finds the “best” line through all four points (we’ll define “best” precisely later), gives estimate f(3) = 4.5.
The table below summarizes how sensitive each estimate is to changes in the last data point (comparing to when the last point was (2,3) and the estimate was f(3)=4):
| Model | Estimate at x=3 | Exact fit? | Sensitivity \frac{\Delta f(3)}{\Delta y_4} |
|---|---|---|---|
| Cubic | 6.0 | Yes | \frac{6-4}{0.5} = 4 |
| Quadratic | 5.5 | No | \frac{5.5-4}{0.5} = 3 |
| Linear | 4.5 | No | \frac{4.5-4}{0.5} = 1 |
As expected, simpler models have lower sensitivity. But how do we find the “best” line through points that aren’t collinear? This requires a precise definition of “best,” which is where probability theory enters the picture.
Looking Ahead
There is no unique solution to the estimation problem—your estimate depends on the model you choose. In this class, we will focus on linear models and learn how to choose among them using probability theory and statistics.
In the next lecture, we will introduce the method of maximum likelihood estimation, which gives a principled way to define “best fit.” We’ll see that under natural assumptions about measurement errors, maximum likelihood leads to the method of least squares—the same method Gauss used to find Ceres.
Additional Exercises
NoteOptional Exercises: Connections to Linear Algebra
These exercises connect polynomial interpolation to linear algebra concepts.
Exercise 8: Reinterpret Exercises 5 and 6 in terms of linear algebra. What vector space are we working in? What linear algebraic concepts do the Lagrange polynomials correspond to? What are you doing in Exercise 6 in terms of linear algebra?
Exercise 9: Suppose you fit a degree n-1 polynomial to the data points (1, y_1), (2, y_2), \dots, (n, y_n). Write down the system of linear equations for the coefficients. The matrix of this system is called a Vandermonde matrix.
Exercise 10: (Challenge) Find the coefficients of the Lagrange basis polynomials in terms of the inverse of the Vandermonde matrix. Compare this to your solution of Exercise 5. Use this to find a formula for the inverse of a Vandermonde matrix. (Hint: What are the columns of the inverse matrix?)