論文の概要: Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies

• arxiv url: http://arxiv.org/abs/2404.01930v1
• Date: Tue, 2 Apr 2024 13:23:54 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-03 16:19:00.903040
• Title: Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies
• Title（参考訳）: Adaptive Combinatorial Maximization: 近似グリーディポリシーを超えて
• Authors: Shlomi Weitzman, Sivan Sabato,
• Abstract要約: 我々は、機械学習における中核的な課題である適応性(adaptive)を研究し、アクティブな学習だけでなく、他の多くのドメインにも応用しています。 我々は、以前の結果をサブスメイトし、それらを大幅に強化する新しい包括的近似保証を提供する。 特に、最大ゲイン比が政策のグリーディ近似因子より大きくないことを示し、それよりもかなり小さくできることを示した。
• 参考スコア（独自算出の注目度）: 16.13856749986119
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study adaptive combinatorial maximization, which is a core challenge in machine learning, with applications in active learning as well as many other domains. We study the Bayesian setting, and consider the objectives of maximization under a cardinality constraint and minimum cost coverage. We provide new comprehensive approximation guarantees that subsume previous results, as well as considerably strengthen them. Our approximation guarantees simultaneously support the maximal gain ratio as well as near-submodular utility functions, and include both maximization under a cardinality constraint and a minimum cost coverage guarantee. In addition, we provided an approximation guarantee for a modified prior, which is crucial for obtaining active learning guarantees that do not depend on the smallest probability in the prior. Moreover, we discover a new parameter of adaptive selection policies, which we term the "maximal gain ratio". We show that this parameter is strictly less restrictive than the greedy approximation parameter that has been used in previous approximation guarantees, and show that it can be used to provide stronger approximation guarantees than previous results. In particular, we show that the maximal gain ratio is never larger than the greedy approximation factor of a policy, and that it can be considerably smaller. This provides a new insight into the properties that make a policy useful for adaptive combinatorial maximization.
• Abstract（参考訳）: 我々は、機械学習における中核的な課題である適応的組合せ最大化(Adaptive combinatorial maximization)について研究する。 ベイズの設定について検討し、基準制約と最小コストカバレッジの下での最大化の目的について考察する。 我々は、以前の結果をサブスメイトし、それらを大幅に強化する新しい包括的近似保証を提供する。 我々の近似は最大ゲイン比と準モジュラーなユーティリティ関数を同時にサポートし、濃度制約の下での最大化と最小コストカバレッジ保証の両方を含む。 さらに,修正前の確率に依存しないアクティブな学習保証を得るためには,修正前の確率を近似保証する。 さらに,適応選択政策のパラメータを新たに発見し,これを「最大ゲイン比」と呼ぶ。 このパラメータは, 従来の近似保証に使用されていたグリーディ近似パラメータよりも厳密に制限されていないことを示し, 従来の結果よりも強い近似保証を提供できることを示す。 特に、最大ゲイン比が政策のグリーディ近似因子より大きくないことを示し、それよりもかなり小さくできることを示した。 これは、アダプティブな組合せの最大化に有用なポリシーを作る性質に関する新しい洞察を与える。

関連論文リスト

• Statistical Inference for Temporal Difference Learning with Linear Function Approximation [62.69448336714418]
  時間差差(TD)学習は、おそらく政策評価に最も広く使用されるものであり、この目的の自然な枠組みとして機能する。 本稿では,Polyak-Ruppert平均化と線形関数近似によるTD学習の整合性について検討し,既存の結果よりも3つの重要な改善点を得た。
  論文  参考訳（メタデータ） (2024-10-21T15:34:44Z)
• Adjusting Regression Models for Conditional Uncertainty Calibration [46.69079637538012]
  本稿では,分割共形予測手法を適用して条件付きカバレッジを改善するために,回帰関数を訓練する新しいアルゴリズムを提案する。 本研究では,条件付きカバレッジと名目付きカバレッジ率の差分を求める上限を確立し,この上限値を制御するためのエンドツーエンドアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-26T01:55:45Z)
• Information-Theoretic Safe Bayesian Optimization [59.758009422067005]
  そこでは、未知の(安全でない)制約に反するパラメータを評価することなく、未知の関数を最適化することを目的としている。 現在のほとんどのメソッドはドメインの離散化に依存しており、連続ケースに直接拡張することはできない。 本稿では,GP後部を直接利用して,最も情報に富む安全なパラメータを識別する情報理論的安全な探索基準を提案する。
  論文  参考訳（メタデータ） (2024-02-23T14:31:10Z)
• Trust-Region-Free Policy Optimization for Stochastic Policies [60.52463923712565]
  本研究では,政策に対する信頼領域の制約が,基礎となるモノトニック改善の保証を損なうことなく,信頼領域のない制約によって安全に置き換えられることを示す。 我々は,TREFree(Trust-Region-Free Policy Optimization)と呼ばれるアルゴリズムを,信頼領域の制約が不要であるとして明示する。
  論文  参考訳（メタデータ） (2023-02-15T23:10:06Z)
• Constrained Variational Policy Optimization for Safe Reinforcement Learning [40.38842532850959]
  安全強化学習は、安全クリティカルなアプリケーションにデプロイする前に、一定の制約を満たすポリシーを学ぶことを目的としている。 主要な制約付き最適化フレームワークとしての原始双対は不安定な問題に悩まされ、最適性の保証が欠如している。 本稿では,新しい確率的推論の観点から問題を克服し,安全政策を学習するための期待最大化方式を提案する。
  論文  参考訳（メタデータ） (2022-01-28T04:24:09Z)
• Understanding the Effect of Stochasticity in Policy Optimization [86.7574122154668]
  最適化手法の優位性は、正確な勾配が用いられるかどうかに大きく依存することを示す。 次に,政策最適化におけるコミット率の概念を紹介する。 第三に、外部のオラクル情報がない場合には、収束を加速するために幾何を利用することと、最適性をほぼ確実に達成することとの間に本質的にトレードオフがあることが示される。
  論文  参考訳（メタデータ） (2021-10-29T06:35:44Z)
• Uniform-PAC Bounds for Reinforcement Learning with Linear Function Approximation [92.3161051419884]
  線形関数近似を用いた強化学習について検討する。 既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。 我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
  論文  参考訳（メタデータ） (2021-06-22T08:48:56Z)
• Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds Globally Optimal Policy [95.98698822755227]
  本研究は,リスクに敏感な深層強化学習を,分散リスク基準による平均報酬条件下で研究する試みである。 本稿では,ポリシー,ラグランジュ乗算器,フェンシェル双対変数を反復的かつ効率的に更新するアクタ批判アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-12-28T05:02:26Z)
• Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications [15.191184049312467]
  我々は,単調部分関数のグリーディアルゴリズムを微分可能とする理論的に保証された多元性フレームワークを確立する。 乱数化によってグリーディアルゴリズムを滑らかにし、濃度や$kappa$-extensible(拡張可能なシステム制約)の場合に期待する元の近似保証をほぼ回復することを示した。
  論文  参考訳（メタデータ） (2020-05-06T03:33:46Z)

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

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