Robust Conditional Probabilities
Conditional probabilities are a core concept in machine learning. For example, optimal prediction of a label Y given an input X corresponds to maximizing the conditional probability of Y given X. A common approach to inference tasks is learning a model of conditional probabilities. However, these models are often based on strong assumptions (e.g., log-linear models), and hence their estimate of conditional probabilities is not robust and is highly dependent on the validity of their assumptions. Here we propose a framework for reasoning about conditional probabilities without assuming anything about the underlying distributions, except knowledge of their second order marginals, which can be estimated from data. We show how this setting leads to guaranteed bounds on conditional probabilities, which can be calculated efficiently in a variety of settings, including structured-prediction. Finally, we apply them to semi-supervised deep learning, obtaining results competitive with variational autoencoders.
This paper studies the problem of computing probability bounds, more specifically bounds over probability of atoms of the joint space and conditional probabilities of the class, under the assumption that only some pairwise marginal as well as some univariate marginal values are known. The idea is that such marginals may be easier to obtain than fully specified probabilities, and that cautious inferences can then be used to produce predictions. 
It is shown that when the marginals follow a tree structure (results are extended to a few other structures), then the problem can actually be solved in closed, analytical form, relating it to cover set and maximum flow problems. Some experiments performed on neural networks  show that this simple method is actually competitive with other more complex approaches (Ladder, VAE), while outperforming methods of comparable complexity. 
The paper is elegantly written, with quite understandable and significant results. I see no reason to not accept it. Authors may be interested in looking at the following papers coming from the imprecise probability literature (since they deal with partially specified probabilities, this may be related):
* Benavoli, A., Facchini, A., Piga, D., & Zaffalon, M. (2017). SOS for bounded rationality. arXiv preprint arXiv:1705.02663.
* Miranda, E., De Cooman, G., & Quaeghebeur, E. (2007). The Hausdorff moment problem under finite additivity. Journal of Theoretical Probability, 20(3), 663-693.
Typos:
* L112:  solved Our —> solved. Our
* L156: assume are —> assume we are
* References: 28/29 are redundant