論文の概要: Discovering Lattice Reduction Strategies via Self-Play

• arxiv url: http://arxiv.org/abs/2606.15301v1
• Date: Sat, 13 Jun 2026 13:48:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 16:21:33.261537
• Title: Discovering Lattice Reduction Strategies via Self-Play
• Title（参考訳）: セルフプレイによる格子低減戦略の発見
• Authors: Mohamed Malhou, Kristin Lauter, Ludovic Perret,
• Abstract要約: Lenstra-Lenstra-Lovsz (LLL) アルゴリズムは格子基底の低減に使用されるコンピュータ科学への基礎的な貢献である。 深層強化学習はLLLの原始的行動空間と相互作用することで,より優れた,一般化可能な縮小戦略を見出すことができることを示す。 格子削減を単一プレーヤ決定プロセス(MDP)として定式化し,AlphaZero方式の自己再生パイプラインを用いて深層残留ネットワークを訓練する。
• 参考スコア（独自算出の注目度）: 0.9722250595763385
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Lenstra-Lenstra-Lovász (LLL) algorithm is a seminal contribution to computer science used for lattice basis reduction, yet its polynomial-time outputs produce bases that are far from optimal as the dimension grows. We show that deep reinforcement learning can discover strictly superior, generalizable reduction strategies by interacting with the primitive action space of LLL. We formulate lattice reduction as a single-player Markov Decision Process (MDP) and train a deep residual network using an AlphaZero-style self-play pipeline augmented with adaptive-horizon MCTS (Monte Carlo Tree Search), which couples multi-step network predictions with an entropy-gated expansion mechanism. The resulting policy, DeltaStar, is trained exclusively on small $8$-dimensional $q$-ary lattices and requires fewer primitive row operations than LLL. Crucially, it generalizes zero-shot to unseen moduli and higher dimensions up to $n=32$ without retraining.
• Abstract（参考訳）: Lenstra-Lenstra-Lovász (LLL) アルゴリズムは格子基底の減少に使用されるコンピュータ科学への基礎的な貢献であるが、その多項式時間出力は次元が大きくなるにつれて最適ではない基底を生成する。 深層強化学習はLLLの原始的行動空間と相互作用することで,より優れた,一般化可能な縮小戦略を見出すことができることを示す。 適応水平MCTS(Monte Carlo Tree Search)を付加したAlphaZeroスタイルの自己再生パイプラインを用いて,マルチステップネットワーク予測とエントロピーゲート拡張機構を併用した,単一プレーヤのマルコフ決定プロセス(MDP)として格子縮小を定式化し,深層残留ネットワークを訓練する。 DeltaStarは、わずか8$の$q$-ary格子でのみ訓練されており、LLLよりもプリミティブな行演算を必要としない。 重要なことに、ゼロショットを非可視なモジュライに一般化し、再トレーニングなしで最大$n=32$まで高次元にすることができる。

関連論文リスト

• Hierarchical Zero-Order Optimization for Deep Neural Networks [33.991611257471114]
  本稿では,ネットワークの深さ次元を分解する新たな分割・対数戦略である階層零次最適化(HZO)を提案する。 我々はHZOがクエリの複雑さを$O(ML2)$から$O(ML log L)$に減らすことを証明した。
  論文  参考訳（メタデータ） (2026-02-11T07:56:07Z)
• LESA: Learnable LLM Layer Scaling-Up [57.0510934286449]
  LLM(Large Language Models)をスクラッチからトレーニングするには膨大な計算資源が必要であるため、非常に高価である。 モデルスケーリングアップは、より小さなモデルのパラメータを活用してより大きなモデルを作成することで、有望なソリューションを提供する。 深度スケールアップのための新しい学習方法である textbfLESA を提案する。
  論文  参考訳（メタデータ） (2025-02-19T14:58:48Z)
• ReFill: Reinforcement Learning for Fill-In Minimization [3.9134031118910264]
  補充の最小化はNPハードであり、既存の最小化(Minimum Degree)やNested Dissection(Nested Dissection)は適応性に制限を与える。 我々は,グラフニューラルネットワーク(GNN)によって強化された強化学習フレームワークであるtextitReFillを導入し,補充のための適応順序付け戦略を学習する。
  論文  参考訳（メタデータ） (2025-01-27T15:20:41Z)
• A Unified Algebraic Perspective on Lipschitz Neural Networks [88.14073994459586]
  本稿では,様々なタイプの1-Lipschitzニューラルネットワークを統一する新しい視点を提案する。 そこで本研究では,SDP(Common semidefinite Programming)条件の解析解を求めることによって,既存の多くの手法を導出し,一般化することができることを示す。 SDPベースのLipschitz Layers (SLL) と呼ばれる我々のアプローチは、非自明で効率的な凸ポテンシャル層の一般化を設計できる。
  論文  参考訳（メタデータ） (2023-03-06T14:31:09Z)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• A Parallelizable Lattice Rescoring Strategy with Neural Language Models [62.20538383769179]
  自動音声認識のためのニューラルネットワークモデル(LM)を用いた効率的な格子相関のための後部格子拡張アルゴリズムを提案する。 スイッチボードデータセットにおける実験により,提案手法が同等の認識性能を得た。 PyTorchで訓練されたニューラル LM をKaldi との格子再構成に簡単に統合することで、並列再描画法により柔軟性が向上する。
  論文  参考訳（メタデータ） (2021-03-08T21:23:12Z)
• Model-based Reinforcement Learning for Continuous Control with Posterior Sampling [10.91557009257615]
  連続状態空間における強化学習(PSRL)のためのモデルベース後方サンプリングについて検討した。 MPC-PSRLはモデルに基づく後部サンプリングアルゴリズムであり,行動選択のためのモデル予測制御を行う。
  論文  参考訳（メタデータ） (2020-11-20T21:00:31Z)
• Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
  本稿では,割引決定(MDP)のための強化学習について検討する。 本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。 以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-23T17:08:54Z)

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

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