論文の概要: How Many Data Are Needed for Robust Learning?
- arxiv url: http://arxiv.org/abs/2202.11592v1
- Date: Wed, 23 Feb 2022 16:10:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-24 19:17:43.418330
- Title: How Many Data Are Needed for Robust Learning?
- Title(参考訳): ロバスト学習に必要なデータはいくつあるか?
- Authors: Hongyang Zhang, Yihan Wu, Heng Huang
- Abstract要約: 本研究では,ロバスト問題におけるサンプルの複雑さが,入力次元において指数関数的であることを示す。
また,データの単位球内における位相遷移現象も発見する。
- 参考スコア(独自算出の注目度): 84.33752026418045
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We show that the sample complexity of robust interpolation problem could be
exponential in the input dimensionality and discover a phase transition
phenomenon when the data are in a unit ball. Robust interpolation refers to the
problem of interpolating $n$ noisy training data in $\R^d$ by a Lipschitz
function. Although this problem has been well understood when the covariates
are drawn from an isoperimetry distribution, much remains unknown concerning
its performance under generic or even the worst-case distributions. Our results
are two-fold: 1) too many data hurt robustness; we provide a tight and
universal Lipschitzness lower bound $\Omega(n^{1/d})$ of the interpolating
function for arbitrary data distributions. Our result disproves potential
existence of an $\mathcal{O}(1)$-Lipschitz function in the overparametrization
scenario when $n=\exp(\omega(d))$. 2) Small data hurt robustness:
$n=\exp(\Omega(d))$ is necessary for obtaining a good population error under
certain distributions by any $\mathcal{O}(1)$-Lipschitz learning algorithm.
Perhaps surprisingly, our results shed light on the curse of big data and the
blessing of dimensionality for robustness, and discover an intriguing
phenomenon of phase transition at $n=\exp(\Theta(d))$.
- Abstract(参考訳): その結果,ロバスト補間問題のサンプル複雑性は入力次元において指数関数的であり,データが単位球内にある場合の相転移現象を発見できることがわかった。
ロバスト補間(Robust interpolation)とは、Lipschitz関数によって$\R^d$のノイズの多いトレーニングデータを補間する問題を指す。
この問題は、共変数が等値分布から引き出されるときによく理解されているが、ジェネリック分布や最悪の場合分布の下での性能についてはほとんど不明である。
結果は2倍になります。
我々は任意のデータ分布に対する補間関数の$\Omega(n^{1/d})$に対して、厳密で普遍的なリプシッツ性を提供する。
我々の結果は、$n=\exp(\omega(d))$ のとき、オーバーパラメトリゼーションシナリオにおける $\mathcal{O}(1)$-Lipschitz 関数の存在を証明している。
2小データはロバスト性を傷つける:$n=\exp(\Omega(d))$は、任意の$\mathcal{O}(1)$-Lipschitz学習アルゴリズムによって、特定の分布の下で良い集団誤差を得るために必要である。
おそらく、我々の結果は、ビッグデータの呪いとロバスト性に対する次元の祝福に光を当て、$n=\exp(\Theta(d))$で相転移の興味深い現象を発見した。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。