Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
arXiv:1909.12176
Abstract
In the era of big data, one of the key challenges is the development of novel optimization algorithms that can accommodate vast amounts of data while at the same time satisfying constraints and limitations of the problem under study. The need to solve optimization problems is ubiquitous in essentially all quantitative areas of human endeavor, including industry and science. In the last decade there has been a surge in the demand from practitioners, in fields such as machine learning, computer vision, artificial intelligence, signal processing and data science, for new methods able to cope with these new large scale problems. In this thesis we are focusing on the design, complexity analysis and efficient implementations of such algorithms. In particular, we are interested in the development of randomized iterative methods for solving large scale linear systems, stochastic quadratic optimization problems, the best approximation problem and quadratic optimization problems. A large part of the thesis is also devoted to the development of efficient methods for obtaining average consensus on large scale networks.
arXiv commentPhD Thesis, University of Edinburgh, 2019
References in corpus (28)
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Paved with Good Intentions: Analysis of a Randomized Block Kaczmarz Method
- Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- Geographic Gossip: Efficient Averaging for Sensor Networks
- Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
- Stochastic Gradient Push for Distributed Deep Learning
- Optimization and Analysis of Distributed Averaging with Short Node Memory
- Polynomial Filtering for Fast Convergence in Distributed Consensus
- Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling
- Accelerated Gradient Methods for Networked Optimization
- Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization
- Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control
- Stochastic Dual Ascent for Solving Linear Systems
- Communication/Computation Tradeoffs in Consensus-Based Distributed Optimization
- SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization
- On the Randomized Kaczmarz Algorithm
- Stochastic Dual Coordinate Ascent with Adaptive Probabilities
- Direct Acceleration of SAGA using Sampled Negative Momentum
- Inexact Non-Convex Newton-Type Methods
- Linearly convergent stochastic heavy ball method for minimizing generalization error
- Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives
- Privacy Preserving Randomized Gossip Algorithms
- Global Convergence of Arbitrary-Block Gradient Methods for Generalized Polyak-Łojasiewicz Functions
- Linearly Convergent Randomized Iterative Methods for Computing the Pseudoinverse
- Reducing the variance in online optimization by transporting past gradients
- A Privacy Preserving Randomized Gossip Algorithm via Controlled Noise Insertion
- Optimal Matrix Momentum Stochastic Approximation and Applications to Q-learning