論文の概要: Two-dimensional Parallel Tempering for Constrained Optimization

• arxiv url: http://arxiv.org/abs/2506.14781v1
• Date: Sat, 24 May 2025 20:41:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-22 23:32:14.667389
• Title: Two-dimensional Parallel Tempering for Constrained Optimization
• Title（参考訳）: 制約付き最適化のための2次元並列テンパリング
• Authors: Corentin Delacour, M Mahmudul Hasan Sajeeb, Joao P. Hespanha, Kerem Y. Camsari,
• Abstract要約: パワーパラレルテンパリングアルゴリズム(PT)の2次元拡張を導入する。 結果として得られる2次元並列テンパリングアルゴリズム(2D-PT)は、厳密な制約のあるレプリカの混合を改善する。 この方法は制約付きIsing問題に広く適用され、既存のIsingマシンにデプロイできる。
• 参考スコア（独自算出の注目度）: 0.3068068202044424
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sampling Boltzmann probability distributions plays a key role in machine learning and optimization, motivating the design of hardware accelerators such as Ising machines. While the Ising model can in principle encode arbitrary optimization problems, practical implementations are often hindered by soft constraints that either slow down mixing when too strong, or fail to enforce feasibility when too weak. We introduce a two-dimensional extension of the powerful parallel tempering algorithm (PT) that addresses this challenge by adding a second dimension of replicas interpolating the penalty strengths. This scheme ensures constraint satisfaction in the final replicas, analogous to low-energy states at low temperature. The resulting two-dimensional parallel tempering algorithm (2D-PT) improves mixing in heavily constrained replicas and eliminates the need to explicitly tune the penalty strength. In a representative example of graph sparsification with copy constraints, 2D-PT achieves near-ideal mixing, with Kullback-Leibler divergence decaying as O(1/t). When applied to sparsified Wishart instances, 2D-PT yields orders of magnitude speedup over conventional PT with the same number of replicas. The method applies broadly to constrained Ising problems and can be deployed on existing Ising machines.
• Abstract（参考訳）: ボルツマン確率分布のサンプリングは機械学習と最適化において重要な役割を果たし、Isingマシンのようなハードウェアアクセラレータの設計を動機付けている。 イジングモデルは原則として任意の最適化問題を符号化するが、現実的な実装は、強すぎると混合が遅くなる、あるいは弱すぎると実現不可能な、ソフトな制約によって妨げられることが多い。 本稿では, ペナルティ強度を補間する2次元のレプリカを追加することで, この課題に対処する強力な並列テンパリングアルゴリズム(PT)の2次元拡張を提案する。 このスキームは、低温での低エネルギー状態に類似した最終レプリカにおける制約満足度を保証する。 結果として得られる2次元並列テンパリングアルゴリズム(2D-PT)は、厳密な制約のあるレプリカの混合を改善し、ペナルティ強度を明示的に調整する必要をなくす。 コピー制約付きグラフスペーサー化の代表的な例では、2D-PTはO(1/t)としてKulback-Leibler分散が崩壊して、ほぼ理想的混合を達成する。 分散Wishartインスタンスに適用すると、2D-PTは同じレプリカ数で従来のPTよりも桁違いのスピードアップが得られる。 この方法は制約付きIsing問題に広く適用され、既存のIsingマシンにデプロイできる。

関連論文リスト

• Effective Dimension Aware Fractional-Order Stochastic Gradient Descent for Convex Optimization Problems [2.5971517743176915]
  データ駆動方式で分数指数を適応する2SED分数次勾配Descent (2SEDFOSGD)を提案する。 理論的には、この手法は、na"ive fractional SGD"で観察されるスラグや不安定な振る舞いを伴わない分数記憶の利点を保っている。
  論文  参考訳（メタデータ） (2025-03-17T22:57:37Z)
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers [0.4969640751053581]
  我々は、pコンピュータがハード最適化問題の解法において最先端の量子アニールを超越できることを示す。 これらのアルゴリズムは、成熟した半導体技術のおかげで、現代のハードウェアで容易に実装可能であることを示す。 この結果から,pコンピュータをスケーラブルでエネルギー効率のよいハードウェアとして,実用的な量子優位性を実現することができた。
  論文  参考訳（メタデータ） (2025-03-13T12:24:13Z)
• Rank Reduction Autoencoders [3.180674374101366]
  我々は、新しい決定論的オートエンコーダ、ランク削減オートエンコーダ(RRAE)を導入する。 RRAEでは、ボトルネックは潜在行列のランクによって定義され、これによりエンコーダ/デコーダアーキテクチャのボトルネックサイズへの依存性が軽減される。 RRAEとARRAEはどちらも安定し,スケーラブルで,信頼性が高いことを実証的に実証した。
  論文  参考訳（メタデータ） (2024-05-22T20:33:09Z)
• SqueezeLLM: Dense-and-Sparse Quantization [80.32162537942138]
  LLMにおける生成推論の主なボトルネックは、単一のバッチ推論のための計算ではなく、メモリ帯域幅である。 学習後量子化フレームワークであるSqueezeLLMを導入し、最大3ビットの超低精度でのロスレス圧縮を実現する。 本フレームワークは,2次情報に基づく最適ビット精度割当を探索する感度ベース非一様量子化法と,2次情報に基づくDense-and-Sparse分解法と,2次情報量割当値と感度重み値を効率的にスパース形式で格納するDense-and-Sparse分解法である。
  論文  参考訳（メタデータ） (2023-06-13T08:57:54Z)
• Flover: A Temporal Fusion Framework for Efficient Autoregressive Model Parallel Inference [3.005912820808423]
  自己回帰モデル上の推論は、現在のトークンの確率分布が前のトークンに条件付けられている時間依存性を利用する。 並列に複数のリクエストを効率的に推測するための時間融合フレームワークであるFloverを提案する。 トークンレベルの並列性のオーケストレーションによって、Floverはハードウェアの最適効率を示し、システムリソースを著しく節約する。
  論文  参考訳（メタデータ） (2023-05-22T20:58:09Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  ニューラルネットワークの評価や自己回帰モデルからのサンプリングなどのフィードフォワード計算は、機械学習においてユビキタスである。 本稿では,非線形方程式の解法としてフィードフォワード計算の課題を定式化し,ジャコビ・ガウス・シーデル固定点法とハイブリッド法を用いて解を求める。 提案手法は, 並列化可能な繰り返し回数の削減(あるいは等値化)により, 元のフィードフォワード計算と全く同じ値が与えられることを保証し, 十分な並列化計算能力を付与する。
  論文  参考訳（メタデータ） (2020-02-10T10:11:31Z)

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

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