Overfitting and divergence between types of scoring metrics

Question

Since I have started tinkering with ML, I have been hearing about the dangers of overfitting, and I definitely understand the concern. I also understand that according to many, diagnosing overfitting is an art, not a science.

However, assume that it is a science, and that we have a formal definition of overfitting, such as the one offered in one of the courses I took on ML:

w1 is an overfit model iff there is a w2 such that:

(a) training error(w1) < training error(w2),

(b) test error(w1) > test error(w2)

Here is the code and output (Traning set: 900 samples from 2015-2016; Test set: 227 samples from 2017). :

SCORING3 = accuracy_score
SCORING = roc_auc_score
model_num = 0
for Cs in [10.0, 1.0]:
    model_num += 1
    log_l1_model = LogisticRegression(penalty='l1',tol=0.001, C= Cs,\
                                      fit_intercept=False, intercept_scaling=1,\
                                      class_weight=None, solver='liblinear', n_jobs = -1)

    log_l1_model.fit(Train_X, Train_y)

    y_hat_train = log_l1_model.predict(Train_X)
    y_hat = log_l1_model.predict(Test_X)

    print "model w"+str(model_num), "training ROC_AUC_score :", SCORING(Train_y, y_hat_train)
    print "model w"+str(model_num),"test ROC_AUC_score :",  SCORING(Test_y, y_hat), '\n'

    print "model w"+str(model_num),"training ACCURACY_score :", SCORING3(Train_y, y_hat_train)
    print "model w"+str(model_num),"test ACCURACY_score :",  SCORING3(Test_y, y_hat)
    print '***************************************************' 

model w1 training ROC_AUC_score : 0.556576576577
model w1 test ROC_AUC_score : 0.57170846395 

model w1 training ACCURACY_score : 0.841573033708
model w1 test ACCURACY_score : 0.70625
***************************************************
model w2 training ROC_AUC_score : 0.519954954955
model w2 test ROC_AUC_score : 0.5 

model w2 training ACCURACY_score : 0.833707865169
model w2 test ACCURACY_score : 0.725
***************************************************

Given the evidence of this two-model run, and the "formal" definition above, w1 is overfit relative to the accuracy_score metric, but it is not overfit relative to the roc_auc_score metric.

Question: Is this "hidden" relativity in the formal definition of "overfit" an insurmountable obstacle to any attempt to give a formal definition?

I can see that the answer could be "no" if one could uniquely identify a metric as "the correct metric relevant to one's purpose" (e.g. minimizing false positives), but all I have read and heard also suggests that this is often not possible.

Answer 1

I'm sceptical of your "formal" definition, since there is an infinite set of models for every model accepting reals as input, even if one eliminates irrational reals. For models accepting only finite sets of discrete inputs, there are still a combinatorially large set of models. Since a simple lookup table is a valid model, eg, for three binary features, the following is a model:

x_1 x_2 x_3   y
  0   0   0   0
  0   0   1   0
  0   1   0   1
  0   1   1   0
  1   0   0   1
  1   0   1   1
  1   1   0   1
  1   1   1   0

A lookup table can have any arbitrary inputs and outputs defined. Therefore, if you have access to the training data and test data, you can construct a model $w_2$, such that:

• for every example on the training set, $w_2$ gives the wrong answer
• for every example on the test set, that is not in the training set, $w_2$ gives the correct answer

In the general case, $w_2$ thus constructed will thus meet the conditions of overfit you have proposed. And since the formal definition you are proposing only requires the existence of such a $w_2$, it is perfectly legitimate to look at the training and testing data to construct such a $w_2$.

Therefore, I am sceptical that the proposed formal definition of overfit is a valid test for overfitting?