What is "information leak from test to train" ? Is stratification by target a leak? It's common practice to do procedures such as standardization and even missing value imputation (commonly based on some means) after train/test split - otherwise it is treated as information leak from test to train.
But what sort of "leaks" we are worried about? If I impute "Apple" to empty "device_brand" fields, where "device_os" is "iOS" - and only after that perform train/test split, is it a "leak"?
Another example - in imbalanced classification problems, it's common practice to explicitly preserve class balance while splitting dataset to train/test. But why stratification (preserving class balance) is not considered as info leak by the same reason?
Are there more or less formal rules, what sort of data preprocessing can be done before train/test splitting, and what can't?
 A: The problem with information leakage is that for proper assessment of prediction quality in the test sample it is assumed that the information from the observations in the test sample is not used to construct the predictor by which they are predicted. In reality we have new observations to predict that cannot be used to construct the classifier, and the use of test and training sample should mimic that situation.
Intuitively, the plain number of observations isn't really information that can help to predict the test observation better (whereas if they are used for missing values imputation or standardisation, not only their number is used but also their actual value). (Note: I only realised later that the question in fact is about using the class information for stratification, see the last paragraph for this.)
If one wanted to show this mathematically, chances are it would be necessary to restrict oneself to specific models and prediction methods. In particular, I suspect that examples can be constructed in which the sample size per class is random and potentially informative (and used as such by the classifier). Showing how the test error/loss relates to the expected prediction error/loss is hard enough in standard situations, but I can well imagine that non-influence of stratification rules such as balancing can be shown in some simple standard situations. Even without that, in most (though not necessarily all) situations I'd rely on the intuition that sample size isn't informative to classify the individual observations.
Note by the way that sample splitting/stratification in fact will have an influence on the characteristics of the prediction loss estimation (which is why people pay attention to this), but this is regardless of the values taken by the actual observations. If I think about it, it may be hard, even in a simple situation, to set up a theorem that proves that "there is no information leakage by stratification", because it may be hard to figure out what such a theorem should say in the first place.
After having seen the change in the question title, I should also add that "stratification by target" uses the class information of the observations for splitting. Intuitively this may well still be harmless because it isn't informative about how the class relates to the other variables, which is what the classifier should assess. However chances are it is even harder to prove any positive result (that this does not do harm) in any situation.
A: To answer the final question: "What sort of data preprocessing can be done before train/test splitting, and what can't?"
None of it. Aside from removing undeniably corrupted data maybe (e.g. a human male weighing 0.75 kg) nothing else should be done in terms of preprocessing. We should design all our pre-processing based on our training set only and then apply it to our test set.
Regarding the original comments and queries on stratification:
You raise a valid point. The main reason why stratification is usually not a problem is that stratification (e.g. sampling such that both our training and test sets have an approximately equal proportion of positive examples) is done to ensure that our model is trained and evaluated on subsets of data that closely reflect the entire dataset's reality; we thus avoid sampling variation leading us to misleading insights.
If we then choose to somehow alter the class proportion in our training set (usually not a great idea but let's assume we want to), our test set still needs to reflect the reality captured in our original raw sample. For the particular example in the post: imputing Apple to a device_brand field is fine if device_brand is an explanatory feature, this is just a pre-processing step for one of our features. We can do the same in our test set as it does not alter our targets. Nevertheless, if device_brand is our target/response variable then we actively change our task at hand! We do not predict something reflects the reality our model is expected to operate in! It is not the imputation that is the problem, it is the role of the feature being imputed!
As a rule of thumb: Changing our target variable's characteristics is a dubious practice and should be avoided. That is because it hurts the generalisability of our model responses and can mislead our assessment of its performance. Changing our explanatory features based on training set insights is usually fine. That is because this amounts to preprocessing our data and giving our learner a (hopefully) easier feature space to explore while keeping what we aim to predict unchanged.
A: The data transformation that you describe is usually not referred to as "imputation", and it will not lead to information leakage. If the value of device brand is determined only by the value of device_os from the same observation, then the procedure for each observation is independent from all other observations, so there cannot be any exchange of information between your test and training data.
In other words, information leakage occurs if the training data is processed in a way that is informed by the test data. The rule of assigning "Apple" to all iOS devices is not something that you have learned from the data, and you don't need information on any other observations to determine the imputed value of a specific observation.
It would be different if you would use another approach to imputation, e.g. multiple imputation, where the imputed value is informed by the whole data, for example by fitting a model to the data to individually predict missing values. In this case, the imputed value depends on the data, and if you do that before the split, the model is trained on information provided by the test data, so there is information leakage.
