Convergence analysis of inexact randomized iterative methods
From MaRDI portal
convex optimizationinexact methodsiteration complexitylinear systemsquadratic optimizationrandomized block coordinate descentrandomized block Kaczmarzstochastic gradient descentstochastic Newton method
Linear equations (linear algebraic aspects) (15A06) Random matrices (algebraic aspects) (15B52) Iterative numerical methods for linear systems (65F10) Complexity and performance of numerical algorithms (65Y20) Randomized algorithms (68W20) Analysis of algorithms (68W40) Stochastic programming (90C15) Quadratic programming (90C20) Convex programming (90C25)
Abstract: In this paper we present a convergence rate analysis of inexact variants of several randomized iterative methods. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic subspace ascent. A common feature of these methods is that in their update rule a certain sub-problem needs to be solved exactly. We relax this requirement by allowing for the sub-problem to be solved inexactly. In particular, we propose and analyze inexact randomized iterative methods for solving three closely related problems: a convex stochastic quadratic optimization problem, a best approximation problem and its dual, a concave quadratic maximization problem. We provide iteration complexity results under several assumptions on the inexactness error. Inexact variants of many popular and some more exotic methods, including randomized block Kaczmarz, randomized Gaussian Kaczmarz and randomized block coordinate descent, can be cast as special cases. Numerical experiments demonstrate the benefits of allowing inexactness.
Recommendations
Cites work
- A flexible coordinate descent method
- A UNIFIED FRAMEWORK FOR SOME INEXACT PROXIMAL POINT ALGORITHMS*
- Accelerated, parallel, and proximal coordinate descent
- Acceleration of randomized Kaczmarz method via the Johnson-Lindenstrauss lemma
- An investigation of Newton-sketch and subsampled Newton methods
- Applied iterative methods.
- Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
- Convergence rates for Kaczmarz-type algorithms
- 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
- First-order methods of smooth convex optimization with inexact oracle
- scientific article; zbMATH DE number 5454133 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 3027894 (Why is no real title available?)
- Hybrid deterministic-stochastic methods for data fitting
- Inexact and accelerated proximal point algorithms
- Inexact coordinate descent: complexity and preconditioning
- Inexact Newton Methods
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Least-squares solution of overdetermined inconsistent linear systems using kaczmarz's relaxation
- Linear convergence of the randomized sparse Kaczmarz method
- Newton-type methods for non-convex optimization under inexact Hessian information
- Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity
- Numerical Optimization
- On the convergence of inexact block coordinate descent methods for constrained optimization
- Order-Optimal Consensus Through Randomized Path Averaging
- Parallel coordinate descent methods for big data optimization
- Paved with good intentions: analysis of a randomized block Kaczmarz method
- Randomized block Kaczmarz method with projection for solving least squares
- Randomized extended Kaczmarz for solving least squares
- Randomized iterative methods for linear systems
- Randomized Kaczmarz solver for noisy linear systems
- Randomized methods for linear constraints: convergence rates and conditioning
- Rate Analysis of Inexact Dual First-Order Methods Application to Dual Decomposition
- Stochastic Primal-Dual Hybrid Gradient Algorithm with Arbitrary Sampling and Imaging Applications
- Stochastic reformulations of linear systems: algorithms and convergence theory
- Termination criteria for inexact fixed-point schemes.
Cited in
(9)- On the generally randomized extended Gauss-Seidel method
- On convergence rate of the randomized Gauss-Seidel method
- Convergence Analysis of Iterative Solvers in Inexact Rayleigh Quotient Iteration
- Convergence analyses based on frequency decomposition for the randomized row iterative method
- Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
- Convergence to approximate solutions and perturbation resilience of iterative algorithms
- Randomized iterative methods for generalized absolute value equations: solvability and error bounds
- On the adaptively inexact sketched Newton-Raphson methods for nonlinear systems of equations
- On the alternating randomized row-action methods with the application to data fitting
This page was built for publication: Convergence analysis of inexact randomized iterative methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5856678)
