Linear regression from data that don't represent a function

I have $(x,\ y)$ pairs with a strongly suspected linear correlation. So I want to fit the "best" linear function in order to make predictions for unknown $x$'s. These pairs don't represent a function, i.e. there are many different values of $y$ for some $x$. I want to know if there is an issue with that considering this as a machine learning problem. Should I use some unique "representative" (average, maximum, minimum, most frequent, etc.) and convert the input data in a function or it is OK to work with the data as it is?

If you perform linear regression on your raw data using Ordinary Least Squares to estimate the model parameters you will get a model that estimates the conditional mean of $Y$ given the observed value of $X$. I.e. $\hat{f}(x)=E[Y|X=x].$ Since your model outputs the conditional expectation of the response it wouldn't be necessary to convert your $Y|X=x$ into a descriptive statistic prior to your analysis.
• You're right that your validation method wouldn't make much sense. Since you said, "there are many different values of y for some x," you know that there is no "real" value of $Y$ at a given level of $X$, i.e. the relationship isn't deterministic. Using linear regression with OLS estimators you can predict $E[Y|X=x]$, so you could compare these predictions to the average Y value at a given level of X to determine how accurate your model is. The regression output should provide you with diagnostics to make checks similar to this. – tjnel Nov 8 '13 at 21:42