Fugu-MT 論文翻訳(概要): Data-dependent Evaluations for Budgeted Submodular Maximization

論文の概要: Data-dependent Evaluations for Budgeted Submodular Maximization

arxiv url: http://arxiv.org/abs/2607.05759v1
Date: Tue, 07 Jul 2026 02:34:10 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-08 21:24:51.369683
Title: Data-dependent Evaluations for Budgeted Submodular Maximization
Title（参考訳）: 予算サブモジュールの最大化のためのデータ依存評価
Abstract要約: Submodularは、機械学習やマイニングなど、多くの分野でアルゴリズムを開発するための重要なビルディングブロックである。与えられた問題インスタンスに対して、ソリューションがどのように最適なものであるかを評価するのは容易ではない。理論的には、それらの解が最適解を支配し、その利点を実証的に証明する。
参考スコア（独自算出の注目度）: 7.795374338122115
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.
Abstract（参考訳）: 部分モジュラ最大化は、機械学習やデータマイニングなど、多くの分野でアルゴリズムを開発するための重要なビルディングブロックである。この問題のNP硬さのため、部分モジュラー最大化アルゴリズムの解析は、悲観的な最悪の近似要素のみを提供するのが一般的である。生成した解が与えられた問題インスタンスに対して最適な解にどれほど近いかを評価するのは容易ではない。そこで本稿では,knapsack制約を用いた部分モジュラー最大化のためのデータ依存上界を新たに開発する。最適解が最適解を支配していることを理論的に証明し、実世界のデータセットによる実験を通じて、最適解がどの程度近いかを実証する彼らの利点を実証する。

関連論文リスト

Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective [5.848643785361479]
本稿では,政策選択誤差確率の指数的減衰率を原理的効率指標として紹介する。我々は、ネストされた問題の最適解という観点から、最適性の相補的な2つの概念を定式化する。得られた強化学習アルゴリズムは, 最適性基準の下でほぼロマンスに最適であることが証明された。
論文参考訳（メタデータ） (2026-05-27T16:08:56Z)
Pareto Optimization with Robust Evaluation for Noisy Subset Selection [34.83487850400559]
サブセット選択は最適化の基本的な問題であり、影響やスパース回帰といった幅広い応用がある。欲求アルゴリズムや進化進化的POSSを含む従来のアルゴリズムは、ノイズの多い環境で苦労するか、過剰な計算資源を消費する。本稿では,頑健な評価関数を最大化し,同時にサブセットサイズを最小化する,雑音性サブセット選択(PORE)のためのロバスト評価を用いたパレート最適化に基づく新しい手法を提案する。
論文参考訳（メタデータ） (2025-01-12T14:04:20Z)
Nearly Optimal Latent State Decoding in Block MDPs [74.51224067640717]
エピソードブロック MDP では、意思決定者は少数の潜在状態から生成される豊富な観測やコンテキストにアクセスすることができる。まず、固定動作ポリシーに基づいて生成されたデータに基づいて、潜時状態復号関数を推定することに興味がある。次に、報酬のないフレームワークにおいて、最適に近いポリシーを学習する問題について研究する。
論文参考訳（メタデータ） (2022-08-17T18:49:53Z)
Data-Driven Minimax Optimization with Expectation Constraints [9.373649142701803]
本稿では,最小値予測制約問題に対処するために,効率的な原始双対アルゴリズムのクラスを提案する。我々のアルゴリズムは$mathcalO(frac1sqrtN)$の最適速度で収束することを示す。
論文参考訳（メタデータ） (2022-02-16T05:23:27Z)
Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文参考訳（メタデータ） (2021-11-01T21:06:35Z)
Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization [12.742028139557384]
有限和構造を持つ凸凹最小値問題の解法として,無作為なリシャッフィングを基本とした最適勾配Descent-Ascentアルゴリズムを提案する。このアルゴリズムは凸最小化問題に対するゼロ階アルゴリズムと同じ収束率を持つことを示す。
論文参考訳（メタデータ） (2021-06-16T18:49:59Z)
Instance Specific Approximations for Submodular Maximization [45.91235224228292]
実世界のインスタンス上で最適な解に対して,アルゴリズムの性能をベンチマークする手法を模索する。大きな疑問は、実際に遭遇したインスタンスの最適なソリューションと比較して、アルゴリズムのパフォーマンスを測定する方法です。我々の主な貢献は、サブモジュラー最小化のための新しいアルゴリズムではなく、サブモジュラーインスタンスのアルゴリズムがいかに最適かを測定する分析手法である。
論文参考訳（メタデータ） (2021-02-23T19:39:32Z)
Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文参考訳（メタデータ） (2021-02-16T06:04:27Z)
Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文参考訳（メタデータ） (2020-11-19T10:00:54Z)
An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文参考訳（メタデータ） (2020-10-23T09:12:47Z)
Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。最先端アルゴリズムの利点を論じ、解説する。
論文参考訳（メタデータ） (2020-09-28T15:22:24Z)

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