How many sample points do we need for least squares?

Event Start
Event End


The goal of the least squares method is to find the best linear combination of certain given functions to fit given data. A typical example is the following: given pairs $(x_i, y_i)$, find the coefficients, $a$ and $b$ that minimize the error $\sum_i (y_i-a -b x_i)^2$. In this case, if at least two of the coordinates $x_i$ are distinct, we can always find coefficients $a$ and $b$. However, if the $x_i$ are randomly sampled, these coordinates may be extremely close, creating large errors in the estimated values of $a$ and $b$. In this talk, we investigate lower bounds on the minimum number of points needed to obtain quantitative bounds for the coefficients $a$ and $b$.

Brief Biography

Diogo Gomes is a Professor and Program Chair of Applied Mathematics and Computational Sciences and Engineering Program at KAUST. He is known for his work on mean-field games and Hamilton--Jacobi equations. He has integrated mean-field game theory with price models, emphasizing both theoretical and numerical applications, especially using Machine Learning. He is a principal investigator for the ``Escapismo" project, which seeks to understanding the human behavior during escape scenarios. With over 100 publications in prestigious journals, he also serves as an associate editor for journals like the SIAM J. of Mathematical Analysis, J. Dynamic Games and Applications, J. of Dynamics and Games, among others.