論文の概要: Automated Proof of Polynomial Inequalities via Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2503.06592v1
- Date: Sun, 09 Mar 2025 12:50:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-11 15:45:30.841549
- Title: Automated Proof of Polynomial Inequalities via Reinforcement Learning
- Title（参考訳）: 強化学習による多項式不等式の自動証明
- Authors: Banglong Liu, Niuniu Qi, Xia Zeng, Lydia Dehbi, Zhengfeng Yang,
- Abstract要約: 本稿では,強化学習に基づく不等式証明のためのKrivine-Basis表現の探索手法を提案する。
APPIRL(Reinforcementによる多項式不等式の自動証明)というツールも実装している。
- 参考スコア（独自算出の注目度）: 4.246350085706678
- License:
- Abstract: Polynomial inequality proving is fundamental to many mathematical disciplines and finds wide applications in diverse fields. Current traditional algebraic methods are based on searching for a polynomial positive definite representation over a set of basis. However, these methods are limited by truncation degree. To address this issue, this paper proposes an approach based on reinforcement learning to find a {Krivine-basis} representation for proving polynomial inequalities. Specifically, we formulate the inequality proving problem as a linear programming (LP) problem and encode it as a basis selection problem using reinforcement learning (RL), achieving a non-negative {Krivine basis}. Moreover, a fast multivariate polynomial multiplication method based on Fast Fourier Transform (FFT) is employed to enhance the efficiency of action space search. Furthermore, we have implemented a tool called {APPIRL} (Automated Proof of Polynomial Inequalities via Reinforcement Learning). Experimental evaluation on benchmark problems demonstrates the feasibility and effectiveness of our approach. In addition, {APPIRL} has been successfully applied to solve the maximum stable set problem.
- Abstract（参考訳）: 多項式不等式証明は多くの数学の分野に基本的であり、様々な分野の幅広い応用を見出す。
現在の伝統的な代数的手法は、基底の集合上の多項式正定表現の探索に基づいている。
しかし、これらの方法はトラルニケート度によって制限される。
そこで本研究では,多項式の不等式を証明するために,強化学習に基づくKrivine-Basis表現の探索手法を提案する。
具体的には、線形プログラミング(LP)問題として不等式証明問題を定式化し、強化学習(RL)を用いてベース選択問題として符号化し、非負の {Krivine ベース} を達成する。
さらに,Fast Fourier Transform (FFT) に基づく高速多変量多項式乗算法を用いて,行動空間探索の効率化を図る。
さらに,強化学習による多項不等式の自動証明(APPIRL)というツールを実装した。
ベンチマーク問題に対する実験的評価は,本手法の有効性と有効性を示すものである。
さらに、AppIRL} は最大安定セット問題の解法としてうまく適用されている。
関連論文リスト
- Quantified Linear and Polynomial Arithmetic Satisfiability via Template-based Skolemization [4.2518927441106]
既存の手法の主なボトルネックは計算コストのかかる定量化器の除去ステップである。
テンプレートに基づく Skolemization 手法を提案し,線形/ポリノミカルな Skolem 関数を自動的に合成し,式中の量化子を除去する。
提案手法は, 高性能な実用性能と相まって, 魅力的な理論特性を提供する。
論文 参考訳（メタデータ） (2024-12-18T14:37:15Z) - A practical, fast method for solving sum-of-squares problems for very large polynomials [10.645318208507213]
正方形最適化(SOS:Sum of squares)は、 as の正則性を強制しなければならない問題を解くための強力な手法である。
私たちのゴールは、現在より大きく、より複雑な問題に対処できるアプローチを考案することにあります。
論文 参考訳（メタデータ） (2024-10-21T12:47:42Z) - Complementary polynomials in quantum signal processing [0.0]
与えられた$P$を実装するには、まず対応する補完的な$Q$を構築しなければならない。
この問題に対する既存のアプローチでは、明示的な誤り解析には適さない数値的手法が採用されている。
複素解析を用いた補体系に対する新しいアプローチを提案する。
論文 参考訳（メタデータ） (2024-06-06T16:47:11Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
逆法に(双対の形で)方法から単純かつ直接的に還元する。
これは、双対形式におけるどんな下界も、特定の形式の逆下界であることを示している。
論文 参考訳（メタデータ） (2023-01-24T21:37:20Z) - Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix [17.31412310131552]
いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。
コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
論文 参考訳（メタデータ） (2023-01-16T14:25:19Z) - Blind Polynomial Regression [28.35687689204994]
我々は(潜在的に部分的な)ブラインド回帰問題を述べ、その理論的性質の一部をレンダリングし、それを解決するアルゴリズム的アプローチを提案する。
ケーススタディとして,ジッタ補正問題に適用し,その性能を相関させる。
論文 参考訳（メタデータ） (2022-10-21T10:54:35Z) - SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum
Cocoercive Variational Inequalities [137.6408511310322]
有限サムコヒーレンシブ変分不等式の問題を考える。
強い単調な問題に対しては、この方法を用いて解への線形収束を達成することができる。
論文 参考訳（メタデータ） (2022-10-12T08:04:48Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-08-22T16:00:45Z) - Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。
大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。
応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
論文 参考訳（メタデータ） (2020-08-05T17:52:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。