#### 論文の概要: 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
• 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の証明を修正する。

#### 関連論文リスト

• $\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)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• 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)
• Fair Representation Clustering with Several Protected Classes [13.53362222844008]
我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。 我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
論文  参考訳（メタデータ） (2022-02-03T03:45:45Z)
• 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)