  We propose a new approach to apply the chaining technique in conjunction with
information-theoretic measures to bound the generalization error of machine
learning algorithms. Different from the deterministic chaining approach based
on hierarchical partitions of a metric space, previously proposed by Asadi et
al., we propose a stochastic chaining approach, which replaces the hierarchical
partitions with an abstracted Markovian model borrowed from successive
refinement source coding. This approach has three benefits over deterministic
chaining: 1) the metric space is not necessarily bounded, 2) facilitation of
subsequent analysis to yield more explicit bound, and 3) further opportunity to
optimize the bound by removing the geometric rigidity of the partitions. The
proposed approach includes the traditional chaining as a special case, and can
therefore also utilize any deterministic chaining construction. We illustrate
these benefits using the problem of estimating Gaussian mean and that of phase
retrieval. For the former, we derive a bound that provides an order-wise
improvement over previous results, and for the latter we provide a stochastic
chain that allows optimization over the chaining parameter.
