Fugu-MT 論文翻訳(概要): Memory-Sample Lower Bounds for Learning Parity with Noise

論文の概要: Memory-Sample Lower Bounds for Learning Parity with Noise

arxiv url: http://arxiv.org/abs/2107.02320v1
Date: Mon, 5 Jul 2021 23:34:39 GMT
ステータス: 処理完了
システム内更新日: 2021-07-07 13:37:13.328546
Title: Memory-Sample Lower Bounds for Learning Parity with Noise
Title（参考訳）: 雑音によるパリティ学習のためのメモリサンプル下限
Authors: Sumegha Garg, Pravesh K. Kothari, Pengda Liu and Ran Raz
Abstract要約: ノイズ下でのパリティ学習においてよく研究されている問題に対して、任意の学習アルゴリズムは、$Omega(n2/varepsilon)$または指数的なサンプル数を必要とすることを示す。我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。
参考スコア（独自算出の注目度）: 2.724141845301679
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn $x=(x_1,\ldots,x_n) \in \{0,1\}^n$ from a stream of random linear equations over $\mathrm{F}_2$ that are correct with probability $\frac{1}{2}+\varepsilon$ and flipped with probability $\frac{1}{2}-\varepsilon$, that any learning algorithm requires either a memory of size $\Omega(n^2/\varepsilon)$ or an exponential number of samples. In fact, we study memory-sample lower bounds for a large class of learning problems, as characterized by [GRT'18], when the samples are noisy. A matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem with error parameter $\varepsilon$: an unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen uniformly at random and $b_i = M(a_i,x)$ with probability $1/2+\varepsilon$ and $b_i = -M(a_i,x)$ with probability $1/2-\varepsilon$ ($0<\varepsilon< \frac{1}{2}$). Assume that $k,\ell, r$ are such that any submatrix of $M$ of at least $2^{-k} \cdot |A|$ rows and at least $2^{-\ell} \cdot |X|$ columns, has a bias of at most $2^{-r}$. We show that any learning algorithm for the learning problem corresponding to $M$, with error, requires either a memory of size at least $\Omega\left(\frac{k \cdot \ell}{\varepsilon} \right)$, or at least $2^{\Omega(r)}$ samples. In particular, this shows that for a large class of learning problems, same as those in [GRT'18], any learning algorithm requires either a memory of size at least $\Omega\left(\frac{(\log |X|) \cdot (\log |A|)}{\varepsilon}\right)$ or an exponential number of noisy samples. Our proof is based on adapting the arguments in [Raz'17,GRT'18] to the noisy case.
Abstract（参考訳）: 本研究では、雑音下でのパリティをよく研究する問題に対して、学習者は、$x=(x_1,\ldots,x_n) \in \{0,1\}^n$を確率$\frac{1}{2}+\varepsilon$で正し確率$\frac{1}{2}-\varepsilon$で正し、確率$\frac{1}{2}-\varepsilon$で反転するランダム線形方程式のストリームから学習しようとする。実際に,サンプルがうるさい場合に,[GRT'18]によって特徴付けられるような,大規模な学習問題に対するメモリサンプルの低い境界について検討する。行列 $M: A \times X \rightarrow \{-1,1\}$ は、誤差パラメータ $\varepsilon$:未知の要素 $x \in X$ がランダムに一様に選択される、以下の学習問題に対応する。 a_1, b_1), (a_2, b_2) \ldots$, ここで、各$i$, $a_i \in a$はランダムに選択され、$b_i = m(a_i,x)$ with probability $1/2+\varepsilon$ and $b_i = -m(a_i,x)$ with probability $1/2-\varepsilon$ ($0<\varepsilon< \frac{1}{2}$)。 $k,\ell, r$ は、少なくとも$2^{-k} \cdot |A|$ rows と少なくとも$2^{-\ell} \cdot |X|$ columns の任意の部分行列が、少なくとも$2^{-r}$のバイアスを持つようなものであると仮定する。誤差のある$m$に対応する学習問題の学習アルゴリズムは、少なくとも$\omega\left(\frac{k \cdot \ell}{\varepsilon} \right)$または少なくとも$2^{\omega(r)}$のサンプルを必要とする。特に、[grt'18]と同じ、大きな学習問題のクラスでは、任意の学習アルゴリズムは、少なくとも$\omega\left(\frac{(\log |x|) \cdot (\log |a|)}{\varepsilon}\right)$または指数関数数のノイズサンプルを必要とする。我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。

論文の概要: Memory-Sample Lower Bounds for Learning Parity with Noise

関連論文リスト