論文の概要: Adaptive Regularized Submodular Maximization
- arxiv url: http://arxiv.org/abs/2103.00384v1
- Date: Sun, 28 Feb 2021 03:31:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-03 17:25:26.760212
- Title: Adaptive Regularized Submodular Maximization
- Title（参考訳）: adaptive regularized submodular maximization
- Authors: Shaojie Tang, Jing Yuan
- Abstract要約: 本研究では,適応的条件下での適応的部分モジュラー関数と非負的モジュラー関数との差を最大化する問題について検討する。
問題の入力は$n$アイテムのセットで、各アイテムは既知の事前ディストリビューションである$p$から引き出された特定の状態を持っています。
我々の目標は、$k$-cardinality制約の下で、最良のポリシー $pioin argmax_pig_avg(pi)-c_avg(pi)$を特定することです。
- 参考スコア（独自算出の注目度）: 28.24164217929491
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of maximizing the difference between an
adaptive submodular (revenue) function and an non-negative modular (cost)
function under the adaptive setting. The input of our problem is a set of $n$
items, where each item has a particular state drawn from some known prior
distribution $p$. The revenue function $g$ is defined over items and states,
and the cost function $c$ is defined over items, i.e., each item has a fixed
cost. The state of each item is unknown initially, one must select an item in
order to observe its realized state. A policy $\pi$ specifies which item to
pick next based on the observations made so far. Denote by $g_{avg}(\pi)$ the
expected revenue of $\pi$ and let $c_{avg}(\pi)$ denote the expected cost of
$\pi$. Our objective is to identify the best policy $\pi^o\in
\arg\max_{\pi}g_{avg}(\pi)-c_{avg}(\pi)$ under a $k$-cardinality constraint.
Since our objective function can take on both negative and positive values, the
existing results of submodular maximization may not be applicable. To overcome
this challenge, we develop a series of effective solutions with performance
grantees. Let $\pi^o$ denote the optimal policy. For the case when $g$ is
adaptive monotone and adaptive submodular, we develop an effective policy
$\pi^l$ such that $g_{avg}(\pi^l) - c_{avg}(\pi^l) \geq
(1-\frac{1}{e}-\epsilon)g_{avg}(\pi^o) - c_{avg}(\pi^o)$, using only
$O(n\epsilon^{-2}\log \epsilon^{-1})$ value oracle queries. For the case when
$g$ is adaptive submodular, we present a randomized policy $\pi^r$ such that
$g_{avg}(\pi^r) - c_{avg}(\pi^r) \geq \frac{1}{e}g_{avg}(\pi^o) -
c_{avg}(\pi^o)$.
- Abstract（参考訳）: 本稿では,適応的条件下での適応的部分モジュラー関数と非負的モジュラー関数との差を最大化する問題について検討する。
問題の入力は$n$アイテムのセットで、各アイテムは既知の事前ディストリビューションである$p$から引き出された特定の状態を持っています。
収益関数 $g$ はアイテムとステートで定義され、コスト関数 $c$ はアイテム、すなわち各アイテムが固定コストで定義される。
それぞれのアイテムの状態は最初不明であり、実現された状態を監視するためにアイテムを選択する必要がある。
ポリシー$\pi$は、これまでの観察に基づいて次に選択すべき項目を指定する。
注意:$g_{avg}(\pi)$ 期待される$\pi$ と $c_{avg}(\pi)$ は、期待される$\pi$ のコストを表す。
私たちの目標は、$k$-cardinality制約の下で最高のポリシー$\pi^o\in \arg\max_{\pi}g_{avg}(\pi)-c_{avg}(\pi)$を特定することです。
目的関数は負値と正値の両方を取ることができるので、サブモジュラー最大化の既存の結果は適用できないかもしれない。
この課題を克服するために,我々は,パフォーマンス付与者による効果的なソリューションを連続的に開発する。
$\pi^o$ を最適方針とする。
g$ が適応モノトーンおよび適応部分モジュラの場合、$g_{avg}(\pi^l) - c_{avg}(\pi^l) \geq (1-\frac{1}{e}-\epsilon)g_{avg}(\pi^o) - c_{avg}(\pi^o)$ のみを使用して、$O(n\epsilon^{-2}\log \epsilon^{-1})$ の値オラクルクエリを行うような有効なポリシー $\pi^l$ を開発する。
g$ が適応部分モジュラーである場合、$g_{avg}(\pi^r) - c_{avg}(\pi^r) \geq \frac{1}{e}g_{avg}(\pi^o)c_{avg}(\pi^o)$ となるようなランダム化されたポリシー $\pi^r$ を示す。
関連論文リスト
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [59.65871549878937]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Minimum Cost Adaptive Submodular Cover [4.680686256929023]
適応部分モジュラ函数の最小コスト被覆の問題を考える。
このアルゴリズムは,すべての$pge 1$に対して,同時に$(p+1)p+1cdot (ln Q+1)p$近似を保証することを示す。
論文 参考訳（メタデータ） (2022-08-17T15:26:47Z) - Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文 参考訳（メタデータ） (2022-06-19T11:33:07Z) - Finite-Sample Maximum Likelihood Estimation of Location [16.44999338864628]
固定$f$ の場合、最大類似度推定 (MLE) は infty$ に対して$n の極限で最適であることが知られている。
任意の$f$と$n$について、滑らかな$f$のフィッシャー情報に基づいて同様の理論を復元できることを示し、そこでは滑らかな半径が$n$で崩壊する。
論文 参考訳（メタデータ） (2022-06-06T04:33:41Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳（メタデータ） (2021-04-06T20:25:57Z) - $\lambda$-Regularized A-Optimal Design and its Approximation by
$\lambda$-Regularized Proportional Volume Sampling [1.256413718364189]
本稿では,$lambda$-regularized $A$-optimal design problemについて検討し,$lambda$-regularized proportional volume sample algorithmを紹介する。
この問題は、リッジ回帰モデルにおける真の係数からリッジ回帰予測器の2乗誤差を最小化しようとする、リッジ回帰の最適設計から動機づけられている。
論文 参考訳（メタデータ） (2020-06-19T15:17:57Z) - Regularized Submodular Maximization at Scale [45.914693923126826]
亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。
正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
論文 参考訳（メタデータ） (2020-02-10T02:37:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。