論文の概要: Strong Memory Lower Bounds for Learning Natural Models
- arxiv url: http://arxiv.org/abs/2206.04743v1
- Date: Thu, 9 Jun 2022 19:35:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-13 15:03:52.370171
- Title: Strong Memory Lower Bounds for Learning Natural Models
- Title（参考訳）: 自然モデル学習のための強記憶下限
- Authors: Gavin Brown, Mark Bun, Adam Smith
- Abstract要約: ワンパスストリーミングアルゴリズムで要求されるメモリ量に対して,より低いバウンダリを与える。
ほぼ最小の例($tilde O(kappa)$)を用いて学習するアルゴリズムは、$tilde Omega(dkappa)$ bits of spaceを使用する必要がある。
- 参考スコア（独自算出の注目度）: 16.900376638975978
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give lower bounds on the amount of memory required by one-pass streaming
algorithms for solving several natural learning problems. In a setting where
examples lie in $\{0,1\}^d$ and the optimal classifier can be encoded using
$\kappa$ bits, we show that algorithms which learn using a near-minimal number
of examples, $\tilde O(\kappa)$, must use $\tilde \Omega( d\kappa)$ bits of
space. Our space bounds match the dimension of the ambient space of the
problem's natural parametrization, even when it is quadratic in the size of
examples and the final classifier. For instance, in the setting of $d$-sparse
linear classifiers over degree-2 polynomial features, for which
$\kappa=\Theta(d\log d)$, our space lower bound is $\tilde\Omega(d^2)$. Our
bounds degrade gracefully with the stream length $N$, generally having the form
$\tilde\Omega\left(d\kappa \cdot \frac{\kappa}{N}\right)$.
Bounds of the form $\Omega(d\kappa)$ were known for learning parity and other
problems defined over finite fields. Bounds that apply in a narrow range of
sample sizes are also known for linear regression. Ours are the first such
bounds for problems of the type commonly seen in recent learning applications
that apply for a large range of input sizes.
- Abstract（参考訳）: 我々は,自然学習問題の解法として,ワンパスストリーミングアルゴリズムが要求するメモリ容量を低くする。
例が$\{0,1\}^d$ にあり、最適な分類器が $\kappa$ ビットで符号化できるような設定では、最小に近い数の例を使って学習するアルゴリズム $\tilde o(\kappa)$ が $\tilde \omega(d\kappa)$ の空間ビットを使用する必要がある。
我々の空間境界は、例のサイズと最終分類器で二次である場合でも、問題の自然パラメトリゼーションの周囲の空間の次元に一致する。
例えば、次数2の多項式上の$d$スパース線型分類器の設定では、$\kappa=\Theta(d\log d)$ であり、この空間下限は $\tilde\Omega(d^2)$ である。
我々の境界はストリーム長$N$で優雅に分解され、一般に $\tilde\Omega\left(d\kappa \cdot \frac{\kappa}{N}\right)$ という形になる。
$\omega(d\kappa)$ の形の境界は、有限体上で定義されるパリティやその他の問題を学ぶことで知られている。
狭い範囲のサンプルサイズに適用される境界もまた線形回帰として知られている。
我々の研究は、最近の学習アプリケーションでよく見られる、幅広い入力サイズに適用されるタイプの問題に対する最初の境界である。
関連論文リスト
- Tight Time-Space Lower Bounds for Constant-Pass Learning [1.7387739961208148]
サンプルストリームを$q$で通過するパリティ学習アルゴリズムに対して,メモリサンプルの少ないバウンダリを厳密に証明する。
このような学習者には、メモリサイズが$Omega(n2)$か、少なくとも$Omega(n)$サンプルが必要である。
これまでの研究と同様に、この結果は、ほぼ直交的な概念を多く含んだ学習問題にまで及んでいる。
論文 参考訳（メタデータ） (2023-10-12T06:36:31Z) - Optimal Approximation Rates for Deep ReLU Neural Networks on Sobolev and Besov Spaces [2.7195102129095003]
ReLU活性化関数を持つディープニューラルネットワークは、ソボレフ空間$Ws(L_q(Omega))$とBesov空間$Bs_r(L_q(Omega))$の関数を近似することができる。
この問題は、様々な分野におけるニューラルネットワークの適用を研究する際に重要である。
論文 参考訳（メタデータ） (2022-11-25T23:32:26Z) - The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。
すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
論文 参考訳（メタデータ） (2022-09-04T10:01:39Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Tractability from overparametrization: The example of the negative
perceptron [9.077560551700163]
我々は線形プログラミングアルゴリズムを解析し、対応するしきい値である$delta_textlin(kappa)$を特徴付ける。
閾値$delta_textlin(kappa)$間のギャップを観察し、他のアルゴリズムの振る舞いに関する疑問を提起する。
論文 参考訳（メタデータ） (2021-10-28T01:00:13Z) - Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。
本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文 参考訳（メタデータ） (2021-10-25T08:34:00Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - 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) - Subspace Embeddings Under Nonlinear Transformations [19.28531602450729]
空間 $S = y: y = f(x)text for x in Z$, where $Z$ is a $k$-dimensional subspace of $mathbbRn$ and $f(x)$ is applied to $x$。
特に、追加の$epsilon$エラー埋め込みを$O(fracklog (n/epsilon)epsilon2)$ dimensionsに与えます。
論文 参考訳（メタデータ） (2020-10-05T18:18:04Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Optimal Contextual Pricing and Extensions [32.152826900874075]
このアルゴリズムは$Omega(d log T)$ lower bound up to the $d log d$ additive factor。
これらのアルゴリズムは、凸領域のスタイナー固有値を様々なスケールで有界化する新しい手法に基づいている。
論文 参考訳（メタデータ） (2020-03-03T18:46:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。