論文の概要: A Unified Approach for Maximizing Continuous DR-submodular Functions
- arxiv url: http://arxiv.org/abs/2305.16671v2
- Date: Fri, 3 Nov 2023 04:37:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-06 18:08:51.464252
- Title: A Unified Approach for Maximizing Continuous DR-submodular Functions
- Title（参考訳）: 連続DR-部分モジュラ関数の最大化のための統一的アプローチ
- Authors: Mohammad Pedramfar and Christopher John Quinn and Vaneet Aggarwal
- Abstract要約: 本稿では,連続DR-部分モジュラ函数の最大化のための統一的アプローチを提案する。
このアプローチには、単調関数と非単調関数の両方に対して、フランク=ウルフ型がオフラインである。
- 参考スコア（独自算出の注目度）: 33.38582292895673
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper presents a unified approach for maximizing continuous
DR-submodular functions that encompasses a range of settings and oracle access
types. Our approach includes a Frank-Wolfe type offline algorithm for both
monotone and non-monotone functions, with different restrictions on the general
convex set. We consider settings where the oracle provides access to either the
gradient of the function or only the function value, and where the oracle
access is either deterministic or stochastic. We determine the number of
required oracle accesses in all cases. Our approach gives new/improved results
for nine out of the sixteen considered cases, avoids computationally expensive
projections in two cases, with the proposed framework matching performance of
state-of-the-art approaches in the remaining five cases. Notably, our approach
for the stochastic function value-based oracle enables the first regret bounds
with bandit feedback for stochastic DR-submodular functions.
- Abstract（参考訳）: 本稿では,さまざまな設定と oracle アクセスタイプを包含する連続的な dr-submodular 関数を最大化する統一的アプローチを提案する。
我々のアプローチは、一般凸集合に対する異なる制約を持つ単調関数と非単調関数の両方に対するフランク・ウルフ型オフラインアルゴリズムを含む。
私たちは、oracleが関数の勾配または関数値のみへのアクセスを提供し、oracleアクセスが決定論的または確率的であるような設定を検討する。
すべてのケースで必要なoracleアクセスの数を決定します。
提案手法は,16例中9例に新しい/改善結果を与え,計算コストの高い投射を2例で回避し,残りの5例で最先端手法の性能にマッチするフレームワークを提案する。
特に、確率関数値に基づくオラクルに対する我々のアプローチは、確率DR-部分モジュラ関数に対する帯域フィードバックによる最初の後悔のバウンドを可能にする。
関連論文リスト
- Linear Submodular Maximization with Bandit Feedback [7.926559636438099]
準モジュラー目的関数 $f:2UtomathbbR_geq 0$, ここでは $f=sum_i=1dw_iF_i$ に対する近似アルゴリズムの開発を検討する。
F_i$ 関数へのオラクルアクセスが期待できるが、係数 $w_i$ は未知であり、$f$ はノイズの多いクエリによってのみアクセス可能である。
我々のアルゴリズムは、$fの線形構造を利用していないアルゴリズムと比較して、サンプル効率の点で大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2024-07-02T18:40:52Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。
既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。
提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
論文 参考訳（メタデータ） (2023-07-08T15:41:48Z) - Active Nearest Neighbor Regression Through Delaunay Refinement [79.93030583257597]
近接回帰に基づく能動関数近似アルゴリズムを提案する。
我々のActive Nearest Neighbor Regressor (ANNR) は計算幾何学の Voronoi-Delaunay フレームワークに頼り、空間を一定の関数値のセルに分割する。
論文 参考訳（メタデータ） (2022-06-16T10:24:03Z) - Mono-surrogate vs Multi-surrogate in Multi-objective Bayesian
Optimisation [0.0]
目的関数毎に代理モデルを構築し、スカラー化関数分布がガウス的でないことを示す。
標準ベンチマークや実世界の最適化問題に対する既存手法との比較は,マルチサロゲート方式の可能性を示している。
論文 参考訳（メタデータ） (2022-05-02T09:25:04Z) - R-MBO: A Multi-surrogate Approach for Preference Incorporation in
Multi-objective Bayesian Optimisation [0.0]
本稿では,多目的BOにおける意思決定者の嗜好として,目的関数を目的関数値に組み込むための,a-priori Multi-surrogateアプローチを提案する。
ベンチマークと実世界の最適化問題に対する既存モノ代理手法との比較は,提案手法の可能性を示している。
論文 参考訳（メタデータ） (2022-04-27T19:58:26Z) - Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
凸最適化における総和係数法に着想を得て,広範な分岐関数を持つネットワーク上での検証クエリを解析するための新しい手法を提案する。
標準ケース分析に基づく完全探索手順の拡張は、各検索状態で実行される凸手順をDeepSoIに置き換えることによって達成できる。
論文 参考訳（メタデータ） (2022-03-19T15:05:09Z) - Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。
従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
論文 参考訳（メタデータ） (2021-11-24T13:38:34Z) - Randomized Algorithms for Monotone Submodular Function Maximization on
the Integer Lattice [5.543220407902113]
濃度制約を受ける有界整数格子上の単調部分モジュラ函数を最大化する問題を考える。
特に、DR-部分モジュラ函数の最大化、すなわち減少するリターン特性を示す整数格子上で定義される関数に焦点をあてる。
提案したアルゴリズムを整数格子に適用することは、設定された領域に対する目標問題を減らし、最も高速に設定された部分モジュラーアルゴリズムを適用するなど、他のアルゴリズムよりも高速である。
論文 参考訳（メタデータ） (2021-11-19T12:07:16Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - From Sets to Multisets: Provable Variational Inference for Probabilistic
Integer Submodular Models [82.95892656532696]
サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。
本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。
整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
論文 参考訳（メタデータ） (2020-06-01T22:20:45Z) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-12T16:44:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。