論文の概要: MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search

• arxiv url: http://arxiv.org/abs/2507.03833v1
• Date: Fri, 04 Jul 2025 22:57:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-08 15:46:34.893352
• Title: MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search
• Title（参考訳）: MatRL:モンテカルロ木探索によるおそらく一般化可能な反復アルゴリズム発見
• Authors: Sungyoon Kim, Rajat Vadiraj Dwaraknath, Longling geng, Mert Pilanci,
• Abstract要約: MatRLは、行列関数を計算するための反復アルゴリズムを自動的に発見する強化学習フレームワークである。 そこで本研究では,MateRLが文献の様々なベースラインを上回るアルゴリズムを生成することを示す。
• 参考スコア（独自算出の注目度）: 37.24058519921229
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Iterative methods for computing matrix functions have been extensively studied and their convergence speed can be significantly improved with the right tuning of parameters and by mixing different iteration types. Handtuning the design options for optimal performance can be cumbersome, especially in modern computing environments: numerous different classical iterations and their variants exist, each with non-trivial per-step cost and tuning parameters. To this end, we propose MatRL -- a reinforcement learning based framework that automatically discovers iterative algorithms for computing matrix functions. The key idea is to treat algorithm design as a sequential decision-making process. Monte-Carlo tree search is then used to plan a hybrid sequence of matrix iterations and step sizes, tailored to a specific input matrix distribution and computing environment. Moreover, we also show that the learned algorithms provably generalize to sufficiently large matrices drawn from the same distribution. Finally, we corroborate our theoretical results with numerical experiments demonstrating that MatRL produces algorithms that outperform various baselines in the literature.
• Abstract（参考訳）: 行列関数の反復的計算法は広く研究されており、それらの収束速度はパラメータの正しいチューニングと異なる反復型を混合することにより著しく改善することができる。 最適なパフォーマンスのために設計オプションを手動で調整するのは、特に現代のコンピューティング環境では厄介なことだ: 様々な古典的なイテレーションとその変種が存在し、それぞれが非自明なステップ毎のコストとチューニングパラメータを持つ。 そこで本稿では,行列関数の反復アルゴリズムを自動的に検出する強化学習ベースのフレームワークであるMatRLを提案する。 鍵となる考え方は、アルゴリズム設計をシーケンシャルな意思決定プロセスとして扱うことである。 モンテカルロ木探索は、特定の入力行列分布と計算環境に合わせて、行列の反復とステップサイズのハイブリッド列を計画するために使用される。 さらに, 学習アルゴリズムは, 同じ分布から引き出された十分大きな行列に対して, 十分に一般化可能であることを示す。 最後に、MateRLが文学における様々な基礎を上回るアルゴリズムを生成することを示す数値実験で、理論的結果と相関する。

関連論文リスト

• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。 標準的な暗号仮定の下では、既存のアルゴリズムよりも決定的に高速なアルゴリズムを設計できることを示す。
  論文  参考訳（メタデータ） (2025-02-18T17:08:59Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Learning distributed representations with efficient SoftMax normalization [3.8673630752805437]
  有界ノルムを持つ埋め込みベクトルに対して$rm SoftMax(XYT)$の正規化定数を計算する線形時間近似を提案する。 本稿では,提案手法が競合手法よりも高い精度あるいは同等の精度を達成できるような事前学習した埋め込みデータセットについて述べる。 提案アルゴリズムは解釈可能で,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms [9.245687221460654]
  単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。 我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。 そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-01-17T14:53:52Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)
• Denise: Deep Robust Principal Component Analysis for Positive Semidefinite Matrices [8.1371986647556]
  Deniseは、共分散行列の堅牢なPCAのためのディープラーニングベースのアルゴリズムである。 実験により、デニスは分解品質の点で最先端の性能と一致していることが示された。
  論文  参考訳（メタデータ） (2020-04-28T15:45:21Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。