Learning a performance metric of Buchberger's algorithm
- URL: http://arxiv.org/abs/2106.03676v1
- Date: Mon, 7 Jun 2021 14:57:57 GMT
- Title: Learning a performance metric of Buchberger's algorithm
- Authors: Jelena Mojsilovi\'c, Dylan Peifer, Sonja Petrovi\'c
- Abstract summary: 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.
- Score: 2.1485350418225244
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: What can be (machine) learned about the complexity of Buchberger's algorithm?
Given a system of polynomials, Buchberger's algorithm computes a Gr\"obner
basis of the ideal these polynomials generate using an iterative procedure
based on multivariate long division. The runtime of each step of the algorithm
is typically dominated by a series of polynomial additions, and the total
number of these additions is a hardware independent performance metric that is
often used to evaluate and optimize various implementation choices. In this
work we attempt to predict, using just the starting input, the number of
polynomial additions that take place during one run of Buchberger's algorithm.
Good predictions are useful for quickly estimating difficulty and understanding
what features make Gr\"obner basis computation hard. Our features and methods
could also be used for value models in the reinforcement learning approach to
optimize Buchberger's algorithm introduced in [Peifer, Stillman, and
Halpern-Leistner, 2020].
We show that a multiple linear regression model built from a set of
easy-to-compute ideal generator statistics can predict the number of polynomial
additions somewhat well, better than an uninformed model, and better than
regression models built on some intuitive commutative algebra invariants that
are more difficult to compute. We also train a simple recursive neural network
that outperforms these linear models. Our work serves as a proof of concept,
demonstrating that predicting the number of polynomial additions in
Buchberger's algorithm is a feasible problem from the point of view of machine
learning.
Related papers
- A Simple Solution for Homomorphic Evaluation on Large Intervals [0.0]
Homomorphic encryption (HE) is a promising technique used for privacy-preserving computation.
Homomorphic evaluation of approximations for non-polynomial functions plays an important role in privacy-preserving machine learning.
We introduce a simple solution to approximating any functions, which might be overmissed by researchers.
arXiv Detail & Related papers (2024-05-24T04:13:22Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks.
The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions.
We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
arXiv Detail & Related papers (2023-09-30T15:57:14Z) - Exploring and Learning in Sparse Linear MDPs without Computationally
Intractable Oracles [39.10180309328293]
In this paper we revisit linear MDPs from the perspective of feature selection.
Our main result is the first-time algorithm for this problem.
We show that they do exist and can be computed efficiently via convex programming.
arXiv Detail & Related papers (2023-09-18T03:35:48Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Exponential Hardness of Reinforcement Learning with Linear Function
Approximation [20.066210529358177]
We show a computational lower bound, which is exponential in feature and horizon, for linear reinforcement learning under the Exponential Time Hypothesis.
We also show a lower bound optimized for horizon dependence that almost matches the best known upper bound of $exp(sqrtH)$.
arXiv Detail & Related papers (2023-02-25T00:19:49Z) - What learning algorithm is in-context learning? Investigations with
linear models [87.91612418166464]
We investigate the hypothesis that transformer-based in-context learners implement standard learning algorithms implicitly.
We show that trained in-context learners closely match the predictors computed by gradient descent, ridge regression, and exact least-squares regression.
Preliminary evidence that in-context learners share algorithmic features with these predictors.
arXiv Detail & Related papers (2022-11-28T18:59:51Z) - Structure learning in polynomial time: Greedy algorithms, Bregman
information, and exponential families [12.936601424755944]
We study a general greedy score-based algorithm for learning DAGs.
We show how recent algorithm-time algorithms for learning DAG models are a special case of this algorithm.
This observation suggests new score functions and optimality conditions based on the duality between Bregman divergences and exponential families.
arXiv Detail & Related papers (2021-10-10T06:37:51Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression.
We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
arXiv Detail & Related papers (2020-11-09T01:13:07Z) - 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) - The data-driven physical-based equations discovery using evolutionary
approach [77.34726150561087]
We describe the algorithm for the mathematical equations discovery from the given observations data.
The algorithm combines genetic programming with the sparse regression.
It could be used for governing analytical equation discovery as well as for partial differential equations (PDE) discovery.
arXiv Detail & Related papers (2020-04-03T17:21:57Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates.
The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature.
It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
arXiv Detail & Related papers (2020-02-20T10:50: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.