Just what the title says. In every model we try to approximate a function
$$Y = f(X) + \epsilon$$
Assume we that $Var(\epsilon)=0 \forall X$. However, the train/test set correspond to different sets of $(X, Y)$ pairs. In that scenario, is overfitting possible?
Imagine that your data is two dimensional, where you predict $Y=f(X)$, where $f$ is unknown, high-degree polynomial function. Say that you take every second datapoint as your training set, and the rest as test set. Your task in here would be simply to connect the dots using polynomial function. This seems simple, but you can easily choose wrong polynomial function that connects all the training samples, but misses the test ones. Since we've all seen hundreds of pictures of overfitting polynomials, I'm omitting the plot.
Yes, it is possible. Without noise, your $X,Y$ pairs should completely satisfy $f(X)=Y$. From your $N$ training points, you can find $N+1,N+2,...$ degree polynomials to fit in perfectly. And, since you don't know the truth of it, a wrong choice of polynomial degree will result in overfitting.
