論文の概要: A note on the price of bandit feedback for mistake-bounded online
learning
- arxiv url: http://arxiv.org/abs/2101.06891v2
- Date: Sun, 31 Jan 2021 21:08:43 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-27 05:48:58.600873
- Title: A note on the price of bandit feedback for mistake-bounded online
learning
- Title（参考訳）: ミスバウンドオンライン学習における盗聴フィードバックの価格に関する一考察
- Authors: Jesse Geneson
- Abstract要約: 標準モデルとバンディットモデルは、ミスバウンドモデルからオンラインマルチクラス分類への一般化である。
両方のモデルでは、学習者は各ラウンドで分類を推測しますが、標準モデルでは、学習者は各推測後に正しい分類を受け取ります。
この補題は、$s$ と $t$ が互いに複数の mod $p$ である場合に正確に偽であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The standard model and the bandit model are two generalizations of the
mistake-bound model to online multiclass classification. In both models the
learner guesses a classification in each round, but in the standard model the
learner recieves the correct classification after each guess, while in the
bandit model the learner is only told whether or not their guess is correct in
each round. For any set $F$ of multiclass classifiers, define $opt_{std}(F)$
and $opt_{bandit}(F)$ to be the optimal worst-case number of prediction
mistakes in the standard and bandit models respectively.
Long (Theoretical Computer Science, 2020) claimed that for all $M > 2$ and
infinitely many $k$, there exists a set $F$ of functions from a set $X$ to a
set $Y$ of size $k$ such that $opt_{std}(F) = M$ and $opt_{bandit}(F) \ge (1 -
o(1))(|Y|\ln{|Y|})opt_{std}(F)$. The proof of this result depended on the
following lemma, which is false e.g. for all prime $p \ge 5$, $s = \mathbf{1}$
(the all $1$ vector), $t = \mathbf{2}$ (the all $2$ vector), and all $z$.
Lemma: Fix $n \ge 2$ and prime $p$, and let $u$ be chosen uniformly at random
from $\left\{0, \dots, p-1\right\}^n$. For any $s, t \in \left\{1, \dots,
p-1\right\}^n$ with $s \neq t$ and for any $z \in \left\{0, \dots,
p-1\right\}$, we have $\Pr(t \cdot u = z \mod p \text{ } | \text{ } s \cdot u =
z \mod p) = \frac{1}{p}$.
We show that this lemma is false precisely when $s$ and $t$ are multiples of
each other mod $p$. Then using a new lemma, we fix Long's proof.
- Abstract（参考訳）: 標準モデルとバンディットモデルは、ミスバウンドモデルからオンラインマルチクラス分類への2つの一般化である。
どちらのモデルでも、学習者は各ラウンドの分類を推測するが、標準モデルでは、学習者は各推測の後に正しい分類を関連付けるが、バンディットモデルでは、学習者は各ラウンドの推測が正しいかどうかのみを指示される。
マルチクラス分類器の任意のセット$F$に対して、$opt_{std}(F)$と$opt_{bandit}(F)$をそれぞれ標準モデルとバンディットモデルにおける予測ミスの最適ケース数として定義する。
Long (Theoretical Computer Science, 2020) は、すべての$M > 2$と無限に多くの $k$ に対して、$opt_{std}(F) = M$ and $opt_{bandit}(F) \ge (1o(1))(|Y|\ln{|Y|})opt_{std}(F)$ であるような集合 $X$ から a set $Y$ までの関数の集合 $F$ が存在すると主張した。
この結果の証明は次の補題(例えば偽)に依存する。
すべての素数$p \ge 5$, $s = \mathbf{1}$ (すべての$$ベクトル)、$t = \mathbf{2}$ (すべての$2$ベクトル)、およびすべての$z$に対して。
Lemma: Fix $n \ge 2$ and prime $p$, and let $u$ be uniformly at random from $\left\{0, \dots, p-1\right\}^n$。
任意の$s, t \in \left\{1, \dots, p-1\right\}^n$ with $s \neq t$ and any $z \in \left\{0, \dots, p-1\right\}$ に対して、$\pr(t \cdot u = z \mod p \text{ } | \text{ } s \cdot u = z \mod p) = \frac{1}{p}$ となる。
この補題は、$s$ と $t$ が互いに mod $p$ であるときに正しく偽であることを示している。
そして、新しい補題を使って、Longの証明を修正する。
関連論文リスト
- 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) - $\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) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - 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) - Self-training Converts Weak Learners to Strong Learners in Mixture
Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。
さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文 参考訳（メタデータ） (2021-06-25T17:59:16Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - Sharper bounds for online learning of smooth functions of a single
variable [0.0]
ここでは$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$を示します。
また、$opt_1+epsilon(mathcalF_q) = Theta(epsilon-frac12)$ も示します。
論文 参考訳（メタデータ） (2021-05-30T23:06:21Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - 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) - Learning and Testing Variable Partitions [13.575794982844222]
我々は $mathcalO(k n2)(delta + epsilon)$ が、任意の $epsilon > 0$ に対して $tildemathcalO(n2 mathrmpoly (1/epsilon)$ で学習可能であることを示す。
また、両面のテスタでさえ$k = 2$の場合に$Omega(n)$クエリが必要であることも示しています。
論文 参考訳（メタデータ） (2020-03-29T10:12:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。