論文の概要: Accelerating Fourier--Motzkin elimination: redundancy removal and the choice of variable elimination order

• arxiv url: http://arxiv.org/abs/2609.07960v1
• Date: Mon, 07 Sep 2026 20:39:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-11 19:59:04.15304
• Title: Accelerating Fourier--Motzkin elimination: redundancy removal and the choice of variable elimination order
• Title（参考訳）: 加速フーリエ--モツキン除去:冗長除去と可変除去順序の選択
• Abstract要約: Imbertの冗長性テストは線形プログラミングによる冗長性除去ではインターリーブできない。 また,Imbertテストで用いられる導出記録が各ステップ後に再起動された場合,この2つの手法を健全に組み合わせることができることを示す。 本稿では,変数の除去順序を選択するためのルールを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fourier-Motzkin elimination computes an inequality description of the projection of a polyhedron onto a subset of its coordinates by eliminating one variable at a time. It is used in several areas of optimisation and computer science, and it is a standard way of obtaining the entropic constraints of a causal structure, where the marginalisation over the latent variables produces such a projection. Its limitation is the growth of the intermediate systems of inequalities, which can be doubly exponential in the number of eliminated variables even though the projection itself grows only as a single exponential. In practice the computational overload of the method therefore depends on two choices: how the redundant inequalities are removed after each step, and the order in which the variables are eliminated. We consider both. We first show, by an explicit example, that Imbert's redundancy test cannot be interleaved with redundancy removal by linear programming. We show that the two methods, however, can be combined soundly if the derivation records used by Imbert's test are re-initialised after every step at which linear programming is used. We then propose a rule for choosing the elimination order of the variables that gives a significant computational advantage, however, at the cost of increased resource usage. We demonstrate this advantage on some random polytopes, where the rule reduces the running time by factors of between 6 and 25 compared with the same elimination under a fixed order. For entropic descriptions of causal structures, with more than 250 inequalities and more than 100 variables to eliminate, our rule keeps the number of inequalities handled at each step one to two orders of magnitude lower than a fixed order.
• Abstract（参考訳）: フーリエ・モツキン除去は、ポリヘドロンの座標部分集合への射影の不等式の記述を、一度に1つの変数を排除して計算する。 これは最適化と計算機科学のいくつかの分野で使われ、因果構造のエントロピー的制約を得る標準的な方法であり、潜伏変数の辺縁化はそのような射影を生成する。 その極限は不等式の中間系の成長であり、射影自体が単一の指数関数としてしか成長しないにもかかわらず、排除された変数の数で2倍指数関数的である。 実際には、メソッドの計算過負荷は、各ステップの後に冗長な不等式が除去される方法と、変数が除去される順序の2つの選択肢に依存する。 両方検討する。 まず,Imbertの冗長性テストは線形プログラミングによる冗長性除去とインターリーブできないことを示す。 しかし、Imbertテストで使用される導出レコードが線形プログラミングが使われるステップ毎に再起動された場合、この2つの手法が健全に結合可能であることを示す。 そこで我々は,資源使用量の増加を犠牲にして,計算上の優位性を示す変数の除去順序を選択するルールを提案する。 この利点はランダムなポリトープで示され、規則は6から25の係数でランニング時間を減少させる。 因果構造のエントロピー的記述では、250以上の不等式と100以上の変数を排除し、各ステップで処理される不等式数は、固定順序よりも1～2桁低い。

関連論文リスト

• Difference-of-Convex Regularization for Graph Learning by Differentiable Programming [1.9651461643699661]
  直接反転なしでラプラシアン擬似逆のスペクトル作用を近似する差分凸正規化器(DCR)グラフ学習フレームワークを提案する。 Laplacian-Regularized Non negative Least Squares (LR-NNLS) を二重表現で再構成することにより、DCRはインスタンス固有の推論から擬似逆学習を分離する。 DCRアルゴリズムの安定性と一意な固定点の存在を理論的に保証する。
  論文  参考訳（メタデータ） (2026-08-13T03:10:05Z)
• Stabilizing Extrapolation in Looped Transformers via Learned Stochastic Stopping [56.14767235650558]
  共有トランスブロックを繰り返し適用するLooped Transformerは、可変長の計算タスクに自然に適合するアーキテクチャである。 この差分を、列長とループ数の間の単純なアルゴリズムタスクにおける突発的相関に追従する。 私たちの研究は、"停止する時"は単なる推論時間割当ルールではなく、トレーニング設計の選択として扱われるべきであることを示唆しています。
  論文  参考訳（メタデータ） (2026-06-29T08:58:09Z)
• Analysis of Hessian Scaling for Local and Global Costs in Variational Quantum Algorithm [0.42970700836450487]
  変分量子アルゴリズムにおけるヘッセンのエントリーワイズ解の定量化を行う。 ショットノイズに対してヘッセン成分を解くのに必要なサンプルの複雑さを規定する2つの異なるスケーリング機構を示す。
  論文  参考訳（メタデータ） (2026-01-31T15:49:23Z)
• A Linear Combination of Unitaries Decomposition for the Laplace Operator [0.0]
  離散楕円微分作用素のクラスに対するユニタリ分解の新しい線形結合を提供する。 分解に必要なユニタリ項の数は、離散化に使用される格子点の数とは無関係である。 各ユニタリに対する明示的な回路構成が与えられ、その複雑さが解析される。
  論文  参考訳（メタデータ） (2026-01-10T00:54:39Z)
• Refined Risk Bounds for Unbounded Losses via Transductive Priors [67.12679195076387]
  線形回帰の逐次変分を2乗損失、ヒンジ損失の分類問題、ロジスティック回帰で再検討する。 我々の鍵となるツールは、慎重に選択された導出先を持つ指数重み付けアルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2024-10-29T00:01:04Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Efficient correlation-based discretization of continuous variables for annealing machines [0.6882042556551611]
  本稿では,連続変数の相関を用いた離散化手法を提案する。 提案手法は,予測精度を著しく低下させることなく,QUBOの定式化に必要なバイナリ変数数を削減できることを数値的に示す。
  論文  参考訳（メタデータ） (2023-01-18T01:04:03Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Supermodularity and valid inequalities for quadratic optimization with indicators [3.8073142980733]
  階数 1 の二次数の基底集合関数は線形時間で最小化できることを示す。 凸殻の明示的な形式は、元の空間変数と、円錐二次表現可能な不等式による拡張公式の両方で与えられる。 実験により、円錐二次形式における昇降超モジュラー不等式は、インジケータによる二次最適化の積分ギャップを低減するのに非常に効果的であることが示されている。
  論文  参考訳（メタデータ） (2020-12-29T07:03:09Z)
• Competitive Mirror Descent [67.31015611281225]
  制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。 本稿では, 競合ミラー降下法(CMD)を提案する。 特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
  論文  参考訳（メタデータ） (2020-06-17T22:11:35Z)

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

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