The question does not quite accurately represent the definition given in the paper:
Interpolation versus “overfitting”. In this paper we will refer to
classifiers as interpolated if their square loss on the training error
is zero or close to zero. We will call classifiers overfitted if the
same holds for classification loss (for the theoretical bounds we will
additionally require a small fixed margin on the training data).
Notice that while interpolation implies overfitting, the converse does
not hold.
From the question:
"if interpolated classifier as an algo that has zero or close to zero training error and overfitted as an algo "if the same holds for classification loss"."
Note that the paper says "squared loss" rather than "training error", so it is regarding interpolation as if the model is a regression model, predicting the numeric value of the target. However the paper is really about classification, so it is re-using the term "overfitting" to make a distinction between treating the output as a regression (square loss) and a classification (classification loss/error rate).
Question 1: what is the mathematical definition of these two types of
classifiers?
There isn't two types of classifier, I think it is just two different interpretations of the output.
If an interpolated classifier only depends on the training data, then
an overfitted algo in this context could mean an algo that has zero or
near zero test error (i.e. generalization error)...which seems
different than more traditional definitions of "overfit".
No, they are both talking about the error on the training set. If the model interpolates, then it's output is numerically close to the the target value. However, you don't need to be very close to the target value to get the classification right as the "score" is thresholded to make the classification.
Question 2. The authors then go on to state that in their definitions
an interpolated classifier is necessarily an overfit classifier --
why?
If a model interpolates, then the numeric difference between the prediction and target will be much smaller than the difference between the target and the classification threshold, so any interpolated point will be correctly classified. If the model correctly classifies all patterns in the training set then it is defined as being "overfitted". This doesn't apply the other way round, the model predictions can be just the right side of the threshold for all training patterns, in which case it is overfitted (by their definition) but it doesn't interpolate (as there is a substantial error on the prediction of the label when viewed as a regression).
I would define overfitting as meaning reducing the training loss (which measures the "fit" of the model to the data) so much that generalisation performance (e.g. test/validation set) becomes worse. Arguably while the generalisation performance is improving you haven't fitted the model too closely as fitting it closer still improves generalisation performance.
However, I can see the logic in their usage. If you had a perfect Bayes optimal classifier, it would give a non-zero classification error on the training sample as well, so you could argue that the model is overfit because there exists a better model with better generalisation performance but worse training set performance. However, however, it is not necessarily the case that the Bayes optimal classifier is realisable by the current model architecture or can actually be found by the training algorithm, so in practice the best model may be achievable with zero training set error and we have benign "overfitting".
It is best not to get too focussed on terminology - sometimes a sub-field will be using their own definitions/meanings of terms and we just have to learn their jargon.
Question 3. In section 4, does the t-overfits the data definition
depend on a fixed training set? I.e. do they mean t-overfit a fixed
but arbitrary training dataset?
Yes, I think that is correct - that is fairly standard for analysis of generalisation bounds.
