論文の概要: Tight Time-Space Lower Bounds for Constant-Pass Learning
- arxiv url: http://arxiv.org/abs/2310.08070v1
- Date: Thu, 12 Oct 2023 06:36:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-15 11:10:17.040508
- Title: Tight Time-Space Lower Bounds for Constant-Pass Learning
- Title（参考訳）: 定値学習のための時間空間低境界
- Authors: Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang
- Abstract要約: サンプルストリームを$q$で通過するパリティ学習アルゴリズムに対して,メモリサンプルの少ないバウンダリを厳密に証明する。
このような学習者には、メモリサイズが$Omega(n2)$か、少なくとも$Omega(n)$サンプルが必要である。
これまでの研究と同様に、この結果は、ほぼ直交的な概念を多く含んだ学習問題にまで及んでいる。
- 参考スコア（独自算出の注目度）: 1.7387739961208148
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In his breakthrough paper, Raz showed that any parity learning algorithm
requires either quadratic memory or an exponential number of samples [FOCS'16,
JACM'19]. A line of work that followed extended this result to a large class of
learning problems. Until recently, all these results considered learning in the
streaming model, where each sample is drawn independently, and the learner is
allowed a single pass over the stream of samples. Garg, Raz, and Tal [CCC'19]
considered a stronger model, allowing multiple passes over the stream. In the
$2$-pass model, they showed that learning parities of size $n$ requires either
a memory of size $n^{1.5}$ or at least $2^{\sqrt{n}}$ samples. (Their result
also generalizes to other learning problems.)
In this work, for any constant $q$, we prove tight memory-sample lower bounds
for any parity learning algorithm that makes $q$ passes over the stream of
samples. We show that such a learner requires either $\Omega(n^{2})$ memory
size or at least $2^{\Omega(n)}$ samples. Beyond establishing a tight lower
bound, this is the first non-trivial lower bound for $q$-pass learning for any
$q\ge 3$. Similar to prior work, our results extend to any learning problem
with many nearly-orthogonal concepts.
We complement the lower bound with an upper bound, showing that parity
learning with $q$ passes can be done efficiently with $O(n^2/\log q)$ memory.
- Abstract（参考訳）: ラズは彼の画期的な論文で、任意のパリティ学習アルゴリズムは二次記憶か指数的なサンプル数(FOCS'16, JACM'19]を必要とすることを示した。
その後の一連の研究は、その結果を大規模な学習問題へと拡張した。
最近まで、これらすべての結果は、各サンプルが独立に描画され、学習者が1回のパスでサンプルのストリームを渡すストリーミングモデルで学習することを考慮していた。
Garg, Raz, Tal [CCC'19] はより強力なモデルであり、ストリーム上で複数のパスが可能である。
2ドルのパスモデルでは、サイズの学習パリティである$n$が、サイズ$n^{1.5}$または少なくとも$^{\sqrt{n}}$サンプルを必要とすることを示した。
(この結果は、他の学習問題にも一般化します) この研究では、一定の$q$ に対して、サンプルストリームを$q$ で渡すパリティ学習アルゴリズムのメモリサンプル下限を厳密に証明します。
このような学習者には、メモリサイズが$\Omega(n^{2})$か、少なくとも$2^{\Omega(n)}$サンプルが必要である。
厳密な下限を確立することに加えて、これは任意の$q\ge 3$に対する$q$パス学習のための最初の非自明な下限である。
先行研究と同様に, ほぼ正方形に近い概念を持つ学習問題にも拡張した。
我々は下界を上界で補完し、$q$パスのパリティ学習を$O(n^2/\log q)$メモリで効率的に行うことを示す。
関連論文リスト
- Optimal algorithms for learning quantum phase states [8.736370689844682]
未知の次数$d$相状態を学ぶ際のサンプルの複雑さは、分離可能な測定を許せば$Theta(nd)$であることを示す。
また、f$がsparsity-$s$, degree-$d$を持つ場合の学習フェーズ状態も検討する。
論文 参考訳（メタデータ） (2022-08-16T17:15:06Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Strong Memory Lower Bounds for Learning Natural Models [16.900376638975978]
ワンパスストリーミングアルゴリズムで要求されるメモリ量に対して,より低いバウンダリを与える。
ほぼ最小の例($tilde O(kappa)$)を用いて学習するアルゴリズムは、$tilde Omega(dkappa)$ bits of spaceを使用する必要がある。
論文 参考訳（メタデータ） (2022-06-09T19:35:47Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - Memory-Sample Lower Bounds for Learning Parity with Noise [2.724141845301679]
ノイズ下でのパリティ学習においてよく研究されている問題に対して、任意の学習アルゴリズムは、$Omega(n2/varepsilon)$または指数的なサンプル数を必要とすることを示す。
我々の証明は[Raz'17,GRT'18]の引数をノイズケースに適応させることに基づいている。
論文 参考訳（メタデータ） (2021-07-05T23:34:39Z) - On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。
簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
論文 参考訳（メタデータ） (2021-06-15T11:21:06Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Few-Shot Learning via Learning the Representation, Provably [115.7367053639605]
本稿では,表現学習による少数ショット学習について検討する。
1つのタスクは、ターゲットタスクのサンプルの複雑さを減らすために、$T$ソースタスクと$n_1$データを使用して表現を学習する。
論文 参考訳（メタデータ） (2020-02-21T17:30:00Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。