Fast Stochastic Bregman Gradient Methods: Sharp Analysis and Variance\n Reduction

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