Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
From MaRDI portal
Publication:3169111
DOI10.1287/moor.1100.0456zbMath1216.15006arXiv0806.3015OpenAlexW2167820643MaRDI QIDQ3169111
Publication date: 27 April 2011
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0806.3015
randomizationcondition numbererror boundmetric regularitycoordinate descentdistance to ill-posednessiterated projectionslinear constraintaveraged projections
Convex programming (90C25) Linear inequalities of matrices (15A39) Iterative numerical methods for linear systems (65F10) Conditioning of matrices (15A12)
Related Items (only showing first 100 items - show all)
Randomized numerical linear algebra: Foundations and algorithms ⋮ PLSS: A Projected Linear Systems Solver ⋮ Approximate Solutions of Linear Systems at a Universal Rate ⋮ Block-cyclic stochastic coordinate descent for deep neural networks ⋮ On adaptive block coordinate descent methods for ridge regression ⋮ Randomized Kaczmarz iteration methods: algorithmic extensions and convergence theory ⋮ Randomized Kaczmarz method with adaptive stepsizes for inconsistent linear systems ⋮ On multi-step randomized extended Kaczmarz method for solving large sparse inconsistent linear systems ⋮ Block Policy Mirror Descent ⋮ On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations ⋮ On convergence rates of Kaczmarz-type methods with different selection rules of working rows ⋮ A randomised iterative method for solving factorised linear systems ⋮ Randomized Block Proximal Damped Newton Method for Composite Self-Concordant Minimization ⋮ Randomized Douglas–Rachford Methods for Linear Systems: Improved Accuracy and Efficiency ⋮ Faster Deterministic Pseudoinverse-Free Block Extension of Motzkin Method for Large Consistent Linear Systems ⋮ Sparse sampling Kaczmarz–Motzkin method with linear convergence ⋮ Linearly convergent adjoint free solution of least squares problems by random descent ⋮ On greedy randomized block Gauss-Seidel method with averaging for sparse linear least-squares problems ⋮ An easily computable upper bound on the Hoffman constant for homogeneous inequality systems ⋮ On pseudoinverse-free block maximum residual nonlinear Kaczmarz method for solving large-scale nonlinear system of equations ⋮ Local linear convergence of proximal coordinate descent algorithm ⋮ Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition ⋮ A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility ⋮ Rows versus Columns: Randomized Kaczmarz or Gauss--Seidel for Ridge Regression ⋮ Randomized Projection Methods for Linear Systems with Arbitrarily Large Sparse Corruptions ⋮ Randomized Projection Methods for Convex Feasibility: Conditioning and Convergence Rates ⋮ Convergence Analysis of Inexact Randomized Iterative Methods ⋮ A generic coordinate descent solver for non-smooth convex optimisation ⋮ A Partially Greedy Randomized Extended Gauss-Seidel Method for Solving Large Linear Systems ⋮ Effects of depth, width, and initialization: A convergence analysis of layer-wise training for deep linear neural networks ⋮ A two-step randomized Gauss-Seidel method for solving large-scale linear least squares problems ⋮ Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection ⋮ Parallel random block-coordinate forward-backward algorithm: a unified convergence analysis ⋮ Accelerated, Parallel, and Proximal Coordinate Descent ⋮ An accelerated randomized Kaczmarz algorithm ⋮ An Accelerated Randomized Proximal Coordinate Gradient Method and its Application to Regularized Empirical Risk Minimization ⋮ Inexact coordinate descent: complexity and preconditioning ⋮ Stochastic block projection algorithms with extrapolation for convex feasibility problems ⋮ Convergence Properties of the Randomized Extended Gauss--Seidel and Kaczmarz Methods ⋮ Randomized Iterative Methods for Linear Systems ⋮ On greedy randomized average block Kaczmarz method for solving large linear systems ⋮ A Fast Block Coordinate Descent Method for Solving Linear Least-Squares Problems ⋮ On Convergence of the Partially Randomized Extended Kaczmarz Method ⋮ Sampling Kaczmarz-Motzkin method for linear feasibility problems: generalization and acceleration ⋮ Solving systems of phaseless equations via Kaczmarz methods: a proof of concept study ⋮ Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds ⋮ On the relaxed greedy deterministic row and column iterative methods ⋮ Adaptively sketched Bregman projection methods for linear systems ⋮ A real-time iterative projection scheme for solving the common fixed point problem and its applications ⋮ Randomized Kaczmarz with averaging ⋮ Accelerated sampling Kaczmarz Motzkin algorithm for the linear feasibility problem ⋮ A greedy block Kaczmarz algorithm for solving large-scale linear systems ⋮ Linear convergence of first order methods for non-strongly convex optimization ⋮ RidgeSketch: A Fast Sketching Based Solver for Large Scale Ridge Regression ⋮ Block Kaczmarz method with inequalities ⋮ Almost sure convergence of the Kaczmarz algorithm with random measurements ⋮ Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization ⋮ On the convergence of randomized and greedy relaxation schemes for solving nonsingular linear systems of equations ⋮ On relaxed greedy randomized coordinate descent methods for solving large linear least-squares problems ⋮ On the Efficiency of Random Permutation for ADMM and Coordinate Descent ⋮ A Randomized Nonmonotone Block Proximal Gradient Method for a Class of Structured Nonlinear Programming ⋮ A linearly convergent doubly stochastic Gauss-Seidel algorithm for solving linear equations and a certain class of over-parameterized optimization problems ⋮ Randomized Quasi-Newton Updates Are Linearly Convergent Matrix Inversion Algorithms ⋮ On multi-step greedy randomized coordinate descent method for solving large linear least-squares problems ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ A note on convergence rate of randomized Kaczmarz method ⋮ On the relation between the randomized extended Kaczmarz algorithm and coordinate descent ⋮ Splitting-based randomized iterative methods for solving indefinite least squares problem ⋮ Paved with good intentions: analysis of a randomized block Kaczmarz method ⋮ Greedy and randomized versions of the multiplicative Schwarz method ⋮ Linear convergence of the randomized sparse Kaczmarz method ⋮ Optimization for deep learning: an overview ⋮ A stochastic Kaczmarz algorithm for network tomography ⋮ Worst-case complexity of cyclic coordinate descent: \(O(n^2)\) gap with randomized version ⋮ Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function ⋮ On convergence rate of the randomized Gauss-Seidel method ⋮ Two-subspace projection method for coherent overdetermined systems ⋮ Randomized Extended Average Block Kaczmarz for Solving Least Squares ⋮ Randomized block Kaczmarz method with projection for solving least squares ⋮ On the complexity analysis of randomized block-coordinate descent methods ⋮ A Randomized Exchange Algorithm for Computing Optimal Approximate Designs of Experiments ⋮ A Smooth Inexact Penalty Reformulation of Convex Problems with Linear Constraints ⋮ Optimization Methods for Large-Scale Machine Learning ⋮ An extended row and column method for solving linear systems on a quantum computer ⋮ A doubly stochastic block Gauss-Seidel algorithm for solving linear equations ⋮ Two Symmetrized Coordinate Descent Methods Can Be $O(n^2)$ Times Slower Than the Randomized Version ⋮ A geometric probability randomized Kaczmarz method for large scale linear systems ⋮ On Motzkin's method for inconsistent linear systems ⋮ Schwarz iterative methods: infinite space splittings ⋮ New characterizations of Hoffman constants for systems of linear constraints ⋮ A new randomized Gauss-Seidel method for solving linear least-squares problems ⋮ Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods ⋮ On the von Neumann and Frank--Wolfe Algorithms with Away Steps ⋮ Proximal algorithms and temporal difference methods for solving fixed point problems ⋮ The Kaczmarz algorithm, row action methods, and statistical learning algorithms ⋮ A refinement of an iterative orthogonal projection method ⋮ Stochastic First-Order Methods with Random Constraint Projection ⋮ Faster Randomized Block Kaczmarz Algorithms ⋮ On the error estimate of the randomized double block Kaczmarz method ⋮ A weighted randomized Kaczmarz method for solving linear systems
This page was built for publication: Randomized Methods for Linear Constraints: Convergence Rates and Conditioning
