Range-Net: A High Precision Streaming SVD for Big Data Applications

• URL: http://arxiv.org/abs/2010.14226v6
• Date: Thu, 18 Mar 2021 18:46:17 GMT
• Title: Range-Net: A High Precision Streaming SVD for Big Data Applications
• Abstract summary: In a Big Data setting computing the dominant SVD factors is restrictive due to the main memory requirements. We present Range-Net as an alternative to randomized SVD that satisfies the tail-energy lower bound given by Eckart-Young-Mirsky (EYM) theorem.
• Score: 6.050462414301623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a Big Data setting computing the dominant SVD factors is restrictive due to the main memory requirements. Recently introduced streaming Randomized SVD schemes work under the restrictive assumption that the singular value spectrum of the data has exponential decay. This is seldom true for any practical data. Although these methods are claimed to be applicable to scientific computations due to associated tail-energy error bounds, the approximation errors in the singular vectors and values are high when the aforementioned assumption does not hold. Furthermore from a practical perspective, oversampling can still be memory intensive or worse can exceed the feature dimension of the data. To address these issues, we present Range-Net as an alternative to randomized SVD that satisfies the tail-energy lower bound given by Eckart-Young-Mirsky (EYM) theorem. Range-Net is a deterministic two-stage neural optimization approach with random initialization, where the main memory requirement depends explicitly on the feature dimension and desired rank, independent of the sample dimension. The data samples are read in a streaming setting with the network minimization problem converging to the desired rank-r approximation. Range-Net is fully interpretable where all the network outputs and weights have a specific meaning. We provide theoretical guarantees that Range-Net extracted SVD factors satisfy EYM tail-energy lower bound at machine precision. Our numerical experiments on real data at various scales confirms this bound. A comparison against the state of the art streaming Randomized SVD shows that Range-Net accuracy is better by six orders of magnitude while being memory efficient.

Related papers

• Determinant Estimation under Memory Constraints and Neural Scaling Laws [48.68885778257016]
  We derive a novel hierarchical algorithm for large-scale log-determinant calculation in memory-constrained settings. We show that the ratio of pseudo-determinants satisfies a power-law relationship, allowing us to derive corresponding scaling laws. This enables accurate estimation of NTK log-determinants from a tiny fraction of the full dataset.
  arXiv  Detail & Related papers  (2025-03-06T13:32:13Z)
• Winner-Take-All Column Row Sampling for Memory Efficient Adaptation of Language Model [89.8764435351222]
  We propose a new family of unbiased estimators called WTA-CRS, for matrix production with reduced variance. Our work provides both theoretical and experimental evidence that, in the context of tuning transformers, our proposed estimators exhibit lower variance compared to existing ones.
  arXiv  Detail & Related papers  (2023-05-24T15:52:08Z)
• On the Size and Approximation Error of Distilled Sets [57.61696480305911]
  We take a theoretical view on kernel ridge regression based methods of dataset distillation such as Kernel Inducing Points. We prove that a small set of instances exists in the original input space such that its solution in the RFF space coincides with the solution of the original data. A KRR solution can be generated using this distilled set of instances which gives an approximation towards the KRR solution optimized on the full input data.
  arXiv  Detail & Related papers  (2023-05-23T14:37:43Z)
• RENs: Relevance Encoding Networks [0.0]
  This paper proposes relevance encoding networks (RENs): a novel probabilistic VAE-based framework that uses the automatic relevance determination (ARD) prior in the latent space to learn the data-specific bottleneck dimensionality. We show that the proposed model learns the relevant latent bottleneck dimensionality without compromising the representation and generation quality of the samples.
  arXiv  Detail & Related papers  (2022-05-25T21:53:48Z)
• Meta Learning Low Rank Covariance Factors for Energy-Based Deterministic Uncertainty [58.144520501201995]
  Bi-Lipschitz regularization of neural network layers preserve relative distances between data instances in the feature spaces of each layer. With the use of an attentive set encoder, we propose to meta learn either diagonal or diagonal plus low-rank factors to efficiently construct task specific covariance matrices. We also propose an inference procedure which utilizes scaled energy to achieve a final predictive distribution.
  arXiv  Detail & Related papers  (2021-10-12T22:04:19Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  We study the prediction discriminability and diversity by studying the structure of the classification output matrix of a randomly selected data batch. We propose Batch Nuclear-norm Maximization and Minimization, which performs nuclear-norm on the target output matrix to enhance the target prediction ability. Experiments show that our method could boost the adaptation accuracy and robustness under three typical domain adaptation scenarios.
  arXiv  Detail & Related papers  (2021-07-13T15:08:32Z)
• Robust Implicit Networks via Non-Euclidean Contractions [63.91638306025768]
  Implicit neural networks show improved accuracy and significant reduction in memory consumption. They can suffer from ill-posedness and convergence instability. This paper provides a new framework to design well-posed and robust implicit neural networks.
  arXiv  Detail & Related papers  (2021-06-06T18:05:02Z)
• An improved LogNNet classifier for IoT application [0.0]
  This paper proposes a feed forward LogNNet neural network which uses a semi-linear Henon type discrete chaotic map to classify MNIST-10 dataset. It is shown that there exists a direct relation between the value of entropy and accuracy of the classification.
  arXiv  Detail & Related papers  (2021-05-30T02:12:45Z)
• Tail-Net: Extracting Lowest Singular Triplets for Big Data Applications [0.0]
  We extend the previously proposed Range-Net to textbfTail-Net for a memory and compute efficient extraction of lowest singular factors of a given big dataset and a specified rank-r. We present a number of numerical experiments on both synthetic and practical data-sets for verification and bench-marking.
  arXiv  Detail & Related papers  (2021-04-28T19:17:34Z)
• Fundamental Limits of Ridge-Regularized Empirical Risk Minimization in High Dimensions [41.7567932118769]
  Empirical Risk Minimization algorithms are widely used in a variety of estimation and prediction tasks. In this paper, we characterize for the first time the fundamental limits on the statistical accuracy of convex ERM for inference.
  arXiv  Detail & Related papers  (2020-06-16T04:27:38Z)

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.