論文の概要: Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2407.17200v1
• Date: Wed, 24 Jul 2024 12:00:30 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-25 14:04:14.543935
• Title: Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems
• Title（参考訳）: 組合せ最適化問題に対するサロゲートポリシの一般化境界
• Authors: Pierre-Cyril Aubin-Frankowski, Yohann De Castro, Axel Parmentier, Alessandro Rudi,
• Abstract要約: 最近の構造化学習手法のストリームは、様々な最適化問題に対する技術の実践的状態を改善している。 鍵となる考え方は、インスタンスを別々に扱うのではなく、インスタンス上の統計分布を利用することだ。 本稿では,最適化を容易にし,一般化誤差を改善するポリシを摂動することでリスクを円滑にする手法について検討する。
• 参考スコア（独自算出の注目度）: 61.580419063416734
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: A recent stream of structured learning approaches has improved the practical state of the art for a range of combinatorial optimization problems with complex objectives encountered in operations research. Such approaches train policies that chain a statistical model with a surrogate combinatorial optimization oracle to map any instance of the problem to a feasible solution. The key idea is to exploit the statistical distribution over instances instead of dealing with instances separately. However learning such policies by risk minimization is challenging because the empirical risk is piecewise constant in the parameters, and few theoretical guarantees have been provided so far. In this article, we investigate methods that smooth the risk by perturbing the policy, which eases optimization and improves generalization. Our main contribution is a generalization bound that controls the perturbation bias, the statistical learning error, and the optimization error. Our analysis relies on the introduction of a uniform weak property, which captures and quantifies the interplay of the statistical model and the surrogate combinatorial optimization oracle. This property holds under mild assumptions on the statistical model, the surrogate optimization, and the instance data distribution. We illustrate the result on a range of applications such as stochastic vehicle scheduling. In particular, such policies are relevant for contextual stochastic optimization and our results cover this case.
• Abstract（参考訳）: 最近の構造化学習手法のストリームは、操作研究で遭遇する複雑な目的を伴う様々な組合せ最適化問題の実践的状況を改善している。 このようなアプローチは、任意の問題のインスタンスを実現可能な解にマッピングするために、代理組合せ最適化オラクルで統計モデルをチェーンするポリシーを訓練する。 鍵となる考え方は、インスタンスを別々に扱うのではなく、インスタンス上の統計分布を利用することだ。 しかしながら、リスク最小化によるこのような政策の学習は、経験的リスクがパラメータの断片的に一定であり、これまで理論的な保証がほとんど提供されていないため、困難である。 本稿では,最適化の容易化と一般化の向上を図り,リスクの平滑化を図る。 我々の主な貢献は、摂動バイアス、統計的学習誤差、最適化誤差を制御する一般化境界である。 我々の分析は、統計モデルと代理組合せ最適化オラクルの相互作用を捕捉し定量化する、一様弱特性の導入に依存している。 この性質は、統計モデル、代理最適化、およびインスタンスデータ分布に関する軽微な仮定の下で成り立つ。 本稿では,確率的車両スケジューリングなど,様々な応用について述べる。 特に、このようなポリシーは文脈確率最適化に関係しており、我々の結果はこのケースをカバーしている。

関連論文リスト

• Bayesian Nonparametrics Meets Data-Driven Distributionally Robust Optimization [29.24821214671497]
  機械学習と統計モデルのトレーニングは、しばしばデータ駆動型リスク基準の最適化を伴う。 ベイズ的非パラメトリック(ディリクレ過程)理論と、スムーズなあいまいさ-逆選好の最近の決定論的モデルを組み合わせた、新しいロバストな基準を提案する。 実用的な実装として、よく知られたディリクレプロセスの表現に基づいて、評価基準の抽出可能な近似を提案し、研究する。
  論文  参考訳（メタデータ） (2024-01-28T21:19:15Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。 汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。 我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
  論文  参考訳（メタデータ） (2023-10-10T01:39:04Z)
• Domain Generalization without Excess Empirical Risk [83.26052467843725]
  一般的なアプローチは、一般化を捉え、ペナルティと共同で経験的リスクを最小化するために、データ駆動の代理ペナルティを設計することである。 我々は、このレシピの重大な失敗モードは、共同最適化における誤ったペナルティや難しさによる過度なリスクであると主張している。 我々は,この問題を解消するアプローチを提案し,経験的リスクと刑罰を同時に最小化する代わりに,経験的リスクの最適性の制約の下でのペナルティを最小化する。
  論文  参考訳（メタデータ） (2023-08-30T08:46:46Z)
• PARL: A Unified Framework for Policy Alignment in Reinforcement Learning from Human Feedback [106.63518036538163]
  我々は、強化学習におけるポリシーアライメントの最近強調された重要な問題に対処するために、新しい統合された二段階最適化ベースのフレームワーク、textsfPARLを提案する。 本フレームワークは, 上向きの目標(逆設計)の分布を, 下向きの最適変数で明示的にパラメータ化することにより, これらの問題に対処する。 その結果,提案したtextsfPARL が RL のアライメントの懸念に対処できる可能性が示唆された。
  論文  参考訳（メタデータ） (2023-08-03T18:03:44Z)
• Robust Data-driven Prescriptiveness Optimization [4.792851066169871]
  本稿では、古典的経験的リスク目標最小化に代えて、規範性の係数が代わる分布的ロバストな文脈最適化モデルを提案する。 サンプル外データセットが様々な分散シフトを受ける場合の代替手法に対する結果のロバスト性を評価する。
  論文  参考訳（メタデータ） (2023-06-09T14:56:06Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Integrated Conditional Estimation-Optimization [6.037383467521294]
  確率のある不確実なパラメータを文脈的特徴情報を用いて推定できる実世界の多くの最適化問題である。 不確実なパラメータの分布を推定する標準的な手法とは対照的に,統合された条件推定手法を提案する。 当社のI CEOアプローチは、穏健な条件下で理論的に一貫性があることを示します。
  論文  参考訳（メタデータ） (2021-10-24T04:49:35Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• Optimistic variants of single-objective bilevel optimization for evolutionary algorithms [6.788217433800101]
  ベンチマーク問題を解くために部分的部分進化的アプローチが提案され、優れた結果が得られた。 また、一般的な収束アプローチ、すなわち楽観的で悲観的なアプローチにも新しい変種が提案されている。 実験の結果、アルゴリズムは楽観的な変量を持つ最適解に異なる収束性を示す。
  論文  参考訳（メタデータ） (2020-08-22T23:12:07Z)

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

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