論文の概要: Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods

• arxiv url: http://arxiv.org/abs/2310.05309v2
• Date: Tue, 7 Nov 2023 00:37:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-08 19:09:10.286218
• Title: Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods
• Title（参考訳）: 組合せ問題に対する解サンプリングの最適化--政策グラディエント手法のランドスケープ
• Authors: Constantine Caramanis, Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos Tzamos
• Abstract要約: 本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
• 参考スコア（独自算出の注目度）: 52.0617030129699
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Deep Neural Networks and Reinforcement Learning methods have empirically shown great promise in tackling challenging combinatorial problems. In those methods a deep neural network is used as a solution generator which is then trained by gradient-based methods (e.g., policy gradient) to successively obtain better solution distributions. In this work we introduce a novel theoretical framework for analyzing the effectiveness of such methods. We ask whether there exist generative models that (i) are expressive enough to generate approximately optimal solutions; (ii) have a tractable, i.e, polynomial in the size of the input, number of parameters; (iii) their optimization landscape is benign in the sense that it does not contain sub-optimal stationary points. Our main contribution is a positive answer to this question. Our result holds for a broad class of combinatorial problems including Max- and Min-Cut, Max-$k$-CSP, Maximum-Weight-Bipartite-Matching, and the Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla gradient descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
• Abstract（参考訳）: 深層ニューラルネットワークと強化学習手法は、組合せ問題に取り組む上で大きな可能性を実証してきた。 これらの手法では、ディープニューラルネットワークを解生成器として使用し、勾配に基づく手法(例えばポリシー勾配)で訓練し、より良い解分布を連続的に得る。 本研究では,そのような手法の有効性を解析するための理論的枠組みを紹介する。 生成モデルが存在するかどうかを問うと i) ほぼ最適な解を生成するのに十分な表現性 (ii) 抽出可能な,すなわち入力の大きさの多項式,パラメータ数を有する。 (iii)その最適化の展望は、準最適静止点を含まないという意味で良質である。 私たちの主な貢献は、この質問に対するポジティブな答えです。 その結果,Max-およびMin-Cut,Max-$k$-CSP,Maximum-Weight-Bipartite-Matching,Traveing Salesman問題など,幅広い組み合わせの問題が得られた。 解析の副産物として,バニラ勾配降下の新たな正則化プロセスを導入し,脱落勾配問題に対処し,不動点を回避できることを理論的および実験的に証明する。

関連論文リスト

• Constrained or Unconstrained? Neural-Network-Based Equation Discovery from Data [0.0]
  我々はPDEをニューラルネットワークとして表現し、物理情報ニューラルネットワーク(PINN)に似た中間状態表現を用いる。 本稿では,この制約付き最適化問題を解くために,ペナルティ法と広く利用されている信頼領域障壁法を提案する。 バーガーズ方程式とコルトヴェーグ・ド・ヴライス方程式に関する我々の結果は、後者の制約付き手法がペナルティ法より優れていることを示している。
  論文  参考訳（メタデータ） (2024-05-30T01:55:44Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  マルチオブジェクト強化学習(MORL)エージェントでは、意思決定行動の最適化を行う。 重みベクトル w でパラメータ化される線型効用関数の場合に焦点を当てる。 学習過程の異なる段階で最も有望な重みベクトルを効率的に探索する上信頼境界に基づく手法を提案する。
  論文  参考訳（メタデータ） (2024-05-01T09:34:42Z)
• A Block-Coordinate Approach of Multi-level Optimization with an Application to Physics-Informed Neural Networks [0.0]
  非線形最適化問題の解法として多レベルアルゴリズムを提案し,その評価複雑性を解析する。 物理インフォームドニューラルネットワーク (PINN) を用いた偏微分方程式の解に適用し, 提案手法がより良い解法と計算量を大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-05-23T19:12:02Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Physics and Equality Constrained Artificial Neural Networks: Application to Partial Differential Equations [1.370633147306388]
  偏微分方程式(PDE)の解を学ぶために物理インフォームドニューラルネットワーク(PINN)が提案されている。 本稿では,この目的関数の定式化方法が,PINNアプローチにおける厳密な制約の源であることを示す。 本稿では,逆問題と前方問題の両方に対処可能な多目的フレームワークを提案する。
  論文  参考訳（メタデータ） (2021-09-30T05:55:35Z)
• On the Treatment of Optimization Problems with L1 Penalty Terms via Multiobjective Continuation [0.0]
  本稿では,線形・非線形最適化におけるスパース性の影響を詳細に把握するアルゴリズムを提案する。 本手法は非線形の場合に対する線形回帰問題に対するよく知られたホモトピー法の一般化と見なすことができる。
  論文  参考訳（メタデータ） (2020-12-14T13:00:50Z)
• Deep Magnification-Flexible Upsampling over 3D Point Clouds [103.09504572409449]
  本稿では,高密度点雲を生成するためのエンドツーエンド学習ベースのフレームワークを提案する。 まずこの問題を明示的に定式化し、重みと高次近似誤差を判定する。 そこで我々は,高次改良とともに,統一重みとソート重みを適応的に学習する軽量ニューラルネットワークを設計する。
  論文  参考訳（メタデータ） (2020-11-25T14:00:18Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  本稿では,マスク付き自己回帰ニューラルネットワークを用いて解空間上の均一分布をモデル化するクロスエントロピー法(CEM)を提案する。 我々のアルゴリズムは複雑な解空間を表現でき、様々な異なる解領域を追跡できる。
  論文  参考訳（メタデータ） (2020-02-17T20:21:20Z)

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

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