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

2021/04/20 by Dragomir, Radu-Alexandru, Mathieu Even, Even, Mathieu +3 · 4 citations
Computer Science · Economics, Econometrics and Finance · Engineering · Mathematics · #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Stochastic Gradient Optimization Techniques #Stochastic processes and financial applications

paper · pdf · doi:10.48550/arxiv.2104.09813

openalex publication_date 2021/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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(\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

Cited by

• On-line Pick-Freeze Mirror algorithm for Sensitity Analysis
• Bregman Stochastic Proximal Point Algorithm with Variance Reduction
• On Relatively Smooth Optimization over Riemannian Manifolds
• On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem

Related

• Stochastic Bregman Proximal Gradient Method Revisited: Kernel Conditioning and Painless Variance Reduction
• Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization
• Accelerated Bregman gradient methods for relatively smooth and relatively Lipschitz continuous minimization problems
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Explicit Regularization of Stochastic Gradient Methods through Duality