  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.
