論文の概要: Phase Transitions in Rate Distortion Theory and Deep Learning

• arxiv url: http://arxiv.org/abs/2008.01011v1
• Date: Mon, 3 Aug 2020 16:48:49 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-03 07:17:32.404222
• Title: Phase Transitions in Rate Distortion Theory and Deep Learning
• Title（参考訳）: レート歪理論とディープラーニングにおける相転移
• Authors: Philipp Grohs, Andreas Klotz, Felix Voigtlaender
• Abstract要約: もし$mathcalS$をエンコードするために$mathcalO(R-s)$のエラーを達成できれば、$mathcalS$は$s$で圧縮できると言う。 ある"ニッチ"信号クラスに対して、$mathcalS$が相転移を起こすことを示す。
• 参考スコア（独自算出の注目度）: 5.145741425164946
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Rate distortion theory is concerned with optimally encoding a given signal class $\mathcal{S}$ using a budget of $R$ bits, as $R\to\infty$. We say that $\mathcal{S}$ can be compressed at rate $s$ if we can achieve an error of $\mathcal{O}(R^{-s})$ for encoding $\mathcal{S}$; the supremal compression rate is denoted $s^\ast(\mathcal{S})$. Given a fixed coding scheme, there usually are elements of $\mathcal{S}$ that are compressed at a higher rate than $s^\ast(\mathcal{S})$ by the given coding scheme; we study the size of this set of signals. We show that for certain "nice" signal classes $\mathcal{S}$, a phase transition occurs: We construct a probability measure $\mathbb{P}$ on $\mathcal{S}$ such that for every coding scheme $\mathcal{C}$ and any $s >s^\ast(\mathcal{S})$, the set of signals encoded with error $\mathcal{O}(R^{-s})$ by $\mathcal{C}$ forms a $\mathbb{P}$-null-set. In particular our results apply to balls in Besov and Sobolev spaces that embed compactly into $L^2(\Omega)$ for a bounded Lipschitz domain $\Omega$. As an application, we show that several existing sharpness results concerning function approximation using deep neural networks are generically sharp. We also provide quantitative and non-asymptotic bounds on the probability that a random $f\in\mathcal{S}$ can be encoded to within accuracy $\varepsilon$ using $R$ bits. This result is applied to the problem of approximately representing $f\in\mathcal{S}$ to within accuracy $\varepsilon$ by a (quantized) neural network that is constrained to have at most $W$ nonzero weights and is generated by an arbitrary "learning" procedure. We show that for any $s >s^\ast(\mathcal{S})$ there are constants $c,C$ such that, no matter how we choose the "learning" procedure, the probability of success is bounded from above by $\min\big\{1,2^{C\cdot W\lceil\log_2(1+W)\rceil^2 -c\cdot\varepsilon^{-1/s}}\big\}$.
• Abstract（参考訳）: 速度歪み理論は、与えられた信号クラス $\mathcal{S}$ を$R$ビットの予算で最適に$R\to\infty$ と符号化することに関心がある。 我々は$\mathcal{S}$を$s$で圧縮することができ、$\mathcal{O}(R^{-s})$を符号化するために$\mathcal{O}(R^{-s})$の誤差を達成できるならば、その上限圧縮レートは$s^\ast(\mathcal{S})$と表される。 固定符号スキームが与えられた場合、通常、与えられた符号スキームによって$s^\ast(\mathcal{S})$よりも高い速度で圧縮される$\mathcal{S}$の要素が存在する。 確率測度 $\mathbb{P}$ on $\mathcal{S}$ は、すべての符号化スキーム $\mathcal{C}$ と任意の $s >s^\ast(\mathcal{S})$ に対して、エラー $\mathcal{O}(R^{-s})$ でエンコードされた信号の集合は、$\mathcal{C}$ となる。 特に、この結果は、コンパクトに$L^2(\Omega)$に埋め込まれたベソフ空間とソボレフ空間の球体に適用される。 本研究では,ディープニューラルネットワークを用いた関数近似に関する既存のシャープネスの結果が汎用的にシャープであることを示す。 また、ランダムな$f\in\mathcal{S}$が$R$ビットを用いて精度$\varepsilon$にエンコードできる確率に関する量的および非漸近的境界も提供する。 この結果は、最大$w$非ゼロの重みを持つように制約され、任意の「学習」手順によって生成される(量子化された)ニューラルネットワークによって、精度で$f\in\mathcal{s}$を約$\varepsilon$として表現する問題に適用される。 任意の $s >s^\ast(\mathcal{S})$ に対して、$c,C$ が存在して、「学習」手順をどう選択しても、成功確率は$\min\big\{1,2^{C\cdot W\lceil\log_2(1+W)\rceil^2 -c\cdot\varepsilon^{-1/s}}\big\}$ で上限づけられる。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
  この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
  論文  参考訳（メタデータ） (2024-03-04T18:30:33Z)
• Learned Nonlinear Predictor for Critically Sampled 3D Point Cloud Attribute Compression [24.001318485207207]
  我々はデコーダによる3次元点雲圧縮について検討した。 本稿では,$f_l*$をレベル$l+1$,$f_l*$$l$,$G_l*$のエンコーディングを$p=1$で予測する。
  論文  参考訳（メタデータ） (2023-11-22T17:26:54Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Local approximation of operators [0.0]
  距離空間 $mathfrakX$ と $mathfrakY$ の間の非線形作用素の近似の度合いを決定する問題について検討する。 例えば、$mathbbSd$ の近似に関係する定数は $mathcalO(d1/6)$ である。
  論文  参考訳（メタデータ） (2022-02-13T19:28:34Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• 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)
• Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
  ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。 我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
  論文  参考訳（メタデータ） (2020-06-23T20:21:27Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。