論文の概要: A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2510.24755v1
- Date: Mon, 20 Oct 2025 10:38:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-30 22:35:31.193325
- Title: A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization
- Title（参考訳）: 組合せ最適化のための圧縮センシングインスパイアされたモンテカルロ法
- Authors: Baptiste Chevalier, Shimpei Yamaguchi, Wojciech Roga, Masahiro Takeoka,
- Abstract要約: 圧縮可能と仮定される最適化問題の解法として,モンテカルロ圧縮最適化アルゴリズムを提案する。
本アルゴリズムの実用性は,利用可能な計算資源にパラメータを調整できることによって向上する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we present the Monte-Carlo Compressive Optimization algorithm, a new method to solve a combinatorial optimization problem that is assumed compressible. The method relies on random queries to the objective function in order to estimate generalized moments. Next, a greedy algorithm from compressive sensing is repurposed to find the global optimum when not overfitting to samples. We provide numerical results giving evidences that our methods overcome state-of-the-art dual annealing. Moreover, we also give theoretical justification of the algorithm success and analyze its properties. The practicality of our algorithm is enhanced by the ability to tune heuristic parameters to available computational resources.
- Abstract（参考訳）: 本稿では,圧縮可能と仮定される組合せ最適化問題を解く新しい手法であるモンテカルロ圧縮最適化アルゴリズムを提案する。
この方法は、一般化モーメントを推定するために、ランダムなクエリを目的関数に頼っている。
次に、圧縮センシングによる欲求的アルゴリズムを再利用し、サンプルに過度に適合しない場合のグローバルな最適度を求める。
本手法が最先端の二重焼鈍を克服する証拠となる数値的な結果を提供する。
さらに,アルゴリズムの成功を理論的に正当化し,その特性を解析する。
本アルゴリズムの実用性は,利用可能な計算資源にヒューリスティックパラメータをチューニングできることによって向上する。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Adaptive Stochastic Optimisation of Nonconvex Composite Objectives [2.1700203922407493]
一般化された複合ミラー降下アルゴリズムの一群を提案し,解析する。
適応的なステップサイズでは、提案アルゴリズムは問題の事前知識を必要とせずに収束する。
決定集合の低次元構造を高次元問題に活用する。
論文 参考訳（メタデータ） (2022-11-21T18:31:43Z) - Sequential Subspace Search for Functional Bayesian Optimization
Incorporating Experimenter Intuition [63.011641517977644]
本アルゴリズムは,実験者のガウス過程から引き出された一組の引き数で区切られた関数空間の有限次元ランダム部分空間列を生成する。
標準ベイズ最適化は各部分空間に適用され、次の部分空間の出発点(オリジン)として用いられる最良の解である。
シミュレーションおよび実世界の実験,すなわちブラインド関数マッチング,アルミニウム合金の最適析出強化関数の探索,深層ネットワークの学習速度スケジュール最適化において,本アルゴリズムを検証した。
論文 参考訳（メタデータ） (2020-09-08T06:54:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。