Fastest rates for stochastic mirror descent methods
From MaRDI portal
Abstract: Relative smoothness - a notion introduced by Birnbaum et al. (2011) and rediscovered by Bauschke et al. (2016) and Lu et al. (2016) - generalizes the standard notion of smoothness typically used in the analysis of gradient type methods. In this work we are taking ideas from well studied field of stochastic convex optimization and using them in order to obtain faster algorithms for minimizing relatively smooth functions. We propose and analyze two new algorithms: Relative Randomized Coordinate Descent (relRCD) and Relative Stochastic Gradient Descent (relSGD), both generalizing famous algorithms in the standard smooth setting. The methods we propose can be in fact seen as a particular instances of stochastic mirror descent algorithms. One of them, relRCD corresponds to the first stochastic variant of mirror descent algorithm with linear convergence rate.
Recommendations
- Relatively smooth convex optimization by first-order methods, and applications
- On the convergence of mirror descent beyond stochastic convex programming
- On stochastic subgradient mirror-descent algorithm with weighted averaging
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- On the complexity analysis of randomized block-coordinate descent methods
Cites work
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A Stochastic Approximation Method
- Coordinate descent with arbitrary sampling. I: Algorithms and complexity.
- Coordinate descent with arbitrary sampling. II: Expected separable overapproximation.
- Efficiency of coordinate descent methods on huge-scale optimization problems
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- Image deblurring with Poisson data: from cells to galaxies
- Introductory lectures on convex optimization. A basic course.
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Linear coupling: an ultimate unification of gradient and mirror descent
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- MM optimization algorithms
- On optimal probabilities in stochastic coordinate descent methods
- On stochastic subgradient mirror-descent algorithm with weighted averaging
- On the complexity of parallel coordinate descent
- Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework
- Parallel coordinate descent methods for big data optimization
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Proportional response dynamics in the Fisher market
- Robust Stochastic Approximation Approach to Stochastic Programming
- Stochastic block mirror descent methods for nonsmooth and stochastic optimization
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Understanding machine learning. From theory to algorithms
- Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems
Cited in
(15)- A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization
- Relatively smooth convex optimization by first-order methods, and applications
- Adaptivity of stochastic gradient methods for nonconvex optimization
- On the convergence of mirror descent beyond stochastic convex programming
- Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
- Stochastic composition optimization of functions without Lipschitz continuous gradient
- Stochastic incremental mirror descent algorithms with Nesterov smoothing
- Coordinate descent methods beyond smoothness and separability
- An accelerated stochastic mirror descent method
- Regularized Rényi divergence minimization through Bregman proximal gradient algorithms
- Stochastic Bregman subgradient methods for nonsmooth nonconvex optimization problems
- Nonconvex stochastic Bregman proximal gradient method with application to deep learning
- Parallel block coordinate descent methods with identification strategies
- Adaptive Schauder Stochastic Mirror Descent in Banach Spaces
- Bregman proximal gradient algorithms for deep matrix factorization
This page was built for publication: Fastest rates for stochastic mirror descent methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2044496)
