# Does the convergence of algorithms in machine learning to train set make sense?

Think of the hypothetical situation where we have a y reponse and a scalar input x, we want a function that maps x to y perfectly at least in the training set. This does not make sense, it is just imagining a situation where there are two instances with the same value of x but different responses, it is mathematically impossible to propose a function that correctly predicts these two instances. In view of this problem, why are convergence criteria used in some ML algorithms such as neural networks?

• If you have two y's for one x, it's not a function. But you can still try to approximate this relation with a function. – Arya McCarthy May 1 at 21:18
• Perfectly predicting the training set is often a smell for an overfitted model. Which convergence criteria are you referring to? – Arya McCarthy May 2 at 3:53
• With convergence I meant is there a model F such that L(F,yi)=0 for all i in {1,....,N}. I know what overfitting is but i'm interested on it in this question. – Davi Américo May 2 at 21:22

Having two different $$y$$'s for the same value of $$x$$ will make the function not well defined, you can try plugging a data like this to a machine learning algorithm(say NN), if all your data is the same $$x$$ but all have different $$y$$, the algorithm will try to approximate the function but will not succeed to converge! As for the mathematical analysis of machine learning, you can check PAC Learning

You can try with this example(or tweak it) but it will not converge with this kind of data:

from tensorflow import keras
import numpy as np
x=np.array([1 for _ in range(100000)],dtype=float)
y=np.array([x for x in range(2,2+len(x))],dtype=float)
model=keras.Sequential([keras.layers.Dense(10,input_shape=[1])])
model.compile(optimizer="SGD",loss="MSE")
model.fit(x,y,batch_size=500)


Neural networks learn mathematical functions by minimizing the loss function between the function and the observed data. A function in mathematics is a mapping, that maps $$X$$ values to $$Y$$, $$f: X \to Y$$. There are one-to-one functions, where each of the elements in $$X$$ maps to a distinct element in $$Y$$, and functions that can map multiple $$X$$ elements to the same $$Y$$ values (e.g. absolute value function). There are no functions that map the same inputs $$X$$ to different outputs $$Y$$.

In most cases, we apply neural networks to learn from real-life data that is noisy, $$y = f(x) + \varepsilon$$, so we assume that the observed values $$y$$ depend on the deterministic function $$f(x)$$ and random noise $$\varepsilon$$. In such a case, it can happen that different $$X$$'s are paired with the same $$Y$$'s because of the random noise. What neural network (or any other machine learning algorithm) would do in such cases, is it will either predict something like an average between the two possible outputs or learn to pick one of them as a prediction. Another solution might be to use a probabilistic model. It will learn how probable are the outcomes and assign the same probabilities to both outcomes. To make a point prediction, you could do something like predicting the expected value (an average) or choosing between them at random, based on the predicted probabilities.

The convergence criteria used in such a case is observing that training the model further does not lead to any improvement. Obviously, this does not give you any guarantees whatsoever that a better solution is not possible, it shows only that the model that you are using, with the random initialization and hyperparameters that you used, does not seem to improve anymore. It still may be possible that using a different model, random seed, hyperparameters, or optimizer, etc could lead to better result.

TL;DR What you are asking is impossible. You cannot have perfectly fitting one-to-many mappings, they cannot be learned. There are however solutions that would yield optimal, though not exact predictions. In such a case, you train the model until it stops improving.

• Suppose i am using any machine learning algorithm to minimize a loss function, suppose that in two consecutive iterations the difference in the loss function value between these iterations is close enough to zero, it just means that my model is not more improving as iterations go by but it doesn’t mean that my loss function has converged to the global minimum, is that what you mean ?, that is the word "convergence" most of the time means that my model no longer improves instead to get a convergence to a minimum in the loss function? – Davi Américo May 2 at 21:18
• @DaviAmérico more or less yes. Usually, you have no guarantees that you found a global minimum. – Tim May 2 at 23:10
• even if L is a convex function? – Davi Américo May 3 at 1:01
• @DaviAmérico you asked about case where it isn’t, because of having multiple minimas. – Tim May 3 at 5:13
• I've asked in general case.I'm still in doubt if it can get convergency even if loss function is convex. – Davi Américo May 4 at 1:45