Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton

• URL: http://arxiv.org/abs/2502.13583v1
• Date: Wed, 19 Feb 2025 09:49:38 GMT
• Title: Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton
• Authors: Chengmei Niu, Zhenyu Liao, Zenan Ling, Michael W. Mahoney,
• Abstract summary: Inversion bias is the phenomenon that inverses of random sketches are not unbiased, despite the unbiasedness of the sketches themselves. This bias presents challenges for the use of random sketches in various machine learning pipelines. We show how the inversion bias can be corrected for random sampling methods, both uniform and non-uniform leverage-based, as well as for structured random projections.
• Score: 43.55440953429919
• License:
• Abstract: A substantial body of work in machine learning (ML) and randomized numerical linear algebra (RandNLA) has exploited various sorts of random sketching methodologies, including random sampling and random projection, with much of the analysis using Johnson--Lindenstrauss and subspace embedding techniques. Recent studies have identified the issue of inversion bias -- the phenomenon that inverses of random sketches are not unbiased, despite the unbiasedness of the sketches themselves. This bias presents challenges for the use of random sketches in various ML pipelines, such as fast stochastic optimization, scalable statistical estimators, and distributed optimization. In the context of random projection, the inversion bias can be easily corrected for dense Gaussian projections (which are, however, too expensive for many applications). Recent work has shown how the inversion bias can be corrected for sparse sub-gaussian projections. In this paper, we show how the inversion bias can be corrected for random sampling methods, both uniform and non-uniform leverage-based, as well as for structured random projections, including those based on the Hadamard transform. Using these results, we establish problem-independent local convergence rates for sub-sampled Newton methods.

Related papers

• Weak Generative Sampler to Efficiently Sample Invariant Distribution of Stochastic Differential Equation [8.67581853745823]
  Current deep learning-based method solves the stationary Fokker--Planck equation to determine the invariant probability density function in form of deep neural networks. We introduce a framework that employs a weak generative sampler (WGS) to directly generate independent and identically distributed (iid) samples. Our proposed loss function is based on the weak form of the Fokker--Planck equation, integrating normalizing flows to characterize the invariant distribution.
  arXiv  Detail & Related papers  (2024-05-29T16:41:42Z)
• Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs [22.925108493465363]
  We provide an algorithmic framework for gaussianizing data distributions via averaging. We show that it is possible to efficiently construct data sketches that are nearly indistinguishable from sub-gaussian random designs.
  arXiv  Detail & Related papers  (2022-06-21T12:16:45Z)
• Bias-Free Scalable Gaussian Processes via Randomized Truncations [26.985324213848475]
  This paper analyzes two common techniques: early truncated conjugate gradients (CG) and random Fourier features (RFF) CG tends to underfit while RFF tends to overfit. We address these issues using randomized truncation estimators that eliminate bias in exchange for increased variance.
  arXiv  Detail & Related papers  (2021-02-12T18:54:10Z)
• Pathwise Conditioning of Gaussian Processes [72.61885354624604]
  Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations. This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector. We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
  arXiv  Detail & Related papers  (2020-11-08T17:09:37Z)
• 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)
• Efficiently Sampling Functions from Gaussian Process Posteriors [76.94808614373609]
  We propose an easy-to-use and general-purpose approach for fast posterior sampling. We demonstrate how decoupled sample paths accurately represent Gaussian process posteriors at a fraction of the usual cost.
  arXiv  Detail & Related papers  (2020-02-21T14:03:16Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems. We derive novel approximation guarantees for classical sketching methods and analyze the accuracy of parameter averaging for distributed sketches. We illustrate the performance of distributed sketches in a serverless computing platform with large scale experiments.
  arXiv  Detail & Related papers  (2020-02-16T08:35:48Z)
• 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.