Learning selection strategies in Buchberger's algorithm
- URL: http://arxiv.org/abs/2005.01917v3
- Date: Mon, 17 Aug 2020 22:01:54 GMT
- Title: Learning selection strategies in Buchberger's algorithm
- Authors: Dylan Peifer, Michael Stillman, Daniel Halpern-Leistner
- Abstract summary: 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.
- Score: 3.4376560669160394
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Studying the set of exact solutions of a system of polynomial equations
largely depends on a single iterative algorithm, known as Buchberger's
algorithm. Optimized versions of this algorithm are crucial for many computer
algebra systems (e.g., Mathematica, Maple, Sage). We introduce a new approach
to Buchberger's algorithm that uses reinforcement learning agents to perform
S-pair selection, a key step in the algorithm. We then study how the difficulty
of the problem depends on the choices of domain and distribution of
polynomials, about which little is known. Finally, we train a policy model
using proximal policy optimization (PPO) to learn S-pair selection strategies
for random systems of binomial equations. In certain domains, the trained model
outperforms state-of-the-art selection heuristics in total number of polynomial
additions performed, which provides a proof-of-concept that recent developments
in machine learning have the potential to improve performance of algorithms in
symbolic computation.
Related papers
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms.
Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability.
We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
arXiv Detail & Related papers (2023-07-17T20:11:56Z) - Learning the Markov Decision Process in the Sparse Gaussian Elimination [0.0]
We propose a learning-based approach for the sparse Gaussian Elimination.
We proposed some Q-Learning algorithms for the main modules of sparse solver.
arXiv Detail & Related papers (2021-09-30T08:56:39Z) - Algorithm Selection on a Meta Level [58.720142291102135]
We introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors.
We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework.
arXiv Detail & Related papers (2021-07-20T11:23:21Z) - Learning a performance metric of Buchberger's algorithm [2.1485350418225244]
We try to predict, using just the starting input, the number of additions that take place during one of Buchberger's algorithm runs.
Our work serves as a proof of concept, demonstrating that predicting the number of additions in Buchberger's algorithm is a problem from the point of machine learning.
arXiv Detail & Related papers (2021-06-07T14:57:57Z) - Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient
adaptive algorithms for neural networks [0.0]
We present a new class of Langevin based algorithms, which overcomes many of the known shortcomings of popular adaptive vanishing algorithms.
In particular, we provide a nonasymptotic analysis and full theoretical guarantees for the convergence properties of an algorithm of this novel class, which we named TH$varepsilon$O POULA (or, simply, TheoPouLa)
arXiv Detail & Related papers (2021-05-28T15:58:48Z) - Safe Learning and Optimization Techniques: Towards a Survey of the State
of the Art [3.6954802719347413]
Safe learning and optimization deals with learning and optimization problems that avoid, as much as possible, the evaluation of non-safe input points.
A comprehensive survey of safe reinforcement learning algorithms was published in 2015, but related works in active learning and in optimization were not considered.
This paper reviews those algorithms from a number of domains including reinforcement learning, Gaussian process regression and classification, evolutionary algorithms, and active learning.
arXiv Detail & Related papers (2021-01-23T13:58:09Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
We propose a method for meta-learning reinforcement learning algorithms.
The learned algorithms are domain-agnostic and can generalize to new environments not seen during training.
We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
arXiv Detail & Related papers (2021-01-08T18:55:07Z) - Model-free optimal control of discrete-time systems with additive and
multiplicative noises [1.656520517245166]
This paper investigates the optimal control problem for a class of discrete-time systems subject to additive and multiplicative noises.
A modelfree reinforcement learning algorithm is proposed to learn the optimal admissible control policy using the data of the system states and inputs.
It is proven that the learning algorithm converges to the optimal admissible control policy.
arXiv Detail & Related papers (2020-08-20T02:18:00Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
We develop a meta-algorithm that selects between base algorithms.
We show through a lower bound that even when one of the base algorithms has $O(sqrtT)$ regret, in general it is impossible to get better than $Omega(sqrtT)$ regret.
arXiv Detail & Related papers (2020-03-03T18:46:34Z) - 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) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms.
We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
arXiv Detail & Related papers (2020-01-29T09:40:58Z)
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.