  When one observes a sequence of variables $(x_1, y_1), \ldots, (x_n, y_n)$,
Conformal Prediction (CP) is a methodology that allows to estimate a confidence
set for $y_{n+1}$ given $x_{n+1}$ by merely assuming that the distribution of
the data is exchangeable. CP sets have guaranteed coverage for any finite
population size $n$. While appealing, the computation of such a set turns out
to be infeasible in general, e.g. when the unknown variable $y_{n+1}$ is
continuous. The bottleneck is that it is based on a procedure that readjusts a
prediction model on data where we replace the unknown target by all its
possible values in order to select the most probable one. This requires
computing an infinite number of models, which often makes it intractable. In
this paper, we combine CP techniques with classical algorithmic stability
bounds to derive a prediction set computable with a single model fit. We
demonstrate that our proposed confidence set does not lose any coverage
guarantees while avoiding the need for data splitting as currently done in the
literature. We provide some numerical experiments to illustrate the tightness
of our estimation when the sample size is sufficiently large, on both synthetic
and real datasets.
