論文の概要: A Tight Bound for Stochastic Submodular Cover
- arxiv url: http://arxiv.org/abs/2102.01149v1
- Date: Mon, 1 Feb 2021 20:37:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-04 04:13:11.823109
- Title: A Tight Bound for Stochastic Submodular Cover
- Title（参考訳）: 確率的サブモジュラカバーのタイトバウンド
- Authors: Lisa Hellerstein, Devorah Kletenik and Srinivasan Parthasarathy
- Abstract要約: Golovin and Krause の Adaptive Greedy アルゴリズム (2011) は部分モジュラー被覆に対して$(ln (Q/eta)+1) の近似限界を達成することを示す。
私たちの境界は、既知の$(lnm + 1)$の近似を古典的な問題に対してグリーディに有界に一般化し、$m$は基底集合のサイズである。
- 参考スコア（独自算出の注目度）: 8.668055353339287
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that the Adaptive Greedy algorithm of Golovin and Krause (2011)
achieves an approximation bound of $(\ln (Q/\eta)+1)$ for Stochastic Submodular
Cover: here $Q$ is the "goal value" and $\eta$ is the smallest non-zero
marginal increase in utility deliverable by an item. (For integer-valued
utility functions, we show a bound of $H(Q)$, where $H(Q)$ is the $Q^{th}$
Harmonic number.) Although this bound was claimed by Golovin and Krause in the
original version of their paper, the proof was later shown to be incorrect by
Nan and Saligrama (2017). The subsequent corrected proof of Golovin and Krause
(2017) gives a quadratic bound of $(\ln(Q/\eta) + 1)^2$. Other previous bounds
for the problem are $56(\ln(Q/\eta) + 1)$, implied by work of Im et al. (2016)
on a related problem, and $k(\ln (Q/\eta)+1)$, due to Deshpande et al. (2016)
and Hellerstein and Kletenik (2018), where $k$ is the number of states. Our
bound generalizes the well-known $(\ln~m + 1)$ approximation bound on the
greedy algorithm for the classical Set Cover problem, where $m$ is the size of
the ground set.
- Abstract（参考訳）: ここで、golovin and krause (2011) の適応的グリーディアルゴリズムは、確率的部分多様体被覆に対して $(\ln (q/\eta)+1)$ の近似境界を達成していることを示す。
(整数値のユーティリティ関数の場合、$H(Q)$の有界な値を示し、$H(Q)$は$Q^{th}$ハーモニック数である。)
この境界は Golovin と Krause によって論文の原版で主張されたが、この証明は後に Nan と Saligrama (2017) によって誤りであることが示されている。
その後の Golovin and Krause (2017) の補正された証明は、$(\ln(Q/\eta) + 1)^2$ の二次境界を与える。
この問題に対する他の以前の境界は、Im et al の作業によって暗示される 56(\ln(Q/\eta) + 1)$ である。
(2016) 関連する問題、および $k(\ln (Q/\eta)+1)$ について、Deshpande らによる。
2016年) と Hellerstein and Kletenik (2018) では、$k$ は州数である。
我々の境界は、古典集合被覆問題に対するグリーディアルゴリズム上のよく知られた $(\ln~m + 1)$ 近似を一般化し、ここで $m$ は基底集合の大きさである。
関連論文リスト
- Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
近似の性能をMonge-Kantorovich $p$-costで定量化する。
次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - Higher rank antipodality [0.0]
一般確率論に動機づけられて、集合 $X$ in $mathbbRd$ はランク $k$ のエンファンティポッドであると言う。
k=1$ の場合、Klee が導入した(ペアワイズで)反ポッド性の概念と一致する。
論文 参考訳（メタデータ） (2023-07-31T17:15:46Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality [6.621324975749854]
関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
論文 参考訳（メタデータ） (2021-11-01T20:45:42Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
カーネル群に基づく暗黙の空間性誘導機構について述べる。
アプリケーションとしては、この疎結合誘導機構を使用して、特徴選択に一貫性のあるアルゴリズムを構築します。
論文 参考訳（メタデータ） (2021-10-12T09:36:41Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z) - Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation [28.93486346263364]
零次逆凸最適化に対するミニマックス後悔の情報理論上界は、少なくとも$O(d2.5 sqrtn log(n))$であることを示す。
これはBubeckらによって$O(d9.5 sqrtn log(n)7.5$で改善される。
論文 参考訳（メタデータ） (2020-05-31T09:22:10Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。