Meaning of NOT having a distribution on data In statistics and machine learning, a common starting point is to assume some unknown distribution $\mathbb{P}$ on the cartesian product $\mathcal{X} \times \mathcal{Y}$ of input space and output space. The training data $\{x_i, y_i\}_{i = 1, \ldots , n}$ is then assumed to be i.i.d. samples from $\mathbb{P}$.
What does it mean to not have this assumption? Specifically, does it make sense to have an assumption which says that there is no distribution on $\mathcal{X} \times \mathcal{Y}$ that generated the training sample? Is learning possible in this regime?
Of course, we can always assume that the training data was sampled from the empirical distribution $\frac{1}{n}\sum_{i=1}^n \delta_{(x_i, y_i)}$, and so there always exists a distribution on $\mathcal{X} \times \mathcal{Y}$ that could have generated the sample, but this seems too trivial to be useful or interesting.
The original assumption is studied under the label of "distribution free setting", and perhaps what I am asking is "Is there literally a distribution free setting studied in statistics or ML?"
 A: Your question is only a slight variation (and arguably a duplicate) of a question here.  At its most general, your problem will involve a joint distribution for the vector $(x_1,...,x_n,y_1,...,y_n)$, but if the pairs of values in this vector are not IID then this will not reduce to a common distribution for each $(x_i,y_i)$, and so there will be no unambiguous distribution of interest on $\mathcal{X} \times \mathcal{Y}$.
If you assume that the IID assumption holds, so that you have a common distribution for each pair $(x_i,y_i)$, you then have to decide if you want to impose any structure on the distribution (e.g., an assumption that it is of a particular parametric family of distributions).  If no further structure is imposed, such that this is just an arbitrary bivariate distribution, some sources will call this a "distribution-free" analysis.  (I have always hated this terminology; what they really mean is that they are not using any parametric family of distributions, but they are still using a distribution in a broader space.)
Even in the case where you don't use the IID assumption, statistical modelling will still assume that there is some joint distribution over the vector $(x_1,...,x_n,y_1,...,y_n)$ containing all the observable quantities in the analysis.  This comes from the underlying assumption that these we are working within some probability space, and the observable variables are numeric labels on the sample space (i.e., mappings from the sample space to real numbers).  In this case there is a single $2n$-variate distribution instead of a common bivariate distribution.  You can't really do much in this case, since you will only have one observation from this distribution, so inference of its structure is essentially impossible.
Now, it is of course possible to go further than this, and jettison the entire assumption that we are working within a probability space.  If we do this then there are no probability distributions in the analysis --- this would be a distribution-free model in the literal sense.  (Note that certain "distribution-free" models are not distribution-free in the literal sense; they just eschew parametric families of distributions.)  However, this removes the entire apparatus of probability as a tool of analysis, and so any consequent statistical or machine learning work would then be uninformed by probability theory.  This is possible of course, but it is a bit like performing surgery without use of the underlying biology of the human body; it is messy, and can lead to disaster.
