論文の概要: Primal-dual algorithm for contextual stochastic combinatorial optimization

• arxiv url: http://arxiv.org/abs/2505.04757v1
• Date: Wed, 07 May 2025 19:37:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-09 21:43:49.651807
• Title: Primal-dual algorithm for contextual stochastic combinatorial optimization
• Title（参考訳）: 文脈確率的組合せ最適化のための主二元アルゴリズム
• Authors: Louis Bouvier, Thibault Prunet, Vincent Leclère, Axel Parmentier,
• Abstract要約: 本稿では,不確実性のある意思決定に対処するために,運用研究と機械学習を統合する,文脈最適化の新しいアプローチを提案する。 我々の目標は、不確実なパラメータやコンテキストに関する過去のデータから推定される経験的リスクを最小化することです。
• 参考スコア（独自算出の注目度）: 1.4999444543328293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces a novel approach to contextual stochastic optimization, integrating operations research and machine learning to address decision-making under uncertainty. Traditional methods often fail to leverage contextual information, which underscores the necessity for new algorithms. In this study, we utilize neural networks with combinatorial optimization layers to encode policies. Our goal is to minimize the empirical risk, which is estimated from past data on uncertain parameters and contexts. To that end, we present a surrogate learning problem and a generic primal-dual algorithm that is applicable to various combinatorial settings in stochastic optimization. Our approach extends classic Fenchel-Young loss results and introduces a new regularization method using sparse perturbations on the distribution simplex. This allows for tractable updates in the original space and can accommodate diverse objective functions. We demonstrate the linear convergence of our algorithm under certain conditions and provide a bound on the non-optimality of the resulting policy in terms of the empirical risk. Experiments on a contextual stochastic minimum weight spanning tree problem show that our algorithm is efficient and scalable, achieving performance comparable to imitation learning of solutions computed using an expensive Lagrangian-based heuristic.
• Abstract（参考訳）: 本稿では,文脈確率最適化への新たなアプローチを導入し,不確実性のある意思決定に対処するための操作研究と機械学習を統合する。 従来の手法は文脈情報を活用するのに失敗することが多く、新しいアルゴリズムの必要性を浮き彫りにしている。 本研究では,ニューラルネットワークと組合せ最適化層を用いてポリシーを符号化する。 我々の目標は、不確実なパラメータやコンテキストに関する過去のデータから推定される経験的リスクを最小化することです。 そこで我々は,確率的最適化において,様々な組合せ設定に適用可能な代理学習問題と汎用原始双対アルゴリズムを提案する。 提案手法は,古典的なFenchel-Young損失を低減し,分布単純性に対するスパース摂動を用いた新たな正規化手法を提案する。 これにより、オリジナルスペースのトラクタブルな更新が可能になり、多様な目的関数に対応できる。 特定の条件下でのアルゴリズムの線形収束を実証し、経験的リスクの観点から結果のポリシーの最適性に縛られる。 木問題にまたがる文脈確率的最小ウェイト実験により,我々のアルゴリズムは効率的かつスケーラブルであり,高価なラグランジアンベースのヒューリスティックを用いて計算された解の模倣学習に匹敵する性能を示した。

関連論文リスト

• Effectively Leveraging Momentum Terms in Stochastic Line Search Frameworks for Fast Optimization of Finite-Sum Problems [0.5156484100374059]
  過度にパラメータ化された状態における深度最適化のための最近の線探索手法と運動量方向との関係について検討する。 モーメントパラメータの定義にデータ持続性、共役型ルールの混合を利用するアルゴリズムを導入する。 結果のアルゴリズムは、他の一般的な手法よりも優れていることを実証的に示している。
  論文  参考訳（メタデータ） (2024-11-11T16:26:33Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
  最近の構造化学習手法のストリームは、様々な最適化問題に対する技術の実践的状態を改善している。 鍵となる考え方は、インスタンスを別々に扱うのではなく、インスタンス上の統計分布を利用することだ。 本稿では,最適化を容易にし,一般化誤差を改善するポリシを摂動することでリスクを円滑にする手法について検討する。
  論文  参考訳（メタデータ） (2024-07-24T12:00:30Z)
• From Inverse Optimization to Feasibility to ERM [11.731853838892487]
  パラメータの予測に付加的なコンテキスト情報を利用するコンテキスト逆設定について検討する。 合成および実世界の問題に対する我々のアプローチを実験的に検証し,既存手法と比較して性能が向上したことを示す。
  論文  参考訳（メタデータ） (2024-02-27T21:06:42Z)
• Adaptive pruning-based Newton's method for distributed learning [14.885388389215587]
  本稿では,分散適応ニュートン学習(textttDANL)という,新規で効率的なアルゴリズムを提案する。 textttDANLは、利用可能なリソースに効率よく適応し、高い効率を維持しながら、線形収束率を達成する。 実験により、textttDANLは、効率的な通信と異なるデータセット間の強い性能で線形収束を実現することが示された。
  論文  参考訳（メタデータ） (2023-08-20T04:01:30Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  本稿では,ノード,エッジ,あるいはその両方に情報をエンコードするグラフベースの問題を扱う新しいニューラル改善(NI)モデルを提案する。 提案モデルは,各地区の操作の選択を誘導する丘登頂に基づくアルゴリズムの基本的な構成要素として機能する。
  論文  参考訳（メタデータ） (2022-06-01T10:35:29Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。 信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。 最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
  論文  参考訳（メタデータ） (2021-04-06T05:23:20Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

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