Learning the Markov Decision Process in the Sparse Gaussian Elimination

• URL: http://arxiv.org/abs/2109.14929v1
• Date: Thu, 30 Sep 2021 08:56:39 GMT
• Title: Learning the Markov Decision Process in the Sparse Gaussian Elimination
• Authors: Yingshi Chen
• Abstract summary: We propose a learning-based approach for the sparse Gaussian Elimination. We proposed some Q-Learning algorithms for the main modules of sparse solver.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a learning-based approach for the sparse Gaussian Elimination. There are many hard combinatorial optimization problems in modern sparse solver. These NP-hard problems could be handled in the framework of Markov Decision Process, especially the Q-Learning technique. We proposed some Q-Learning algorithms for the main modules of sparse solver: minimum degree ordering, task scheduling and adaptive pivoting. Finally, we recast the sparse solver into the framework of Q-Learning. Our study is the first step to connect these two classical mathematical models: Gaussian Elimination and Markov Decision Process. Our learning-based algorithm could help improve the performance of sparse solver, which has been verified in some numerical experiments.

Related papers

• Learning to Optimize for Mixed-Integer Non-linear Programming [20.469394148261838]
  Mixed-integer non-NLP programs (MINLPs) arise in various domains, such as energy systems and transportation, but are notoriously difficult to solve. Recent advances in machine learning have led to remarkable successes in optimization, area broadly known as learning to optimize. We propose two differentiable correction layers that generate integer outputs while preserving gradient.
  arXiv  Detail & Related papers  (2024-10-14T20:14:39Z)
• Deep Learning Methods for S Shaped Utility Maximisation with a Random Reference Point [0.0]
  We develop several numerical methods for solving the problem using deep learning and duality methods. We use deep learning methods to solve the associated Hamilton-Jacobi-Bellman equation for both the primal and dual problems. We compare the solution of this non-concave problem to that of concavified utility, a random function depending on the benchmark, in both complete and incomplete markets.
  arXiv  Detail & Related papers  (2024-10-07T22:07:59Z)
• Two-Step Q-Learning [0.0]
  The paper proposes a novel off-policy two-step Q-learning algorithm, without importance sampling. Numerical experiments demonstrate the superior performance of both the two-step Q-learning and its smooth variants.
  arXiv  Detail & Related papers  (2024-07-02T15:39:00Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• QBoost for regression problems: solving partial differential equations [0.0]
  The hybrid algorithm is capable of finding a solution to a partial differential equation with good precision and favorable scaling in the required number of qubits. The classical part is composed by training several regressors, capable of solving a partial differential equation using machine learning. The quantum part consists of adapting the QBoost algorithm to solve regression problems.
  arXiv  Detail & Related papers  (2021-08-30T16:13:04Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes [53.72166325215299]
  We study minimax optimal reinforcement learning in episodic factored Markov decision processes (FMDPs) First one achieves minimax optimal regret guarantees for a rich class of factored structures. Second one enjoys better computational complexity with a slightly worse regret.
  arXiv  Detail & Related papers  (2020-06-24T00:50:17Z)
• Learning selection strategies in Buchberger's algorithm [3.4376560669160394]
  We introduce a new approach to Buchberger's algorithm that uses reinforcement learning agents to perform S-pair selection. We then study how the difficulty of the problem depends on the choices of domain and distribution of S-pairs. We train a policy model using policy optimization (PPO) to learn S-pair selection strategies for random systems of proximal binomial equations.
  arXiv  Detail & Related papers  (2020-05-05T02:27:00Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  We propose an efficient and differentiable solver for general linear programming problems. We show the use of our solver in a video segmentation task and meta-learning for few-shot learning.
  arXiv  Detail & Related papers  (2020-04-30T01:50:37Z)
• 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)

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.