Stochastic Dual Ascent for Solving Linear Systems

Abstract

We develop a new randomized iterative algorithm---stochastic dual ascent (SDA)---for finding the projection of a given vector onto the solution space of a linear system. The method is dual in nature: with the dual being a non-strongly concave quadratic maximization problem without constraints. In each iteration of SDA, a dual variable is updated by a carefully chosen point in a subspace spanned by the columns of a random matrix drawn independently from a fixed distribution. The distribution plays the role of a parameter of the method. Our complexity results hold for a wide family of distributions of random matrices, which opens the possibility to fine-tune the stochasticity of the method to particular applications. We prove that primal iterates associated with the dual process converge to the projection exponentially fast in expectation, and give a formula and an insightful lower bound for the convergence rate. We also prove that the same rate applies to dual function values, primal function values and the duality gap. Unlike traditional iterative methods, SDA converges under no additional assumptions on the system (e.g., rank, diagonal dominance) beyond consistency. In fact, our lower bound improves as the rank of the system matrix drops. Many existing randomized methods for linear systems arise as special cases of SDA, including randomized Kaczmarz, randomized Newton, randomized coordinate descent, Gaussian descent, and their variants. In special cases where our method specializes to a known algorithm, we either recover the best known rates, or improve upon them. Finally, we show that the framework can be applied to the distributed average consensus problem to obtain an array of new algorithms. The randomized gossip algorithm arises as a special case.

This is a slightly refreshed version of the paper originally submitted on Dec 21, 2015. We have added a numerical experiment involving randomized Kaczmarz for rank-deficient systems, added a few relevant references, and corrected a few typos. Stats: 29 pages, 2 algorithms, 1 figure

References in corpus (10)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
• Parallel Coordinate Descent for L1-Regularized Loss Minimization
• SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
• Coordinate Descent with Arbitrary Sampling I: Algorithms and Complexity
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Coordinate Descent with Arbitrary Sampling II: Expected Separable Overapproximation
• Linear Convergence of the Randomized Feasible Descent Method Under the Weak Strong Convexity Assumption
• Convergence properties of the randomized extended Gauss-Seidel and Kaczmarz methods
• Rows vs Columns for Linear Systems of Equations - Randomized Kaczmarz or Coordinate Descent?

Cited by in corpus (26)

• Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives
• Privacy Preserving Randomized Gossip Algorithms
• Linearly Convergent Randomized Iterative Methods for Computing the Pseudoinverse
• Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
• Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms
• Alternating Randomized Block Coordinate Descent
• Stochastic Block BFGS: Squeezing More Curvature out of Data
• Sketch and Project: Randomized Iterative Methods for Linear Systems and Inverting Matrices
• Adaptive Sketch-and-Project Methods for Solving Linear Systems
• A Kaczmarz Method with Simple Random Sampling for Solving Large Linear Systems
• A Privacy Preserving Randomized Gossip Algorithm via Controlled Noise Insertion
• On block Gaussian sketching for the Kaczmarz method
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Greed Works: An Improved Analysis of Sampling Kaczmarz-Motzkin
• Searching equillibriums in large transport networks
• Stochastic Spectral and Conjugate Descent Methods
• A stochastic subspace approach to gradient-free optimization in high dimensions
• Preconvergence of the randomized extended Kaczmarz method
• A Linearly Convergent Doubly Stochastic Gauss-Seidel Algorithm for Solving Linear Equations and A Certain Class of Over-Parameterized Optimization Problems
• SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums
• $\text{RidgeSketch}$: A Fast sketching based solver for large scale ridge regression
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Non accelerated efficient numerical methods for sparse quadratic optimization problems and its generalizations
• A New Perspective on Randomized Gossip Algorithms