Accelerating Matrix Diagonalization through Decision Transformers with Epsilon-Greedy Optimization

• URL: http://arxiv.org/abs/2406.16191v1
• Date: Sun, 23 Jun 2024 18:56:46 GMT
• Title: Accelerating Matrix Diagonalization through Decision Transformers with Epsilon-Greedy Optimization
• Authors: Kshitij Bhatta, Geigh Zollicoffer, Manish Bhattarai, Phil Romero, Christian F. A. Negre, Anders M. N. Niklasson, Adetokunbo Adedoyin,
• Abstract summary: This paper recasts matrix diagonalization as a sequential decision-making problem and applies the power of Decision Transformers (DTs) Our approach determines optimal pivot selection during diagonalization with the Jacobi algorithm, leading to significant speedups compared to the traditional max-element Jacobi method.
• Score: 1.0051474951635875
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a novel framework for matrix diagonalization, recasting it as a sequential decision-making problem and applying the power of Decision Transformers (DTs). Our approach determines optimal pivot selection during diagonalization with the Jacobi algorithm, leading to significant speedups compared to the traditional max-element Jacobi method. To bolster robustness, we integrate an epsilon-greedy strategy, enabling success in scenarios where deterministic approaches fail. This work demonstrates the effectiveness of DTs in complex computational tasks and highlights the potential of reimagining mathematical operations through a machine learning lens. Furthermore, we establish the generalizability of our method by using transfer learning to diagonalize matrices of smaller sizes than those trained.

Related papers

• Efficient Adaptation of Pre-trained Vision Transformer via Householder Transformation [53.88562288388169]
  A common strategy for. Efficient Fine-Tuning (PEFT) of pre-trained Vision Transformers (ViTs) involves adapting the model to downstream tasks. We propose a novel PEFT approach inspired by Singular Value Decomposition (SVD) for representing the adaptation matrix. SVD decomposes a matrix into the product of a left unitary matrix, a diagonal matrix of scaling values, and a right unitary matrix.
  arXiv  Detail & Related papers  (2024-10-30T12:08:30Z)
• Towards Faster Matrix Diagonalization with Graph Isomorphism Networks and the AlphaZero Framework [1.0051474951635875]
  We introduce innovative approaches for accelerating the Jacobi method for matrix diagonalization. We examine the potential of utilizing scalable architecture between different-sized matrices.
  arXiv  Detail & Related papers  (2024-06-30T17:45:01Z)
• Regularized Projection Matrix Approximation with Applications to Community Detection [1.3761665705201904]
  This paper introduces a regularized projection matrix approximation framework designed to recover cluster information from the affinity matrix. We investigate three distinct penalty functions, each specifically tailored to address bounded, positive, and sparse scenarios. Numerical experiments conducted on both synthetic and real-world datasets reveal that our regularized projection matrix approximation approach significantly outperforms state-of-the-art methods in clustering performance.
  arXiv  Detail & Related papers  (2024-05-26T15:18:22Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Matrix Diagonalization as a Board Game: Teaching an Eigensolver the Fastest Path to Solution [2.239917051803692]
  Matrix diagonalization is at the cornerstone of numerous fields of scientific computing. We show how reinforcement learning, using the AlphaZero framework, can accelerate Jacobi matrix diagonalizations. Our findings highlight the opportunity to use machine learning as a promising tool to improve the performance of numerical linear algebra.
  arXiv  Detail & Related papers  (2023-06-16T03:31:58Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  Current algorithms are designed using the block coordinate descent method or the proximal point algorithm. We propose a novel algorithm based on the two-metric projection method, incorporating a carefully designed search direction and variable partitioning scheme. Experimental results on synthetic and real-world datasets demonstrate that our proposed algorithm provides a significant improvement in computational efficiency compared to the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-12-03T14:39:10Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations. We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
  arXiv  Detail & Related papers  (2021-10-13T19:36:50Z)
• OASIS: An Active Framework for Set Inversion [4.014524824655106]
  We introduce a novel method for solving the set inversion problem by formulating it as a binary classification problem. We focus on active learning, a family of new and powerful techniques which can achieve the same level of accuracy with fewer data points compared to traditional learning methods.
  arXiv  Detail & Related papers  (2021-05-31T15:04:43Z)
• Adversarially-Trained Nonnegative Matrix Factorization [77.34726150561087]
  We consider an adversarially-trained version of the nonnegative matrix factorization. In our formulation, an attacker adds an arbitrary matrix of bounded norm to the given data matrix. We design efficient algorithms inspired by adversarial training to optimize for dictionary and coefficient matrices.
  arXiv  Detail & Related papers  (2021-04-10T13:13:17Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  Bilevel optimization is a tool for many machine learning problems. We propose a novel stoc-efficientgradient estimator named stoc-BiO.
  arXiv  Detail & Related papers  (2020-10-15T18:09:48Z)
• 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)

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.