論文の概要: Curriculum learning for multilevel budgeted combinatorial problems
- arxiv url: http://arxiv.org/abs/2007.03151v2
- Date: Mon, 26 Oct 2020 12:23:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 19:05:20.820033
- Title: Curriculum learning for multilevel budgeted combinatorial problems
- Title(参考訳): 多段階予算組合せ問題に対するカリキュラム学習
- Authors: Adel Nabli, Margarida Carvalho
- Abstract要約: マルチレベル最適化問題はそれらの一般化であり、複数のプレイヤーが逐次決定を下す状況を含んでいる。
グラフ上のゼロサムゲームにおいて、2人のプレイヤーが関与する多段階の予算問題を解決するための価値ベース手法を考案する。
我々のフレームワークは単純なカリキュラムに基づいており、もしエージェントが$B$までの予算を持つインスタンスの価値を見積もる方法を知っているなら、可能なすべての余剰状態の方向に関係なく、予算が$B+1$のインスタンスを時間内に解決することができる。
- 参考スコア(独自算出の注目度): 7.804994311050265
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning heuristics for combinatorial optimization problems through graph
neural networks have recently shown promising results on some classic NP-hard
problems. These are single-level optimization problems with only one player.
Multilevel combinatorial optimization problems are their generalization,
encompassing situations with multiple players taking decisions sequentially. By
framing them in a multi-agent reinforcement learning setting, we devise a
value-based method to learn to solve multilevel budgeted combinatorial problems
involving two players in a zero-sum game over a graph. Our framework is based
on a simple curriculum: if an agent knows how to estimate the value of
instances with budgets up to $B$, then solving instances with budget $B+1$ can
be done in polynomial time regardless of the direction of the optimization by
checking the value of every possible afterstate. Thus, in a bottom-up approach,
we generate datasets of heuristically solved instances with increasingly larger
budgets to train our agent. We report results close to optimality on graphs up
to $100$ nodes and a $185 \times$ speedup on average compared to the quickest
exact solver known for the Multilevel Critical Node problem, a max-min-max
trilevel problem that has been shown to be at least $\Sigma_2^p$-hard.
- Abstract(参考訳): グラフニューラルネットワークによる組合せ最適化問題の学習ヒューリスティックスは、最近、古典的なNPハード問題に対して有望な結果を示した。
シングルレベル最適化の問題であり、プレイヤーは1人だけである。
多段階組合せ最適化問題はそれらの一般化であり、複数のプレイヤーが逐次決定を下す状況を含む。
グラフ上のゼロサムゲームにおいて、2人のプレイヤーが関与する多段階の予算の組合せ問題を解くために,価値に基づく手法を考案した。
我々のフレームワークは単純なカリキュラムに基づいており、もしエージェントが予算が最大$B$のインスタンスの価値を見積もる方法を知っていれば、予算が$B+1$のインスタンスを多項式時間で解決できる。
したがって、ボトムアップアプローチでは、エージェントをトレーニングするためにますます大きな予算でヒューリスティックに解決されたインスタンスのデータセットを生成します。
我々は、最大100ドルノードのグラフの最適性に近い結果と、少なくとも$\Sigma_2^p$-hardであることが示されている最大3レベル問題であるMultilevel critical Node問題で知られている最も正確な解法と比較して平均185ドルのスピードアップを報告した。
関連論文リスト
- Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
そこで本研究では,マルチエージェントSOCOのための,真に分散化されたアルゴリズムACORDを提案する。
通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
論文 参考訳(メタデータ) (2024-11-13T05:59:04Z) - Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。
本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。
我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
論文 参考訳(メタデータ) (2023-10-05T15:48:41Z) - Landscape Surrogate: Learning Decision Losses for Mathematical
Optimization Under Partial Information [48.784330281177446]
学習統合最適化の最近の研究は、最適化が部分的にのみ観察される場合や、専門家のチューニングなしに汎用性が不十分な環境では有望であることを示している。
本稿では,$fcirc mathbfg$の代替として,スムーズで学習可能なランドスケープサロゲートを提案する。
このサロゲートはニューラルネットワークによって学習可能で、$mathbfg$ソルバよりも高速に計算でき、トレーニング中に密度が高く滑らかな勾配を提供し、目に見えない最適化問題に一般化でき、交互最適化によって効率的に学習される。
論文 参考訳(メタデータ) (2023-07-18T04:29:16Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳(メタデータ) (2023-06-29T14:57:56Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z) - A Gradient Method for Multilevel Optimization [8.80899367147235]
我々は、Franceschiらのアイデアに基づいて、多レベル$n$レベルの勾配に基づくアルゴリズムを開発した。
私たちの知る限り、これはマルチレベル最適化の理論的保証を持つ最初のアルゴリズムの1つである。
論文 参考訳(メタデータ) (2021-05-28T16:22:10Z) - Efficient Online-Bandit Strategies for Minimax Learning Problems [21.300877551771197]
いくつかの学習問題は、例えば、実験的な分散ロバスト学習や、非標準集約的損失による最小化といった、min-max問題の解決に関係している。
具体的には、これらの問題は、モデルパラメータ$winmathcalW$と、トレーニングセットの実証分布$pinmathcalK$で学習を行う凸線型問題である。
効率的な手法を設計するために、オンライン学習アルゴリズムを(組合せ)帯域幅アルゴリズムと対戦させる。
論文 参考訳(メタデータ) (2021-05-28T16:01:42Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-05T18:28:42Z) - Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT [0.0]
本稿では,最大3-Stisfiability (MAX-E-$3$-SAT) 問題に対して$Theta(N)$で近似解を計算するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-10T07:59:54Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳(メタデータ) (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。