Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition

• URL: http://arxiv.org/abs/2208.09585v2
• Date: Mon, 18 Sep 2023 20:19:15 GMT
• Title: Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition
• Authors: Micha{\l} Derezi\'nski, Elizaveta Rebrova
• Abstract summary: We develop a theoretical framework for obtaining sharp guarantees on the convergence rate of sketch-and-project methods. We show that the convergence rate improves at least linearly with the sketch size, and even faster when the data matrix exhibits certain spectral decays. Our experiments support the theory and demonstrate that even extremely sparse sketches exhibit the convergence properties predicted by our framework.
• Score: 14.453949553412821
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sketch-and-project is a framework which unifies many known iterative methods for solving linear systems and their variants, as well as further extensions to non-linear optimization problems. It includes popular methods such as randomized Kaczmarz, coordinate descent, variants of the Newton method in convex optimization, and others. In this paper, we develop a theoretical framework for obtaining sharp guarantees on the convergence rate of sketch-and-project methods. Our approach is the first to: (1) show that the convergence rate improves at least linearly with the sketch size, and even faster when the data matrix exhibits certain spectral decays; and (2) allow for sparse sketching matrices, which are more efficient than dense sketches and more robust than sub-sampling methods. In particular, our results explain an observed phenomenon that a radical sparsification of the sketching matrix does not affect the per iteration convergence rate of sketch-and-project. To obtain our results, we develop new non-asymptotic spectral bounds for the expected sketched projection matrix, which are of independent interest; and we establish a connection between the convergence rates of iterative sketch-and-project solvers and the approximation error of randomized singular value decomposition, which is a widely used one-shot sketching algorithm for low-rank approximation. Our experiments support the theory and demonstrate that even extremely sparse sketches exhibit the convergence properties predicted by our framework.

Related papers

• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  We consider distributed optimization methods for problems where forming the Hessian is computationally challenging. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
  arXiv  Detail & Related papers  (2022-03-18T05:49:13Z)
• Accumulations of Projections--A Unified Framework for Random Sketches in Kernel Ridge Regression [12.258887270632869]
  Building a sketch of an n-by-n empirical kernel matrix is a common approach to accelerate the computation of many kernel methods. We propose a unified framework of constructing sketching methods in kernel ridge regression.
  arXiv  Detail & Related papers  (2021-03-06T05:02:17Z)
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications [24.763531954075656]
  We study a novel class of projection-based algorithms for linearly constrained problems (LCPs) We propose the delayed projection technique that calls a projection once for a while, lowering the projection frequency and improving the projection efficiency. We show that it is feasible to improve projection efficiency in both strongly convex and generally convex cases.
  arXiv  Detail & Related papers  (2021-01-05T13:42:41Z)
• Progressive Batching for Efficient Non-linear Least Squares [31.082253632197023]
  Most improvements of the basic Gauss-Newton tackle convergence guarantees or leverage the sparsity of the underlying problem structure for computational speedup. Our work borrows ideas from both machine learning and statistics, and we present an approach for non-linear least-squares that guarantees convergence while at the same time significantly reduces the required amount of computation.
  arXiv  Detail & Related papers  (2020-10-21T13:00:04Z)
• Precise expressions for random projections: Low-rank approximation and randomized Newton [63.68433510953756]
  Matrix sketching has emerged as a powerful technique for performing such dimensionality reduction very efficiently. We develop techniques that provide provably accurate expressions for the expected value of random projection matrices obtained via sketching. These expressions can be used to characterize the performance of dimensionality reduction in a variety of common machine learning tasks.
  arXiv  Detail & Related papers  (2020-06-18T16:23:00Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• Statistical Outlier Identification in Multi-robot Visual SLAM using Expectation Maximization [18.259478519717426]
  This paper introduces a novel and distributed method for detecting inter-map loop closure outliers in simultaneous localization and mapping (SLAM) The proposed algorithm does not rely on a good initialization and can handle more than two maps at a time.
  arXiv  Detail & Related papers  (2020-02-07T06:34:44Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.