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

• arxiv url: http://arxiv.org/abs/2407.17200v2
• Date: Sat, 11 Oct 2025 14:56:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-14 18:06:29.49179
• Title: Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems
• Title（参考訳）: 組合せ最適化問題に対するサロゲートポリシの一般化境界
• Authors: Pierre-Cyril Aubin-Frankowski, Yohann De Castro, Axel Parmentier, Alessandro Rudi,
• Abstract要約: 我々はスムーズな(摂動された)ポリシーを解析し、線形オラクルが使用する方向に対して制御されたランダムな摂動を付加する。 我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。 車両のスケジューリングやスムーズ化がトラクタブルトレーニングと制御された一般化の両方を可能にしていることを示す。
• 参考スコア（独自算出の注目度）: 53.03951222945921
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: A recent line of structured learning methods has advanced the practical state-of-the-art for combinatorial optimization problems with complex, application-specific objectives. These approaches learn policies that couple a statistical model with a tractable surrogate combinatorial optimization oracle, so as to exploit the distribution of problem instances instead of solving each instance independently. A core obstacle is that the empirical risk is then piecewise constant in the model parameters. This hinders gradient-based optimization and only few theoretical guarantees have been provided so far. We address this issue by analyzing smoothed (perturbed) policies: adding controlled random perturbations to the direction used by the linear oracle yields a differentiable surrogate risk and improves generalization. Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error. The analysis hinges on a new Uniform Weak (UW) property capturing the geometric interaction between the statistical model and the normal fan of the feasible polytope; we show it holds under mild assumptions, and automatically when a minimal baseline perturbation is present. The framework covers, in particular, contextual stochastic optimization. We illustrate the scope of the results on applications such as stochastic vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
• Abstract（参考訳）: 近年,複雑なアプリケーション固有の目的を持つ組合せ最適化問題に対して,構造化学習手法が実用化されつつある。 これらのアプローチは、統計モデルとトラクタブルなサロゲート組合せ最適化オラクルを結合するポリシーを学習し、各インスタンスを独立して解決するのではなく、問題インスタンスの分布を利用する。 中心となる障害は、経験的リスクがモデルパラメータにおいて断片的に一定であることである。 これにより勾配に基づく最適化が妨げられ、これまでのところ理論的な保証はほとんど得られていない。 線形オラクルが使用する方向に制御されたランダムな摂動を加えると、異なるサロゲートリスクが発生し、一般化が向上する。 我々の主な貢献は、過剰リスクを摂動バイアス、統計的推定誤差、最適化誤差に分解する一般化境界である。 解析は、統計モデルとポリトープの通常のファンとの幾何学的相互作用を捉えた新しい一様弱み(UW)特性に基づいており、軽微な仮定の下で保持し、最小のベースライン摂動が存在する場合に自動的に保持することを示す。 このフレームワークは、特に文脈確率最適化をカバーしている。 確率的車両スケジューリングなどの応用における結果の範囲について, トラクタブルトレーニングと制御一般化の両面において, 円滑化がいかに有効かを強調した。

関連論文リスト

• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  強化学習(Reinforcement Learning, RL)は、ニューラルネットワーク最適化のための強力なツールとして登場した。 大幅な進歩にもかかわらず、既存のRLアプローチは報酬信号の減少や大規模な行動空間における非効率な探索といった課題に直面している。 統計的比較モデルを用いて定量的報酬信号を定性的選好信号に変換する新しい手法であるPreference Optimizationを提案する。
  論文  参考訳（メタデータ） (2025-05-13T16:47:00Z)
• Primal-dual algorithm for contextual stochastic combinatorial optimization [1.4999444543328293]
  本稿では,不確実性のある意思決定に対処するために,運用研究と機械学習を統合する,文脈最適化の新しいアプローチを提案する。 我々の目標は、不確実なパラメータやコンテキストに関する過去のデータから推定される経験的リスクを最小化することです。
  論文  参考訳（メタデータ） (2025-05-07T19:37:12Z)
• Semiparametric Counterfactual Regression [2.356908851188234]
  一般化可能なフレームワーク内での非実効的回帰のための2つの頑健なスタイル推定器を提案する。 当社のアプローチでは,標準手法を維持しながら適応性を高めるために,漸進的な介入を用いる。 解析の結果,提案した推定器は幅広い問題に対して$sqrn$-consistencyと正規性が得られることがわかった。
  論文  参考訳（メタデータ） (2025-04-03T15:32:26Z)
• Representation-based Reward Modeling for Efficient Safety Alignment of Large Language Model [84.00480999255628]
  大規模言語モデル(LLM)の安全性アライメントのための強化学習アルゴリズムは,分散シフトの課題に直面している。 現在のアプローチでは、ターゲットポリシーからのオンラインサンプリングを通じてこの問題に対処するのが一般的である。 モデル固有の安全判断能力を活用して報酬信号を抽出する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-03-13T06:40:34Z)
• 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)
• Off-Policy Evaluation with Policy-Dependent Optimization Response [90.28758112893054]
  我々は,テキスト政治に依存した線形最適化応答を用いた非政治評価のための新しいフレームワークを開発した。 摂動法による政策依存推定のための非バイアス推定器を構築する。 因果介入を最適化するための一般的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-25T20:25: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)

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

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