論文の概要: A Law of Robustness beyond Isoperimetry
- arxiv url: http://arxiv.org/abs/2202.11592v2
- Date: Thu, 1 Jun 2023 03:21:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-03 02:12:59.428854
- Title: A Law of Robustness beyond Isoperimetry
- Title(参考訳): 等尺法を超えたロバストネスの法則
- Authors: Yihan Wu, Heng Huang, Hongyang Zhang
- Abstract要約: 我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
- 参考スコア(独自算出の注目度): 84.33752026418045
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the robust interpolation problem of arbitrary data distributions
supported on a bounded space and propose a two-fold law of robustness. Robust
interpolation refers to the problem of interpolating $n$ noisy training data
points in $\mathbb{R}^d$ by a Lipschitz function. Although this problem has
been well understood when the samples are drawn from an isoperimetry
distribution, much remains unknown concerning its performance under generic or
even the worst-case distributions. We prove a Lipschitzness lower bound
$\Omega(\sqrt{n/p})$ of the interpolating neural network with $p$ parameters on
arbitrary data distributions. With this result, we validate the law of
robustness conjecture in prior work by Bubeck, Li, and Nagaraj on two-layer
neural networks with polynomial weights. We then extend our result to arbitrary
interpolating approximators and prove a Lipschitzness lower bound
$\Omega(n^{1/d})$ for robust interpolation. Our results demonstrate a two-fold
law of robustness: i) we show the potential benefit of overparametrization for
smooth data interpolation when $n=\mathrm{poly}(d)$, and ii) we disprove the
potential existence of an $O(1)$-Lipschitz robust interpolating function when
$n=\exp(\omega(d))$.
- Abstract(参考訳): 有界空間上で支持される任意のデータ分布のロバスト補間問題を研究し、ロバスト性に関する2次元法則を提案する。
ロバスト補間(Robust interpolation)とは、リプシッツ関数によって$\mathbb{R}^d$で$n$ノイズの多いトレーニングデータポイントを補間する問題を指す。
この問題はイソペリメトリー分布からサンプルを引き出す際によく理解されているが、一般分布や最悪の場合においてもその性能については不明な点が多い。
我々は任意のデータ分布に対して$p$パラメータを持つ補間ニューラルネットワークの低境界$\Omega(\sqrt{n/p})$を証明する。
この結果から, 多項式重み付き2層ニューラルネットワークにおいて, bubeck, li, nagarajによる先行研究におけるロバストネス予想の法則を検証する。
そして、任意の補間近似子に結果を拡張し、ロバスト補間のために下限の$\omega(n^{1/d})$ を証明する。
私たちの結果は、堅牢性の2倍の法則を示します。
i) $n=\mathrm{poly}(d)$, and and then $n=\mathrm{poly}(d)$, and overparametrization による滑らかなデータ補間の可能性を示す。
i)$n=\exp(\omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
関連論文リスト
- Interplay between depth and width for interpolation in neural ODEs [0.0]
それらの幅$p$と層遷移数$L$の相互作用について検討する。
高次元設定では、$p=O(N)$ニューロンが正確な制御を達成するのに十分であることを示す。
論文 参考訳(メタデータ) (2024-01-18T11:32:50Z) - The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳(メタデータ) (2023-11-09T14:29:25Z) - Estimation and Inference in Distributional Reinforcement Learning [28.253677740976197]
サイズ$widetilde Oleft(frac|mathcalS||mathcalA|epsilon2 (1-gamma)4right)$ suffices to ensure the Kolmogorov metric and total variation metric between $hatetapi$ and $etapi$ is below $epsilon$ with high probability。
以上の結果から,多種多様な統計的汎関数の統計的推測への統一的アプローチがもたらされた。
論文 参考訳(メタデータ) (2023-09-29T14:14:53Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳(メタデータ) (2022-12-01T15:57:58Z) - Penalized Langevin and Hamiltonian Monte Carlo Algorithms for
Constrained Sampling [8.333246626497363]
分布(x)prop ef(x)$と$x$が凸体上で制約されるような制約付きサンプリング問題を考える。
我々は,制限されたサンプリング問題をペナルティ関数制約違反を導入して非拘束なものに変換する,ペナルティ付ハミルトンモンテカルロダイナミクス(PLD)とペナルティ付ハミルトンモンテカルロダイナミクス(PHMC)を提案する。
PHMCでは、Hessianが$であるときに $tildemathcalO(sqrtd/varepsilon7)$に改善します。
論文 参考訳(メタデータ) (2022-11-29T18:43:22Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳(メタデータ) (2022-08-19T18:00:34Z) - Parameter-free Statistically Consistent Interpolation:
Dimension-independent Convergence Rates for Hilbert kernel regression [0.0]
最近提案された重み付き補間近接補間法 (wiNN) はこのクラスに属する。
プラグインの余剰リスクは 2|f(x)-1/2|1-1-varepsilon) sigma(x)((n))-frac2$ 以下の任意の$に対して、$f$ は回帰関数 $xmapstomathbbE[yx]$ であることを示す。
論文 参考訳(メタデータ) (2021-06-07T05:50:02Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。