  We study the problem of minimizing a relatively-smooth convex function using
stochastic Bregman gradient methods. We first prove the convergence of Bregman
Stochastic Gradient Descent (BSGD) to a region that depends on the noise
(magnitude of the gradients) at the optimum. In particular, BSGD with a
constant step-size converges to the exact minimizer when this noise is zero
(\emph{interpolation} setting, in which the data is fit perfectly). Otherwise,
when the objective has a finite sum structure, we show that variance reduction
can be used to counter the effect of noise. In particular, fast convergence to
the exact minimizer can be obtained under additional regularity assumptions on
the Bregman reference function. We illustrate the effectiveness of our approach
on two key applications of relative smoothness: tomographic reconstruction with
Poisson noise and statistical preconditioning for distributed optimization.
