I'm trying to understand the behavior of machine learning algorithms where the loss function is non-convex and the problem of training the ML on a specific data set is computationally hard.

Now let's imagine for a moment that we have an "Optimization Oracle" that can give us the global minimum of the loss function on the training set (or on a set of cross-validated training sets) - or maybe it just turns out that P=NP (unlikely, but this is a thought experiment).

Would this actually improve the performance of the ML algorithm in terms of out of sample accuracy and generalization ability?

The reason I ask, is that I see conflicting trends in the ML community:

  • On one hand, traditional regularization and feature selection approaches such as L1 and L2 regularization of the loss function, and hyper-parameter search methods like cross-validation and Bayesian Optimization would definitely benefit from an "Optimization Oracle", since they are all about redefining the training of the model from a naive optimization of the loss function, to a more sophisticated optimization problem or to a more global global one. But ultimately the problem of training the model is still an optimization problem over a non-convex set, and hence an algorithm with global optimality guarantees can only improve its outcomes.

  • On the other hand, some of the more recent methods for improving generalization ability and avoiding overfitting, such as ensembling, bootstrapping, dropout and early stopping (these last two are specific to neural networks), etc...seem to fly in the face of an Optimization Oracle being of any use to a supervised learning model. They are all about avoiding overfitting by adding stochasticity and robustness to the training process or to the prediction process. Implicitly, this class of methods seem to equate finding the absolute minimum of the loss function - regularized or not - with overfitting; e.g. putting "too much effort" into finding the absolute lowest possible value of the loss function will just lead to a high variance model since it would be too specific to the training data set (although I can't figure out a more rigorous expression of this idea, so I might be wrong).

So to restate my question:

Would supervised learning algorithms that deal with non-convex loss functions benefit from an Optimization Oracle because ultimately any training (regularized or not) or hyper-parameter search procedure boils down to an optimization problem? Or is it the case that finding a global optimum will lead to overfitting, because the global minimum of any loss function on a training data set is necessarily specific to that data set, and therefore would reduce generalization ability?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.