論文の概要: When Do Learned Diffusion Proposals Help Constraint Solving? A Controlled Study on Continuous Algebraic Systems

• arxiv url: http://arxiv.org/abs/2607.27169v1
• Date: Wed, 29 Jul 2026 17:44:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-30 21:06:25.76618
• Title: When Do Learned Diffusion Proposals Help Constraint Solving? A Controlled Study on Continuous Algebraic Systems
• Title（参考訳）: 学習拡散の提案はいつ解決に役立ったか? 連続代数系に関する制御された研究
• Authors: Quang Bui, Sparsh Roy, Akash Gundimeda, Davin Yin,
• Abstract要約: 確率 1 - (1 - q(n))K で、q(n) は単発到達可能である。 学習した提案が解決者を改善する体制をマッピングする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving a continuous algebraic constraint system requires two decisions: which values satisfy the constraints, and which structural augmentation renders an unsolvable system solvable. Classical solvers answer the first well and the second only by enumeration. On that discrete decision, a candidate-conditioned repair ranker choosing among K augmentations reaches the exhaustive-search ceiling at a fraction of the calls, outperforming random (0.997 vs 0.236 balanced nonlinear menu accuracy; p < 10^-70; 0.982 +/- 0.006 across seeds) and beating a budget-matched per-candidate probe on accuracy and cost. MARC turns such a system into a factor graph, over which a graph-neural diffusion denoiser proposes assignments, descent on an exact computer-algebra energy polishes them, and an exact symbolic checker certifies solutions. Evaluations of diffusion-based proposals rarely include one control: random multi-start under the same refinement budget. Applied to our system, it sharply curtails what the learned proposal contributes on the value decision. Does it beat random multi-start at choosing satisfying assignments? Only narrowly, in a predictable regime. Across trapped low-dimensional families it ties with random restart, but dominates in high dimension, where random search fails. Once variables couple, the advantage is gone. Since all methods share one polish and one checker, best-of-K random multi-start succeeds with probability exactly 1 - (1 - q(n))^K, where q(n) is single-start reachability; one measured constant, with no free parameters, reproduces the entire curve (mean absolute error 0.012). The favorable regime is not specific to our synthetic families: across eight real-world systems in robotics, positioning, optimization, and algebra, classical multi-start solved all eight, none in the learning-favorable regime. We map the regimes in which learned proposals improve solvers.
• Abstract（参考訳）: 連続代数的制約系を解くには、どの値が制約を満たすか、どの構造的拡張が解けないシステムを解けるかという2つの決定が必要である。 古典的な解法は、列挙によってのみ第1の井戸と第2の井戸に答える。 この離散的な決定では、Kオーグメンテーションの中から選択された候補条件の補修ランクが、ランダム(0.997 vs 0.236のバランスの取れた非線形メニュー精度、p < 10^-70; 0.982 +/- 0.006)を上回り、精度とコストで予算整合された候補毎のプローブを打ち負かした。 MARCはそのようなシステムを因子グラフに変換し、グラフ-神経拡散デノイザが割り当てを提案し、コンピュータ-代数エネルギーの降下によってそれらが洗練され、正確な記号チェッカーが解を認証する。 拡散に基づく提案の評価には、1つの制御が含まれることはめったにない。 私たちのシステムに適用すると、学習した提案が価値決定にどのような貢献をするのかを、徹底的に計算します。 満足度の高い課題を選択することで、ランダムなマルチスタートを達成できるだろうか? 厳密に言えば、予測可能な体制です。 低次元のファミリー全体はランダムに再起動するが、ランダム検索が失敗する高次元で支配される。 一度変数が結合すると、利点はなくなる。 すべてのメソッドが1つの研磨と1つのチェッカーを共有するため、K のランダムなマルチスタートは確率 1 - (1 - q(n))^K で成功する。 ロボット工学、位置決め、最適化、代数の8つの現実世界のシステムにおいて、古典的なマルチスタートは8つすべて解決した。 学習した提案が解決者を改善する体制をマッピングする。

関連論文リスト

• Quantile-Optimal Policy Learning under Unmeasured Confounding [55.72891849926314]
  ここでは,報酬分布が (0, 1) で最大$alpha$-quantileを持つポリシーを見つけることを目標とする量子最適政策学習について検討する。 このような問題は、(i)報酬分布の関数としての量子目標の非線形性、(ii)未観測の共起問題、(iii)オフラインデータセットのカバー不足という3つの大きな課題に悩まされている。
  論文  参考訳（メタデータ） (2025-06-08T13:37:38Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Semi-Bandit Learning for Monotone Stochastic Optimization [16.921694787482213]
  一般的なオンライン学習アルゴリズムは「モノトーン」問題のクラスのために開発されている。 当社のフレームワークは,預言不平等やPandoraのボックス,単一リソースの収益管理,ポスト価格など,いくつかの基本的な問題に適用しています。
  論文  参考訳（メタデータ） (2023-12-24T07:46:37Z)
• Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
  オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。 我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
  論文  参考訳（メタデータ） (2023-10-03T17:51:42Z)
• 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)
• Autoregressive Bandits [58.46584210388307]
  本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。 報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。 次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
  論文  参考訳（メタデータ） (2022-12-12T21:37:36Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
  有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。 意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。 この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
  論文  参考訳（メタデータ） (2020-12-13T04:47:37Z)

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

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